学习算法的时候,总会有一些让人生畏的名词,比方动态规划
,贪心算法
等,听着就很难;而这一 part 就是为了攻破之前一直没有系统学习的 贪心算法
;
有一说一,做了这些贪心题,其实并没觉得发现了什么套路新大陆等,因为贪心有的时候很巧妙,而且想到就是想到了,没想到可能就不用贪心去做了,所以这属于做完只是刷了存在感的 part;
唯一的收获就是减轻了对贪心的恐惧,明白它也就是一种 局部贪心导致全局贪心得到最优解
的一种思路方法,所以以后遇到了,也就能心平气和的去学习使用它了;
下一 part 去做一下比较难的并查集
分析 -- 贪心
var findContentChildren = function (g, s) {
g.sort((a,b) => a-b)
s.sort((a,b) => a-b)
let ret = 0
let sl = s.length-1;
let gl = g.length-1
while(gl>=0){
// 人没了,饼干可以还存在
if(s[sl]>=g[gl] && sl>=0){
// 最大的饼干能否满足最大胃口的孩子
ret++
sl--
}
gl--
}
return ret
}
分析 -- 贪心
var wiggleMaxLength = function(nums) {
if(nums.length<2) return nums.length
let ret = 1 // 从 1 开始是因为要求的是整个摆动序列的长度,所以先初始化1,然后遇到极值递增即可
let preDiff = 0 // 初始化第一个差值;设置为0,则无论真正第一个差值是多少,得到的都是 0
let curDiff = 0
for(let i = 1;i<nums.length;i++){
curDiff = nums[i]- nums[i-1]
// 差值必须是正负数,如果是 0 则跳过
if(curDiff === 0) continue
if(preDiff * curDiff <= 0){
ret++
preDiff = curDiff
}
}
return ret
};
分析 -- 贪心
连续子数组
var maxSubArray = function (nums) {
let max = -Infinity;
let sum = 0
for(let i = 0 ;i<nums.length;i++){
sum+=nums[i]
max = Math.max(sum,max)
if(sum<=0){
sum=0
}
}
return max
};
分析 -- 回溯 -- 超时了
var canJump = function (nums) {
let ret = false;
const dfs = (start) => {
// 只要有一个成功,就直接不做其他处理了
if (start >= nums.length || ret) return;
if (start+nums[start] >= nums.length-1) {
ret = true;
return;
}
for (let i = 1; i <= nums[start]; i++) {
dfs(start + i); // 在当前这一个节点,可以跳的步数
}
};
dfs(0)
return ret;
};
分析
var canJump = function (nums) {
for(let i=0;i<nums.length-1;i++){
if(nums[i] === 0){
// 开始寻找可以跳过当前 i 值的节点
let valIndex = i-1
while(nums[valIndex]<= i -valIndex && valIndex>=0){
valIndex--
}
if(valIndex<0) return false
}
}
return true
}
/** * @分析 -- 已知能到达位置,求最少跳跃次数 * 1. 看到最少,想到用 dp 做;其中 dp[i] 就是到达 i 这个位置最少需要跳跃的次数, 但是控制当前状态的变量在上一个值,感觉 dp 不太合适 * 2. 感觉用贪心+回溯会更好一点,每一次尽量远的跳,如果不行再跳回来 * 3. 然后正常超时了 */
var jump = function(nums) {
if(nums.length < 2) return 0
let ret = Infinity
const dfs = (index,sum) => {
if(index>=nums.length-1) {
// 贪心走出来的,肯定是
ret = Math.min(sum,ret)
return
}
if(sum>=ret || nums[index] === 0) return // 只要出了第一个,后面的全部不玩了
for(let i = nums[index];i>0;i--){
dfs(index+i,sum+1)
}
}
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 i=1;i<nums.length;i++){
dp[i] = Infinity
for(let j = i-1;j>=0;j--){
if(nums[j]+j>=i){
// 这样才能从 j 跳到 i
dp[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 = 0
let ret = 0
for(let i =0;i<nums.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++
}
}
}
注意,这里并没有用到贪心,但是这是一个主题的题目,所以也放在一起来学习了;比较分块学习也是按组类学习,而我们真正遇到问题的时候,是不会给你打 tag 说是用啥方法做的,所以相类似的题放一起做,即便由于题目改变了,没有用到相应的技术,也值得放在一起学习一哈; 分析 -- BFS
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
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;
};
分析
var largestSumAfterKNegations = function(nums, k) {
nums.sort((a,b)=>a-b)
let index = 0
while(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)=>pre+cur,0)
if(k % 2) sum -= min*2
return sum
};
分析 -- 贪心
var maxProfit = function(prices) {
let ret = 0
for(let i = 1;i<prices.length;i++){
const temp = prices[i]-prices[i-1]
if(temp>0){
ret+=temp
}
}
return ret
}
分析
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; //恢复到 -1
sum = 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
};
分析
var canCompleteCircuit = function (gas, cost) {
const leaves = gas.map((g, i) => g - cost[i]); // 每一个站台加油后跑路之后,剩余值的数组,正数就是有剩余,负数就是不足,需要在某些地方补充;
let ret = -1;
let sum = 0; // 缓存当前油量
let gasSum = 0
let costSum = 0
for (let i = 0; i < leaves.length; i++) {
costSum+=cost[i]
gasSum+=gas[i]
if (leaves[i] >= 0) {
if (ret === -1) {
ret = i;
}
sum += leaves[i];
continue;
}
if (sum + leaves[i] < 0) {
// 之前那个起点已经失败了
ret = -1; //恢复到 -1
sum = 0;
} else {
sum += leaves[i]; // 继续走着
}
}
if (gasSum<costSum) return -1;
return ret
};
分析 -- 题目描述有问题
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);
};
分析
var lemonadeChange = function(bills) {
let fives = 0
let tens = 0
for(let i =0;i<bills.length;i++){
const b = bills[i]
if(b === 5){
fives++
}
if(b === 10 ) {
if(fives>0){
fives--
tens++
}else {
return false
}
}
if(b === 20){
// 现在用贪心,先尽可能的用 10 块去找零,因为 5 块是粒度更小的零钱,它通用性更强,所以尽可能贪心的保存 5 块
if(tens>0 && fives>0){
tens--
fives--
}else if (tens === 0 && fives>=3){
fives -=3
}else{
return false
}
}
}
return true
};
分析
最高且前面人数最少
的 item, 这个时候队列的两个条件已经一起限制好,只需要按照 itemi 插入到 ret 上就足够了 -- 后续的插入是不会影响到当前插入的,因为后续的值肯定会贴合现有排好的 ret;var reconstructQueue = function(people) {
const map = new Map(); // 先将身高一眼给的缓存起来
for(let i = 0;i<people.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;i<arr.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)
分析 -- 失败
重叠最多
的位置进行射击,当气球射完需要多少箭;-- 也就是找到交集的数量分析2
var findMinArrowShots = function(points) {
const len = points.length
let ret = [] // 缓存没有交集的数组
for(let i =0;i<len;i++){
const pp = points[i]
let isMerge = false
for(let i = 0;i<ret.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
var findMinArrowShots = function(points) {
const len = points.length
points.sort((a,b)=>a[0]-b[0])
let cur = -Infinity;
let ret = 0
for(let i = 0 ;i<len;i++){
const pp = points[i]
if(pp[0]>cur) {
// 超出范围了
ret++
cur = 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 -- 右侧节点排序
var findMinArrowShots = function(points) {
const len = points.length
points.sort((a,b)=>a[1]-b[1]) // 右侧排序
let right = -Infinity;
let ret = 0
for(let i = 0 ;i<len;i++){
const pp = points[i]
if(pp[0]>right) {
// 超出范围了
ret++
right = pp[1] // 修改
}
}
return ret
}
分析
var eraseOverlapIntervals = function(intervals) {
const length = intervals.length
intervals.sort((a,b) => a[1]-b[1]) // 按右侧大小排列好
let right = -Infinity
let ret = 0 // 集合数量
for(let i = 0;i<length;i++){
const ii = intervals[i]
if(ii[0]>=right) {
ret++
right = ii[1]
}
}
return length-ret
}
分析
var partitionLabels = function(s) {
const map = new Map() // 记录字符和最后一个字符对应的下标
for(let i = 0;i<s.length;i++){
const ss = s[i]
map.set(ss,i)
}
console.log(map)
let ret = []
let start = 0
// 现在尽可能短的获取片段
while(start<s.length){
let temp = start // 起始值
let end = map.get(s[start]) //第一个字母的最后一个下标
while(start<=end){
if(map.get(s[start])>end){
end = map.get(s[start]) // 将 end 变长
}
start++
}
// 抛出一轮了
ret.push(start-temp)
}
return ret
};
console.log(partitionLabels('ababcbacadefegdehijhklij'))
分析
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]]
)
);
分析
var monotoneIncreasingDigits = function (n) {
if(n<10) return n //如果是个位数,直接返回 n
const str = String(n)
const len = str.length
const arr = str.split('')
let flag = Infinity // 标记最后一个设置为 9 的下标,从这个下标之后的值,都得换成 9
for(let i =len-1;i>=0;i--){
if(arr[i-1]>arr[i]){
// 如果前一位大于后一位,那么为了当增,需要将当前位减一,后一位换成 9
flag = i
arr[i-1] = arr[i-1] -1
}
}
for (let i = flag; i < len; i++) {
arr[i] = 9
}
return Number(arr.join(''))
};
分析
父节点
上去安装,这样就可以一次性覆盖到叶子节点,同时由于是自底向上的遍历,那么不需要考虑更底层的覆盖,只需要考虑当前节点和它的叶子节点即可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 ? ret+1 : ret
};
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。