贪心算法

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

解题步骤：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

455. 分发饼干

首先需要将小孩数组和饼干数组排序，使用两个指针从后往前遍历，统计满足的小孩数量。

/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
var findContentChildren = function(g, s) {
    g.sort((a,b) => a -b)
    s.sort((a,b) => a -b)
    // console.log('g 小孩：', g)
    // console.log('s 饼干：', s)
    let j = s.length - 1
    let i = g.length - 1
    let count = 0
    while(i >= 0 && j >= 0){
        if(s[j] >= g[i]){
            i --
            j --
            count ++
        }else{
            i --
        }
    }
    return count
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

376. 摆动序列

需要统计数组的峰值数量, 相当于是删除单一坡度上的节点，然后统计长度

先处理长度小于2和等于2的特殊情况

result 记录长度，初始值为1，相当于默认最右边为峰值

pre 记录前一个坡度，初始值是0，cur记录当前坡度

/**
 * @param {number[]} nums
 * @return {number}
 */
var wiggleMaxLength = function(nums) {
    if(nums.length < 2) return nums.length
    else if(nums.length == 2 && nums[0] != nums[1]) return 2
    else if(nums.length == 2) return 1
    let result = 1
    let pre = 0
    let cur
    for(let i = 1; i < nums.length; i++){
        cur = nums[i] - nums[i-1]
        if(!cur) continue
        if((pre <= 0 && cur > 0) || (pre >= 0 && cur < 0)){
            result ++
            pre = cur
        }
    }
    return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

53. 最大子数组和

count用来计数，初始化为0；max用来记录区间最大值，初始化为题目给定的最小值 -10000

累加当前值，更新max；如果当前count小于0，则将count清零，从下一位开始继续累加

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    if(nums.length === 1) return nums[0]
    let count = 0
    let max = -10000
    for(let i = 0; i < nums.length; i++){
        count += nums[i]
        max = Math.max(count, max)
        // console.log('max, count',max, count)
        if(count < 0){
            count = 0
        }
    }
    return max
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

122. 买卖股票的最佳时机 II

先计算出两天的利润差，选取正的加在一起即可

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if(prices.length <= 1) return 0
    let count = 0
    for(let i = 1; i < prices.length; i++){
        if(prices[i] - prices[i-1] > 0)
            count += prices[i] - prices[i-1]
    }
    return count
};
1
2
3
4
5
6
7
8
9
10
11
12
13

55. 跳跃游戏

只需要判断最大的覆盖距离能否刚好到达或者超过终点

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    if(nums.length <= 1) return true
    let cover = 0
    for(let i = 0; i <= cover; i++){
        cover = Math.max(i + nums[i], cover)
        if(cover >= nums.length - 1) return true
    }
    return false
};
1
2
3
4
5
6
7
8
9
10
11
12
13

45. 跳跃游戏 II

ans 记录需要跳跃的步数，初始值为9

cur记录当前可以到达的最大范围，初始值为0

next记录下一步可以到达的最大范围，初始值为0

如果当前位置刚好在当前最大范围的边界并且没有到达终点，则ans+1，更新当前最大范围，如果此时的最大范围包含终点，结束；

