Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit500ed63

Browse files
Merge pull requestyoungyangyang04#432 from KailokFung/master
fix(1047): 新增双指针java写法;使用ArrayDeque
2 parentse23b6a1 +a150c61 commit500ed63

File tree

2 files changed

+61
-1
lines changed

2 files changed

+61
-1
lines changed

‎problems/0239.滑动窗口最大值.md

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -208,6 +208,7 @@ public:
208208

209209
Java：
210210
```Java
211+
//解法一
211212
//自定义数组
212213
classMyQueue {
213214
Deque<Integer> deque=newLinkedList<>();
@@ -260,6 +261,40 @@ class Solution {
260261
return res;
261262
}
262263
}
264+
265+
//解法二
266+
//利用双端队列手动实现单调队列
267+
/**
268+
* 用一个单调队列来存储对应的下标，每当窗口滑动的时候，直接取队列的头部指针对应的值放入结果集即可
269+
* 单调队列类似 （tail -->） 3 --> 2 --> 1 --> 0 (--> head) (右边为头结点，元素存的是下标)
270+
*/
271+
classSolution {
272+
publicint[]maxSlidingWindow(int[]nums,intk) {
273+
ArrayDeque<Integer> deque=newArrayDeque<>();
274+
int n= nums.length;
275+
int[] res=newint[n- k+1];
276+
int idx=0;
277+
for(int i=0; i< n; i++) {
278+
// 根据题意，i为nums下标，是要在[i - k + 1, k] 中选到最大值，只需要保证两点
279+
// 1.队列头结点需要在[i - k + 1, k]范围内，不符合则要弹出
280+
while(!deque.isEmpty()&& deque.peek()< i- k+1){
281+
deque.poll();
282+
}
283+
// 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
284+
while(!deque.isEmpty()&& nums[deque.peekLast()]< nums[i]) {
285+
deque.pollLast();
286+
}
287+
288+
deque.offer(i);
289+
290+
// 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
291+
if(i>= k-1){
292+
res[idx++]= nums[deque.peek()];
293+
}
294+
}
295+
return res;
296+
}
297+
}
263298
```
264299

265300
Python：

‎problems/1047.删除字符串中的所有相邻重复项.md

Lines changed: 26 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -127,7 +127,9 @@ Java：
127127
```Java
128128
class Solution {
129129
public String removeDuplicates(String S) {
130-
Deque<Character> deque = new LinkedList<>();
130+
//ArrayDeque会比LinkedList在除了删除元素这一点外会快一点
131+
//参考：https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist
132+
ArrayDeque<Character> deque = new ArrayDeque<>();
131133
char ch;
132134
for (int i = 0; i < S.length(); i++) {
133135
ch = S.charAt(i);
@@ -171,6 +173,29 @@ class Solution {
171173
}
172174
```
173175

176+
拓展：双指针
177+
```java
178+
classSolution {
179+
publicStringremoveDuplicates(Strings) {
180+
char[] ch= s.toCharArray();
181+
int fast=0;
182+
int slow=0;
183+
while(fast< s.length()){
184+
// 直接用fast指针覆盖slow指针的值
185+
ch[slow]= ch[fast];
186+
// 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了
187+
if(slow>0&& ch[slow]== ch[slow-1]){
188+
slow--;
189+
}else{
190+
slow++;
191+
}
192+
fast++;
193+
}
194+
returnnewString(ch,0,slow);
195+
}
196+
}
197+
```
198+
174199
Python：
175200
```python3
176201
classSolution:

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp