hot100之贪心

买卖股票的最佳时期(121)

1. class Solution {
2.     public int maxProfit(int[] prices) {
3.         int res = 0;
4.         int min = Integer.MAX_VALUE;
6.         for (int i = 0; i < prices.length; i++){
7.             min = Math.min(min, prices[i]);
8.             res = Math.max(res,prices[i] - min);
9.         }
10.         return res;
11.     }
12. }

复制代码

• 感悟
  

贪心就是贪局部最优解, 扩散到全局
跳跃游戏(055)

1. class Solution {
2.     public boolean canJump(int[] nums) {
3.         int max_length = 0;
4.         int i = 0;
5.         for (; max_length >= i && i < nums.length; i++){
6.             max_length = Math.max(max_length, i + nums[i]);
7.         }
8.         return i == nums.length;
9.     }
10. }

复制代码

• 分析
  

max_length来维护理论可达距离
跳跃游戏II(045)

1. class Solution {
2.     public int jump(int[] nums) {
3.         int n = nums.length;
4.         int res = 0;
5.         int curr = 0;
6.         int nextCurr = 0;
7.         for (int i = 0; i < n-1 ; i++){
8.             nextCurr = Math.max(nextCurr, i+ nums[i]);
9.             if (i == curr){
10.                 curr = nextCurr;
11.                 res++;
12.             }
13.         }
14.         return res;
15.     }
16. }

复制代码

• 分析
  

curr 维护本次跳跃最大可达距离
nextCurr 通过遍历途经点, 维护下次跳跃最大可达距离
划分字母区间(763)

1. class Solution {
2.     public List<Integer> partitionLabels(String s) {
3.         int n = s.length();
4.         char[] charArray = s.toCharArray();
5.         int[] last = new int[26];
6.         for (int i = 0 ; i < n; i++){
7.             last[charArray[i]- 'a'] = i;
8.         }
10.         List<Integer> res = new ArrayList<>();
11.         int start = 0;
12.         int end = 0;
13.         for (int i = 0; i < n; i++){
14.             end = Math.max(end, last[charArray[i] - 'a']);
15.             if (end == i){
16.                 res.add(end - start + 1);
17.                 start = i+1;
18.             }
19.         }
20.         return res;
21.     }
22. }

复制代码

• 分析
  

将字符串预处理, 产生每个字符的最大索引
提取[start,end]范围内字符的最远索引来更新end

• 感悟
  

遇到这种熟悉又陌生的题型真别怕, 先把陌生数据转换成熟悉的, 这题就跟跳跃游戏II(045)一样了

来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除