基础算法 - 贪心算法
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致全局最优解的算法。贪心算法在某些问题中能够产生全局最优解，而在另一些问题中只能产生近似解。
贪心算法的主要特点包括：
- 局部最优选择：每一步都选择当前状态下的局部最优解。
- 简单高效：相对于其他复杂算法，贪心算法通常更为简单且计算效率高。
- 不保证全局最优：贪心算法并不总能保证找到全局最优解，适用于某些特定类型的问题。
贪心算法的应用
贪心算法通常应用于以下类型的问题：
- 最小生成树：如 Kruskal 算法和 Prim 算法。
- 单源最短路径：如 Dijkstra 算法。
- 活动选择问题：选择最大数量的互不相交活动。
- 背包问题：在一定容量限制下选择物品使总价值最大（贪心算法仅适用于分数背包问题）。
相关题目
难度：简单
动态规划
想要获得最大收益，可以计算在第i天买入股票可以获得的最大收益的每一种可能，然后进行比较得出最小值。
在第i天买入股票可以获得的最大收益值 = 第i天之后的最高股价 - 第i天的股价。
可以用暴力的解法，两个for循环，时间复杂度为O(n^2^)。
将买入的钱固定下来，去寻找未知的卖出的钱，而卖出的钱就一直往后遍历就可以，这样其实每一次遍历都会有多余的操作，因为只要遍历一次j就可以知道某一个范围内最大的是多少了，而这样按照这种暴力的思想，会导致其重复计算。
那么，如何避免这个多余的遍历呢，我们可以用记忆化搜索的方式，或者说是动态规划的方法来记录。
核心思想就在：如果今日买入股票，获得的最高收益 = 之后股价最大值 - 今日股票值，而这个“之后股价最大值“由我们先遍历一次得出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int maxProfit(int[] prices) {
int ans = 0;
int len = prices.length;
int[] dp = new int[len];
dp[len-1] = Integer.MIN_VALUE;
for(int i=len-2;i>=0;i--){
dp[i] = Math.max(dp[i+1],prices[i+1]);
}
for(int i=0;i<len-1;i++){
ans = Math.max(dp[i] - prices[i],ans);
}
return ans;
}
}
|
贪心
并不关心其他日子买入股票所获得的最大收益，只关注最大收益。
最大收益就是 股票最高价 - 曾经的股票最低价
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int maxProfit(int[] prices) {
int res = 0;
int min = Integer.MAX_VALUE;
for(int n : prices){
min = Math.min(min,n);
res = Math.max(res,n - min);
}
return res;
}
}
|
难度：中等
DFS
可以利用DFS 确保探索所有可能的路径，当找到成功成功路劲之后直接返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
boolean flag = false;
public boolean canJump(int[] nums) {
dfs(nums,0);
return flag;
}
private void dfs(int[] nums,int cur){
if(flag||cur>=nums.length){
flag = true;
return;
}
int val = nums[cur];
for(int i=val;i>=1;i--){
dfs(nums,cur+i);
if(flag==true)return;
}
}
}
|
但是这种方法在数据特别大的情况下很容易运行超时，而且还容易栈溢出。
效率低下：DFS 在每个节点尝试所有可能的跳跃，导致时间复杂度较高，特别是在数组较大或跳跃次数较多的情况下，容易导致运行超时。
冗余计算：很多路径会被重复计算，导致性能问题。
贪心
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public boolean canJump(int[] nums) {
int len = nums.length;
int max = 0;
for(int i=0;i<len;i++){
if(i>max)return false;
max = Math.max(max,nums[i]+i);
}
return true;
}
}
|
具体来说，它体现了以下贪心策略：
- 局部最优选择：在每一步，选择当前能跳到的最远位置。这意味着每次都在尽可能扩展能到达的范围。
- 全局最优结果：通过每次选择当前能到达的最远位置，最终判断是否能够到达数组的末尾。
在代码中，max变量记录了当前能到达的最远位置。遍历数组时，max会不断更新为nums[i] + i和max中的最大值，这意味着在每一步，算法都选择能跳到的最远位置。
确保在每一步都选择当前最优的跳跃，从而判断是否能够跳到最后一个位置。
难度：中等
与跳跃游戏比，这里给出的样例都可以满足抵达最后一个位置，但这个题求的是最小的跳跃次数。
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
int res = Integer.MAX_VALUE;
public int jump(int[] nums) {
dfs(nums, 0, 0);
return res;
}
private void dfs(int[] nums, int cur, int jumps) {
if (cur >= nums.length - 1) {
res = Math.min(res, jumps);
return;
}
int val = nums[cur];
for (int i = 1; i <= val; i++) {
dfs(nums, cur + i, jumps + 1);
}
}
}
|
遍历每一个成功路径，同时记录跳跃数，将最小跳跃数留下。
超时
动态规划
dp[i]代表跳到位置i需要的最少跳跃数。
对于位置 i，你可以跳 nums[i] 步。那么对于所有可以从 i 跳到的位置 i + j，更新 dp 数组的逻辑如下：
- 当前的位置：
i
- 可以跳的步数：
nums[i]
- 从当前位置
i 跳到所有可能的位置 i + j
1
2
3
| for (int j = 1; j <= nums[i] && i + j < len; j++) {
dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
}
|
完整代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int jump(int[] nums) {
int len = nums.length;
int[] dp = new int[len];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0] = 0;
int tmp;
for(int i=0;i<len;i++){
tmp = dp[i];
for(int j=1;j<=nums[i]&&i+j<len;j++){
dp[i+j] = Math.min(dp[i+j],dp[i]+1);
}
}
return dp[len-1];
}
}
|
这种方法是可以通过的，不过时间复杂度略高O(n*m)， m=Max(nums[i]),而本题中0<nums[i]<1000，所以最大也就1000而已，所以还是可以通过的，如果数字更大一点，这个方法就会超时了。
贪心
关注起跳的时机
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int jump(int[] nums) {
int left = 0;
int right = 1;
int maxPos = 0;
int count = 0;
while(maxPos < nums.length - 1){
for(int i = left; i < right; i++){
maxPos = Math.max(maxPos, i + nums[i]);
}
count++;
left = right;
right = maxPos + 1;
}
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
| class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> res = new ArrayList<>();
int len = s.length();
int[] last = new int[26];
char tmp;
for(int i=0;i<len;i++){
tmp = s.charAt(i);
last[tmp-'a'] = i;
}
int start = 0;
int end = 0;
int cur = 0;
while(cur<len){
tmp = s.charAt(cur);
end = Math.max(end,last[tmp-'a']);
if(cur==end){
res.add(end-start+1);
start = end+1;
}
cur++;
}
return res;
}
}
|
通过这种方式，每次都选择一个尽可能大的区间，使得区间内的字符在该区间之外不再出现。
当遍历到的位置 cur 等于当前区间的终点 end 时，说明当前区间 [start, end] 已经确定，即[start,end]中所有的字串不会出现在其他区间中。并且这样还做到了将字符串划分为尽可能多的片段。
