文章目录一、用最少数量的箭引爆气球解题思路代码实现及解析总结二、整数替换解题思路代码实现及解析总结三、俄罗斯套娃信封问题解题思路代码实现及解析总结四、可被三整除的最大和解题思路代码实现及解析总结五、距离相等的条形码解题思路代码实现及解析总结一、用最少数量的箭引爆气球Leetcode链接有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points 其中points[i] [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭若有一个气球的直径的开始和结束坐标为 xstartxend 且满足 xstart ≤ x ≤ xend则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后可以无限地前进。给你一个数组 points 返回引爆所有气球所必须射出的 最小 弓箭数 。解题思路points数组里放的是气球的宽度但是没有给气球在y轴的上下位置但是题目又说弓箭是垂直于x轴且可以向上一直走的所以压根就不需要y坐标。要求每个弓箭尽可能多地引爆气球那我们只要把箭射向多个气球重叠的位置就行了我们发现这其实还是一个【区间问题】气球宽度就是区间。我们还是先把区间按左边界排序将区间排序之后有两个性质①能够合并的区间也就是之前【合并区间】那题那些连续有交集的区间可以合并是连续的一旦中断后面的区间就不会再和当前合并区间有交集了性质①就是用来解决【合并问题】的②互相重叠的区间也是连续的互相重叠是指一些区间之间任意两个区间都有重叠这些区间就共同形成了一个“重叠堆”一旦后面有个区间不再和之前的区间一样满足这样的性质不再属于这个重叠堆了那它后面所有的区间也一定不会再属于这个重叠堆了只能再形成一个新的重叠堆这样一来排序之后区间就会呈先一个一个分开的“堆”一个不和其他区间有交集的区间也算一个“堆”性质②就是用来解决【交集问题】的依据性质②我们只需要统计一下有多少个这样的“堆”就行了如何确定哪些区间是属于同一个“堆”的呢其实和【合并区间】这题差不多选一个起点[left,right]用它的 right 判断它和后面的待判区间[a,b]有没有交集有交集就形成了一个“堆”把交集部分叫做重叠区间然后把right更新为重叠区间的右边界这样如果下一个区间和重叠区间有交集righta那么它就和之前其他的区间都有交集如果与这个待判区间没有交集就把right更新为b并把这个新的“堆”计数继续向后判断代码实现及解析classSolution{publicintfindMinArrowShots(int[][]points){//1.按左端点排序Arrays.sort(points,(o1,o2)-o1[0]o2[0]?1:-1);//端点值可能超出int范围所以不要把他们相减用三目表达式判断一下//2.统计“重叠堆”的数量intret1;//先把第一个重叠堆计数下次都是统计的新的堆这样计数不会像之前那样把最后一次给漏掉了intrightpoints[0][1],npoints.length;for(inti1;in;i){intapoints[i][0],bpoints[i][1];//先计算一下待判定区间的左、右边界if(righta){//与重叠区间有交集rightMath.min(right,b);//更新一下重叠区间的右边界即可}else{//没有交集rightb;//更换该待判区间的右边界为新的重叠区间边界继续向后判断ret;//并把这个新的重叠区间计数}}returnret;}}总结复习解题思路二、整数替换Leetcode链接给定一个正整数 n 你可以做如下操作如果 n 是偶数则用 n / 2替换 n 。如果 n 是奇数则可以用 n 1或n - 1替换 n 。返回 n 变为 1 所需的 最小替换次数 。解题思路可以用dfs算法试遍所有的选法可以OC但是本题还有个贪心的策略不过就是要结合二进制数去发现很巧妙的规律只能说当经验吸收吧首先偶数没的说只能选 /2 操作但如何确定奇数选择1和-1哪个最优奇数按其二进制数的最后两位数可分为两类一类为“…01”一类为“…11”可以看到第一类为“…01”前提n1就是保证省略号那部分中至少还有一个1的选择-1操作后比选择1后的二进制数中“1”的含量是要少的这样一来它就可以在接近十进制的数字 1 的过程中处理更少的“1”就可以更多地使用 /2 更快的接近 “1D”第二类同理“…11”图中为方便展示用01111示例实际只需要看最后两位分类选择1之后二进制数中的“1”含量是较少的之后便于使用更多的 /2 接近“1D”不是一次/2省略号里面还有反正比选择-1的那种二进制中的“1”少n3是因为n3是特殊情况它选选择-1再/2就到达“1D”了更快代码实现及解析classSolution{publicintintegerReplacement(intn){intcount0;while(n1){if(n%20){n/2;//n是偶数的话只能选择/2count;}else{if(n3){//先处理一下特殊情况count2;returncount;}elseif((n2)0){//n的二进制的最后两位是01n-1;count;}else{//n22:n的二进制的最后两位是11//n1;这里非常恶心如果n的值为int的最大值的话1正好存不下直接完了nn/21;//但是有个很好用的技巧如果再发现这种情况但是1和/2操作是一起的话因为1后变偶数下一次一定是/2//就可以先/2再1,这样值不变也不会导致溢出了count2;}}}returncount;}}总结复习解题思路和最后那个int溢出的注释三、俄罗斯套娃信封问题Leetcode链接给你一个二维整数数组 envelopes 其中 envelopes[i] [wi, hi] 表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候这个信封就可以放进另一个信封里如同俄罗斯套娃一样。请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封即可以把一个信封放到另一个信封里面。注意不允许旋转信封。解题思路解法一常规/通用解法对乱序的信封数组我们先按照左端点宽度进行排序这样一来一封信想要找它可以套住的信封时就只需要去前面找就行了后面的信封宽度一定比它大所以不行。这样这道题就变成了一道非常熟悉的题目了【最长递增子序列】本题是找到最长的大小严格递增的信封序列也就是最多层的套娃关键就是我们先按照一个维度的因素排好序了这样就已经有助于题目的解答了这样就和【最长递归子序列】一样只需要往前连接位置就行了解题思路基本上就是一样的状态表示dp[i]不是以e[i]为结尾的所有递增信封序列中最长的递增序列的长度方法一会超时因为题目的数据太大但这不代表它不是一个值得尝试的算法有可能其他题目就可以OC算法本身很契合题目解法二重写排序贪心二分解法二就是和【最长递增子序列】一样使用贪心二分进行优化代码实现基本一样就是数据从单个数变为了含有两个影响因素的信封[wide,height]但问题就在这这种双影响因子的元素在使用我们这个解题技巧不同长度的子序列分类保留每类中结尾最小的那一个时我们原来先是按照宽度升序排序但是宽度一样的这些元素的排序是必须要继续处理的不然不止一种情况下会导致逻辑出错所以我们要重写排序宽度一样我们要按照其高度继续进行降序排序这样才不会出问题其实在处理这些元素时我们仍然是以一个数组的形式去看待它们的但当我们按宽度升序宽度相等时再按高度降序对信封排序后就不用再看宽度了直接把宽度给删掉不看了就只取高度的数据去实现代码这样的话这题就真的完完全全变成【最长递归子序列】了但是还是要注意一定要重写排序建议就这样实现代码要是将这些信封还是看做一个数组[wide,height]来处理的话会比较麻烦还可能会出错代码实现及解析classSolution{publicintmaxEnvelopes(int[][]envelopes){intnenvelopes.length;//1.排序宽度不相等就按宽度升序宽度相等的就按其高度降序Arrays.sort(envelopes,(o1,o2)-o1[0]o2[0]?o2[1]-o1[1]:o1[0]-o2[0]);//2.贪心二分ArrayListIntegerhashnewArrayList();//hash表储存筛选后那些信封的高度hash.add(envelopes[0][1]);for(inti1;in;i){intheightenvelopes[i][1];if(heighthash.get(hash.size()-1)){//像【最长递增子序列】那样处理一下特殊情况hash.add(height);}else{//用二分找到height的插入位置intleft0,righthash.size()-1;while(leftright){intmid(leftright)/2;if(hash.get(mid)height){leftmid1;}else{rightmid;}}hash.set(right,height);}}returnhash.size();}}总结复习解题思路四、可被三整除的最大和Leetcode链接给你一个整数数组 nums请你找出并返回能被三整除的元素 最大和。示例 1输入nums [3,6,5,1,8]输出18解释选出数字 3, 6, 1 和 8它们的和是 18可被 3 整除的最大和。解题思路解法一正着来是使用的dp算法dp[i][j]表示前i个元素中选择和为sum且sum%3jj∈0,1,2sum的最大值解法二贪心算法是正难则反思想我们可以先看一下nums的和sum是否满足sum%3 0满足的话就它了。如果不满足那就需要在nums中尽可能挑选一些较小的元素减掉使最终的sum%30可以看到sum%3 0不成立的话只能两种可能①sum%3 1②sum%3 2而对于两种情况产生的原因也是可分类谈论的设xi满足xi%31yi满足yi%3 2①1.sum的组成x1其他使得①成立2.sum的组成y1y2其他y1y2使得①成立②1.sum的组成y1其他使得②成立2.sum的组成x1x2其他x1x2使得②成立这样的话只需要找到数组中最小的两个x1、x2和两个y1、y2按照优先级队列的逻辑自己实现一下就行最后再分类讨论哪种情况就使用哪种推论返回①/②中两个假设的max代码实现及解析classSolution{publicintmaxSumDivThree(int[]nums){intINF0x3f3f3f3f,x1INF,x2INF,y1INF,y2INF;intsum0;for(intnum:nums){sumnum;if(num%31){if(numx1){x2x1;x1num;}elseif(numx2){x2num;}}elseif(num%32){if(numy1){y2y1;y1num;}elseif(numy2){y2num;}}}if(sum%30)returnsum;elseif(sum%31)returnMath.max(sum-x1,sum-y1-y2);elsereturnMath.max(sum-x1-x2,sum-y1);}}总结复习解题思路五、距离相等的条形码Leetcode链接在一个仓库里有一排条形码其中第 i 个条形码为 barcodes[i]。请你重新排列这些条形码使其中任意两个相邻的条形码不能相等。 你可以返回任何满足该要求的答案此题保证存在答案。示例 1输入barcodes [1,1,1,2,2,2]输出[2,1,2,1,2,1]解题思路怎么把这些数排列使得相邻的数不相等直接给出思路间隔插入法统计出每个数出现的次数并同时将出现次数最多的数maxNum以及该次数maxCount都记录先把所有的maxNum从0下标开始每间隔一个位置进行放置maxNum用完之后继续拿出其他统计出的一样的数按此规则继续放置直到放到数组末尾。此时数组中的所有空位也都是间隔的把剩下的数依次放入间隔先放a个x1再放b个x2…这样只要同一种数一块放就行不同类的顺序不需要关心为什么一定要先处理出现次数最多的数假如用例为[1,2,2]如果先放1那最后的结果还是[1,2,2]所以必须先放出现次数较多的2[2,1,2]关于用例是否可以成功构建目标排列的证明不过本题已注明用例均存在答案把所有的数分为两两一组不够两个的自成一组总共可以分为(n1)/2组利用鸽巢原理可以证得如果出现次数最多的那个数出现的次数不超过(n1)/2的话就存在符合题意的排列而如果maxCount(n1)/2的话那至少存在一组中出现2个maxNum就不存在符合题意的排列代码实现及解析classSolution{publicint[]rearrangeBarcodes(int[]barcodes){HashMapInteger,IntegerhashnewHashMap();intmaxNum0,maxCount0;//记录每个数出现的次数的同时把出现次数最多的数以及该次数都记录for(intx:barcodes){hash.put(x,hash.getOrDefault(x,0)1);if(maxCounthash.get(x)){maxNumx;maxCounthash.get(x);}}intindex0;//先把出现次数最多的数间隔一个位置进行放置for(inti0;imaxCount;i){barcodes[index]maxNum;index2;}//然后处理剩下的数顺序随意hash.remove(maxNum);for(intkey:hash.keySet()){for(inti0;ihash.get(key);i){if(indexbarcodes.length)index1;//index越界的话就重新回到前面第一个空位barcodes[index]key;index2;//依次填放在空位上}}returnbarcodes;}}总结复习解题思路