LeetCode 专题：贪心算法

作者: 李威威 | 来源:发表于2019-05-26 05:31 被阅读0次

贪心算法，又称贪婪算法。

1、在对问题求解时，总是做出在当前看来最好的选择。即贪心算法不从整体最优上加以考虑。

2、贪心算法所作出的是在某种意义上的局部最优解。

贪心算法和动态规划算法都是由局部最优导出全局最优，二者的区别如下。

贪心算法：
1、贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。
2、贪心法正确的前提是：每一步的最优解一定包含上一步的最优解。

动态规划：
1、全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解；
2、动态规划的关键是确定“状态转移方程”，即如何通过已经求出的局部最优解推导出全局最优解；
3、边界条件：即最简单的，可以直接得出的局部最优解。

LeetCode 第 11 题：盛最多水的容器

给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

img

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

public class Solution {

    // 指针对撞、贪心思想
    // 参考解答：https://www.cnblogs.com/zichi/p/5745992.html

    public int maxArea(int[] height) {
        int len = height.length;
        if (len < 2) {
            // 0 或者 1 的时候，不能形成区间，所以不能形成容器
            return 0;
        }
        int l = 0;
        int r = len - 1;
        int res = 0;
        while (l < r) {
            // 这里其实就是木桶原理，取决于最短的那根木板
            // [1,2,3] 3 和 1 之间的长度就是 (3-1=)2
            int area = (r - l) * Math.min(height[l], height[r]);
            res = Math.max(res, area);
            if (height[l] < height[r]) {
                l++;
            } else {
                // height[l] >= height[r]
                r--;
            }
        }
        return res;
    }


    // 暴力解法，时间复杂度太高，我们应该使用指针对撞的方法
    public int maxArea1(int[] height) {
        int len = height.length;
        if (len < 2) {
            return 0;
        }
        int res = 0;
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                res = Integer.max(res, Integer.min(height[i], height[j]) * (j - i));
            }
        }
        return res;
    }
}

LeetCode 第 435 题：无重叠区间

传送门：435. 无重叠区间。

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

可以认为区间的终点总是大于它的起点。

区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]

输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: [ [1,2], [1,2], [1,2] ]

输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: [ [1,2], [2,3] ]

输出: 0

解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

思路1：贪心算法。

写法1：按照起点排序：选择结尾最早的，后面才有可能接上更多的区间。

如果两个区间有重叠，应该保留那个结尾短的。即要删除的是：与之前的区间有重叠的，并且结尾还比当前结尾长的那个区间。

Python 代码：

# Definition for an interval.
class Interval:
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e