如果当前位置刚好在当前最大范围的边界并且到达终点，也结束。

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    let cur = 0
    let next = 0
    let ans = 0
    for(let i = 0; i < nums.length; i++){
        next = Math.max(next, i + nums[i])
        if(i == cur){
            if(i != nums.length - 1){
                ans ++
                cur = next
                if(cur >= nums.length - 1) return ans
            }else return ans
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1005. K 次取反后最大化的数组和

先将数组从小到大排序，使用<= k次将数组的尽可能多的负数转为正数，每次k-1，顺便求和

如果遍历结束之后，k为0，或者为偶数，则直接将求和结果返回

如果k为奇数，需要找出转换后数组的最小元素，返回 求和 - 2*最小元素

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var largestSumAfterKNegations = function(nums, k) {
    nums.sort((a,b) => a - b)
    console.log(nums)
    let sum = 0
    for(let i = 0 ; i < nums.length ; i++){
        if(k && nums[i] < 0){
            nums[i] = -nums[i]
            k --
        }
        sum += nums[i]
    }
    if(k == 0 || k % 2 == 0 ) return sum
    else return sum - 2*Math.min(...nums)
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

134. 加油站

• 如果总的gas小于cost，则一定不能跑完全程，返回 -1

• 从头开始累加gas[i]-cost[i]，如果遇到累加和小于0，则前面累加的节点都不能作为起点，更新起点为下一个节点，继续累加

/**
 * @param {number[]} gas
 * @param {number[]} cost
 * @return {number}
 */
var canCompleteCircuit = function(gas, cost) {
    let start = 0
    let total = 0
    let cur = 0
    for(let i = 0; i < gas.length; i++){
        total += gas[i] - cost[i]
        cur += gas[i] - cost[i]
        if(cur < 0){
            start = i + 1
            cur = 0
        }
    }
    if(total < 0) return -1
    return start
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

135. 分发糖果

先从前往后遍历，处理右边大于左边的情况，如果ratings[i+1] > ratingd[i]，则ans[i+1] = ans[i] + 1，否则ans[i+1] =1

然后再从后往前遍历，处理左边大于右边的情况，如果ratings[i-1] > ratings[i],则此时ratings[i-1]对应的ans应该为max(ans[i-1],ratings[i] + 1 )

/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function(ratings) {
    let ans = new Array(ratings.length)
    ans[0] = 1
    for(let i = 1; i < ans.length; i++){
        if(ratings[i] > ratings[i-1]){
            ans[i] = ans[i - 1] + 1
        }else ans[i] = 1
    }
    let sum = 0
    for(let i = ans.length - 1; i > 0 ; i--){
        if(ratings[i-1] > ratings[i]){
            ans[i-1] = Math.max(ans[i-1], ans[i] + 1)
        }
        sum += ans[i]
    }
    return sum + ans[0]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

860. 柠檬水找零

m数组记录5,10元的个数

当遇到5元,m[0] ++

当遇到10元，如果此时m[0] = 0，没有5元可以找零，返回false；否则m[0] --,m[1] ++

当遇到20元，优先考虑找零10+5，不符合再去考虑 5*3，两个都不满足则返回false

都满足则返回true

/**
 * @param {number[]} bills
 * @return {boolean}
 */
var lemonadeChange = function(bills) {
    let m = [0,0]
    for(let i = 0; i < bills.length; i++){
        if(bills[i] == 5){
            m[0] ++
        }else if(bills[i] == 10){
            if(!m[0]) return false
            else{
                m[1] ++
                m[0] --
            }
        }else if(bills[i] == 20){
            if(m[1] >= 1 && m[0] >= 1){
                m[1] --
                m[0] --
            }else if(m[0] >= 3){
                m[0] -= 3
            }else return false
        }
    }
    return true
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

406. 根据身高重建队列

有两个维度需要考虑：h和k，类似于分糖果问题，先确定身高h，按照身高从高到低排序，然后再根据k去插入调整。

/**
 * @param {number[][]} people
 * @return {number[][]}
 */
var reconstructQueue = function(people) {
    people.sort((a,b) => {
        if(a[0] == b[0]){
            return a[1] - b[1]
        }else{
            return b[0] - a[0]
        }
    })
    let ans = []
    for(let i = 0; i < people.length; i++){
        ans.splice(people[i][1],0,people[i])
    }
    return ans
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

452. 用最少数量的箭引爆气球

pre 记录前一个区间，或者是合并后的前一个区间，初始化points的第一个元素

cnt初始化为去剪个总个数，遍历points，当发现pre和当前points[i]有重叠的话，cnt - 1，因为此时的气球可以和上一个使用同一个箭，然后还需要将pre更新为两个区间的重叠部分；如果pre和points[i]没有重叠，则将pre更新为当前区间

/**
 * @param {number[][]} points
 * @return {number}
 */
var findMinArrowShots = function(points) {
    points.sort((a,b)=>{
        if(a[0] !== b[0]) return a[0] - b[0]
        else return a[1] - b[1]
    })
    let cnt = points.length
    let pre = points[0]
    for(let i = 1; i < points.length; i++){
        if(points[i][0] <= pre[1]){
            cnt --
            pre = [Math.max(pre[0], points[i][0]),Math.min(pre[1], points[i][1])]
        }else{
            pre = points[i]
        }
    }
    return cnt
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

435. 无重叠区间

按照右边界排序，从左向右记录交叉区间的个数。就是需要移除的区间个数了。

pre 用来记录前一个不需要被移出的区间，初始化为intervals[0]，遍历intervals，当前区间与pre有重叠，计数器+1，表明当前区间需要被移除，如果不重叠，则更新pre。

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function(intervals) {
    intervals.sort((a,b) => a[1] - b[1])
    let pre = intervals[0]
    let cnt = 0
    for(let i = 1; i < intervals.length; i++){
        if(intervals[i][0] < pre[1]){
            cnt ++
        }else{
            pre = intervals[i]
        }
    }
    return cnt
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

763. 划分字母区间

• 遍历字符串，记录字符的最远下标
• 遍历字符，更新字符对应的最远出现下标，如果之前字符最大下标和当前下标相等，则为分割点

/**
 * @param {string} s
 * @return {number[]}
 */
var partitionLabels = function(s) {
    let obj = {}
    for(let i = 0; i < s.length; i++){
        obj[s[i]] = i
    }
    let max = 0
    let index = 0
    let ans = []
    for(let i = 0; i < s.length; i++){
        max = Math.max(max, obj[s[i]])
        if(i == max){
            ans.push(s.substring(index, i + 1).length)
            index = i + 1
        }
    }
    return ans
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

56. 合并区间

• ans 记录最终合并的区间数组，初始化放入第一个区间
• pre 记录最终合并后的区间数组的最后一个区间
• 遍历intervals，如果当前区间与pre有交集，则将ans最后一个区间pop出去，再放入当前区间和pre的并集，更新pre
• 如果当前区间与pre没有交集，则直接将当前区间放入ans，并且更新pre
• 最后返回 ans

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    intervals.sort((a,b) => a[0] - b[0])
    let ans = [intervals[0]]
    let pre = intervals[0]
    for(let i = 1; i < intervals.length; i++){
        if(intervals[i][0] <= pre[1]){
            pre = [pre[0], Math.max(pre[1], intervals[i][1])]
            ans.pop()
            ans.push(pre)
        }else{
            ans.push(intervals[i])
            pre = intervals[i]
        }
    }
    return ans
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

738. 单调递增的数字

• 遇到 n[i-1] > n[i] 的情况，让 n[i-1] --，n[i] 和n[i]之后的所有位数都变成9，来达到一个最大的情况，所有还需要设置一个标志位 flag
• 处理顺序为从低位到高位（从后往前）

/**
 * @param {number} n
 * @return {number}
 */
var monotoneIncreasingDigits = function(n) {
    let nums = n.toString().split('')
    let flag = nums.length
    for(let i = nums.length - 1; i >= 1; i--){
        if(nums[i-1] > nums[i]){
            nums[i-1] --
            flag = i
        }
    }
    for(let i = flag; i < nums.length; i++){
        nums[i] = 9
    }
    return Number(nums.join(''))
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

714. 买卖股票的最佳时机含手续费

买入日期：遇到更低点就更新

卖出日期：没有必要算出准确的卖出日期，如果当前价格大于 最低价格 + 手续费，则可以收获利润，可以在第一次买入的时候就算上手续费，之后更新最低价格时将手续费减去。

• 如果当前价格比最低价格还要小则更新记录最小价格
• 当前价格小于 最低价格 + 手续费，卖出会亏本，则忽略
• 当前价格大于 最低价格+手续费，计算利润，更新最低价格（为了不要重复计算手续费），以后可能有连续的利润可以收获

/**
 * @param {number[]} prices
 * @param {number} fee
 * @return {number}
 */
var maxProfit = function(prices, fee) {
    let result = 0
    let min = prices[0]
    for(let i = 1; i < prices.length; i++){
        // 1. 更新最低价格 相当于前一次已经将股票卖出 现在确定最低的买入价格
        if(prices[i] < min){
            min = prices[i]
        }
        // 2. 此时如果未拥有股票买入不划算 如果拥有股票卖出会亏本 保持现状
        if(prices[i] >= min && prices[i] <= min + fee){
            continue
        }
        // 3. 计算利润
        if(prices[i] > min + fee){
            result += prices[i] - min - fee
            min = prices[i] - fee
        }
    }
    return result
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

968. 监控二叉树

从叶子结点往上看，让因为头结点放不放摄像头也只能省下一个摄像头，叶子结点放不放摄像头是指数级别的。叶子结点的父节点安装摄像头，所用摄像头最少，整体最优。

由于是从叶子结点到根节点，需要使用回溯，选择 0,1,2 分别代表二叉树中节点的不同状态：

• 0：该节点无覆盖
• 1：该节点有摄像头
• 2：该节点有覆盖

需要根据左右节点的状态来确定当前节点的状态，于是选择后序遍历，先拿到左右子树的递归结果，再来推导当前节点。

递归函数的终止条件是遇到了空节点，那么空节点的返回值应该是什么呢？应该是状态2有覆盖，这样就能在叶子结点的父节点上放置摄像头了。

如何根据左右节点的情况推导当前节点：

• 左右节点都有覆盖，则该节点应该是无覆盖
• 左右节点有一个或者无覆盖，则该节点需要放置摄像头
• 左右节点有一个或者两个有摄像头，则该节点为有覆盖
• 最后需要判断头结点是否为无覆盖，因为右节点没有父节点复放置摄像头让头结点再去满足条件，所有这里只能在头结点放置一个摄像头

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minCameraCover = function(root) {
    let ans = 0
    function traversal(node){
        if(!node) return 2
        let left = traversal(node.left)
        let right = traversal(node.right)
        if( left == 2 && right == 2){
            return 0
        }
        if( left == 0 || right == 0){
            ans ++
            return 1
        }
        if( left == 1 || right == 1){
            return 2
        }
    }
    let headStatus = traversal(root)
    if(headStatus == 0) ans ++
    return ans
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33