目錄

1.加油站

2.單調遞增的數字

3.壞了的計算器

---

1.加油站

鏈接：. - 力扣（LeetCode）

思路：?

gas[index] - cost[index]，ret 表示的是在i位置開始循環時剩余的油量

a到達的最大路徑假設是f那么我們可以得出 a + b + c + d + e +f < 0? 那么從b開始的話到達f那也是小于0的無法循環（b是正數 即只能從正的位置開始循環）

代碼：

    public static int canCompleteCircuit(int[] gas, int[] cost) {int n = gas.length,step = 0;for (int i = 0; i < n; i++) {int ret = 0;for( step = 0; step < n;step++){int index = (step + i) % n;ret = ret + gas[index] - cost[index];if(ret < 0){break;}}if(ret >= 0){return i ;}
//更新i要滿足兩個條件，首先是要step循環要結束，
//同時要判斷i坐標下的ret小于0，即該位置下的最大step 
//同時如果 ret = 0時就需要再更新i坐標i = i +step;}return -1;}

2.單調遞增的數字

鏈接：. - 力扣（LeetCode）

?思路：

代碼：

class Solution {public int monotoneIncreasingDigits(int n) {char[] ch = Integer.toString(n).toCharArray();int l = ch.length,i = 0;while(i + 1 < l && ch[i] <= ch[i + 1]) i++;//第一種情況 數組都是單調遞增的 i恰好是在l - 1的位置if(i == l - 1){return n;}//  如果出現連續數字都是相同的情況我們需要把相同的第一個數字減一其他的變為9就好while( i - 1 >= 0 && ch[i] == ch[i - 1])i--;ch[i] --;for(int j = i +1 ; j < l;j++){ch[j] = '9';}return Integer.parseInt(new String(ch));}
}

3.壞了的計算器

題目鏈接：991. 壞了的計算器 - 力扣（LeetCode）

題目給出的處理方式為-1和 *2 ，這里我們采用逆放思想此時的處理方式只有+1 和 /2，分兩種情況討論。

一種是 startValue >= target ，此時逆放推理由target變到startValue，要想增加只能+1.

例如?：startValue = 10 ，target = 4 ，target為偶數除以2只會離startValue越來越小，所以不管奇偶只要+1就好，處理次數為 startValue - target。

第二種 startValue < target ，此時逆反推理偶數先除2更優。target除2之后變小離startValue更近。

證明：x,k為偶數? ? x如果執行先+1操作 假設+k次之后再進行除2操作（最終必須除2因為 target 大于 startValue要變小）就需要執行（k+1）次操作變成（x+k)/2；

? ?如果x先除2未達到startValue之后再進行+1操作 ，只需加k/2次，操作次數為（k/2+1）;

假設：startValue = 3 ，target = 10，由target推理startValue，偶數target先除2變奇數+1target > startValue前提下 再除2。

代碼：

class Solution {public static int brokenCalc(int startValue, int target) {int count = 0;while (target > startValue){if( target% 2 == 0) target /= 2;else target += 1;count++;}return count+ startValue - target;}
}