買賣股票的最佳時期(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)一樣了
浙公網安備 33010602011771號