上海工程网站建设,网页设计与制作第三版,聚名,雄县网站制作建设中心目录 加油站#xff08;medium#xff09;
题目解析
讲解算法原理
编写代码
单调递增的数字#xff08;medium#xff09;
题目解析
讲解算法原理
编写代码 加油站#xff08;medium#xff09;
题目解析
1.题目链接#xff1a;. - 力扣#xff08;LeetCodemedium
题目解析
讲解算法原理
编写代码
单调递增的数字medium
题目解析
讲解算法原理
编写代码 加油站medium
题目解析
1.题目链接. - 力扣LeetCode
2.题目描述 在⼀条环路上有 n 个加油站其中第 i 个加油站有汽油 gas[i] 升。你有⼀辆油箱容量⽆限的的汽⻋从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的⼀个加油站出发开始时油箱为空。 给定两个整数数组 gas 和 cost 如果你可以按顺序绕环路⾏驶⼀周则返回出发时加油站的编号否则返回 -1 。如果存在解则保证它是唯⼀的。 ⽰例1: 输⼊:gas[1,2,3,4,5],cost[3,4,5,1,2] 输出:3 解释: 从3号加油站(索引为3处)出发可获得4升汽油。此时油箱有044升汽油开往4号加油站此时油箱有4-158升汽油 开往0号加油站此时油箱有8-217升汽油 开往1号加油站此时油箱有7-326升汽油 开往2号加油站此时油箱有6-435升汽油 开往3号加油站你需要消耗5升汽油正好⾜够你返回到3号加油站。因此3可为起始索引。 ⽰例2: 输⼊:gas[2,3,4],cost[3,4,3] 输出:-1 解释: 你不能从0号或1号加油站出发因为没有⾜够的汽油可以让你⾏驶到下⼀个加油站。我们从2号加油站出发可以获得4升汽油。此时油箱有044升汽油 开往0号加油站此时油箱有4-323升汽油 开往1号加油站此时油箱有3-333升汽油 你⽆法返回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(vectorint gas, vectorint 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满⾜xy时我们称这个整数是单调递增的。给定⼀个整数n返回⼩于或等于n的最⼤数字且数字呈单调递增。 • ⽰例1: 输⼊:n10 输出:9 • ⽰例2: 输⼊:n1234 输出:1234 • ⽰例3: 输⼊:n332 输出:299 • 提⽰: 0n10^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));}
}
