class050 双指针技巧与相关题目【算法】

class050 双指针技巧与相关题目【算法】

算法讲解050【必备】双指针技巧与相关题目

code1 922. 按奇偶排序数组 II

// 按奇偶排序数组II
// 给定一个非负整数数组 nums。nums 中一半整数是奇数 ，一半整数是偶数
// 对数组进行排序，以便当 nums[i] 为奇数时，i也是奇数
// 当 nums[i] 为偶数时， i 也是 偶数
// 你可以返回 任何满足上述条件的数组作为答案
// 测试链接 : https://leetcode.cn/problems/sort-array-by-parity-ii/

奇数指针，偶数指针

package class050;// 按奇偶排序数组II
// 给定一个非负整数数组 nums。nums 中一半整数是奇数 ，一半整数是偶数
// 对数组进行排序，以便当 nums[i] 为奇数时，i也是奇数
// 当 nums[i] 为偶数时， i 也是 偶数
// 你可以返回 任何满足上述条件的数组作为答案
// 测试链接 : https://leetcode.cn/problems/sort-array-by-parity-ii/
public class Code01_SortArrayByParityII {// 时间复杂度O(n)，额外空间复杂度O(1)public static int[] sortArrayByParityII(int[] nums) {int n = nums.length;for (int odd = 1, even = 0; odd < n && even < n;) {if ((nums[n - 1] & 1) == 1) {swap(nums, odd, n - 1);odd += 2;} else {swap(nums, even, n - 1);even += 2;}}return nums;}public static void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}

code2 287. 寻找重复数

// 寻找重复数
// 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n）
// 可知至少存在一个重复的整数。
// 假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
// 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
// 测试链接 : https://leetcode.cn/problems/find-the-duplicate-number/

快指针 慢指针
链表找第一个入环结点

package class050;// 寻找重复数
// 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n）
// 可知至少存在一个重复的整数。
// 假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
// 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
// 测试链接 : https://leetcode.cn/problems/find-the-duplicate-number/
public class Code02_FindTheDuplicateNumber {// 时间复杂度O(n)，额外空间复杂度O(1)public static int findDuplicate(int[] nums) {if (nums == null || nums.length < 2) {return -1;}int slow = nums[0];int fast = nums[nums[0]];while (slow != fast) {slow = nums[slow];fast = nums[nums[fast]];}// 相遇了，快指针回开头fast = 0;while (slow != fast) {fast = nums[fast];slow = nums[slow];}return slow;}}

code3 42. 接雨水

// 接雨水
// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
// 测试链接 : https://leetcode.cn/problems/trapping-rain-water/

求i位置：max(min(左侧最大值和右侧最大值)-i位置的高度,0)

package class050;// 接雨水
// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
// 测试链接 : https://leetcode.cn/problems/trapping-rain-water/
public class Code03_TrappingRainWater {// 辅助数组的解法（不是最优解）// 时间复杂度O(n)，额外空间复杂度O(n)// 提交时改名为trappublic static int trap1(int[] nums) {int n = nums.length;int[] lmax = new int[n];int[] rmax = new int[n];lmax[0] = nums[0];// 0~i范围上的最大值，记录在lmax[i]for (int i = 1; i < n; i++) {lmax[i] = Math.max(lmax[i - 1], nums[i]);}rmax[n - 1] = nums[n - 1];// i~n-1范围上的最大值，记录在rmax[i]for (int i = n - 2; i >= 0; i--) {rmax[i] = Math.max(rmax[i + 1], nums[i]);}int ans = 0;//   x              x//   0 1 2 3...n-2 n-1for (int i = 1; i < n - 1; i++) {ans += Math.max(0, Math.min(lmax[i - 1], rmax[i + 1]) - nums[i]);}return ans;}// 双指针的解法（最优解）// 时间复杂度O(n)，额外空间复杂度O(1)// 提交时改名为trappublic static int trap2(int[] nums) {int l = 1, r = nums.length - 2, lmax = nums[0], rmax = nums[nums.length - 1];int ans = 0;while (l <= r) {if (lmax <= rmax) {ans += Math.max(0, lmax - nums[l]);lmax = Math.max(lmax, nums[l++]);} else {ans += Math.max(0, rmax - nums[r]);rmax = Math.max(rmax, nums[r--]);}}return ans;}}

code4 881. 救生艇

// 救生艇
// 给定数组 people
// people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit
// 每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit
// 返回 承载所有人所需的最小船数
// 测试链接 : https://leetcode.cn/problems/boats-to-save-people/

双指针
数组从小到大排序
体重小和体重大一船，或者体重大一船

拓展：两个人体重和只能是偶数才能一船
可以分为奇数数组偶数数组，分别求出再相加

package class050;import java.util.Arrays;// 救生艇
// 给定数组 people
// people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit
// 每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit
// 返回 承载所有人所需的最小船数
// 测试链接 : https://leetcode.cn/problems/boats-to-save-people/
public class Code04_BoatsToSavePeople {// 时间复杂度O(n * logn)，因为有排序，额外空间复杂度O(1)public static int numRescueBoats(int[] people, int limit) {Arrays.sort(people);int ans = 0;int l = 0;int r = people.length - 1;int sum = 0;while (l <= r) {sum = l == r ? people[l] : people[l] + people[r];if (sum > limit) {r--;} else {l++;r--;}ans++;}return ans;}}

code5 11. 盛最多水的容器

// 盛最多水的容器
// 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
// 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水
// 返回容器可以储存的最大水量
// 说明：你不能倾斜容器
// 测试链接 : https://leetcode.cn/problems/container-with-most-water/

双指针l,r
当前height[l]小，l++
否则r–

package class050;// 盛最多水的容器
// 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
// 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水
// 返回容器可以储存的最大水量
// 说明：你不能倾斜容器
// 测试链接 : https://leetcode.cn/problems/container-with-most-water/
public class Code05_ContainerWithMostWater {// 时间复杂度O(n)，额外空间复杂度O(1)public static int maxArea(int[] height) {int ans = 0;for (int l = 0, r = height.length - 1; l < r;) {ans = Math.max(ans, Math.min(height[l], height[r]) * (r - l));if (height[l] <= height[r]) {l++;} else {r--;}}return ans;}}

code6 code6 475. 供暖器

// 供暖器
// 冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
// 在加热器的加热半径范围内的每个房屋都可以获得供暖。
// 现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置
// 请你找出并返回可以覆盖所有房屋的最小加热半径。
// 说明：所有供暖器都遵循你的半径标准，加热的半径也一样。
// 测试链接 : https://leetcode.cn/problems/heaters/

双指针i，j
对于每一个房屋[i]找到最优的供暖器[j]，最优半径

package class050;import java.util.Arrays;// 供暖器
// 冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
// 在加热器的加热半径范围内的每个房屋都可以获得供暖。
// 现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置
// 请你找出并返回可以覆盖所有房屋的最小加热半径。
// 说明：所有供暖器都遵循你的半径标准，加热的半径也一样。
// 测试链接 : https://leetcode.cn/problems/heaters/
public class Code06_Heaters {// 时间复杂度O(n * logn)，因为有排序，额外空间复杂度O(1)public static int findRadius(int[] houses, int[] heaters) {Arrays.sort(houses);Arrays.sort(heaters);int ans = 0;for (int i = 0, j = 0; i < houses.length; i++) {// i号房屋// j号供暖器while (!best(houses, heaters, i, j)) {j++;}ans = Math.max(ans, Math.abs(heaters[j] - houses[i]));}return ans;}// 这个函数含义：// 当前的地点houses[i]由heaters[j]来供暖是最优的吗？// 当前的地点houses[i]由heaters[j]来供暖，产生的半径是a// 当前的地点houses[i]由heaters[j + 1]来供暖，产生的半径是b// 如果a < b, 说明是最优，供暖不应该跳下一个位置// 如果a >= b, 说明不是最优，应该跳下一个位置public static boolean best(int[] houses, int[] heaters, int i, int j) {return j == heaters.length - 1 ||Math.abs(heaters[j] - houses[i]) < Math.abs(heaters[j + 1] - houses[i]);}}

code7 41. 缺失的第一个正数

// 缺失的第一个正数
// 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
// 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
// 测试链接 : https://leetcode.cn/problems/first-missing-positive/

双指针
l：表示l左侧的位置上放好l+1的值
r：垃圾区；最好预期1…r的值都有
①nums[l]=l+1,l++
②nums[l]<=l,垃圾
③nums[l]>r,垃圾
④nums[nums[l]-1]=nums[l],重复垃圾
⑤交换(l,nums[l]-1)
返回l+1

package class050;// 缺失的第一个正数
// 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
// 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
// 测试链接 : https://leetcode.cn/problems/first-missing-positive/
public class Code07_FirstMissingPositive {// 时间复杂度O(n)，额外空间复杂度O(1)public static int firstMissingPositive(int[] arr) {// l的左边，都是做到i位置上放着i+1的区域// 永远盯着l位置的数字看，看能不能扩充(l++)int l = 0;// [r....]垃圾区// 最好的状况下，认为1~r是可以收集全的，每个数字收集1个，不能有垃圾// 有垃圾呢？预期就会变差(r--)int r = arr.length;while (l < r) {if (arr[l] == l + 1) {l++;} else if (arr[l] <= l || arr[l] > r || arr[arr[l] - 1] == arr[l]) {swap(arr, l, --r);} else {swap(arr, l, arr[l] - 1);}}return l + 1;}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}}