【贪心算法】（第十篇）

目录

加油站（medium）

题目解析

讲解算法原理

编写代码

单调递增的数字（medium）

题目解析

讲解算法原理

编写代码

---

加油站（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

在⼀条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有⼀辆油箱容量⽆限的的汽⻋，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油
cost[i] 升。你从其中的⼀个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路⾏驶⼀周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则保证它是唯⼀的。

⽰例1:
输⼊:gas=[1,2,3,4,5],cost=[3,4,5,1,2]
输出:3
解释:
从3号加油站(索引为3处)出发，可获得4升汽油。此时油箱有=0+4=4升汽油开往4号加油站，此时油箱有4-1+5=8升汽油
开往0号加油站，此时油箱有8-2+1=7升汽油
开往1号加油站，此时油箱有7-3+2=6升汽油
开往2号加油站，此时油箱有6-4+3=5升汽油
开往3号加油站，你需要消耗5升汽油，正好⾜够你返回到3号加油站。因此，3可为起始索引。
⽰例2:
输⼊:gas=[2,3,4],cost=[3,4,3]
输出:-1
解释:
你不能从0号或1号加油站出发，因为没有⾜够的汽油可以让你⾏驶到下⼀个加油站。我们从2号加油站出发，可以获得4升汽油。此时油箱有=0+4=4升汽油
开往0号加油站，此时油箱有4-3+2=3升汽油
开往1号加油站，此时油箱有3-3+3=3升汽油
你⽆法返回2号加油站，因为返程需要消耗4升汽油，但是你的油箱只有3升汽油。因此，⽆论怎样，你都不可能绕环路⾏驶⼀周。

提⽰:
◦ gas.length == n
◦ cost.length == n
◦ 1 <= n <= 10(5)
◦ 0 <= gas[i], cost[i] <= 10(4)

讲解算法原理

解法（暴⼒解法->贪⼼）：
暴⼒解法：
a. 依次枚举所有的起点；
b. 从起点开始，模拟⼀遍加油的流程
贪⼼优化：
我们发现，当从 i 位置出发，⾛了 step 步之后，如果失败了。那么 [i, i + step] 这个区间内任意⼀个位置作为起点，都不可能环绕⼀圈。
因此我们枚举的下⼀个起点，应该是 i + step + 1 。

编写代码

c++算法代码：

class Solution
{
public: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; // 求出⾛ step 步之后的下标rest = rest + gas[index] - cost[index];if(rest < 0) break;}if(rest >= 0) return i;i = i + step; // 优化}return -1;}
};

java算法代码：

class Solution
{public int canCompleteCircuit(int[] gas, int[] cost) {int n = gas.length;for(int i = 0; i < n; i++) // 依次枚举所有的起点 {int rest = 0; // 统计净收益int 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;}
}

单调递增的数字（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

当且仅当每个相邻位数上的数字x和y满⾜x<=y时，我们称这个整数是单调递增的。给定⼀个整数n，返回⼩于或等于n的最⼤数字，且数字呈单调递增。
• ⽰例1:
输⼊:n=10
输出:9
• ⽰例2:
输⼊:n=1234
输出:1234
• ⽰例3:
输⼊:n=332
输出:299
• 提⽰:
0<=n<=10^9

讲解算法原理

解法（贪⼼）：
a. 为了⽅便处理数中的每⼀位数字，可以先讲整数转换成字符串；b. 从左往右扫描，找到第⼀个递减的位置；
c. 从这个位置向前推，推到相同区域的最左端；d. 该点的值 -1 ，后⾯的所有数统⼀变成 9 。

编写代码

c++算法代码：

class Solution
{
public: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);}
};

java算法代码：

class Solution
{public int monotoneIncreasingDigits(int n) {// 把数字转化成字符串char[] s = Integer.toString(n).toCharArray();int i = 0, m = s.length;// 找第⼀个递减的位置while(i + 1 < m && s[i] <= s[i + 1]) i++;if(i == m - 1) 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 Integer.parseInt(new String(s));}
}