class Solution:

    # 
    # 那么
    # 关键：

    def eraseOverlapIntervals(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        # 特判
        size = len(intervals)
        if size <= 1:
            return 0
        intervals.sort(key=lambda x: x.start)
        # 表示去掉的区间数
        res = 0
        end = intervals[0].end

        for interval in intervals[1:]:
            # 根据题目意思，严格小，才算重叠
            if interval.start < end:
                res += 1
                end = min(end, interval.end)
            else:
                end = interval.end
        return res


if __name__ == '__main__':
    intervals = [Interval(1, 2), Interval(1, 2), Interval(1, 2)]
    solution = Solution()
    result = solution.eraseOverlapIntervals(intervals)
    print(result)

写法2：把问题转换成最多能保留多少个区间，使得它们互相不重复。则可以按照终点排序。每个区间的结尾很重要，结尾越小，则后面越有可能容纳更多的区间。

Python 代码：

# Definition for an interval.
class Interval:
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e


class Solution:
    def eraseOverlapIntervals(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """

        size = len(intervals)
        if size <= 1:
            return 0

        intervals.sort(key=lambda x: x.end)

        end = intervals[0].end
        res = 1

        for interval in intervals[1:]:
            if interval.start >= end:
                res += 1
                end = interval.end

        return size - res


if __name__ == '__main__':
    intervals = [Interval(1, 2), Interval(1, 2), Interval(1, 2)]
    solution = Solution()
    result = solution.eraseOverlapIntervals(intervals)
    print(result)

Java 代码：

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public int eraseOverlapIntervals(Interval[] intervals) {
        int ilen = intervals.length;
        if (ilen == 0) {
            return 0;
        }
        // 按结尾升序排序
        Arrays.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if (o1.end != o2.end) {
                    return o1.end - o2.end;
                }
                return o1.start - o2.start;
            }
        });
        int res = 1;
        // 前一个结尾区间的索引
        int pre = 0;
        for (int i = 1; i < ilen; i++) {
            if (intervals[i].start >= intervals[pre].end) {
                res++;
                pre = i;
            }
        }
        return ilen - res;
    }
}

思路2：动态规划。

同样转换问题：问最多保留多少个区间，使得这些区间互相不重叠。这件事情像极了“最长上升子序列”。通常的思考方式：按照起始点进行排序。

Java 代码：

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public int eraseOverlapIntervals(Interval[] intervals) {
        int ilen = intervals.length;
        if (ilen == 0) {
            return 0;
        }

        Arrays.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if (o1.start != o2.start) {
                    return o1.start - o2.start;
                }
                return o1.end - o2.end;
            }
        });

        // dp[i] 表示以 intervals[i] 为结尾的区间能够成的最长不重叠的区间序列有几个
        int[] dp = new int[ilen];
        Arrays.fill(dp, 1);
        for (int i = 1; i < ilen; i++) {
            for (int j = 0; j < i; j++) {
                if (intervals[i].start >= intervals[j].end) {
                    dp[i] = Integer.max(dp[i], dp[j] + 1);
                }
            }
        }

        int res = dp[0];
        for (int i = 1; i < ilen; i++) {
            res = Integer.max(res, dp[i]);
        }
        return ilen - res;
    }
}

LeetCode 第 402 题：Remove K Digits

参考资料：https://blog.csdn.net/qq508618087/article/details/52584133

传送门：402. 移掉K位数字。

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

注意:

num 的长度小于 10002 且 ≥ k。

num 不会包含任何前导零。

示例 1 :
输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例 2 :
输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 :
输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。

思路：肯定要移除大的数，所以遍历的时候，先移除那些左边比右边大的数，若没有移除完则直接去除后面的。

Python 代码：

class Solution:
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        if len(num) == k: # 等于，直接返回‘0’
            return '0'
        stack = []
        for i in num: #遍历
            while stack and i < stack[-1] and k > 0: #当前数字小于栈顶数字，出栈。
                stack.pop()
                k -= 1
            stack.append(i)
        if k > 0:
            stack = stack[:-k] # 若还没移除K位，则直接移除后面。
        while stack and stack[0] == "0": # 移除0
            stack.pop(0)
        if not stack:
            return '0'
        else:
            return ''.join(stack)

LeetCode 第 55 题：JumpGame（是否能跳到最后一格）

传送门：55. 跳跃游戏。

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

思路：本题用一个数 max_arrive 表示能到达的最远下标，一步步走下去，如果发现在 max_arrive 范围之内某处能达到的范围大于 max_arrive，那么我们就用更大的范围来替换掉原先的 max_arrive，这样一个局部的最优贪心策略，在全局看来也是最优的，因为局部能够到达的最大范围也是全局能够到达的最大范围。

参考资料：https://blog.csdn.net/happyaaaaaaaaaaa/article/details/51636861
Python 代码：

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        l = len(nums)
        if l == 0:
            return True
        max_arrive = nums[0]
        for i in range(1, l):
            if i > max_arrive:
                return False
            else:
                max_arrive = max(max_arrive, i + nums[i])
        return True

LeetCode 第 12 题：整型转罗马数字

贪心算法：写好对应关系。

image-20190110155600773

image-20190110155317032

# 整形转罗马数字
class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        nums = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        romans = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
        index = 0
        res = ''
        while index < 13:
            # 注意：这里是等于号
            while num >= nums[index]:
                res += romans[index]
                num -= nums[index]
            index += 1
        return res

LeetCode 第 13题：罗马数字转整形

例：LVIII，编写对应关系，从左边看到右边，只要左边比右边小的，就减去两倍自己。

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """

        l = len(s)
        if l == 0:
            return 0
        map = {
            'I': 1,
            'V': 5,
            'X': 10,
            'L': 50,
            'C': 100,
            'D': 500,
            'M': 1000
        }

        res = map[s[0]]
        for i in range(1, l):
            pre = map[s[i - 1]]
            cur = map[s[i]]
            if pre < cur:
                res += (cur - 2 * pre)
            else:
                res += cur
        return res

（本节完）

LeetCode 专题：贪心算法

LeetCode 第 11 题：盛最多水的容器

LeetCode 第 435 题：无重叠区间

LeetCode 第 402 题：Remove K Digits

LeetCode 第 55 题：JumpGame（是否能跳到最后一格）

LeetCode 第 12 题：整型转罗马数字

LeetCode 第 13题：罗马数字转整形

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

算法

LeetCode 专题 ：贪心算法

LeetCode 第 11 题：盛最多水的容器

LeetCode 第 435 题 ：无重叠区间

LeetCode 第 402 题：Remove K Digits

LeetCode 第 55 题：JumpGame（是否能跳到最后一格）

LeetCode 第 12 题：整型转罗马数字

LeetCode 第 13题：罗马数字转整形

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

算法

LeetCode 专题：贪心算法

LeetCode 第 435 题：无重叠区间