---

1、分發餅干

455. 分發餅干

其實看完這個題會發現，如果給定的兩個數組不排序的話會非常難受，所以無論怎樣，先排序。接下來需要比較兩個數組的值，可以用雙指針來指向。兩個數組的兩個元素比較時，和之前有相同的思路，如果滿足條件，那么后面的元素都比這個元素大，肯定也滿足，但為了滿足更多次的條件，所以就選用最小的那個值；如果不滿足條件，這里就跳過去，找下一個更大的元素去看看能否滿足條件。這也就是貪心思想。

    int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int res = 0, m = g.size(), n = s.size();for(int i = 0, j = 0; i < m && j < n; ++i, ++j){while(j < n && s[j] < g[i]) ++j;if(j < n) res++;}return res;}

2、最優除法

553. 最優除法

無論怎樣，假設abcdefg7個數，a / b / c / d / e / f，整個式子就是一個分式，a一定在分子，b一定在分母。對于貪心來說，讓分子變大，讓分母變小，就是最優解。這道題來看，其實應當讓分子變大就是它的最優解，所以接下來就要讓分子變大。讓分子變大的辦法就是在把b ~ f都放到一個括號里，這樣就變成了 a * c * d * e * f / b。

    string optimalDivision(vector<int>& nums) {int n = nums.size();if(n == 1) return to_string(nums[0]);if(n == 2) return to_string(nums[0]) + "/" + to_string(nums[1]);string res = to_string(nums[0]) + "/(" + to_string(nums[1]);for(int i = 2; i < n; ++i){res += "/" + to_string(nums[i]);}res += ")";return res;}

3、跳躍游戲Ⅱ

45. 跳躍游戲 II

這道題意思就是如果是[2, 3, 1, 5, 4]，那么在0下標位置時最多可以跳2步到1這個位置。

這道題可以用動規，以i位置為結尾，遍歷一遍前面所有的元素，如果能從某個位置跳過來，那就選那個位置，而那個位置存儲了到它的最小跳躍數，然后+1即可，但這樣是n ^ 2的時間復雜度，思路并不行。

這道題的思路可以是一個類似層序遍歷的過程。假設一個數組[2, 3, 1, 1, 4, 2, 6, 7, 1, 5, 8]，從0下標開始，是2，我們能夠確定跳到3或1這個點，也就是第一次選定起點后確定了下一次起跳的左端點和右端點；接著，3可以跳到1，1，4，而1這里，就加上貪心，因為3跳得遠，且它一定比1要至少1，所以1能跳到的，3一定能跳到的，所以這里就只考慮大的數字，跳的區間為114，但是重疊了，重疊部分是2下標處的1，所以把這部分去掉，只看1和4，1就是左端點，4就是右端點；接著從4走，能到2671，這時候14和2671沒有重疊的，所有不會劃掉一部分，2就是左端點，1就是右端點。這樣的過程就是選定了一個點后，就能確定下一次的左端點和右端點，所以很像層序遍歷。

