第八章 貪心算法 part02
122.買賣股票的最佳時(shí)機(jī)II
本題解法很巧妙掷倔，本題大家可以先自己思考一下然后再看題解眉孩，會(huì)有驚喜！
文章講解
思路
- 把利潤(rùn)分解為每天的維度勒葱，只收集正利潤(rùn)
class Solution {
public int maxProfit(int[] prices) {
int result = 0;
for(int i = 1; i < prices.length; i++){
result += Math.max(prices[i]-prices[i-1], 0);
}
return result;
}
}
55. 跳躍游戲
本題如果沒接觸過浪汪，很難想到，所以不要自己憋時(shí)間太久凛虽，讀題思考一會(huì)死遭，沒思路立刻看題解
文章講解
思路
- 判斷跳躍范圍能不能覆蓋到終點(diǎn)
class Solution {
public boolean canJump(int[] nums) {
int cover = 0;
if(nums.length == 1) return true;
for(int i = 0; i <= cover; i++){
cover = Math.max(i + nums[i], cover);
if(cover >= nums.length-1) return true;
}
return false;
}
}
45.跳躍游戲II
本題同樣不容易想出來。貪心就是這樣凯旋，有的時(shí)候 會(huì)感覺簡(jiǎn)單到離譜呀潭，有時(shí)候钉迷，難的不行，主要是不容易想到钠署。
文章講解
思路
- 盡可能跳最大值糠聪，但是寫代碼時(shí)不能這樣實(shí)現(xiàn)。
- 比如 [2,3,1,1,4]谐鼎，在最開始的位置不能跳兩步舰蟆，而是應(yīng)該先跳到3的位置
- 依然是用盡量少的步數(shù)來增加更多覆蓋范圍。只記錄下一步最大的覆蓋范圍狸棍。
class Solution {
public int jump(int[] nums) {
if (nums.length == 1) return 0;
int curDistance = 0; // 當(dāng)前覆蓋最遠(yuǎn)距離下標(biāo)
int nextDistance = 0; // 下一步覆蓋最遠(yuǎn)距離下標(biāo)
int result = 0; // 記錄走的最大步數(shù)
for(int i = 0; i < nums.length; i++){ //開始遍歷數(shù)組身害，收集下一步能跳多遠(yuǎn)
nextDistance = Math.max(nums[i] + i, nextDistance); //只記錄最遠(yuǎn)的記錄
if(i == curDistance){ //i移動(dòng)到了當(dāng)前的覆蓋范圍之后怠李，發(fā)現(xiàn)也沒有到終點(diǎn)顺献，要再走一步到終點(diǎn)
if(curDistance < nums.length-1){ // 當(dāng)前的范圍小于數(shù)組長(zhǎng)度，必須要再走一步增加覆蓋范圍
result++;
curDistance = nextDistance;
// 如果當(dāng)前覆蓋范圍已經(jīng)到達(dá)或超過數(shù)組的最后一個(gè)元素姐赡，退出循環(huán)
if (curDistance >= nums.length - 1) {
break;
}
}
}
}
return result;
}
}
但實(shí)際上代碼隨想錄的少一個(gè)if
1005.K次取反后最大化的數(shù)組和
本題簡(jiǎn)單一些唐片，估計(jì)大家不用想著貪心 丙猬，用自己直覺也會(huì)有思路。
文章講解
思路
第一步：將數(shù)組按照絕對(duì)值大小從大到小排序牵触，注意要按照絕對(duì)值的大小
第二步：從前向后遍歷淮悼，遇到負(fù)數(shù)將其變?yōu)檎龜?shù)，同時(shí)K--
第三步：如果K還大于0揽思，那么反復(fù)轉(zhuǎn)變數(shù)值最小的元素，將K用完
第四步：求和
- 注意一下Lambda表達(dá)式
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
// 對(duì)數(shù)組按絕對(duì)值從大到小排序
//nums = Arrays.sort(nums, (a, b) -> Integer.compare(Math.abs(b), Math.abs(a))); 不能這樣寫
nums = IntStream.of(nums)
.boxed()
.sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
.mapToInt(Integer::intValue)
.toArray();
//絕對(duì)值從大到小排列 因?yàn)? // Integer.compare(x, y) 方法比較兩個(gè)整數(shù) x 和 y：如果 x < y见擦，返回負(fù)數(shù)（表示 a 應(yīng)該排在 b 前面）钉汗。如果 x == y，返回 0（表示 a 和 b 的順序不變）鲤屡。如果 x > y损痰，返回正數(shù)（表示 b 應(yīng)該排在 a 前面）。
// 依次將負(fù)數(shù)變?yōu)檎龜?shù)酒来，優(yōu)先處理絕對(duì)值最大的
for(int i = 0; i < nums.length && k > 0; i++){ // 注意這里還有K>0
if(nums[i] < 0){
nums[i] = - nums[i];
k--;
}
}
// 如果K還大于0卢未，且K是奇數(shù)，轉(zhuǎn)變數(shù)值最小的元素, 因?yàn)槿绻鹝是偶數(shù)堰汉，正負(fù)轉(zhuǎn)換結(jié)果不變
if(k % 2 == 1) nums[nums.length - 1] = -nums[nums.length - 1];
//計(jì)算結(jié)果 將數(shù)組 nums 轉(zhuǎn)換為一個(gè) IntStream 對(duì)象再求sum
int sum = Arrays.stream(nums).sum();
return sum;
}
}
