贪心算法，又称贪婪算法。
1、在对问题求解时，总是做出在当前看来最好的选择。即贪心算法不从整体最优上加以考虑。
2、贪心算法所作出的是在某种意义上的局部最优解。
贪心算法和动态规划算法都是由局部最优导出全局最优，二者的区别如下。
贪心算法：
1、贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。
2、贪心法正确的前提是：每一步的最优解一定包含上一步的最优解。
动态规划：
1、全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解；
2、动态规划的关键是确定“状态转移方程”，即如何通过已经求出的局部最优解推导出全局最优解；
3、边界条件：即最简单的，可以直接得出的局部最优解。
LeetCode 第 11 题：盛最多水的容器
给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [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 题：整型转罗马数字
贪心算法：写好对应关系。
# 整形转罗马数字
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
（本节完）
