合肥做网站的网络公司,wordpress 如果分类,台州地区网站建设,网址收录查询class050 双指针技巧与相关题目【算法】
算法讲解050【必备】双指针技巧与相关题目
code1 922. 按奇偶排序数组 II
// 按奇偶排序数组II // 给定一个非负整数数组 nums。nums 中一半整数是奇数 #xff0c;一半整数是偶数 // 对数组进行排序#xff0c;以便当 nums[i] 为…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/
双指针ij 对于每一个房屋[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左侧的位置上放好l1的值 r垃圾区最好预期1…r的值都有 ①nums[l]l1,l ②nums[l]l,垃圾 ③nums[l]r,垃圾 ④nums[nums[l]-1]nums[l],重复垃圾 ⑤交换(l,nums[l]-1) 返回l1
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位置上放着i1的区域// 永远盯着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;}}
