买卖股票的最佳时期(121)
class Solution {
public int maxProfit(int[] prices) {
int res = 0;
int min = Integer.MAX_VALUE;
for (int i = 0; i < prices.length; i++){
min = Math.min(min, prices[i]);
res = Math.max(res,prices[i] - min);
}
return res;
}
}
- 感悟
贪心就是贪局部最优解, 扩散到全局
跳跃游戏(055)
class Solution {
public boolean canJump(int[] nums) {
int max_length = 0;
int i = 0;
for (; max_length >= i && i < nums.length; i++){
max_length = Math.max(max_length, i + nums[i]);
}
return i == nums.length;
}
}
- 分析
max_length
来维护理论可达距离
跳跃游戏II(045)
class Solution {
public int jump(int[] nums) {
int n = nums.length;
int res = 0;
int curr = 0;
int nextCurr = 0;
for (int i = 0; i < n-1 ; i++){
nextCurr = Math.max(nextCurr, i+ nums[i]);
if (i == curr){
curr = nextCurr;
res++;
}
}
return res;
}
}
- 分析
curr
维护本次跳跃最大可达距离
nextCurr
通过遍历途经点, 维护下次跳跃最大可达距离
划分字母区间(763)
class Solution {
public List<Integer> partitionLabels(String s) {
int n = s.length();
char[] charArray = s.toCharArray();
int[] last = new int[26];
for (int i = 0 ; i < n; i++){
last[charArray[i]- 'a'] = i;
}
List<Integer> res = new ArrayList<>();
int start = 0;
int end = 0;
for (int i = 0; i < n; i++){
end = Math.max(end, last[charArray[i] - 'a']);
if (end == i){
res.add(end - start + 1);
start = i+1;
}
}
return res;
}
}
- 分析
将字符串预处理, 产生每个字符的最大索引
提取[start,end]
范围内字符的最远索引来更新end
- 感悟
遇到这种熟悉又陌生的题型真别怕, 先把陌生数据转换成熟悉的, 这题就跟跳跃游戏II(045)一样了