[Algorithm][贪心][跳跃游戏][加油站][单调递增的数字][坏了的计算器]详细讲解

---

1.跳跃游戏

1.题目链接

• 跳跃游戏

---

2.算法思路详解

• 贪心：类似层序遍历的过程
  

---

3.代码实现

bool canJump(vector<int>& nums) 
{int left = 0, right = 0, maxPos = 0, n = nums.size();while(left <= right){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;
}

---

2.加油站

1.题目链接

• 加油站

---

2.算法原理详解

• 思路一：暴力解 —> 枚举 —> 会超时:P
  • 依次枚举所有的起点
  • 从起点开始，模拟一遍加油的流程即可
• 思路二：优化暴力解法 —> 找规律(贪心)
  

---

3.代码实现

// v1.0 暴力解
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; // 求出走step步之后的下标rest = rest + gas[index] - cost[index];if(rest < 0){break;}}if(rest >= 0){return i;}}return -1;
}
--------------------------------------------------------------------
// v2.0 贪心
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) 
{int n = gas.size();for(int i = 0; i < n; i++) // 枚举起点{int rest = 0, step = 0;for(; step < n; step++) // 枚举向后走的步数{int index = (i + step) % n; // 求出走step步之后的下标rest = rest + gas[index] - cost[index];if(rest < 0){break;}}if(rest >= 0){return i;}i = i + step; // 优化}return -1;
}

---

3.单调递增的数字

1.题目链接

• 单调递增的数字

---

2.算法原理详解

• 思路一：暴力枚举
  • 从大到小的顺序，枚举[n, 0]区间内的数字
  • 判断数字是否是“单调递增的”
• 思路二：贪心
  • 如果高位单调递增，就不去修改
    • 因为高位如果修改了，那么该数大小会小非常多，影响较大
  • 从左往右，找到第一个递减的位置
    • 从这个位置向前推，推到相同区域的最左端
    • 使其减1，后面的数全部修改成9
      

---

3.代码实现

int monotoneIncreasingDigits(int n) 
{string str = to_string(n); // 把数字转化为字符串，以便逐位操作int i = 0, m = str.size();// 找到第一个递减的位置while(i + 1 < m && str[i] <= str[i + 1]){i++;}// 特判if(i == m - 1){return n;}// 回推while(i - 1 >= 0 && str[i] == str[i - 1]){i--;}// 操作str[i]--;for(int j = i + 1; j < m; j++){str[j] = '9';}return stoi(str);
}

---

4.坏了的计算器

1.代码实现

• 坏了的计算器

---

2.算法原理详解

• 思路一：正向推导，可用DFS解决
  

• 思路二：贪心 --> 正难则反

  • 从目标出发，执行/2或+1操作
    

---

3.代码实现

int brokenCalc(int startValue, int target) 
{int ret = 0;while(target > startValue){if(target % 2 == 0){target /= 2;}else{target += 1;}ret++;}return ret + startValue - target;
}