本文最后更新于 2024年8月18日 下午
今日内容:
56. 合并区间
题目:
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] =
[starti, endi] 。请你合并所有重叠的区间,并返回
一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
思路:
与昨天的重叠区间类型问题一样,按开始点排序,有重合就合并,没重合就新维护
忽然诧异怎么这道题显示已解决,查看提交记录发现这道题在几个月前做过,当初WA4发才做出来结果击败5%,真是感慨
回首向来萧瑟处,也无风雨也无晴,虽然一直感觉在蹉跎人生,但实际上我还是有一点小小的进步,加油共勉!
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| class Solution { public: static bool cmp(const vector<int> & a, const vector<int> & b ) { return a[0] < b[0]; } vector<vector<int>> merge(vector<vector<int>>& intervals) { vector<vector<int>> ans; sort(intervals.begin(), intervals.end(), cmp); int left = intervals[0][0], right = intervals[0][1]; for(int i = 0;i < intervals.size();i++) { if(intervals[i][0] > right) { ans.push_back(vector<int>{left, right}); left = intervals[i][0]; right = intervals[i][1]; } right = max(right, intervals[i][1]); } ans.push_back(vector<int>{left, right}); return ans; } };
CPP
|
738. 单调递增的数字
题目:
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y
时,我们称这个整数是单调递增的。
给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增
。
思路:
此题局部最优策略为,如果数字本身就满足“单调递增”要求,则直接返回该数字即可,若出现反例,即高位大于低位,则将高位减1低位置9
将此局部最优策略应用至全局即可得到最优解,具体代码实现方式见注释。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| class Solution { public: int monotoneIncreasingDigits(int N) { string strNum = to_string(N); 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); } };
CPP
|
968. 监控二叉树
题目:
给定一个二叉树,我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
思路:
不会做😭,抄了
由于涉及二叉树,可以套路化地想到尝试递归遍历,题目所求最少摄像头数量,最少一般是贪心或者dp,那就得分析状态,考虑局部最优全局最优或者状态之间的转移。
在这道题中,一个节点的状态有三种:放了摄像头+被覆盖+没覆盖,关于二叉树的状态容易联想到从两个子树的状态得到当前root树的状态,那么又可以想到:如果子树的根left或者right有摄像头+仅仅被覆盖+没被覆盖这三种状态,这三种状态转移到整个树的状态的方式就为:
1. 如果left或right有一个没被覆盖,则root需要放置摄像头; 2.
如果left或者right有一个有摄像头,则root不需要放置; 3.
如果left和right都只是被覆盖,那么root需要补一个摄像头。
但这并没有取最优化,仅仅只是状态转移,所以不是dp。
dp做法官方题解和灵神的不太一样,树形dp没看懂,dp做法以后再看吧。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| class Solution { public: int result = 0; int traversal(TreeNode* root) { if(root == nullptr) return 2;
int left = traversal(root->left); int right = traversal(root->right);
if(left == 0 || right == 0) { result++; return 1; } else if(left == 1 || right == 1) { return 2; } else { return 0; } return 0; } int minCameraCover(TreeNode* root) { if(traversal(root) == 0) result++; return result; } };
CPP
|