點贊????收藏????關注????
你的支持是對我最大的鼓勵，我們一起努力吧!????

1.壞了的計算器

題目鏈接： 991. 壞了的計算器

題目分析：

算法原理：

解法一：正向推導

以3轉化成10為例，我們正向推導有兩個操作x2，-1。

此時拿到3要么x2，要么-1，此時我們有一個小貪心的想法，為了更快到達，所以選擇x2，得到6，這里也有兩種選擇要么x2，要么-1，如果延續剛才的貪心我們會x2，得到12，此時12比10大了，我們只能執行-1操作，得到11，再執行依次-1操作得到10，這里我們共進行了4次操作

但是我們發現如果再6的時候，不去x2，而去-1，得到5，然后在去x2，就得到10，總共才3次操作，反而比剛才的小貪心更優。

所以說在面臨一個數的時候，是x2 還是 -1操作，判斷標準其實是依賴后面的數來判斷前面是x2還是-1好。所以說如果正向推導有點難，我們可以嘗試另一個思路。

解法二：正難則反

我們這道題明顯可能反著來做，x2和-1 操作 可以變成/2和+1 操作。所以說我們能正向從3推導到10，那肯定能逆向推導回去。

假設我們要從end轉化成begin（10 -> 3）

正著難推導，難道逆著就好推導嗎？確實是的，原因就在于這里/2操作，別忘了我們這道題是沒有小數的，沒有小數，那誰才能執行/2操作？那肯定是偶數，偶數/2能除盡，奇數/2除不盡。

所以面對奇數的時候只能執行+1操作，面對偶數我們在分情況討論是/2還是+1。

1. end <= begin

奇數依舊+1，當end <= begin的時候，偶數此時就沒有必要執行/2操作。因為此時end都比begin小了難道你要/2之后在加1嗎？那不如直接加1好了。所以end <= begin，奇數+1，偶數+1，而且這個+1操作也不用一次一次算，我們僅需 begin - end就得到要執行幾次+1了。

2. end > begin

奇數依舊+1，偶數要么/2，要么+1，此時這里我們有一個小貪心，因為end大于begin，我們想最少操作次數到達begin所以我們看似選擇/2是更優的。

那這個貪心的想法對不對呢?

我們證明一下先除更優。

假設x是個偶數，并且大于begin。
如果不執行/2操作，而執行+1操作，那會得到一個奇數，但是奇數只能加1，然后又變成偶數了，又執行+1操作，又變成奇數，奇數只能+1，又變成偶數了。假設x一共加了k個1。這個k也是個偶數，如果k是奇數接下來還要+1總歸要把它先加成一個偶數才行。

x + k 是大于 begin，必然會執行一次 / 2操作，你想把大的數變成小的數不執行除法操作怎么才能變小呢？所以無論加上多少1最終都會執行一次/2操作，變成(x+k)/2，次數這種操作執行的次數就是 k + 1次

但是如果拿x這個數變成(x+k)/2，先執行/2操作變成 x/2，然后僅需在x/2的基礎上加上k/2，就得到(x+k)/2，這種執行操作次數是 1 + k/2次，是比上面執行次數小的。

所以說當 end > begin ，面對偶數我們也不需要分類討論，僅需執行/2操作。奇數+1，偶數/2，一直到end <= begin的時候，執行begin - end就可以得到整個操作次數。

class Solution {
public:int brokenCalc(int startValue, int target) {// 正難則反 + 貪心int ret = 0;while(target > startValue){if(target % 2) target++;else target /= 2;++ret;}return ret + startValue - target;}
};

2.合并區間

題目鏈接： 56. 合并區間

題目分析：

給一個二維矩陣，每一行表示一個區間，里面有兩個元素第一個表示左端點，第二個表示右端點，請你合并所有重疊的區間，并返回 一個不重疊的區間數組，該數組需恰好覆蓋輸入中的所有區間 。

有重疊的部分合并相當于就是求并集。注意示例2這個特殊的情況[1,4]和[4,5]也需要合并，也就是僅有一個點重疊也是可以合并。

算法原理：

關于貪心里面的區間問題的解法，我們都是固定的解法。

1. 排序
2. 根據排序后的結果，總結出一些規律，進而得出解決這個問題的策略

關于第2點也可以先提出一個解決問題的策略，進而總結出一些規律。

關于第1點排序，是分為兩大類的，其中第一類是按照左