算法奇妙屋(四十一)-贪心算法学习之路 8

文章目录一. 力扣 [134. 加油站](https://leetcode.cn/problems/gas-station/description/)1. 题目解析2. 算法原理3. 代码二. 力扣 [738. 单调递增的数字](https://leetcode.cn/problems/monotone-increasing-digits/description/)1. 题目解析2. 算法原理3. 代码一. 力扣134. 加油站1. 题目解析这里要求从i出发, 最后还要能回到i, 形成回路2. 算法原理这道题先写出暴力(枚举)解法, 然后在其基础上进行优化, 即可将时间复杂度降为O(N)3. 代码暴力解法(超时)classSolution{publicintcanCompleteCircuit(int[]gas,int[]cost){intngas.length;int[]diffnewint[n];for(inti0;in;i){diff[i]gas[i]-cost[i];}for(inti0;in;i){intprofit0;intj0;for(;jn;j){profitdiff[(ij)%n];if(profit0){break;}}if(profit0){returni;}}return-1;}}贪心优化classSolution{publicintcanCompleteCircuit(int[]gas,int[]cost){intngas.length;int[]diffnewint[n];for(inti0;in;i){diff[i]gas[i]-cost[i];}for(inti0;in;i){intprofit0;intj0;for(;jn;j){profitdiff[(ij)%n];if(profit0){break;}}if(profit0){returni;}iij;// 优化}return-1;}}二. 力扣738. 单调递增的数字1. 题目解析这道题的暴力解法很好想出来, 从当前数开始逐次递减, 直到每个位置都呈现递增即可2. 算法原理暴力解法是将数字变为字符串, 通过比较每个位置的字符即可, 这里图解只画出贪心解法3. 代码暴力解法代码(超时)classSolution{publicintmonotoneIncreasingDigits(intn){while(n9){StringBuildersnewStringBuilder();s.append(n);inti1;for(;is.length();i){if(s.charAt(i)s.charAt(i-1))break;}if(is.length()){returnn;}n--;}returnn;}}贪心解法代码classSolution{publicintmonotoneIncreasingDigits(intn){StringBuildersnewStringBuilder();s.append(n);intlens.length();inti0;// 找最右面呈递减趋势的位置for(;ilen-1;i){if(s.charAt(i)s.charAt(i1))break;}if(ilen-1){returnn;}// 找最左边相同的数字位置charchs.charAt(i);intji;for(;j0;j--){if(s.charAt(j-1)!ch)break;}s.replace(j,j1,String.valueOf((char)(ch-1)));// 该位置之后都变为9for(intkj1;klen;k){s.replace(k,k1,String.valueOf(9));}returnInteger.valueOf(s.toString());}}