Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                
Skip to content

Commit cd4f67d

Browse files
youngyangyang04youngyangyang04
committed
2 parents 6cbf2d2 + aacb26d commit cd4f67d

9 files changed

+182
-3
lines changed

‎problems/0042.接雨水.md

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -388,6 +388,44 @@ class Solution:
388388
res += res1
389389
return res
390390
```
391+
动态规划
392+
```python3
393+
class Solution:
394+
def trap(self, height: List[int]) -> int:
395+
leftheight, rightheight = [0]*len(height), [0]*len(height)
396+
397+
leftheight[0]=height[0]
398+
for i in range(1,len(height)):
399+
leftheight[i]=max(leftheight[i-1],height[i])
400+
rightheight[-1]=height[-1]
401+
for i in range(len(height)-2,-1,-1):
402+
rightheight[i]=max(rightheight[i+1],height[i])
403+
404+
result = 0
405+
for i in range(0,len(height)):
406+
summ = min(leftheight[i],rightheight[i])-height[i]
407+
result += summ
408+
return result
409+
```
410+
单调栈
411+
```python3
412+
class Solution:
413+
def trap(self, height: List[int]) -> int:
414+
st =[0]
415+
result = 0
416+
for i in range(1,len(height)):
417+
while st!=[] and height[i]>height[st[-1]]:
418+
midh = height[st[-1]]
419+
st.pop()
420+
if st!=[]:
421+
hright = height[i]
422+
hleft = height[st[-1]]
423+
h = min(hright,hleft)-midh
424+
w = i-st[-1]-1
425+
result+=h*w
426+
st.append(i)
427+
return result
428+
```
391429

392430
Go:
393431

‎problems/0084.柱状图中最大的矩形.md

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -191,4 +191,57 @@ public:
191191

192192
这里我依然建议大家按部就班把版本一写出来，把情况一二三分析清楚，然后在精简代码到版本二。 直接看版本二容易忽略细节！
193193

194+
## 其他语言版本
195+
196+
Java:
197+
198+
Python:
199+
200+
动态规划
201+
```python3
202+
class Solution:
203+
def largestRectangleArea(self, heights: List[int]) -> int:
204+
result = 0
205+
minleftindex, minrightindex = [0]*len(heights), [0]*len(heights)
206+
207+
minleftindex[0]=-1
208+
for i in range(1,len(heights)):
209+
t = i-1
210+
while t>=0 and heights[t]>=heights[i]: t=minleftindex[t]
211+
minleftindex[i]=t
212+
213+
minrightindex[-1]=len(heights)
214+
for i in range(len(heights)-2,-1,-1):
215+
t=i+1
216+
while t<len(heights) and heights[t]>=heights[i]: t=minrightindex[t]
217+
minrightindex[i]=t
218+
219+
for i in range(0,len(heights)):
220+
left = minleftindex[i]
221+
right = minrightindex[i]
222+
summ = (right-left-1)*heights[i]
223+
result = max(result,summ)
224+
return result
225+
```
226+
单调栈 版本二
227+
```python3
228+
class Solution:
229+
def largestRectangleArea(self, heights: List[int]) -> int:
230+
heights.insert(0,0) # 数组头部加入元素0
231+
heights.append(0) # 数组尾部加入元素0
232+
st = [0]
233+
result = 0
234+
for i in range(1,len(heights)):
235+
while st!=[] and heights[i]<heights[st[-1]]:
236+
midh = heights[st[-1]]
237+
st.pop()
238+
if st!=[]:
239+
minrightindex = i
240+
minleftindex = st[-1]
241+
summ = (minrightindex-minleftindex-1)*midh
242+
result = max(summ,result)
243+
st.append(i)
244+
return result
245+
```
246+
194247
<div align="center"><img src=https://code-thinking.cdn.bcebos.com/pics/01二维码.jpg width=450> </img></div>

‎problems/0100.相同的树.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -159,7 +159,7 @@ public:
159159
return false;
160160
}
161161
que.push(leftNode->left); // 添加p节点的左子树节点
162-
que.push(rightNode->left); // 添加q节点的左子树节点点
162+
que.push(rightNode->left); // 添加q节点的左子树节点
163163
que.push(leftNode->right); // 添加p节点的右子树节点
164164
que.push(rightNode->right); // 添加q节点的右子树节点
165165
}

‎problems/0102.二叉树的层序遍历.md

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1205,6 +1205,35 @@ public:
12051205
};
12061206
```
12071207

