营销网站手机站,python 网站开发必会,青岛app开发公司,网站制作评价标准文章参考来源代码随想录 (programmercarl.com)
56. 合并区间
本题和前几题类似#xff0c;都是判断上一个元素的右边界与当前元素的左边界大小关系 但是需要注意是#xff1a;本题需要更新结果数组元素的右边界#xff0c;因此比较的是数组最后一个元素右边界与当前元素左…文章参考来源代码随想录 (programmercarl.com)
56. 合并区间
本题和前几题类似都是判断上一个元素的右边界与当前元素的左边界大小关系 但是需要注意是本题需要更新结果数组元素的右边界因此比较的是数组最后一个元素右边界与当前元素左边界大小通过back方法更新
此外在排序之后结果数组应直接存入目标数组的第一个元素方便之后更新。
class Solution {
public:static bool cmp(vectorinta,vectorintb){return a[0]b[0];}vectorvectorint merge(vectorvectorint intervals) {vectorvectorintresult;sort(intervals.begin(),intervals.end(),cmp);result.push_back(intervals[0]);for(int i1;iintervals.size();i){if(result.back()[1]intervals[i][0]){result.back()[1]max(result.back()[1],intervals[i][1]);}else{result.push_back(intervals[i]);}}return result;}
};
738.单调递增的数字
暴力解法
class Solution {
private:// 判断一个数字的各位上是否是递增bool checkNum(int num) {int max 10;while (num) {int t num % 10;if (max t) max t;else return false;num num / 10;}return true;}
public:int monotoneIncreasingDigits(int N) {for (int i N; i 0; i--) { // 从大到小遍历if (checkNum(i)) return i;}return 0;}
};
贪心算法
例如98一旦出现strNum[i - 1] strNum[i]的情况非单调递增首先想让strNum[i - 1]--然后strNum[i]给为9这样这个整数就是89即小于98的最大的单调递增整数。
这一点如果想清楚了这道题就好办了。
此时是从前向后遍历还是从后向前遍历呢
从前向后遍历的话遇到strNum[i - 1] strNum[i]的情况让strNum[i - 1]减一但此时如果strNum[i - 1]减一了可能又小于strNum[i - 2]。
这么说有点抽象举个例子数字332从前向后遍历的话那么就把变成了329此时2又小于了第一位的3了真正的结果应该是299。
那么从后向前遍历就可以重复利用上次比较得出的结果了从后向前遍历332的数值变化为332 - 329 - 299
所以这里先判断前一个元素是否大于当前元素大于的话flag标记位置前一个元素减小
之后从flag开始到最后一位均赋值为9
flag初始化为s.size
class Solution {
public:int monotoneIncreasingDigits(int n) {string sto_string(n);int flags.size();for(int is.size()-1;i0;i--){if(s[i-1]s[i]){flagi;s[i-1]--;}}for(int iflag;is.size();i){s[i]9;}return stoi(s);}
};
