零 叠甲LeetCode 922-287-42-881-11-475一 双指针类型同向双指针快慢双指针对撞双指针其它一 LeetCode 922 按奇偶排序数组LeetCode 922给定一个非负整数数组 nums nums 中一半整数是 奇数 一半整数是 偶数 。对数组进行排序以便当 nums[i] 为奇数时i 也是 奇数 当 nums[i] 为偶数时 i 也是 偶数 。你可以返回 任何满足上述条件的数组作为答案 。示例 1输入nums [4,2,5,7] 输出[4,5,2,7] 解释[4,7,2,5][2,5,4,7][2,7,4,5]也会被接受。 示例 2输入nums [2,3] 输出[2,3]提示2 nums.length 2 * 104 nums.length 是偶数 nums 中一半是偶数 0 nums[i] 1000 1)方法一 (暴力法)创建两个数组odd(存放奇数) even(存放偶数)然后把nums的奇数位置都用odd填充nums的偶数位置都用even填充//AC了classSolution{public:vectorintsortArrayByParityII(vectorintnums){vectorintodd,even;for(intit:nums){if(it1)odd.push_back(it);elseeven.push_back(it);}for(inti0;inums.size();i){if(i1){nums[i]odd[(i-1)/2];}else{nums[i]even[i/2];}}returnnums;}};2)方法二 (双指针)固定最后一个位置arr.back()初始时odd1; even0;如果最后一个位置是奇数 swap(arr.back(),arr[odd] ); odd2;如果最后一个位置是偶数 swap(arr.back(),arr[even] ); even2;就好像是两个快递站一样 odd快递站 和 even快递站 把数组最后的物品发到对应的快递站后 数组最后的位置又更新了 又继续发快递 直到有一个快递站超出范围left的左边(不包含left都是偶数元素)right的右边(不包含right都是奇数)循环结束的时候 right-left1并且left指向奇数元素 right指向偶数元素classSolution{public://双指针实现了原地调整vectorintsortArrayByParityII(vectorintnums){intodd1;//指向奇数位置inteven0;//指向偶数位置while(oddnums.size()evennums.size()){intbacknums.back();//back是最后的值if(back1){//最后一个数是奇数 应该去奇数的快递站swap(nums[odd],nums.back());odd2;//快递站2}else{//最后一个数是偶数 应该去偶数的快递站swap(nums[even],nums.back());even2;//快递站2}}returnnums;}};3)方法三 (双指针更简洁的写法)思路于方法二一样 代码更简洁了classSolution{public:vectorintsortArrayByParityII(vectorintnums){for(intodd1,even0;oddnums.size()evennums.size();){if(nums.back()1){swap(nums[odd],nums.back());odd2;}else{swap(nums[even],nums.back());even2;}}returnnums;}};二 LeetCode 287 寻找重复数LeetCode 287给定一个包含 n 1 个整数的数组 nums 其数字都在 [1, n] 范围内包括 1 和 n可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 返回 这个重复的数 。你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。示例 1输入nums [1,3,4,2,2] 输出2 示例 2输入nums [3,1,3,4,2] 输出3 示例 3 :输入nums [3,3,3,3,3] 输出3提示1 n 105 nums.length n 1 1 nums[i] n nums 中 只有一个整数 出现两次或多次 其余整数均只出现 一次1)方法一 (二分答案 看不懂可以看我之前发的二分答案)答案的范围是[1 , nums.size()-1 ];int left1;int rightnums.size()-1;int middleft(right-left)/2;统计一下整个数组中小于等于midd的元素个数cnt-----如果cntmidd 一定这个重复数字在[1,midd]上 因为比midd小于等于的数的取值有1,2,3…midd 一共有midd种 而小于等于midd的数字的数量cnt比种类多 说明一定会有重复的数字 所以重复数字一定在[1,midd]上 只需要缩小范围 在[1,midd]上寻找就行了-----如果cntmidd 一定这个重复数字在[midd1,n]上 因为比midd大的元素的取值有midd1 midd2 mid3…n 一共有n-midd种 而小于等于midd的元素有cnt种 一共有n1个数 那么大于midd的就有n1-cnt个 这个cntmidd 所以大于midd的数量一定是一定比元素取值的个数多 所以一定在[midd1,n]上有重复数classSolution{public:intfindDuplicate(vectorintnums){intleft1;intrightnums.size()-1;//二分答案//这是一个数轴 也是重复数的范围[1 , nums.size()-1]//1-------------------nums.size()-1//小------------------大while(leftright){intmiddleft(right-left)/2;//下面统计小于等于midd的数量intcnt0;for(intit:nums)if(itmidd)cnt;//如果小于等于midd的数的个数cntmidd//那么重复数字一定在[1,midd]中//否则就在[midd1,nums.size()-1]范围上if(cntmidd){rightmidd;}else{leftmidd1;}}returnleft;}};2)方法二 (双指针 环问题)把数组元素的值看作是下一个元素的地址相当于找链表的环问题//AC了classSolution{public:intfindDuplicate(vectorintnums){intfastnums[0];//fast在第一个位置intslownums[0];//slow在第一个位置do{fastnums[nums[fast]];//fast每次走两步slownums[slow];//slow每次走一步}while(fast!slow);fastnums[0];//fast再从开始走while(fast!slow){fastnums[fast];slownums[slow];}//循环结束就找到了环入口位置returnfast;}};三 LeetCode 42 接雨水LeetCode 421)方法一 (前缀最大值preMax 后缀最大值sufMax)每一个格子中雨水的量这个格子的前缀最大值(包含这个格子)和这个格子的后缀最大值(包含这个格子)中较小的那个minn 用minn-当前格子的数值就是高度 再*1就是中这个格子的容量 最后累加每一个格子就行了每一个格子的容量( max( preMax[i],sufMax[i] )-height[i] )乘1;classSolution{public:inttrap(vectorintheight){//统计每一个元素的前缀最大值(包含这个元素)vectorintpreMax(height.size(),height[0]);for(inti1;iheight.size();i){preMax[i]max(preMax[i-1],height[i]);}//统计后缀最大值vectorintsufMax(height.size(),height.back());for(intiheight.size()-2;i0;--i){sufMax[i]max(sufMax[i1],height[i]);}//下面累加每一个格子的容水量intret0;for(inti0;iheight.size();i){intminnmin(preMax[i],sufMax[i]);ret(minn-height[i])*1;}returnret;//返回}};如果你考虑到了第一个位置和最后一个位置都一定没有水并且想前缀最大值 和 后缀最大值 数组不包含当前值下面代码供你参考//AC了classSolution{public:inttrap(vectorintheight){vectorintpreMax(height.size(),INT_MIN);for(inti1;iheight.size();i){preMax[i]max(preMax[i-1],height[i-1]);}vectorintsufMax(height.size(),INT_MIN);for(intiheight.size()-2;i0;--i){sufMax[i]max(sufMax[i1],height[i1]);}intret0;for(inti1;iheight.size()-1;i){ret(max(min(preMax[i],sufMax[i]),height[i])-height[i])*1;}returnret;}};2)方法二 (双指针 最优解法)简直是神之美妙的想法在上一种方法的基础上优化用leftMax记录左侧部分的最大值 用rightMax记录右侧部分的最大值 left从下标1开始 因为下标0位置一定没有水right从倒数第二个位置开始 因为最后一个位置一定没有水-------如果此时leftMaxrightMax了 那么right指向的格子的储水量就可以确定了 因为right格子的储水量是由左边右边格子的最大值决定的(由短板决定) leftMax已经大于了rightMax 一定就由右侧最大值决定了 所以可以计算右侧格子的储水量了 ( max(rightMax,height[right])-height[right] )*1------同理如果leftMaxrightMax 可以计算左侧格子的储水量了//AC了classSolution{public:inttrap(vectorintheight){intleftMaxheight[0];intrightMaxheight.back();intret0;intleft1;intrightheight.size()-2;while(leftright){if(leftMaxrightMax){//左侧部分最大值 右侧部分最大值ret(max(height[right],rightMax)-height[right])*1;rightMaxmax(rightMax,height[right]);right--;}else{ret(max(height[left],leftMax)-height[left])*1;leftMaxmax(leftMax,height[left]);left;}}returnret;}};四 LeetCode 881LeetCode 881给定数组 people 。people[i]表示第 i 个人的体重 船的数量不限每艘船可以承载的最大重量为 limit。每艘船最多可同时载两人但条件是这些人的重量之和最多为 limit。返回 承载所有人所需的最小船数 。示例 1输入people [1,2], limit 3 输出1 解释1 艘船载 (1, 2) 示例 2输入people [3,2,2,1], limit 3 输出3 解释3 艘船分别载 (1, 2), (2) 和 (3) 示例3输入people [3,5,3,4], limit 5 输出4 解释4 艘船分别载 (3), (3), (4), (5)提示1 people.length 5 * 104 1 people[i] limit 3 * 1041)方法一 (双指针)因为一个船最多只能带两个人我们可以这样看 一个船先把最大的放进去 再看一下能不能放最小的(相当于再仓库放货物时 先把大件的放进去 再塞进去小件 看看能不能塞进去)classSolution{public:intnumRescueBoats(vectorintpeople,intlimit){sort(people.begin(),people.end());intleft0;intrightpeople.size()-1;intpart0;intsum0;while(leftright){sumpeople[right];//每一个船先把体重大的进去//再看看能不能塞进去体重小的if(sumpeople[left]limit){//能塞进去就塞进去sumpeople[left];left;//指针移动}right--;part;sum0;//sum清零 开始下一个船}returnpart;}};也可以这样当leftright时 不管怎样都part了 所以不用再特殊考虑classSolution{public:intnumRescueBoats(vectorintpeople,intlimit){sort(people.begin(),people.end());intleft0;intrightpeople.size()-1;intpart0;while(leftright){if(people[left]people[right]limit){left;}right--;part;}returnpart;}};五 四的扩展题(大厂面试题)题目: 在四的基础上加一个要求: 如果时两个人坐船 体重相加必须为偶数思路:只需要把数组分为odd数组和even数组因为偶数偶数偶数 奇数奇数偶数分别计算各自需要的船part 再相加1)方法一(双指针)classSolution{private:intfun(vectorintarr,intlimit){intpart0;intleft0;intrightarr.size()-1;while(leftright){if(arr[left]arr[right]limit){left;}part;right--;}returnpart;}public:intnumRescueBoats(vectorintpeople,intlimit){vectorintodd,even;for(intit:people)if(it1)odd.push_back(it);elseeven.push_back(it);sort(odd.begin(),odd.end());sort(even.begin(),even.end());intpartfun(odd,limit)fun(even,limit);returnpart;}};六 LeetCode 11 盛最多水的容器LeetCode 11给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明你不能倾斜容器。示例 1输入[1,8,6,2,5,4,8,3,7] 输出49 解释图中垂直线代表输入数组[1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为 49。 示例 2输入height [1,1] 输出1提示n height.length 2 n 105 0 height[i] 1041)方法一(双指针)classSolution{public:intmaxArea(vectorintheight){intleft0;intrightheight.size()-1;intmaxx0;while(leftright){maxxmax(maxx,min(height[left],height[right])*(right-left));if(height[left]height[right]){left;}else{right--;}}returnmaxx;}};七 LeetCode 475 供暖器冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。在加热器的加热半径范围内的每个房屋都可以获得供暖。现在给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置请你找出并返回可以覆盖所有房屋的最小加热半径。注意所有供暖器 heaters 都遵循你的半径标准加热的半径也一样。示例 1:输入: houses [1,2,3], heaters [2] 输出: 1 解释: 仅在位置 2上有一个供暖器。如果我们将加热半径设为 1那么所有房屋就都能得到供暖。 示例 2:输入: houses [1,2,3,4], heaters [1,4] 输出: 1 解释: 在位置 1, 4上有两个供暖器。我们需要将加热半径设为 1这样所有房屋就都能得到供暖。 示例 3输入houses [1,5], heaters [2] 输出3提示1 houses.length, heaters.length 3 * 104 1 houses[i],heaters[i] 1091)方法一(暴力解法)找到每一个房屋的专属供暖器 就是遍历每一个房屋 找到距离最近的那个j 可以遍历heaters数组 最小的距离就是这个供暖器需要的最小半径 maxxmax(maxx,minn);更新maxxclassSolution{public:intfindRadius(vectorinthouses,vectorintheaters){intmaxx0;for(inti0;ihouses.size();i){//找到距离i最近的j 并且更新maxxinttemphouses[i];intminnINT_MAX;for(intj0;jheaters.size();j){minnmin(minn,abs(heaters[j]-temp));}maxxmax(maxx,minn);}returnmaxx;}};2)方法二(双指针)对暴力法的优化对于每一个房屋i 都要找到距离它最近的供暖器j在判断是不是最优 j 时候 可以先排序 因为 j 是上一个的最优供暖器 只需要判断是不是当前这个的最优就行了 如果不是就往后找 j 一直找到最优j 如果j 已经到了数组最后那就是最优了//AC了classSolution{public://判断j是不是i的最优boolisBest(vectorinthouses,vectorintheaters,inti,intj){if(jheaters.size()-1)returntrue;//如果是最后一个 也只能选这个作为最优了 直接返回trueif(abs(houses[i]-heaters[j])abs(houses[i]-heaters[j1]))returntrue;//如果后面的差值要大于当前的j的差值 说明就是最优//注意如果相等也应该选择往后的jreturnfalse;}intfindRadius(vectorinthouses,vectorintheaters){sort(houses.begin(),houses.end());sort(heaters.begin(),heaters.end());intj0;intmaxx0;for(inti0;ihouses.size();i){while(!isBest(houses,heaters,i,j)){//i号房屋选择j号供暖器是最优j;}maxxmax(maxx,abs(houses[i]-heaters[j]));}returnmaxx;}};
双指针(一步一步)(零-＞进阶-＞高难度 ||LeetCode 922-＞287-＞42-＞881-＞11-＞475)
零 叠甲LeetCode 922-287-42-881-11-475一 双指针类型同向双指针快慢双指针对撞双指针其它一 LeetCode 922 按奇偶排序数组LeetCode 922给定一个非负整数数组 nums nums 中一半整数是 奇数 一半整数是 偶数 。对数组进行排序以便当 nums[i] 为奇数时i 也是 奇数 当 nums[i] 为偶数时 i 也是 偶数 。你可以返回 任何满足上述条件的数组作为答案 。示例 1输入nums [4,2,5,7] 输出[4,5,2,7] 解释[4,7,2,5][2,5,4,7][2,7,4,5]也会被接受。 示例 2输入nums [2,3] 输出[2,3]提示2 nums.length 2 * 104 nums.length 是偶数 nums 中一半是偶数 0 nums[i] 1000 1)方法一 (暴力法)创建两个数组odd(存放奇数) even(存放偶数)然后把nums的奇数位置都用odd填充nums的偶数位置都用even填充//AC了classSolution{public:vectorintsortArrayByParityII(vectorintnums){vectorintodd,even;for(intit:nums){if(it1)odd.push_back(it);elseeven.push_back(it);}for(inti0;inums.size();i){if(i1){nums[i]odd[(i-1)/2];}else{nums[i]even[i/2];}}returnnums;}};2)方法二 (双指针)固定最后一个位置arr.back()初始时odd1; even0;如果最后一个位置是奇数 swap(arr.back(),arr[odd] ); odd2;如果最后一个位置是偶数 swap(arr.back(),arr[even] ); even2;就好像是两个快递站一样 odd快递站 和 even快递站 把数组最后的物品发到对应的快递站后 数组最后的位置又更新了 又继续发快递 直到有一个快递站超出范围left的左边(不包含left都是偶数元素)right的右边(不包含right都是奇数)循环结束的时候 right-left1并且left指向奇数元素 right指向偶数元素classSolution{public://双指针实现了原地调整vectorintsortArrayByParityII(vectorintnums){intodd1;//指向奇数位置inteven0;//指向偶数位置while(oddnums.size()evennums.size()){intbacknums.back();//back是最后的值if(back1){//最后一个数是奇数 应该去奇数的快递站swap(nums[odd],nums.back());odd2;//快递站2}else{//最后一个数是偶数 应该去偶数的快递站swap(nums[even],nums.back());even2;//快递站2}}returnnums;}};3)方法三 (双指针更简洁的写法)思路于方法二一样 代码更简洁了classSolution{public:vectorintsortArrayByParityII(vectorintnums){for(intodd1,even0;oddnums.size()evennums.size();){if(nums.back()1){swap(nums[odd],nums.back());odd2;}else{swap(nums[even],nums.back());even2;}}returnnums;}};二 LeetCode 287 寻找重复数LeetCode 287给定一个包含 n 1 个整数的数组 nums 其数字都在 [1, n] 范围内包括 1 和 n可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 返回 这个重复的数 。你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。示例 1输入nums [1,3,4,2,2] 输出2 示例 2输入nums [3,1,3,4,2] 输出3 示例 3 :输入nums [3,3,3,3,3] 输出3提示1 n 105 nums.length n 1 1 nums[i] n nums 中 只有一个整数 出现两次或多次 其余整数均只出现 一次1)方法一 (二分答案 看不懂可以看我之前发的二分答案)答案的范围是[1 , nums.size()-1 ];int left1;int rightnums.size()-1;int middleft(right-left)/2;统计一下整个数组中小于等于midd的元素个数cnt-----如果cntmidd 一定这个重复数字在[1,midd]上 因为比midd小于等于的数的取值有1,2,3…midd 一共有midd种 而小于等于midd的数字的数量cnt比种类多 说明一定会有重复的数字 所以重复数字一定在[1,midd]上 只需要缩小范围 在[1,midd]上寻找就行了-----如果cntmidd 一定这个重复数字在[midd1,n]上 因为比midd大的元素的取值有midd1 midd2 mid3…n 一共有n-midd种 而小于等于midd的元素有cnt种 一共有n1个数 那么大于midd的就有n1-cnt个 这个cntmidd 所以大于midd的数量一定是一定比元素取值的个数多 所以一定在[midd1,n]上有重复数classSolution{public:intfindDuplicate(vectorintnums){intleft1;intrightnums.size()-1;//二分答案//这是一个数轴 也是重复数的范围[1 , nums.size()-1]//1-------------------nums.size()-1//小------------------大while(leftright){intmiddleft(right-left)/2;//下面统计小于等于midd的数量intcnt0;for(intit:nums)if(itmidd)cnt;//如果小于等于midd的数的个数cntmidd//那么重复数字一定在[1,midd]中//否则就在[midd1,nums.size()-1]范围上if(cntmidd){rightmidd;}else{leftmidd1;}}returnleft;}};2)方法二 (双指针 环问题)把数组元素的值看作是下一个元素的地址相当于找链表的环问题//AC了classSolution{public:intfindDuplicate(vectorintnums){intfastnums[0];//fast在第一个位置intslownums[0];//slow在第一个位置do{fastnums[nums[fast]];//fast每次走两步slownums[slow];//slow每次走一步}while(fast!slow);fastnums[0];//fast再从开始走while(fast!slow){fastnums[fast];slownums[slow];}//循环结束就找到了环入口位置returnfast;}};三 LeetCode 42 接雨水LeetCode 421)方法一 (前缀最大值preMax 后缀最大值sufMax)每一个格子中雨水的量这个格子的前缀最大值(包含这个格子)和这个格子的后缀最大值(包含这个格子)中较小的那个minn 用minn-当前格子的数值就是高度 再*1就是中这个格子的容量 最后累加每一个格子就行了每一个格子的容量( max( preMax[i],sufMax[i] )-height[i] )乘1;classSolution{public:inttrap(vectorintheight){//统计每一个元素的前缀最大值(包含这个元素)vectorintpreMax(height.size(),height[0]);for(inti1;iheight.size();i){preMax[i]max(preMax[i-1],height[i]);}//统计后缀最大值vectorintsufMax(height.size(),height.back());for(intiheight.size()-2;i0;--i){sufMax[i]max(sufMax[i1],height[i]);}//下面累加每一个格子的容水量intret0;for(inti0;iheight.size();i){intminnmin(preMax[i],sufMax[i]);ret(minn-height[i])*1;}returnret;//返回}};如果你考虑到了第一个位置和最后一个位置都一定没有水并且想前缀最大值 和 后缀最大值 数组不包含当前值下面代码供你参考//AC了classSolution{public:inttrap(vectorintheight){vectorintpreMax(height.size(),INT_MIN);for(inti1;iheight.size();i){preMax[i]max(preMax[i-1],height[i-1]);}vectorintsufMax(height.size(),INT_MIN);for(intiheight.size()-2;i0;--i){sufMax[i]max(sufMax[i1],height[i1]);}intret0;for(inti1;iheight.size()-1;i){ret(max(min(preMax[i],sufMax[i]),height[i])-height[i])*1;}returnret;}};2)方法二 (双指针 最优解法)简直是神之美妙的想法在上一种方法的基础上优化用leftMax记录左侧部分的最大值 用rightMax记录右侧部分的最大值 left从下标1开始 因为下标0位置一定没有水right从倒数第二个位置开始 因为最后一个位置一定没有水-------如果此时leftMaxrightMax了 那么right指向的格子的储水量就可以确定了 因为right格子的储水量是由左边右边格子的最大值决定的(由短板决定) leftMax已经大于了rightMax 一定就由右侧最大值决定了 所以可以计算右侧格子的储水量了 ( max(rightMax,height[right])-height[right] )*1------同理如果leftMaxrightMax 可以计算左侧格子的储水量了//AC了classSolution{public:inttrap(vectorintheight){intleftMaxheight[0];intrightMaxheight.back();intret0;intleft1;intrightheight.size()-2;while(leftright){if(leftMaxrightMax){//左侧部分最大值 右侧部分最大值ret(max(height[right],rightMax)-height[right])*1;rightMaxmax(rightMax,height[right]);right--;}else{ret(max(height[left],leftMax)-height[left])*1;leftMaxmax(leftMax,height[left]);left;}}returnret;}};四 LeetCode 881LeetCode 881给定数组 people 。people[i]表示第 i 个人的体重 船的数量不限每艘船可以承载的最大重量为 limit。每艘船最多可同时载两人但条件是这些人的重量之和最多为 limit。返回 承载所有人所需的最小船数 。示例 1输入people [1,2], limit 3 输出1 解释1 艘船载 (1, 2) 示例 2输入people [3,2,2,1], limit 3 输出3 解释3 艘船分别载 (1, 2), (2) 和 (3) 示例3输入people [3,5,3,4], limit 5 输出4 解释4 艘船分别载 (3), (3), (4), (5)提示1 people.length 5 * 104 1 people[i] limit 3 * 1041)方法一 (双指针)因为一个船最多只能带两个人我们可以这样看 一个船先把最大的放进去 再看一下能不能放最小的(相当于再仓库放货物时 先把大件的放进去 再塞进去小件 看看能不能塞进去)classSolution{public:intnumRescueBoats(vectorintpeople,intlimit){sort(people.begin(),people.end());intleft0;intrightpeople.size()-1;intpart0;intsum0;while(leftright){sumpeople[right];//每一个船先把体重大的进去//再看看能不能塞进去体重小的if(sumpeople[left]limit){//能塞进去就塞进去sumpeople[left];left;//指针移动}right--;part;sum0;//sum清零 开始下一个船}returnpart;}};也可以这样当leftright时 不管怎样都part了 所以不用再特殊考虑classSolution{public:intnumRescueBoats(vectorintpeople,intlimit){sort(people.begin(),people.end());intleft0;intrightpeople.size()-1;intpart0;while(leftright){if(people[left]people[right]limit){left;}right--;part;}returnpart;}};五 四的扩展题(大厂面试题)题目: 在四的基础上加一个要求: 如果时两个人坐船 体重相加必须为偶数思路:只需要把数组分为odd数组和even数组因为偶数偶数偶数 奇数奇数偶数分别计算各自需要的船part 再相加1)方法一(双指针)classSolution{private:intfun(vectorintarr,intlimit){intpart0;intleft0;intrightarr.size()-1;while(leftright){if(arr[left]arr[right]limit){left;}part;right--;}returnpart;}public:intnumRescueBoats(vectorintpeople,intlimit){vectorintodd,even;for(intit:people)if(it1)odd.push_back(it);elseeven.push_back(it);sort(odd.begin(),odd.end());sort(even.begin(),even.end());intpartfun(odd,limit)fun(even,limit);returnpart;}};六 LeetCode 11 盛最多水的容器LeetCode 11给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明你不能倾斜容器。示例 1输入[1,8,6,2,5,4,8,3,7] 输出49 解释图中垂直线代表输入数组[1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为 49。 示例 2输入height [1,1] 输出1提示n height.length 2 n 105 0 height[i] 1041)方法一(双指针)classSolution{public:intmaxArea(vectorintheight){intleft0;intrightheight.size()-1;intmaxx0;while(leftright){maxxmax(maxx,min(height[left],height[right])*(right-left));if(height[left]height[right]){left;}else{right--;}}returnmaxx;}};七 LeetCode 475 供暖器冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。在加热器的加热半径范围内的每个房屋都可以获得供暖。现在给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置请你找出并返回可以覆盖所有房屋的最小加热半径。注意所有供暖器 heaters 都遵循你的半径标准加热的半径也一样。示例 1:输入: houses [1,2,3], heaters [2] 输出: 1 解释: 仅在位置 2上有一个供暖器。如果我们将加热半径设为 1那么所有房屋就都能得到供暖。 示例 2:输入: houses [1,2,3,4], heaters [1,4] 输出: 1 解释: 在位置 1, 4上有两个供暖器。我们需要将加热半径设为 1这样所有房屋就都能得到供暖。 示例 3输入houses [1,5], heaters [2] 输出3提示1 houses.length, heaters.length 3 * 104 1 houses[i],heaters[i] 1091)方法一(暴力解法)找到每一个房屋的专属供暖器 就是遍历每一个房屋 找到距离最近的那个j 可以遍历heaters数组 最小的距离就是这个供暖器需要的最小半径 maxxmax(maxx,minn);更新maxxclassSolution{public:intfindRadius(vectorinthouses,vectorintheaters){intmaxx0;for(inti0;ihouses.size();i){//找到距离i最近的j 并且更新maxxinttemphouses[i];intminnINT_MAX;for(intj0;jheaters.size();j){minnmin(minn,abs(heaters[j]-temp));}maxxmax(maxx,minn);}returnmaxx;}};2)方法二(双指针)对暴力法的优化对于每一个房屋i 都要找到距离它最近的供暖器j在判断是不是最优 j 时候 可以先排序 因为 j 是上一个的最优供暖器 只需要判断是不是当前这个的最优就行了 如果不是就往后找 j 一直找到最优j 如果j 已经到了数组最后那就是最优了//AC了classSolution{public://判断j是不是i的最优boolisBest(vectorinthouses,vectorintheaters,inti,intj){if(jheaters.size()-1)returntrue;//如果是最后一个 也只能选这个作为最优了 直接返回trueif(abs(houses[i]-heaters[j])abs(houses[i]-heaters[j1]))returntrue;//如果后面的差值要大于当前的j的差值 说明就是最优//注意如果相等也应该选择往后的jreturnfalse;}intfindRadius(vectorinthouses,vectorintheaters){sort(houses.begin(),houses.end());sort(heaters.begin(),heaters.end());intj0;intmaxx0;for(inti0;ihouses.size();i){while(!isBest(houses,heaters,i,j)){//i号房屋选择j号供暖器是最优j;}maxxmax(maxx,abs(houses[i]-heaters[j]));}returnmaxx;}};
