《算法系列》之贪心

简介

  如果说回溯算法的核心是回溯模板，那么贪心算法的核心就是一句话：局部最优，从而达到全局最优。能满足这句话的题，既可用贪心算法去解。其实贪心算法并没有什么固定写法，在我看来动态规化的题，都能找到一定模板的影子，贪心则不能，其写法各种各样。就像张无忌学太极，边学边忘，记住一句心法口决，即可见招拆招，无招胜有招。

理论基础

  贪心算法（贪婪算法）是指在对问题求解时，总是做出在当前看来是最好的选择，就能得到问题的答案。贪心算法需要充分挖掘题目中条件，没有固定的模式，解决有贪心算法需要一定的直觉和经验。贪心算法不是对所有问题都能得到整体最优解。能使用贪心算法解决的问题具有贪心选择性质。贪心选择性质严格意义上需要数学证明。能使用贪心算法解决的问题必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关，即能从局部最优推导出全局最优。
  就像之前的介绍一样，贪心算法的代码实现无固定写法，我做过的题里什么样的写法都有，如果非要说一种的话，应该是循环用的多一点。贪心算法的题，往往是思考上有一定难度，即我们并不知道应该用贪心算法去做，但是写法上一般不难。这里需要注意一点的时，有的题，并不能从局部最优推导出全局最优，此时是不适合用贪心算法的，我们不要因此而陷进贪心算法的陷阱， 及时退出，选择其它的解法。

解题心得

• 贪心算法的核心：局部最优，从而达到全局最优。
• 能满足从局部最优推导出全局最优质，即可用贪心算法。
• 贪心算法写法需要充分挖掘题目中条件，没有固定的模式。
• 因为无固定招式，所以贪心算法题需要一定的直觉和经验。
• 贪心算法的题，往往是思考上有一定难度，即我们并不知道应该用贪心算法去解题，但是写法上一般不难。
• 局部最优并不一定能推导出整体最优，不要因此陷进贪心算法的陷阱。

算法题目

12. 整数转罗马数字

题目解析：贪心算法解决，每次优先选择较大的数。
代码如下：

/**
 * 贪心算法
 */
class Solution {
    int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

    public String intToRoman(int num) {
        StringBuffer roman = new StringBuffer();
        // 从1000依次选择至1
        for (int i = 0; i < values.length; i++) {
            int value = values[i];
            String symbol = symbols[i];
            while (num >= value) {
                num -= value;
                roman.append(symbol);
            }
            if (num == 0) {
                break;
            }
        }
        return roman.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

45. 跳跃游戏 II

题目解析：此题需找出经过路径中，最长位置的索引，作为下一位置起跳。
代码如下：

/**
 * 贪心算法
 */
class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return 0;
        }
        //记录跳跃的次数
        int count=0;
        //当前的覆盖最大区域
        int curDistance = 0;
        //最大的覆盖区域
        int maxDistance = 0;
        for (int i = 0; i < nums.length; i++) {
            //在可覆盖区域内更新最大的覆盖区域
            maxDistance = Math.max(maxDistance,i+nums[i]);
            //说明当前一步，再跳一步就到达了末尾
            if (maxDistance>=nums.length-1){
                count++;
                break;
            }
            //走到当前覆盖的最大区域时，更新下一步可达的最大区域
            if (i==curDistance){
                curDistance = maxDistance;
                count++;
            }
        }
        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
25
26
27
28
29
30
31

55. 跳跃游戏

题目解析：贪心算法，每步都要最大的数字。
代码如下：

/**
 * 贪心算法
 */
class Solution {
    public boolean canJump(int[] nums) {
        int index = 0;
        while (true) {
            int temp = helper(nums, index);
            // 如果下标没变，说明己到最远处，结束循环
            if (index == temp) {
                break;
            } else {
                // 更新下标
                index = temp;
            }
        }

        if (index == nums.length - 1) {
            return true;
        } else {
            return false;
        }

    }

    // 选取每一步最大值的下标
    public int helper(int[] nums, int index) {
        int max = nums[index];
        int len = nums.length;
        for (int i = index; i < i + nums[index]; i++) {
            // 到底直接返回
            if (i == len - 1) {
                return i;
            }
            // 更新下标
            if (i + nums[i] >= index + max) {
                max = nums[i];
                index = i;
            }
        }
        return index;
    }
}
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
34
35
36
37
38
39
40
41
42
43

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

题目解析：只要当天比前一天大，即可卖出，注：根据题目，可当天卖出后，再买入。
代码如下：

/**
 * 贪心算法
 */
class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                res += prices[i] - prices[i - 1];
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

134. 加油站

题目解析：贪心算法，从头到尾遍历每个加油站，并检查以该加油站为起点，最终能否行驶一周。
代码如下：

/**
 * 贪心算法
 */
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // 剩余油量
        int total = 0;
        // 假设起始点
        int index = 0;
        // 从假设起始点的剩余油量之和
        int sum = 0;
        for (int i = 0; i < gas.length; i++) {
            int temp = gas[i] - cost[i];
            // 计算所有剩余油量
            total += temp;
            // 计算从假设起始点的剩余油量
            sum += temp;
            // 如果当前 sum 值为负数，则到目前为此的加油站点都不适合做起点
            if (sum < 0) {
                index = i + 1;
                sum = 0;
            }
        }
        // 如果gas[] < cost[] 总量，则一定不可行驶一周，直接返回 -1
        if (total < 0) {
            return -1;
        }
        return index;
    }
}
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

135. 分发糖果

题目解析：两次遍历，第一次从左往右，左边比右边大，右边糖果数加1。第二次从右往左，右边比左边大，左边选择 max(右边数+1，当前数)，因为并没有说评分一样的，糖果数要一样。
代码如下：

/**
 * 贪心算法 
 */
class Solution {

    public int candy(int[] ratings) {
        
        int[] candyVec = new int[ratings.length];
        candyVec[0] = 1;

        // 默认糖数都为1，从左往右遍历
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candyVec[i] = candyVec[i - 1] + 1;
            } else {
                candyVec[i] = 1;
            }
        }

        // 从右往左遍历
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
            }
        }

        int res = 0;
        for (int s : candyVec) {
            res += s;
        }
        return res;
    }
}
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

179. 最大数

题目解析：自定义一种排序方式 比较 s1 + s2 和 s2 + s1。
代码如下：

/**
 * 贪心算法
 */
class Solution {
    public String largestNumber(int[] nums) {
        PriorityQueue heap = new PriorityQueue<>((x, y) -> (y + x).compareTo(x + y));
        for(int x: nums) heap.offer(String.valueOf(x));
        String res = "";
        while(heap.size() > 0) res += heap.poll();
        if(res.charAt(0) == '0') return "0";
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

回到首页

刷 leetcode 500+ 题的一些感受

下一篇

《算法系列》之动态规划