天津品牌网站制作,怎样建设网站流程,房子装修价格,工业产品设计效果图文章目录 双指针1. 删除有序数组中的重复项#xff08;入门#xff09;1.1 题目描述1.2 解题思路1.3 代码实现 2. 删除有序数组中的重复项 II#xff08;简单#xff09;2.1 题目描述2.2 解题思路2.3 代码实现 3. 移动零#xff08;简单#xff09;3.1 题目描述3.2 代码实… 文章目录 双指针1. 删除有序数组中的重复项入门1.1 题目描述1.2 解题思路1.3 代码实现 2. 删除有序数组中的重复项 II简单2.1 题目描述2.2 解题思路2.3 代码实现 3. 移动零简单3.1 题目描述3.2 代码实现 4. 两数之和入门4.1 题目描述4.2 解题思路4.3 代码实现 5. 盛水最多的容器中等5.1 题目描述5.2 解题思路5.3 代码实现 6. 三数之和中等6.1 题目描述6.2 解题思路6.3 代码实现 7. 最接近的三数之和中等7.1 题目描述7.2 解题思路7.3 代码实现 8. 接雨水中等8.1 题目描述8.2 解题思路8.3 代码实现 双指针
双指针一般是指利用两个变量通过在线性的结构上进行遍历来解决某些特定的问题按照遍历的方式一般多采用同向遍历相向遍历两种方式例如冒泡排序、选择排序、插入排序都是用了两个变量同向遍历来实现快排则是通过相向遍历来实现。
1. 删除有序数组中的重复项入门
1.1 题目描述 1.2 解题思路
快慢指针的简单应用
1.3 代码实现
public int removeDuplicates(int[] nums) {int n nums.length;int p1 0;int p2 1;while (p2 n) {if (nums[p1] ! nums[p2]) {nums[p1] nums[p2];}p2;}return p1 1;
}leetcode跳转26. 删除有序数组中的重复项
2. 删除有序数组中的重复项 II简单
2.1 题目描述 2.2 解题思路
与前一题结合在一起看就是保留前X个相同数字超过X个后再进行比较所以快指针逻辑不变只需要让慢指针在比较时每次往前取两位即可。
2.3 代码实现
public int removeDuplicates(int[] nums) {int n nums.length;if (n 2) {return n;}int p1 2;int p2 2;while (p2 n) {if (nums[p1 - 2] ! nums[p2]) {nums[p1] nums[p2];p1;}p2;}return p1;
}leetcode跳转80. 删除有序数组中的重复项II
3. 移动零简单
3.1 题目描述 3.2 代码实现
public void moveZeroes(int[] nums) {int zero 0;for (int i 0; i nums.length; i) {if (nums[i] ! 0) {int t nums[i];nums[i] 0;nums[zero] t;zero;}}
}leetcode跳转283. 移动零
4. 两数之和入门
4.1 题目描述 4.2 解题思路
左右指针相向遍历
4.3 代码实现
public int[] twoSum(int[] numbers, int target) {int n numbers.length;int left 0;int right n - 1;while (left right) {int sum numbers[left] numbers[right];if (sum target) {return new int[]{left 1, right 1};} else if (sum target) {right--;} else {left;}}return null;
}leetCode跳转167. 两数之和 II - 输入有序数组
5. 盛水最多的容器中等
5.1 题目描述 5.2 解题思路
同样是一道左右指针相向遍历的题每次移动较短的柱子盛水最多的容器即为间距 * min(left, right)
5.3 代码实现
public int maxArea(int[] height) {int n height.length;int left 0;int right n - 1;int ans 0;while (left right) {int min Math.min(height[left], height[right]);ans Math.max(ans, min * (right - left));if (height[left] height[right]) {left;} else {right--;}}return ans;
}leetCode跳转11. 盛水最多的容器
6. 三数之和中等
6.1 题目描述 6.2 解题思路
排序双指针也是常见的组合解法本题只需要排序后再进行枚举即可。
两处优化
6.3 代码实现
public ListListInteger threeSum(int[] nums) {Arrays.sort(nums);ListListInteger ans new ArrayList();int n nums.length;for (int i 0; i n - 2; i) {if (i 0 nums[i] nums[i - 1]) {continue;}if (nums[i] nums[n - 1] nums[n - 2] 0) {continue;}if (nums[i] nums[i 1] nums[i 2] 0) {break;}int k n - 1;for (int j i 1; j k; j) {if (j i 1 nums[j] nums[j - 1]) {continue;}while (j k nums[i] nums[j] nums[k] 0) {k--;}if (j k) {break;}if (nums[i] nums[j] nums[k] 0) {ListInteger list new ArrayList();list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);ans.add(list);}}}return ans;
}leetCode跳转15. 三数之和
7. 最接近的三数之和中等
7.1 题目描述 7.2 解题思路
解法同三数之和
7.3 代码实现
public int threeSumClosest(int[] nums, int target) {Arrays.sort(nums);int ans Integer.MAX_VALUE;int n nums.length;for (int i 0; i n - 2; i) {int j i 1;int k n - 1;while (j k) {int sum nums[i] nums[j] nums[k];if (sum target) {return sum;}// 接近三数之和if (Math.abs(sum - target) Math.abs(ans - target)) {ans sum;}if (sum target) {k--;} else {j;}}}return ans;
}leetCode跳转16. 最接近的三数之和
8. 接雨水中等
8.1 题目描述 8.2 解题思路
左右指针相向遍历。 要求可接的雨水处的水量可以先分别求出位于此处两侧最长柱子的高度然后取其较短的一根即表示其可接水量的上限因此完全可以通过不断的左右遍历收缩较短的柱子的方式计算出每个位置可接的水量。
8.3 代码实现
public int trap(int[] height) {int n height.length;int leftMax 0;int rightMax 0;int left 0;int right n - 1;int ans 0;while (left right) {leftMax Math.max(leftMax, height[left]);rightMax Math.max(rightMax, height[right]);if (height[left] height[right]) {ans leftMax - height[left];left;} else {ans rightMax - height[right];right--;}}return ans;
}leetCode跳转42. 接雨水
