leetcode_day34

本文最后更新于 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();// flag用来标记赋值9从哪里开始
// 设置为超限默认值,为了防止第二个for循环在flag没有被赋值的情况下执行
for (int i = strNum.size() - 1; i > 0; i--) {//倒序遍历数位,若连续出现高位大于低位,则连续减一高位并记录计划变为9的位数
if (strNum[i - 1] > strNum[i] ) {//如果出现高位大于低位,则将高位减1,同时记录低位位数为flag
flag = i;
strNum[i - 1]--;
}
}
for (int i = flag; i < strNum.size(); i++) {//由于从后往前,所以最后得到的计划变9位将是最高的,把后面所有数变9只会增大数字从而得到最优解
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;
//0:无覆盖,1:有摄像头,2:有覆盖
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

leetcode_day34
https://novelyear.github.io/2024/07/01/leetcode-day34/
作者
Leoo Yann
更新于
2024年8月18日
许可协议