day02——背！！！

283. 移动零

思路： 两个指针 i 和 pre ，pre指向0元素，i 往后遍历找到距离pre 最近的一个非0元素，然后进行交换，pre++

class Solution {public void moveZeroes(int[] nums) {int n = nums.length;int pre = -1;for(int i=0;i<n;i++){// 未出发 满足是0 ，pre去第一个0位置if(nums[i] == 0 && pre == -1) pre = i;// 已出发，交换if(nums[i] != 0 && pre != -1){nums[pre] = nums[i];nums[i] = 0;pre++;}}}
}

11. 盛最多水的容器

left right 矮的那个向中间移动。

先算面积再移动——>不然移动前的面积算不到

class Solution {public int maxArea(int[] height) {int n = height.length;int left = 0;int right = n-1;int maxS = 0;//  = while(left<=right){int h = Math.min(height[left], height[right]);maxS = Math.max(maxS, h*(right-left));if(height[left] < height[right]) left++;else right--; }return maxS;}
}

LCR 007. 三数之和

sum = nums[i]+nums[left]+nums[right];

for控制i， while控制left和right。

注意两个循环都要去重！！！   if(i>0 && nums[i] == nums[i-1]) continue;

Arrays.asList(nums[i], nums[left], nums[right])   ——>[ nums[i], nums[left], nums[right] ]

// 方式2：如果你想显式用LinkedList，正确写法如下（二选一即可） // List<Integer> triplet = new LinkedList<>(); // triplet.add(nums[i]); // triplet.add(nums[left]); // triplet.add(nums[right]); // ans.add(triplet);

class Solution {public List<List<Integer>> threeSum(int[] nums) {int n = nums.length;Arrays.sort(nums);List<List<Integer>> ans = new ArrayList<>();for(int i=0;i<n-2;i++){// 对第一个数i去重，避免重复的三元组if(i>0 && nums[i] == nums[i-1]) continue;int left = i+1;int right = n-1;// = while(left < right){int sum = nums[i]+nums[left]+nums[right];if(sum < 0) left++;else if(sum > 0) right--;else{ // 找到和为0的三元组，正确构造List并加入结果
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));while(left<right && nums[left] == nums[left+1]) left++;while(left<right && nums[right] == nums[right-1]) right--;left++;right--;}}}return ans;}
}

42. 接雨水

双指针 max_left， max_right 分别指向i左右两端的最高位置

min为木桶短的那条边，按列遍历 容积 min-height[i]

class Solution {public int trap(int[] height) {int n = height.length;int max_left = 0;int[] max_right = new int[n];for (int i = n - 2; i >= 0; i--)max_right[i] = Math.max(max_right[i + 1], height[i + 1]);int min = 0;int sum = 0;for (int i = 1; i < n - 1; i++) {max_left = Math.max(max_left, height[i - 1]);min = Math.min(max_left, max_right[i]);if (height[i] < min)sum += min - height[i];}return sum;}
}

 

太棒了一题没记住，奖励再写一遍