泉州商城网站开发设计,雄安网站建设,百度左侧排名,长春网站建设找源晟算法训练营 day41 单调递增的数字 买卖股票的最佳时机含手续费
单调递增的数字
738. 单调递增的数字 - 力扣#xff08;LeetCode#xff09;
当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时#xff0c;我们称这个整数是单调递增的。
给定一个整数 n #xff0c…算法训练营 day41 单调递增的数字 买卖股票的最佳时机含手续费
单调递增的数字
738. 单调递增的数字 - 力扣LeetCode
当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时我们称这个整数是单调递增的。
给定一个整数 n 返回 小于或等于 n 的最大数字且数字呈 单调递增 。
例如98一旦出现strNum[i - 1] strNum[i]的情况非单调递增首先想让strNum[i - 1]–然后strNum[i]给为9这样这个整数就是89即小于98的最大的单调递增整数。
局部最优遇到strNum[i - 1] strNum[i]的情况让strNum[i - 1]–然后strNum[i]给为9可以保证这两位变成最大单调递增整数。
全局最优得到小于等于N的最大单调递增的整数。
但这里局部最优推出全局最优还需要其他条件即遍历顺序和标记从哪一位开始统一改成9。
举个例子数字332从前向后遍历的话那么就把变成了329此时2又小于了第一位的3了真正的结果应该是299。
所以从前后向遍历会改变已经遍历过的结果
那么从后向前遍历就可以重复利用上次比较得出的结果了从后向前遍历332的数值变化为332 - 329 - 299
class Solution {public int monotoneIncreasingDigits(int n) {String s n;char[] c s.toCharArray();int flag c.length;for (int i c.length-1; i0; i--) {if (c[i-1]c[i]){flag i;c[i-1]--;}}for (int i flag; i c.length; i) {c[i]9;}return Integer.parseInt(String.valueOf(c));}
}买卖股票的最佳时机含手续费
714. 买卖股票的最佳时机含手续费 - 力扣LeetCode
给定一个整数数组 prices其中 prices[i]表示第 i 天的股票价格 整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易但是你每笔交易都需要付手续费。如果你已经购买了一个股票在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意这里的一笔交易指买入持有并卖出股票的整个过程每笔交易你只需要为支付一次手续费。
如果使用贪心策略就是最低值买最高值如果算上手续费还盈利就卖。
此时无非就是要找到两个点买入日期和卖出日期。
买入日期其实很好想遇到更低点就记录一下。卖出日期这个就不好算了但也没有必要算出准确的卖出日期只要当前价格大于最低价格手续费就可以收获利润至于准确的卖出日期就是连续收获利润区间里的最后一天并不需要计算是具体哪一天。
所以我们在做收获利润操作的时候其实有三种情况
情况一收获利润的这一天并不是收获利润区间里的最后一天不是真正的卖出相当于持有股票所以后面要继续收获利润。情况二前一天是收获利润区间里的最后一天相当于真正的卖出了今天要重新记录最小价格了。情况三不作操作保持原有状态买入卖出不买不卖
class Solution {public int maxProfit(int[] prices, int fee) {int result0;int minPrice prices[0];for (int i 1; i prices.length; i) {if (prices[i]minPrice){minPrice prices[i];}if (prices[i]minPriceprices[i]minPricefee){}if (prices[i]minPricefee){resultprices[i]-minPrice-fee;minPriceprices[i]-fee;}}return result;}
}
