貪心算法：是指在對問題進(jìn)行求解的時候貌矿，總是做出在當(dāng)前看來最好的選擇呐伞，即不易整體為考慮仿粹，而是局部最優(yōu)解。
- 貪心算法并不能對所有問題都得出整體最優(yōu)解各聘，關(guān)鍵是貪心策略的選擇。
- 無后效性：某個狀態(tài)以前的過程不會影響以后的狀態(tài)抡医，只與當(dāng)前狀態(tài)有關(guān)躲因。
- 一般能用貪心算法解決的問題是：在有一個限定值的情況下，使某個期望值能達(dá)到最高或者最低忌傻。
- 無需嘗試去證明貪心算法的正確性大脉，貪心策略一般是顯而易見的。
貪心是一種思想水孩，要參透它镰矿，還是要以刷題為主。
1俘种、買賣股票的最佳時機（簡單）-122
這道題的給出了連續(xù)好多天一直股票的價格秤标，讓我們能制訂買賣策略獲取最大收益，但是在現(xiàn)實中肯定是不行的宙刘。貪心的策略是不要放過任何一次漲苍姜，跌之前就賣掉（要真這樣我就去炒股好了，我的手就可以拿來彈鋼琴了）悬包。
class Solution {
public int maxProfit(int[] prices) {
int profit = 0;
for(int i = 1; i < prices.length; i++) {
if(prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}
}
2衙猪、跳躍游戲（中等）-55
這道題說實話我沒做出來，我一開始想的是從0開始每次我都跳最大布近，實在不行我退回來垫释，但是無法通過，后來想想這樣做吊输，當(dāng)跳一躍的時候饶号，必定會影響到后面的一躍。
其實思想應(yīng)該是：要跳躍到最后一個位置季蚂，中間的每個位置一定都能到達(dá)茫船，如果把能到達(dá)終點的點成為好坐標(biāo)琅束，就可以從倒數(shù)第二個位置開始向前遍歷，每個點要能到達(dá)終點算谈，必須能夠到達(dá)離他最近的好坐標(biāo)涩禀，而后它就成了前面點的最近好坐標(biāo)。最后只要判斷0的位置是不是好坐標(biāo)然眼，就能解決問題了艾船。
class Solution {
public boolean canJump(int[] nums) {
int len = nums.length;
int lastPos = len - 1;
for(int i = len - 1; i >= 0; i--) {
if(i + nums[i] >= lastPos) {
lastPos = i;
}
}
if(lastPos == 0) {
return true;
} else {
return false;
}
}
}
3、加油站 -134
一開始我是想從開到下個加油站能剩余最多油的站開始走高每，但是這樣是會出現(xiàn)到了某段路程開不過的情況屿岂。我又想，那就不要錯過每一個增量鲸匿，也是行不通的爷怀。
其實，因為答案是唯一的带欢，想走完路程运授，只要總油量比總油耗多，肯定是能走完的乔煞。從第一個油站開始吁朦，若出現(xiàn)油耗不夠，那么起點必須在這個加油站的后面渡贾，只要某個點能走到最后一個站逗宜，那它必須能走一圈。
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int start = 0;
int total = 0;
int sum = 0;
for(int i = 0; i < gas.length; i++) {
int rest = gas[i] - cost[i];
total += rest;
sum += rest;
if(sum < 0) {
start = i + 1;
sum = 0;
}
}
return total >= 0 ? start : -1;
}
}
4剥啤、判斷子序列 -392
一開始沒理解輕觸題目锦溪，哦，這不是灑灑水府怯，我用個26長度的數(shù)組統(tǒng)計一下，你來10億個我也能判斷防楷，后來才發(fā)現(xiàn)忽略了順序牺丙。還是得乖乖地去遍歷字符串，但是比對了別人的答案复局，相形見絀冲簿，別人都是用字符串的方法，而我對api都不熟悉亿昏，方法實在不高明啊峦剔。力扣歸類的是貪心，我沒悟到角钩。
我的：
class Solution {
public boolean isSubsequence(String s, String t) {
if("".equals(s)) {
return true;
}
if("".equals(t)) {
return false;
}
char[] a = s.toCharArray();
char[] b = t.toCharArray();
int j = 0;
int len = a.length;
for(int i = 0; i < b.length; i++) {
if(b[i] == a[j]) {
j++;
if(j == len) {
return true;
}
}
}
return false;
}
}
別人的：
class Solution {
public boolean isSubsequence(String s, String t) {
int i = -1;
for(char c : s.toCharArray()){
i = t.indexOf(c,i+1);
System.out.println(i);
if(i == -1){
return false;
}
}
return true;
}
}
作者：shu-pi-2
鏈接：https://dev.lingkou.xyz/problems/two-sum/solution/chong-fen-li-yong-indexofmark-by-shu-pi-2/
來源：力扣（LeetCode）
5吝沫、分發(fā)糖果 -135
之前做的分糖果題目是孔融讓梨一樣小吃小大吃大來分大小不同的題目呻澜，所以一開始切入的時候我還是在找最低分的孩子，但是這道題每個孩子要比較的只是他相鄰的孩子惨险，所以解決不了羹幸。那么，一個孩子可能有兩個相鄰的孩子辫愉，所以既要跟左邊的相比也要跟右邊的相比栅受，就會有兩條規(guī)矩：最先給每個孩子都發(fā)上一個，先從左邊開始遍歷恭朗，只要我比我左邊的人分?jǐn)?shù)高屏镊，我就要分到比他的糖果，不然我就不開心痰腮，再從右邊開始遍歷而芥，每個人與他右邊的孩子相比（沒有就不用），最終糖果數(shù)分別用兩個數(shù)組存儲诽嘉，每個孩子都要滿足這兩個約束蔚出，那當(dāng)然是取多的發(fā)。
class Solution {
public int candy(int[] ratings) {
int count = 0;
int n = ratings.length;
int[] l = new int[n];
int[] r = new int[n];
//初始時每個學(xué)生都分配1個糖果
for(int i = 0; i <= n - 1; i++) {
l[i] = 1;
r[i] = 1;
}
//從左邊遍歷得到分配數(shù)組
for(int i = 1; i <= n - 1; i++) {
if(ratings[i] > ratings[i - 1]) {
l[i] = l[i - 1] + 1;
}
}
//在從右邊遍歷得到分配數(shù)組
for(int i = n - 2; i >= 0; i--) {
if(ratings[i] > ratings[i + 1]) {
r[i] = r[i + 1] + 1;
}
}
for(int i = 0; i < n; i++) {
count += l[i] > r[i] ? l[i] : r[i];
}
return count;
}
}
6骄酗、按要求補齊數(shù)組 -330
欸踏烙，這道題就比較有難度了寒屯。一開始我想的居然是從n開始去減最大的數(shù)处面，然后再n-1繼續(xù)，然后就沒有然后了，怎么可能嘛醉顽，真是愚蠢的雷霆球迷通熄。
這道題講究的是一個覆蓋，要覆蓋[1, n]的區(qū)間饿幅，當(dāng)然使用比n的數(shù)來相加，子區(qū)間也是同樣的道理，所以從1開始蒙兰，用一個miss來表示1開始的區(qū)間覆蓋不到的第一個，如果miss>=某個元素nums[i]就證明區(qū)間連上了梭伐，覆蓋不到的就是nums[i]+miss了痹雅，并檢查下個元素nums[i+1]；如果miss<nums糊识，那肯定就要補充數(shù)了绩社，貪心就體現(xiàn)在這里了摔蓝，補充比miss大的數(shù)，那miss不能被覆蓋到愉耙，補上比miss小的數(shù)贮尉，就有點吃虧了，那miss得變?yōu)槎嗌倌仄友兀勘緛砬懊嫠袛?shù)加上最多是miss-1猜谚，又加上了miss，那miss就等于2miss了赌渣。
class Solution {
public int minPatches(int[] nums, int n) {
int patches = 0;
//miss找不到的時候是要翻倍的魏铅，用Int可能會發(fā)生溢出
long miss = 1;
int i = 0;
while(miss <= n) {
if(i < nums.length && miss >= nums[i]) {
//兩個區(qū)間重疊，區(qū)間能覆蓋到num[i]+miss-1坚芜，去一個區(qū)間從i+1開始
miss += nums[i++];
} else {
//補上miss這個數(shù)览芳，加上前面的數(shù)剛好能覆蓋到2miss-1
miss += miss;
patches ++;
}
}
return patches;
}
}
7、跳躍游戲Ⅱ -45
因為做過之前跳躍游戲那道題鸿竖，在解這題的時候我還是用了相同的方法沧竟，就是由后往前來遍歷，只要能到達(dá)終點的就是好坐標(biāo)缚忧，然后遍歷某個點能到達(dá)的所有好坐標(biāo)悟泵，選出最短的跳數(shù)。
class Solution {
public int jump(int[] nums) {
int n = nums.length;
int[] steps = new int[n];
for(int i = 0; i < n; i++) {
steps[i] = -1;
}
steps[n - 1] = 0;
for(int i = n - 2; i >= 0; i--) {
int least = -1;
for(int j = i + nums[i]; j >= i; j--) {
if(j <= n - 1 && steps[j] != -1) {
//選取跳數(shù)最少的
int step = steps[j] + 1;
if(least == -1) {
least = step;
} else if(least > step) {
least = step;
}
}
}
steps[i] = least;
}
return steps[0];
}
}
很明顯這個耗時是非常不理想的搔谴，這個解法還是不夠高明魁袜。可以看到就是在代碼中是嵌套了兩層循環(huán)敦第，時間復(fù)雜度會達(dá)到O(n*n)峰弹。
其實這個題目已經(jīng)明確告訴我們是能到達(dá)終點的，所以我們從起點開始遍歷芜果，每次都跳到可到達(dá)點中能跳最遠(yuǎn)距離的點鞠呈。
class Solution {
public int jump(int[] nums) {
int steps = 0;
int end = 0;
int maxPosition = 0;
for(int i = 0; i < nums.length - 1; i++) {
//maxPosition表示可達(dá)點能跳躍到的最遠(yuǎn)的距離
maxPosition = Math.max(maxPosition, nums[i] + i);
//end表示的是當(dāng)前點一步可達(dá)的范圍邊界
if(i == end) {
end = maxPosition;
steps ++;
}
}
return steps;
}
}
這次就快很多了，因為只需要遍歷一次數(shù)組右钾，時間復(fù)雜度減低到O(n)蚁吝。
