物流网站公司,江苏seo推广方案,wordpress 微语,网站模版图片56 合并区间
给出一个区间的集合#xff0c;请合并所有重叠的区间。
示例 1:
输入: intervals [[1,3],[2,6],[8,10],[15,18]]输出: [[1,6],[8,10],[15,18]]解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
class Solution {
public:vectorvectorint请合并所有重叠的区间。
示例 1:
输入: intervals [[1,3],[2,6],[8,10],[15,18]]输出: [[1,6],[8,10],[15,18]]解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {vectorvectorint result;if (intervals.size() 0) return result; // 区间集合为空直接返回// 排序的参数使用了lambda表达式sort(intervals.begin(), intervals.end(), [](const vectorint a, const vectorint b){return a[0] b[0];});// 第一个区间就可以放进结果集里后面如果重叠在result上直接合并result.push_back(intervals[0]); for (int i 1; i intervals.size(); i) {if (result.back()[1] intervals[i][0]) { // 发现重叠区间// 合并区间只更新右边界就好因为result.back()的左边界一定是最小值因为我们按照左边界排序的result.back()[1] max(result.back()[1], intervals[i][1]); } else {result.push_back(intervals[i]); // 区间不重叠 }}return result;}
}; 本题主要技巧是在result数组里面进行重叠操作而不是在原数组里面进行合并。 738 单调递增的数字
给定一个非负整数 N找出小于或等于 N 的最大的整数同时这个整数需要满足其各个位数上的数字是单调递增。
当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时我们称这个整数是单调递增的。
示例 1:
输入: N 10输出: 9
示例 2:
输入: N 1234输出: 1234
示例 3:
输入: N 332输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数
本题如果使用暴力解法从后往前一个数一个数的遍历一定会超时所以采用贪心算法
如果前一个数比后一个数大就将后一个数变成9前一个数减1从后往前遍历即可同时在处理变成9的时候不要直接处理而是利用一个flag标志记录此时的位置最后flag后面的所有数一起变成9例如1000如果不用flag的话最后两个00是不会变的
class Solution {
public:int monotoneIncreasingDigits(int N) {string strNum to_string(N);// flag用来标记赋值9从哪里开始// 设置为这个默认值为了防止第二个for循环在flag没有被赋值的情况下执行int flag strNum.size();for (int i strNum.size() - 1; i 0; i--) {if (strNum[i - 1] strNum[i] ) {flag i;strNum[i - 1]--;}}for (int i flag; i strNum.size(); i) {strNum[i] 9;}return stoi(strNum);}
};968 监控二叉树
给定一个二叉树我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 1 输入[0,0,null,0,0]输出1解释如图所示一台摄像头足以监控所有节点。
示例 2 输入[0,0,null,0,null,0,null,null,0]输出2解释需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
提示
给定树的节点数的范围是 [1, 1000]。每个节点的值都是 0。 本题要求的是最少的摄像头所以尽量让叶子节点的父节点为摄像头每隔两层安装一个新的摄像头。于是本题采用后序遍历。 本题分别用数字代表此时的状态0代表这个点没有被覆盖1代表本节点有摄像头2代表本节点被摄像头覆盖。 一共有四种不同情况代码如下
class Solution {
private:int result;int traversal(TreeNode* cur) {// 空节点该节点有覆盖if (cur NULL) return 2;int left traversal(cur-left); // 左int right traversal(cur-right); // 右// 情况1// 左右节点都有覆盖if (left 2 right 2) return 0;// 情况2// left 0 right 0 左右节点无覆盖// left 1 right 0 左节点有摄像头右节点无覆盖// left 0 right 1 左节点有无覆盖右节点摄像头// left 0 right 2 左节点无覆盖右节点覆盖// left 2 right 0 左节点覆盖右节点无覆盖if (left 0 || right 0) {result;return 1;}// 情况3// left 1 right 2 左节点有摄像头右节点有覆盖// left 2 right 1 左节点有覆盖右节点有摄像头// left 1 right 1 左右节点都有摄像头// 其他情况前段代码均已覆盖if (left 1 || right 1) return 2;// 以上代码我没有使用else主要是为了把各个分支条件展现出来这样代码有助于读者理解// 这个 return -1 逻辑不会走到这里。return -1;}public:int minCameraCover(TreeNode* root) {result 0;// 情况4if (traversal(root) 0) { // root 无覆盖result;}return result;}
};
