万户网络做网站,吉林省建设安全信息网官网,网站图片切换怎么做,上海 专业网站设计前言
学习算法的时候#xff0c;总会有一些让人生畏的名词#xff0c;比方动态规划#xff0c;贪心算法 等#xff0c;听着就很难#xff1b;而这一 part 就是为了攻破之前一直没有系统学习的 贪心算法#xff1b;
有一说一#xff0c;做了这些贪心题#xff0c;其实…前言
学习算法的时候总会有一些让人生畏的名词比方动态规划贪心算法 等听着就很难而这一 part 就是为了攻破之前一直没有系统学习的 贪心算法
有一说一做了这些贪心题其实并没觉得发现了什么套路新大陆等因为贪心有的时候很巧妙而且想到就是想到了没想到可能就不用贪心去做了所以这属于做完只是刷了存在感的 part
唯一的收获就是减轻了对贪心的恐惧明白它也就是一种 局部贪心导致全局贪心得到最优解 的一种思路方法所以以后遇到了也就能心平气和的去学习使用它了
下一 part 去做一下比较难的并查集
正文
455. 分发饼干
分析 – 贪心
用最大的饼干满足胃口最大的小孩这样就能局部最优求出全局最优可以满足最多的小孩由于 g,s 都需要取最大所以需要排序最后用两个端套的遍历找出最优解时间复杂度 O(nm)
var findContentChildren function (g, s) {g.sort((a,b) a-b)s.sort((a,b) a-b)let ret 0let sl s.length-1; let gl g.length-1while(gl0){// 人没了饼干可以还存在if(s[sl]g[gl] sl0){// 最大的饼干能否满足最大胃口的孩子retsl--}gl--}return ret
}376. 摆动序列
分析 – 贪心
连续数字之间差值是正负交替的叫做摆动序列边缘情况如果只有1个值或者两个不相等的值也是摆动序列如果出现 0 则直接不是摆动序列了如果局部符合要求按照条件局部删除不符合要求的值就是贪心的做法时间复杂度 O(n)
var wiggleMaxLength function(nums) {if(nums.length2) return nums.lengthlet ret 1 // 从 1 开始是因为要求的是整个摆动序列的长度所以先初始化1然后遇到极值递增即可let preDiff 0 // 初始化第一个差值设置为0则无论真正第一个差值是多少得到的都是 0let curDiff 0for(let i 1;inums.length;i){curDiff nums[i]- nums[i-1]// 差值必须是正负数如果是 0 则跳过if(curDiff 0) continueif(preDiff * curDiff 0){retpreDiff curDiff}}return ret
};53. 最大子序和
分析 – 贪心
求的是最大和的连续子数组用 sum 缓存前面和大于 0 的子数组之和一旦小于 0 就不再累加重新置 0, 保持每一次迭代前 sum 的值都是 0这样对于每一个局部子数组它的累加值都是大于等于 0 的这样每次累加一个新值就进行最大值比较保证整体是一个最大子数组之和时间复杂度 O(n)
var maxSubArray function (nums) {let max -Infinity;let sum 0for(let i 0 ;inums.length;i){sumnums[i]max Math.max(sum,max)if(sum0){sum0}}return max
};55. 跳跃游戏
分析 – 回溯 – 超时了
直接将所有可能性写出来将对应不合适的移除时间复杂度 n∗m 其中 n 是nums 的长度m 是每一个值的大小 var canJump function (nums) {let ret false;const dfs (start) {// 只要有一个成功就直接不做其他处理了if (start nums.length || ret) return;if (startnums[start] nums.length-1) {ret true;return;}for (let i 1; i nums[start]; i) {dfs(start i); // 在当前这一个节点可以跳的步数}};dfs(0)return ret;};分析
这里只要不遇到值为 0 就可以继续往后走也就是局部贪心就是要跳过值为 0 的步骤当然如果 0 是在数组最后一位也是 ok 的我们可以判断一下是否存在一个值 nums[valIndex] 0Index - valIndex, 这样只要到达 valIndex 就可以越过 0 这个点了所以我们需要遍历所有节点找到值为 0 的节点然后再进行跳跃判断由于我们是要走到最后一个下标所以最后一个下标是不用判断的所以 i 最多走到 nums.length-1 的位置时间复杂度最小是 n
参考视频传送门 var canJump function (nums) {for(let i0;inums.length-1;i){if(nums[i] 0){// 开始寻找可以跳过当前 i 值的节点let valIndex i-1while(nums[valIndex] i -valIndex valIndex0){valIndex--}if(valIndex0) return false}}return true}45. 跳跃游戏 II
/** * 分析 -- 已知能到达位置求最少跳跃次数 * 1. 看到最少想到用 dp 做其中 dp[i] 就是到达 i 这个位置最少需要跳跃的次数, 但是控制当前状态的变量在上一个值感觉 dp 不太合适 * 2. 感觉用贪心回溯会更好一点每一次尽量远的跳如果不行再跳回来 * 3. 然后正常超时了 */
var jump function(nums) {if(nums.length 2) return 0let ret Infinityconst dfs (index,sum) {if(indexnums.length-1) {// 贪心走出来的肯定是ret Math.min(sum,ret)return }if(sumret || nums[index] 0) return // 只要出了第一个后面的全部不玩了for(let i nums[index];i0;i--){dfs(indexi,sum1)}}dfs(0,0)return ret
};/** * 分析 * 1. 考虑到跳跃范围必须覆盖一定范围求最小的目的还是从后倒推前面会更舒服一点所以考虑 dp * 2. dp[i] 表示跳跃到 i 这个位置最小的次数 * 3. 状态转移方程: dp[i] Math.min(dp[i-valid]1) 这里的 valid 是值符合 nums[j]j i 的 dp[j], 这样在 j 这个位置才能一次跳到 i * 4. base case: dp[0] 0 原地蹦跶 * 5. 时间复杂度 ${O(n^2)}$ */
var jump function(nums) {const dp new Array(nums.length)dp[0] 0 // 原地蹦跶for(let i1;inums.length;i){dp[i] Infinityfor(let j i-1;j0;j--){if(nums[j]ji){// 这样才能从 j 跳到 idp[i] Math.min(dp[i],dp[j]1)}}}return dp[nums.length-1]
}/** * 分析 -- 贪心 * 1. 每一次跳动都可以缓存最大跳跃范围这是一个范围而不是一个值所以下一跳的时候需要从这个范围内找到最最大跳跃的范围 * 2. 所以只要迭代每一个值就可以找到跑到这个值的时候最大跳跃的覆盖范围 nextIndex 的位置, 同样的我们将上一轮的最大距离设置为 curIndex * 3. 每当迭代到 curIndex, 表明上一次跳跃的覆盖范围都已经遍历完并且记录好了这个范围内的最大值 nextIndex 了这个时候更改 curIndex nextIndex * 4. 其实整个过程就是在 [curIndex,nextIndex] 中找最大范围然后不断迭代 * 5. 只需要遍历一次就能找到结果了所以时间复杂度 ${O(n)}$ */var jump function(nums) {let curIndex nextIndex 0let ret 0for(let i 0;inums.length;i){if(curIndex nums.length-1) return ret // 如果最大覆盖范围已经找到了地方那么就直接跳出遍历了nextIndex Math.max(nextIndex,nums[i]i) // 最远覆盖范围if(curIndex i) {// 如果 i 到达上一次最远覆盖位置那么 nextIndex 就是上一轮 [cur,next] 的最大距离现在需要更新一下curIndex nextIndex// 所谓覆盖就是 jump 一次ret}}
} 1306. 跳跃游戏 III 注意这里并没有用到贪心但是这是一个主题的题目所以也放在一起来学习了比较分块学习也是按组类学习而我们真正遇到问题的时候是不会给你打 tag 说是用啥方法做的所以相类似的题放一起做即便由于题目改变了没有用到相应的技术也值得放在一起学习一哈 分析 – BFS 起点改变跳跃也从单边转左右两边目的地也从尽头到跳跃到 0 的位置 – 注意以前是可以跳任意位置现在只能左右跳两个位置而不是范围跳跃基于 BFS 将数组转成类似二叉树的 bfs 搜索, 每一个节点都可以走左右两个节点 l,r, 如果符合条件就加入到队列中继续走使用的 useSet 缓存走过的节点进行剪枝
var canReach function (arr, start) {const queue [];queue.push(start);const useSet new Set();while (queue.length) {let len queue.length;while (len--) {const node queue.shift();const l node - arr[node];const r node arr[node];if (l 0 !useSet.has(l)) {if (arr[l] 0) return true;queue.push(l);useSet.add(l);}if (r arr.length !useSet.has(r)) {if (arr[r] 0) return true;queue.push(r);useSet.add(r);}}}return false;
};分析 – dfs
由于没一个点最多只能左右跳一次所以和二叉树非常相似可以用 bfs 当然也可以用到 dfs但是判断条件不能简单的用 node 是否在 [0,arr.length-1], 因为在左右跳的过程中会有重复的点如果不讲重复点剪掉不但重复计算而且会导致死循环所以用 set 缓存已经走的 node一旦再进入就移除这样就能完整遍历可以跳到的位置并最终跳出 dfs 遍历得到最终结果时间复杂度 O(n), 空间复杂度 O(n)
var canReach function (arr, start) {let ret false;const useSet new Set(); // 剪枝用的const dfs (node) {if (useSet.has(node) || ret true) return;if (arr[node] 0) {ret true;return;}useSet.add(node);if (node - arr[node] 0) {dfs(node - arr[node]);}if (node - arr[node] arr.length) {dfs(node arr[node]);}};dfs(start);return ret;
};1005. K 次取反后最大化的数组和
分析
我们要转换肯定是要将负数转成正数这样能达到最大那么情况有两种 k 充足将所有负数转换成正数k 不足第一次贪心如果 k 不充足的时候要先将最大的非负数这种情况就需要排序了所以一开始先排个序吧 – 优先给最大的负数进行转换第二次贪心如果将所有非负数转成正数后k 还有那么这个时候只需要处理最小的那个值就好了我们在第一次贪心的时候是排好序去处理非负数的所以当处理完非负数之后index 所在的位置要不就是数组之外要不就是原始数组第一个非负数这个时候 index-1 就是转换后的最小非负数他们之间的对比可以找出当前数组的最小值需要注意两种特殊情况如果入参 nums 全是非负数则 index 不会移动那么 nums[index-1] 就取不到同理如果 nums 全是负数则 index 在数组外了所以要把两种情况考虑进去最后只需要对 min 进行反复转换如果 k 是偶数那么就直接不转了如果是奇数那么就减去 min*2时间复杂度 O(nlogn) var largestSumAfterKNegations function(nums, k) {nums.sort((a,b)a-b)let index 0while(k nums[index] 0){// 如果 k 还存在且当前值还是负数的时候就转换nums[index] - nums[index]k--index}// 转换后 index 所在的位置就是最开始最小值非负数了但是它有可能比转换后的最小正数小所以要对比一下// 但是如果 index 是第一个值也就是一开始全都是非负数的时候这个时候就没有 index-1 了// 同理如果全是负数那么 index 就不存在了let min index 0 ? nums[index] : index nums.length?nums[index-1] :Math.min( nums[index], nums[index-1])// 先将所有负数都转成正数 -- 如果 k 还存在那么就处理 nums[index] 就好了let sum nums.reduce((pre,cur)precur,0)if(k % 2) sum - min*2return sum
};122. 买卖股票的最佳时机 II
分析 – 贪心
多次交易只有计算出每日的收益然后将每日收益为正的收集起来就是最大收益由于本题是多次交易不需要手续费和间隔时间所以如果有连续正收益的时候相当于连续持有如果间隔收益那就是在负收益第一天先卖出后在负收益的后一天买进一样可以得到断开的正收益所以只要将所有正收益手机起来就好这样局部收益就可以扩展成全局收益然后就可以得到最终最大的收益了
var maxProfit function(prices) {let ret 0for(let i 1;iprices.length;i){const temp prices[i]-prices[i-1]if(temp0){rettemp}}return ret
}134. 加油站
分析
我们考虑到每次加完油就要跑路有一些油站油充分那么跑完一段之后会有的剩而有些油站油少还得补贴一点至于具体情况如何我们需要计算一下所以用 leaves 来表示跑 [i,i-1] 的净油量使用贪心的思维起始车是没油的所以必须是 leaves[i]0 的时候才有可能是起始位置然后开始往后面走每次判断一下是否足够下一段路的行走如果不行果断放弃上一次的起始点找下一个起始点如果在第一次遍历过程中没找到一个点 ret 可以走完 [ret,len-1] 的路程那么代表所有起点都失效了直接返回 -1如果存在那么对于循环的车道还得再走一遍 [0,ret-1] 如果也成功了就返回 ret在整个过程中如果累计油量保持为非负那么就不要更改起始位置 ret, 因为你改变了位置情况不会更好只会更坏这也是贪心的本质每一次都做最好的选择那么在中间的时候要不放弃要不就不要改了时间复杂度 O(n), 空间复杂度 O(n)
var canCompleteCircuit function (gas, cost) {const leaves gas.map((g, i) g - cost[i]); // 每一个站台加油后跑路之后剩余值的数组正数就是有剩余负数就是不足需要在某些地方补充let ret -1;let sum 0; // 缓存当前油量for (let i 0; i leaves.length; i) {if (leaves[i] 0) {if (ret -1) {ret i;}sum leaves[i];continue;}if (sum leaves[i] 0) {// 之前那个起点已经失败了ret -1; //恢复到 -1sum 0;} else {sum leaves[i]; // 继续走着}}if (ret -1) return -1; // 如果走完这一段sum 还存在证明在 [ret,leaves.length-1] 是合格的那么继续走一下 [0,ret]for (let i 0; i ret; i) {if (leaves[i] 0) {sum leaves[i];continue;}if (sum leaves[i] 0) {// 在这个循环中一旦出现不合适的就不再走下去了因为已经走过一次了return -1;} else {sum leaves[i]; // 继续走着}}return ret
};分析
基于上面那种贪心其实有更好的判定方式就是只要 gasSum costSum , 那么必然存在一个起点能够让车跑完一圈因为那些差值很大的区间都是最后积攒大量的剩余油才会去跑的上面的第二次 [0,ret] 可以不用跑只要判断出有一个值可以走完 [ret,len-1], 同时 gasSum costSum那么这个 ret 的点就是起点了
var canCompleteCircuit function (gas, cost) {const leaves gas.map((g, i) g - cost[i]); // 每一个站台加油后跑路之后剩余值的数组正数就是有剩余负数就是不足需要在某些地方补充let ret -1;let sum 0; // 缓存当前油量let gasSum 0let costSum 0for (let i 0; i leaves.length; i) {costSumcost[i]gasSumgas[i]if (leaves[i] 0) {if (ret -1) {ret i;}sum leaves[i];continue;}if (sum leaves[i] 0) {// 之前那个起点已经失败了ret -1; //恢复到 -1sum 0;} else {sum leaves[i]; // 继续走着}}if (gasSumcostSum) return -1; return ret
};135. 分发糖果
分析 – 题目描述有问题
第二个条件应该是只要你比临近位置的评分大那么你就必然比临近的人分得的糖果多先初始所有candies 的值为 1然后分两部分处理先和左侧分数值比较只要比左侧大那么 candies[i] 然后再从右往左遍历只要比左侧的分数高那么就进行比较取最大值 Math.max(candies[i],cadies[i1]1)最后得到的数组 candies 就能保证分数更高小孩肯定比临近分数更低的小孩的 candies 更多时间复杂度 O(n)这里最少的发糖就用到了贪心的思想尽可能少的给糖先左边局部最少给糖然后右边局部最少给糖然后就可以影响最终给糖的数量
var candy function (ratings) {const len ratings.length;const candies new Array(len).fill(1); // 发糖果的数组for (let i 1; i len; i) {if (ratings[i] ratings[i - 1]) {candies[i] candies[i - 1] 1;}}for (let i len - 2; i 0; i--) {if (ratings[i] ratings[i 1]) {candies[i] Math.max(candies[i 1] 1,candies[i]); // 从右边数的时候就要判断哪边更大了}}return candies.reduce((pre, cur) pre cur, 0);
};860. 柠檬水找零
分析
如果能思考到局部贪心基本就是一道遍历题由于 5 元属于更小粒度的单位在数量足够的时候可以组合成 10 元 所以我们在给 20 元找零的时候局部贪心的保存 5 元这样能保证出力后续的时候更可能完成任务所以剩下的就是将情况排列出来了时间复杂度 O(n)
var lemonadeChange function(bills) {let fives 0let tens 0for(let i 0;ibills.length;i){const b bills[i] if(b 5){fives}if(b 10 ) {if(fives0){fives--tens}else {return false}}if(b 20){// 现在用贪心先尽可能的用 10 块去找零因为 5 块是粒度更小的零钱它通用性更强所以尽可能贪心的保存 5 块if(tens0 fives0){tens--fives--}else if (tens 0 fives3){fives -3}else{return false}}}return true};406. 根据身高重建队列
分析
先分类将身高一样的先缓存在一起然后根据 key 从高到低开始贪心的排列因为每一次我们都取最高且前面人数最少的 item 这个时候队列的两个条件已经一起限制好只需要按照 item[i] 插入到 ret 上就足够了 – 后续的插入是不会影响到当前插入的因为后续的值肯定会贴合现有排好的 ret我们可以先取出身高更高的值因为这个时候排在它前面的就只有它自己和已经排好的数组 – 这就是局部贪心这个时候在相同身高的数组里还要根据前面的人数进行一次排序保证少的在前面 – 这样当前 item 插入到最终 ret 的时候它就可以根据 item[1] 直接插入到 ret 对应的位置了时间复杂度 O(n),空间复杂度 O(n)
var reconstructQueue function(people) {const map new Map(); // 先将身高一眼给的缓存起来for(let i 0;ipeople.length;i){const key people[i][0]map.set(key,map.get(key)?[...map.get(key),people[i]]:[people[i]])}const arr [...map.keys()].sort((a,b)b-a) // 从大到小const ret []for(let i 0;iarr.length;i){const tempArr map.get(arr[i]) // 取出数组tempArr.sort((a,b)a[1]-b[1]) // 身高相同的数组要根据在他们前面的人的数量进行排序这样才能保证前面人少的在前面// 这个时候需要只需要按找数组的第二个值插入到最终数组即可for(let temp of tempArr){ret.splice(temp[1],0,temp) // 在 temp[1] 的位置插入 temp}}return ret
};const ret reconstructQueue([[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]);
console.log(ret)452. 用最少数量的箭引爆气球
分析 – 失败
首先要审题并理解题目虽然说的是二维空间的气球但是实际排列的时候在一个坐标 x 上可能会存在气球的重叠所以当箭从 x 射进去就可以一次打破 n1 个气球所以题目就转换成 – 每次找到重叠最多的位置进行射击当气球射完需要多少箭-- 也就是找到交集的数量这里可以和并查集进行对比并查集遇到交集后会扩展集合为并集而这里是收缩到交集所以刚好是相反的概念这里用到的贪心思想就是一旦有交集我们就把两个气球收缩为一个更小的气球局部贪心的将有交集的气球压缩到一个更小的气球中这样最后剩下的气球就是相互隔离的达到全局的贪心 – 尽可能少的射击时间复杂度 O(n),空间复杂度 O(n)这种写法失败的原因在于随机找出来一个区间值这个区间值的收缩是随机的所以就会出现一个很小的区间 A 将本来可以容纳更多气球的某一个区间 B 收缩的很小区间 C使得最后的结果不够贪心而最优的情况是将区间 A 放在另外的一个区间 A1 上然后让 B 区间容纳更多的气球 B1,B2所以需要将无序的气球按排好序这样按顺序在局部范围内最贪心的重叠气球就可以保证在局部范围内尽可能小的缩小取值区间容纳更多的气球 – 具体看分析2 var findMinArrowShots function(points) {const len points.length let ret [] // 缓存没有交集的数组for(let i 0;ilen;i){const pp points[i]let isMerge falsefor(let i 0;iret.length;i){const rr ret[i]// 如果起始位置都超过了终止位置那么就没有交集了if(pp[0]rr[1] || pp[1] rr [0]) continue// 否则就是有交集了那么只要保存交集就好因为射中交集的时候一次性就完成所有的气球爆炸ret[i] pp[0]rr[0]?[rr[0],Math.min(pp[1],rr[1])]:[pp[0],Math.min(pp[1],rr[1])]isMerge true // 如果合并了break}if(!isMerge){ret.push(pp)}}return ret.length
};分析2
基于上面那种两边同时限制会出现分组限制更多的情况我们限制其中一边进行排序尽可能使用其中一边作为限制条件在这里我们根据 left 作为排序依据进行排序排序之后我们只需要判断新的气球的最左边是否离开了当前气球的最右边就可以判断是否是同一组如果属于同一组那么需要现在这一组最 right 的位置这个位置也是射击的最右位置保证往这个点射进去这一组的气球全爆所以需要找的是交集最小值时间复杂度 O(nlogn), 空间复杂度 O(1)这里用到的贪心思想就是尽可能局部最多重叠的气球而上题也是因为没法保证会让最多重叠气球放在一起
var findMinArrowShots function(points) {const len points.length points.sort((a,b)a[0]-b[0])let cur -Infinity;let ret 0for(let i 0 ;ilen;i){const pp points[i]if(pp[0]cur) {// 超出范围了retcur pp[1] // 修改}else{cur Math.min(cur,pp[1])}}return ret
}findMinArrowShots([[10,16],[2,8],[1,6],[7,12]])
findMinArrowShots([[1,2]])
findMinArrowShots([[3,9],[7,12],[3,8],[6,8],[9,10],[2,9],[0,9],[3,9],[0,6],[2,8]])分析3 – 右侧节点排序
使用左侧节点排序在重合区域要保证 right 节点最小这个才能保证下一个值可以落到集合的交汇处但是使用右侧排序的时候本身 right 节点就比 left 节点要大所以右侧排序后其他的节点对于当前节点 [l1,r1] 而言只要 l2 r1, 那么必然是存在于区间内的而且只要存在于区间内那么 right 值都不需要变因为第一个取值就是最小了所以有下面的写法这种排序更直观一点画图会更好看清楚
var findMinArrowShots function(points) {const len points.length points.sort((a,b)a[1]-b[1]) // 右侧排序let right -Infinity;let ret 0for(let i 0 ;ilen;i){const pp points[i]if(pp[0]right) {// 超出范围了retright pp[1] // 修改}}return ret
}435. 无重叠区间
分析
和 452. 用最少数量的箭引爆气球 类似只是那边尽可能集合在一起这里是要分开所以这里以区间的右侧值做排序这样 的好处就是一旦某个值的 left 大于当前的 right 值那么就出现完全隔离的区间了最后的答案就是长度减去可以完全隔离的区间
var eraseOverlapIntervals function(intervals) {const length intervals.lengthintervals.sort((a,b) a[1]-b[1]) // 按右侧大小排列好let right -Infinitylet ret 0 // 集合数量for(let i 0;ilength;i){const ii intervals[i]if(ii[0]right) {ret right ii[1]}}return length-ret
}763. 划分字母区间
分析
题目限制条件1相同的字符只能存在于同一个字符串片段限制条件2尽可能多的切分字符串片段所以我们先用 map 缓存每个字符最后出现的下标值那么当我的字符串中存在这个字符那么最少要走到它的尽头下标相当于开启了一个不定长窗口然后在这个窗口遍历过程判断窗口的最长值是否需要扩展当窗口遍历完成后记录窗口的长度然后执行下一个窗口时间复杂度 O(n),空间复杂度 O(n)这里没看出局部贪心导向全局贪心可能是保证所有相同字符都要在一起算是局部贪心吧
var partitionLabels function(s) {const map new Map() // 记录字符和最后一个字符对应的下标for(let i 0;is.length;i){const ss s[i]map.set(ss,i)}console.log(map)let ret []let start 0// 现在尽可能短的获取片段while(starts.length){let temp start // 起始值let end map.get(s[start]) //第一个字母的最后一个下标while(startend){if(map.get(s[start])end){end map.get(s[start]) // 将 end 变长}start}// 抛出一轮了ret.push(start-temp)}return ret
};console.log(partitionLabels(ababcbacadefegdehijhklij))56. 合并区间
分析
这里是合并所有重叠的区间不是两两重叠的区间所以还是得排个序这样只需哟啊判断一遍即可不然直接写个 ret原来不连接的区间可能加了一个新的 item 就连接起来了更麻烦left 节点排序是比较合适的,因为这里需要在某个节点隔断之后往后的节点不会再影响到 ret 数组里的区间如果用 right 节点排序就会出现 [k,r],[k-1,r1] 的情况那么已经放入到单独区域的区间还要拿出来用最后遍历一遍结束时间复杂度 O(n)
var merge function (intervals) {intervals.sort((a, b) a[0] - b[0]);let ret [];let cur intervals[0];for (let i 1; i intervals.length; i) {const temp intervals[i];if (temp[0] cur[1]) {// 当取出的空间的起始值已经比当前值要大的时候那么剩下的其他值也会完全和当前的 cur 隔离开所以将当前 cur 推入 ret 中ret.push(cur);cur temp; // 替换 cur}if (cur[1] temp[1]) {cur[1] temp[1];}}return [...ret, cur];
};console.log(merge([[1,4],[2,3]])
);738. 单调递增的数字
分析
审题这里是要找一个最大的数 numnum 的位需要单增,也就是 1234,这样的同时 num n这题数字转字符串转数组将每个值转成单个数值来计算了这样更方便点这里最后要求的是递增的数组所以我们可以根据 i-1 和 i 之间的值进行替换当 arr[i-1]arr[i] 的时候 arr[i-1] 减一设置锚点 flag从后往前遍历完之后找到左侧第一个需要设置为9的点然后把后面的值全设置为9达到最大值
var monotoneIncreasingDigits function (n) {if(n10) return n //如果是个位数直接返回 nconst str String(n)const len str.lengthconst arr str.split()let flag Infinity // 标记最后一个设置为 9 的下标从这个下标之后的值都得换成 9for(let i len-1;i0;i--){if(arr[i-1]arr[i]){// 如果前一位大于后一位那么为了当增需要将当前位减一后一位换成 9flag iarr[i-1] arr[i-1] -1 }}for (let i flag; i len; i) {arr[i] 9}return Number(arr.join())
};968. 监控二叉树
分析
这里要求尽可能少的安装摄像头但是改装的还是得装上需要全覆盖那么最好的办法肯定是自底向上的装因为层数越深节点越多所以自顶向上能减少摄像头的安装那么现在要尽可能让摄像头覆盖到每一个节点这里节点 val 作为状态值0就是没有覆盖1就是安装摄像头覆盖2是没有安装但是在覆盖范围内我们知道要尽可能的在有状态为 0 的叶子节点的 父节点 上去安装这样就可以一次性覆盖到叶子节点同时由于是自底向上的遍历那么不需要考虑更底层的覆盖只需要考虑当前节点和它的叶子节点即可所以我们用后续遍历的方式进行后续遍历当我们到达叶子节点时返回当我们遇到叶子节点都为不为 0也就是都在覆盖范围内的时候如果存在叶子节点状态为 1即当前节点也属于覆盖范围需要更改状态为 2 然后 return 回去 – 这里用到了贪心也就是必须要有状态为 0 的叶子节点才会去安装摄像头保证摄像头的覆盖范围进而保证数量最小如果存在叶子节点的状态为 0那么就必须在当前节点设置摄像头也就将状态 root.val 设置为 1当我们自低向上遍历到了根节点然后中断遍历的时候还需要考虑最后 root 节点因为我们之前的逻辑是根据叶子节点状态来判断当前节点的更改的所以 root 节点很可能会因为叶子节点是覆盖值而没有进行任何的设置这个时候 root 就可能是 0所以如果 root 是 0 的话还得再安一个摄像头我们最终的结果就是要保证整棵树的节点状态都不为 0即可时间复杂度 O(n)
var minCameraCover function (root) {if (!root) return 0;let ret 0; // 装了多少摄像头const dfs (root) {if (!root.left !root.right) return; // 到达叶子节点直接返回不加摄像头if (root.left) dfs(root.left);if (root.right) dfs(root.right);// 后序遍历遇到父子节点存在摄像头那就不需要加了if ((root.left root.left.val ! 0 || !root.left) (root.right root.right.val ! 0 || !root.right)){if((root.left root.left.val 1) || (root.right root.right.val 1)){// 存在摄像头才能波及root.val 2 // 波及到的}return }// 必须要保证存在的子节点都已经是 1 的时候才可以放心继续往上走root.val 1; //如果大家伙都没有装那就我来装吧ret;};dfs(root);return root.val 0 ? ret1 : ret
};
