「代码随想录算法训练营」第二十七天 | 贪心算法 part5
56. 合并区间
题目链接:https://leetcode.cn/problems/merge-intervals/
题目难度:中等
文章讲解:https://programmercarl.com/0056.合并区间.html
视频讲解:https://www.bilibili.com/video/BV1wx4y157nD
题目状态:有思路,嘻嘻🤣
思路:
首先,按照每个区间开头的前后顺序进行排列,然后定义一个vector<int>
类型的变量来保存我们合并的区间,循环遍历每个区间,判断当前合并的区间结尾是否大于等于下一个区间的开头。若大于,表示可以将该区间合并起来,否则,表明下面的区间不会和已经合并的区间有重叠了,将其存入返回变量,并改变其为下一个区间,继续遍历,直到遍历完。
代码:
点击查看代码
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) {
sort(intervals.begin(), intervals.end(), cmp);
vector<vector<int>> res;
vector<int> temp = intervals[0];
for(int i = 1; i < intervals.size(); ++i) {
if(temp[1] >= intervals[i][0]) {
temp[1] = max(temp[1], intervals[i][1]);
} else {
res.push_back(temp);
temp = intervals[i];
}
}
res.push_back(temp);
return res;
}
};
738. 单调递增的数字
题目链接:https://leetcode.cn/problems/monotone-increasing-digits/
题目难度:中等
文章讲解:https://programmercarl.com/0738.单调递增的数字.html
视频讲解:https://www.bilibili.com/video/BV1Kv4y1x7tP
题目状态:没有思路,不嘻嘻😭
思路:
从后往前遍历(这是关键),判断前一位数是否大于后一位数:
- 若大于,将前一位数减1,这表明前一位数已经大于后面的数了,只能将前面的数减1,之后在将后面的数置为9
- 若不大于,则向前继续遍历。
注意要记录最后一个减1的位数的下一个位数,之后要统一将其后面的数置为9.
代码:
点击查看代码
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);
}
};
968. 监控二叉树
题目链接:hhttps://leetcode.cn/problems/binary-tree-cameras/
题目难度:困难
文章讲解:https://programmercarl.com/0968.监控二叉树.html
视频讲解:https://www.bilibili.com/video/BV1SA411U75i
题目状态:看完题目就知道了,要看题解了😭
思路:
首先,明确遍历顺序,要用后序遍历来实现从下往上遍历,因为要避免叶子节点安装监控(这种情况下会产生最大的浪费)。
之后,将节点的状态分为以下几种:
- 本节点没有被摄像头覆盖,用
0
表示; - 本节点上安装摄像头,用
1
表示; - 本节点被摄像头覆盖,用
2
表示。
注意:递归结果是判断该节点是否为nullptr
来结束的,通常节点为nullptr
时说明我们遍历到了叶子节点的下面,那我们要给空节点设置一个状态,为了符合下面判断的逻辑,我们要将空节点设置为状态2
(尽管并没有被覆盖),因为若我们将空节点设置为没有被覆盖的状态,我们就需要将叶子节点设置为状态1
,此时就出现了最大浪费。
下面我们进行单层的逻辑:
- 本节点的左右孩子都有被覆盖,即
left == 2 && right == 2
此时该节点没有被覆盖,因此该节点的状态为0
。 - 本节点的左右孩子中至少有一个是没有被覆盖的,即
left == 0 || right == 0
此时该节点需要对下面的孩子进行覆盖,因此需要将摄像头的个数加一,然后返回状态1
。 - 本节点的左右孩子中至少一个安装了摄像头,即
left == 1 || right == 1
此时该节点处于被覆盖状态,返回状态2
。
注意:当遍历完之后,若发现返回的根结点的状态是0
,摄像头需要加一。
代码:
点击查看代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int res;
int traversal(TreeNode *cur) {
if(cur == nullptr) return 2;
int left = traversal(cur->left);
int right = traversal(cur->right);
if(left == 2 && right == 2) {
return 0;
}
if(left == 0 || right == 0) {
res++;
return 1;
}
if(left == 1 || right == 1) {
return 2;
}
return -1;
}
int minCameraCover(TreeNode* root) {
res = 0;
if(traversal(root) == 0) {
res++;
}
return res;
}
};
热门相关:欧神 林家有女异世归 吹神 邪王独爱:娘子不准逃跑 大首长,小媳妇