1208+
java代码：
1209+
1210+
```java
1211+
class Solution {
1212+
public Node connect(Node root) {
1213+
Queue<Node> tmpQueue = new LinkedList<Node>();
1214+
if (root != null) tmpQueue.add(root);
1215+
1216+
while (tmpQueue.size() != 0){
1217+
int size = tmpQueue.size();
1218+
1219+
Node cur = tmpQueue.poll();
1220+
if (cur.left != null) tmpQueue.add(cur.left);
1221+
if (cur.right != null) tmpQueue.add(cur.right);
1222+
1223+
for (int index = 1; index < size; index++){
1224+
Node next = tmpQueue.poll();
1225+
if (next.left != null) tmpQueue.add(next.left);
1226+
if (next.right != null) tmpQueue.add(next.right);
1227+
1228+
cur.next = next;
1229+
cur = next;
1230+
}
1231+
}
1232+
1233+
return root;
1234+
}
1235+
}
1236+
```
12081237

12091238
python代码：
12101239

‎problems/0383.赎金信.md

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -209,6 +209,22 @@ class Solution(object):
209209
return True
210210
```
211211

212+
Python写法四：
213+
214+
```python3
215+
class Solution:
216+
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
217+
c1 = collections.Counter(ransomNote)
218+
c2 = collections.Counter(magazine)
219+
x = c1 - c2
220+
#x只保留值大于0的符号，当c1里面的符号个数小于c2时，不会被保留
221+
#所以x只保留下了，magazine不能表达的
222+
if(len(x)==0):
223+
return True
224+
else:
225+
return False
226+
```
227+
212228
Go：
213229

214230
```go

‎problems/0925.长按键入.md

Lines changed: 31 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@
99

1010
# 925.长按键入
1111
题目链接：https://leetcode-cn.com/problems/long-pressed-name/
12+
1213
你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。
1314

1415
你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。
@@ -98,7 +99,36 @@ public:
9899
# 其他语言版本
99100

100101
Java：
101-
102+
```java
103+
class Solution {
104+
public boolean isLongPressedName(String name, String typed) {
105+
int i = 0, j = 0;
106+
int m = name.length(), n = typed.length();
107+
while (i< m && j < n) {
108+
if (name.charAt(i) == typed.charAt(j)) { // 相同则同时向后匹配
109+
i++; j++;
110+
}
111+
else {
112+
if (j == 0) return false; // 如果是第一位就不相同直接返回false
113+
// 判断边界为n-1,若为n会越界,例如name:"kikcxmvzi" typed:"kiikcxxmmvvzzz"
114+
while (j < n-1 && typed.charAt(j) == typed.charAt(j-1)) j++;
115+
if (name.charAt(i) == typed.charAt(j)) { // j跨越重复项之后再次和name[i]匹配
116+
i++; j++; // 相同则同时向后匹配
117+
}
118+
else return false;
119+
}
120+
}
121+
// 说明name没有匹配完
122+
if (i < m) return false;
123+
// 说明type没有匹配完
124+
while (j < n) {
125+
if (typed.charAt(j) == typed.charAt(j-1)) j++;
126+
else return false;
127+
}
128+
return true;
129+
}
130+
}
131+
```
102132
Python：
103133
```python
104134
class Solution:

‎problems/1002.查找常用字符.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -169,6 +169,7 @@ class Solution {
169169
}
170170
}
171171
```
172+
Python
172173
```python
173174
class Solution:
174175
def commonChars(self, words: List[str]) -> List[str]:

‎problems/前序/关于空间复杂度，可能有几个疑问？.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -30,7 +30,7 @@
3030

3131
2. 空间复杂度是准确算出程序运行时所占用的内存么？
3232

33-
不要以为空间复杂度就已经精准的掌握了程序的内存使用大小，很有多因素会影响程序真正内存使用大小，例如编译器的内存对齐，编程语言容器的底层实现等等这些都会影响到程序内存的开销。
33+
不要以为空间复杂度就已经精准的掌握了程序的内存使用大小，很多因素会影响程序真正内存使用大小，例如编译器的内存对齐，编程语言容器的底层实现等等这些都会影响到程序内存的开销。
3434

3535
所以空间复杂度是预先大体评估程序内存使用的大小。
3636

‎problems/剑指Offer58-II.左旋转字符串.md

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -141,6 +141,18 @@ class Solution:
141141
# 空间复杂度：O(n)，python的string为不可变，需要开辟同样大小的list空间来修改
142142
```
143143

144+
```python 3
145+
#方法三：考虑不能用切片的情况下，利用模+下标实现
146+
class Solution:
147+
def reverseLeftWords(self, s: str, n: int) -> str:
148+
new_s = ''
149+
for i in range(len(s)):
150+
j = (i+n)%len(s)
151+
new_s = new_s + s[j]
152+
return new_s
153+
154+
```
155+
144156
Go：
145157

146158
```go

0 commit comments

Comments
 (0)