Two Pointers选编
接雨水问题
对每根柱子，求它的左侧和右侧的greatest element，探讨是否能在这根柱子上蓄水
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public int trap(int[] height) {
int area=0;
int n=height.length;
int[] findLeft=new int[n];
for(int i=1; i<n-1; i++){
findLeft[i]=Math.max(findLeft[i-1],height[i-1]);
}
int[] findRight=new int[n];
for(int i=n-2; i>=1; i--){
findRight[i]=Math.max(findRight[i+1],height[i+1]);
}
for(int i=1; i<n-1; i++){
int left=findLeft[i];
int right=findRight[i];
int h=Math.min(left,right);
if(h<=height[i]){
continue;
}
area+=h-height[i];
}
return area;
}
}
|
由大缩小
双指针技巧：移动较低的一边，因为只有这样才可能使矩形面积增大：
- 矩形面积由较短边和两边间距决定
- 移动指针，两边间距必定缩小
- 若移动较长边，则矩形面积必定缩小！无意义
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int maxArea(int[] height) {
int max=Integer.MIN_VALUE;
int left=0;
int right= height.length-1;
while(left<right){
int area=(right-left)*Math.min(height[left],height[right]);
max=Math.max(area,max);
if(height[left]<=height[right]){
left++;
}else{
right--;
}
}
return max;
}
}
|
数组移除元素
双指针，i 遍历数组，j 保留有效值
注意数组已排序，只需比较当前数组元素与最后一个有效项
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int removeDuplicates(int[] nums) {
int j=0;
for(int i=1; i<nums.length; i++){
if(nums[i]!=nums[j]){
nums[++j]=nums[i];
}
}
return j+1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int removeElement(int[] nums, int val) {
int j=0;
for(int i=0; i<nums.length; i++){
if(nums[i]!=val){
nums[j++]=nums[i];
}
}
return j;
}
}
|
注意要求：maintaining the relative order
直接左右双指针不满足
转换思路：
- j 初始化为第一个0, 用于和非零元素交换
- [0, j] is valid, all 0s are at the end
- i 从 j+1 开始遍历，每找到一个非零元素，就与 j 交换
- [0, i] is valid, where j is the first 0; swap i to j, and set i to 0
- j is where the next non-zero element should stay (the frist zero), so that the result is in original order
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public void moveZeroes(int[] nums) {
int j=0;
while(j<nums.length && nums[j]!=0){
j++;
}
for(int i=j+1; i<nums.length; i++){
if(nums[i]!=0){
nums[j]=nums[i];
nums[i]=0;
j++;
}
}
}
}
|
双指针，直到 i>right
- 遇到0，换，i++
- 遇到2，换，循环，直到nums[i]!=2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public class LeetCode75 {
public void sortColors(int[] nums) {
int left=0;
int right=nums.length-1;
for (int i = 0; i <= right; i++) {
while(i<=right && nums[i]==2){
swap(nums,i,right--);
}
if(nums[i]==0){
swap(nums,i,left++);
}
}
}
void swap(int[] nums, int i, int j){
if(i==j){
return;
}
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
|
字符串
solve it in O(n) time and O(1) space ?
考虑 backspacing, 从后向前比较
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public boolean backspaceCompare(String s, String t) {
int i=s.length()-1;
int j=t.length()-1;
int b1=0;
int b2=0;
while(i>=0 || j>=0){
while(i>=0 && (s.charAt(i)=='#' || b1!=0)){
if(s.charAt(i)=='#'){
b1++;
i--;
}else if(b1!=0){
b1--;
i--;
}
}
while(j>=0 && (t.charAt(j)=='#' || b2!=0)){
if(t.charAt(j)=='#'){
b2++;
j--;
}else if(b2!=0){
b2--;
j--;
}
}
if(i<0 || j<0 || s.charAt(i)!=t.charAt(j)){
break;
}
i--;
j--;
}
if(i>=0 || j>=0){
return false;
}else{
return true;
}
}
}
|