网站定制开发特点,网站建设分几种类型,韩国网站免费模板,国内免费商用图片的网站碎碎念#xff1a;加油 参考#xff1a;代码随想录
56. 合并区间
题目链接
56. 合并区间
思想
这道题的核心还是判断重叠区间#xff0c;本题和之前做过的452. 用最少数量的箭引爆气球、435. 无重叠区间的区别在于判断出重叠区间之后的操作#xff0c;本题需要做的是合…碎碎念加油 参考代码随想录
56. 合并区间
题目链接
56. 合并区间
思想
这道题的核心还是判断重叠区间本题和之前做过的452. 用最少数量的箭引爆气球、435. 无重叠区间的区别在于判断出重叠区间之后的操作本题需要做的是合并重叠区间。 首先要让重叠的区间尽可能挨在一起那么就要对区间排序本解法用的是对左边界排序。 遍历所有区间如果当前遍历到的区间的左边界小于等于上一个区间的右边界那么就发生了重叠需要继续合并区间的操作具体做法是修改区间的右边界如果当前遍历到的区间的左边界大于上一个区间的右边界没有发生重叠把上一个区间加入result即可。
题解
class Solution {
public:static bool cmp (const vectorint a, const vectorint b){return a[0] b[0];}vectorvectorint merge(vectorvectorint intervals) {vectorvectorint result;if (intervals.size() 0) return result;sort(intervals.begin(), intervals.end(), cmp);result.push_back(intervals[0]);for (int i 1; i intervals.size(); i) {if (intervals[i][0] result.back()[1]) {result.back()[1] max(intervals[i][1], result.back()[1]);} else {result.push_back(intervals[i]);}}return result;}
};class Solution:def merge(self, intervals: List[List[int]]) - List[List[int]]:result []if len(intervals) 0:return resultintervals.sort(keylambda x:x[0])result.append(intervals[0])for i in range(1, len(intervals)):if result[-1][1] intervals[i][0]:result[-1][1] max(result[-1][1], intervals[i][1])else:result.append(intervals[i])return result反思
不建议像之前一些题的做法一样在原数组上修改防止遍历的时候混乱。
738.单调递增的数字
题目链接
738.单调递增的数字
思想
遍历数字的每一位如果发现两位不符合要求要对前一位减一后一位要取最大的9。应该从后往前遍历否则得到的可能不符合题意。 定义了一个flag表示某一位往后都是9。
题解
class Solution {
public:int monotoneIncreasingDigits(int n) {string str to_string(n);int flag str.size(); for (int i str.size() - 1; i 0; i--) {if (str[i - 1] str[i]) {str[i - 1]--;flag i;}}for (int i flag; i str.size(); i) {str[i] 9;}return stoi(str);}
};class Solution:def monotoneIncreasingDigits(self, n: int) - int:strNum str(n)flag len(strNum)for i in range(len(strNum) - 1, 0, -1):if strNum[i - 1] strNum[i]:flag istrNum strNum[:i - 1] str(int(strNum[i - 1]) - 1) strNum[i:]for i in range(flag, len(strNum)):strNum strNum[:i] 9 strNum[i1:]return int(strNum)反思
传入的是int类型的为了方便遍历把它转换为string类型的。 注意关于flag的处理为什么设置这样的初始值。
