class050 双指针技巧与相关题目【算法】
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) // 提交时改名为trap public 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-1 for (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) // 提交时改名为trap public 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; } }