文章目錄
- 擺動序列
- 最大子數組合
- 買賣股票
- 跳躍游戲
- 跳躍2
擺動序列
不像是貪心,只要抓住擺動這個點,前一個上升,那下一個就要下降,記錄上一次的狀態為1的話,那下一次就要更新為-1,如果上一次為1,這次還為1那就說明不是擺動的
最大子數組合
一層循環,如果當前和<=0,那么就將當前值置為0,如果當前和>已經保存的res,那么更新res
買賣股票
可以多次買入賣出
等價公式:3-1 = 3-2+2-1 因此可以直接計算每天的差值,相加就行
跳躍游戲
重點在于
- 當前位置i+當前位置可以跳到的最大位置就是判斷的依據
cover = max(i+nums[i], cover);
- 當前位置i取多少就是循環的結束條件
for(int i=0; i<=cover; i++)
跳躍2
要想明白兩個點
一個是 if(i==cur) 和 cur=next;這兩句就隱含了跳躍不會超出覆蓋范圍
一個是如果不按 for(int i=0; i<nums.size(); i++)這個循環來,若使用 i <= cover 作為循環條件,可能會提前終止遍歷,從而無法獲取完整的信息。例如,后續的某個位置可能只需一次跳躍就能跳到更遠的地方,進而減少總的跳躍次數,但由于提前終止遍歷,這個信息就會被遺漏。
for(int i=0; i<nums.size(); i++){next = max(next, i+nums[i]);if(i==cur){res++;if(next>=nums.size()-1) break;cur=next;}
}