算法学习—双指针

指针"/>

算法学习—双指针

算法学习

双指针

922. 按奇偶排序数组 II

给定一个非负整数数组 nums， nums 中一半整数是 奇数 ，一半整数是 偶数 。

对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数 ；当 nums[i] 为偶数时， i 也是 偶数 。

你可以返回 任何满足上述条件的数组作为答案 。

/*** @param {number[]} nums* @return {number[]}*/
var sortArrayByParityII = function(nums) {const swap = function (nums,i,j){let tmp = nums[i]nums[i] = nums[j]nums[j] = tmp}let n = nums.lengthlet old = 1,even =0;while(old<n && even<n){if((nums[n-1] & 1) === 1){swap(nums,old,n-1)old += 2}else{swap(nums,even,n-1)even += 2}}return nums
};

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

/*** @param {number[]} nums* @return {number}*/
var findDuplicate = function(nums) {if(nums === null || nums.length<2) return -1let slow = nums[0]let fast = nums[nums[0]]while(slow !== fast){slow = nums[slow] // 走一步fast = nums[nums[fast]] // 走二步}fast = 0while(slow !== fast){slow = nums[slow]fast = nums[fast]}return slow
};

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

// 解法一：
/*** @param {number[]} height* @return {number}*/
var trap = function(height) {let n = height.lengthlet rmax = []let lmax = []lmax[0] = height[0]for(let i = 1;i < n;i++){lmax[i] = Math.max(lmax[i-1],height[i])}rmax[n-1] = height[n-1]for(let i = n-2;i > 0 ;i--){rmax[i] = Math.max(rmax[i+1],height[i])}let res = 0for(let i = 1;i < n -1;i++){res += Math.max(Math.min(lmax[i],rmax[i])-height[i],0)}return res
};
// 解法二：
/*** @param {number[]} height* @return {number}*/
var trap = function(height) {let L = 1,R = height.length - 2,lmax = height[0],rmax = height[height.length - 1]let res = 0while(L <= R){if(lmax <= rmax){res += Math.max(0, lmax-height[L])lmax = Math.max(lmax,height[L++])}else{res += Math.max(0, rmax-height[R])rmax = Math.max(rmax,height[R--])}}return res
};

881. 救生艇

给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回 承载所有人所需的最小船数 。

/*** @param {number[]} people* @param {number} limit* @return {number}*/
var numRescueBoats = function(people, limit) {people.sort()let res = 0,sum = 0,left = 0let right = people.length - 1while (left <= right) {sum = left === right ? people[left]:people[left]+people[right]if( sum > limit){right--}else{right--left++}res++}return res 
};

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明：**你不能倾斜容器。

/*** @param {number[]} height* @return {number}*/
var maxArea = function(height) {let res = 0let l = 0let r = height.length - 1while(l < r){res = Math.max(res ,(Math.min(height[l],height[r]) * (r-l)))if(height[l]<=height[r]){l++}else{r--}}return res};

475. 供暖器

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

在加热器的加热半径范围内的每个房屋都可以获得供暖。

现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。

注意：所有供暖器 heaters 都遵循你的半径标准，加热的半径也一样。

/*** @param {number[]} houses* @param {number[]} heaters* @return {number}*/
var findRadius = function(houses, heaters) {houses.sort((a,b)=>a-b)heaters.sort((a,b)=>a-b)let res = 0const best = function(houses,heaters,i,j){return j === heaters.length-1 || Math.abs(heaters[j]-houses[i])< Math.abs(heaters[j+1]-houses[i])}for(let i = 0,j = 0;i < houses.length; i++){while(!best(houses,heaters,i,j)){j++}res = Math.max(res, Math.abs(heaters[j]-houses[i]))}return res
};