這個思路的時間復雜度是O(N)。

    int jump(vector<int>& nums) {int left = 0, right = 0, maxPos = 0, n = nums.size(), res = 0;while(left <= right)//防止跳不到n - 1位置{if(maxPos >= n - 1)//先判斷是否已經能跳到最后一個位置return res;for(int i = left; i <= right; ++i){maxPos = max(maxPos, nums[i] + i);}left = right + 1;right = maxPos;res++;}return -1;}

4、跳躍游戲Ⅰ

55. 跳躍游戲

先看跳躍游戲Ⅱ。

其實就是改兩處

    bool canJump(vector<int>& nums) {int left = 0, right = 0, maxPos = 0, n = nums.size();while(left <= right)//防止跳不到n - 1位置{if(maxPos >= n - 1)//先判斷是否已經能跳到最后一個位置return true;for(int i = left; i <= right; ++i){maxPos = max(maxPos, nums[i] + i);}left = right + 1;right = maxPos;}return false;}

5、加油站

134. 加油站

按照這個題的思路來看，兩個數組要同時看，這時不如作為一個數組，因為真正需要的是差。gas和cost兩個數組每每對應，用gas的減cost的，比如例1，就得到[-2, -2, -2, 3, 3]。最簡單的辦法就是暴力解法，依次枚舉所有起點，模擬加油的流程。

實際上，這道題可以在暴力解法上改進而得到。差值的數組不需要創建出來，不過下面還是看差值數組。用i表示下標，然后用一個step變量，表示走多少步，比如走0步就還是原地，走1步就到下一個位置，不過要%上數組大小，這樣就不會越界了。

    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size();for(int i = 0; i < n; i++){int rest = 0;for(int step = 0; step < n; step++){int index = (i + step) % n;rest = rest + gas[index] - cost[index];if(rest < 0) break;}if(rest >= 0) return i;}return -1;}

不過這樣肯定超出時間限制。現在基于這個來優化。假設差值數組是abcdefg，從a走到f就不能走了，說明a + b + c + d + e + f < 0，暴力解法就會從b再來一遍，但這樣明顯做了無用功。上面的式子小于0，那么去掉a，還是小于0，所以就不用管這些了，直接從g位置再出發。這樣平均時間復雜度就是O(N)了。

    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size();for(int i = 0; i < n; i++){int rest = 0;int step = 0;for(; step < n; step++){int index = (i + step) % n;rest = rest + gas[index] - cost[index];if(rest < 0) break;}if(rest >= 0) return i;i = i + step;}return -1;}

6、單調遞增的數字

738. 單調遞增的數字

當然最簡單的方法就是暴力枚舉，從這個數字到0，判斷每一個數字是否是單調遞增，找到的第一個就是結果。不過重點在于如何判斷單調遞增。

對于一個數字，如果想對每一位做一些判斷，轉換成字符串就好。另一個經典操作就是模10再除10，就能從個位開始拿到每一位。

這個暴力解法的時間復雜度是O(nlogn)，取一個數字的每一位的時間復雜度是logn。

但這里不用暴力解法，要用貪心，不過這更像找規律。

從頭開始判斷，如果發現了不是遞增，那要對字符串如何操作？比如123454367，到了5這個位置就不能繼續了，但因為要找更小的數字，那么4367不能改為6367。我們可以修改5，把它減1，然后后面的數字全變成9，就是要求的數字。但這里還有問題，如果是連續的幾個5之后有個4呢？這樣就得把第一個5改成4，后面全變成9。

    int monotoneIncreasingDigits(int n) {string s = to_string(n);int i = 0, m = s.size();while(i + 1 < m && s[i] <= s[i + 1]) ++i;if(i + 1 == m) return n;while(i - 1 >= 0 && s[i] == s[i - 1]) --i;s[i]--;for(int j = i + 1; j < m; ++j) s[j] = '9';return stoi(s);}

7、壞了的計算器

991. 壞了的計算器

對于小于目標的數，那么乘2會更快地接近目標，但是也有不是最優解的，比如6和目標10。

這道題適合逆著思考，把操作變成除2和+1。
這個題沒有小數，所以能除2的只能是偶數，那么遇到奇數的話就只能+1。偶數可以除2，可以+1。把目標值變成原始值，原始值則變成目標值。假設原有的目標值是end，原始值是begin。

針對偶數，如果end <= begin，也就是目標值更小，那么遇到偶數就得+1。如果end > begin，奇數還是只能+1，而偶數，經過證明，其實是先除更優。

    int brokenCalc(int startValue, int target) {//正難則反 + 貪心int res = 0;while(target > startValue){if(target % 2 == 0) target /= 2;else target += 1;res++;}return res + startValue - target;//目標值變成小于原始值了，奇偶數都是+1，所以就是加上差值。}

結束。