前言:以下全部都是关于重叠问题的题目。
一、435. 无重叠区间
首先需要排序,这里选择快排接口,对于二维数组的快排,需要注意:
1 compare函数怎么编写,这里花费很多时间,compare比较的是右边界,如果右边界一样,比较左边界。
2 快排参数定义:
qsort(intervals, intervalsSize, sizeof(intervals[0]), compare);
//第一个参数是数组地址
//第二个参数是数组的size
//第三个参数是数组元素有多少字节,比如此题目二维数组的元素是一维数组,sizeof(arr[0])这里是2个int类型
//第四个参数是compare
//注意compare用法
int compare(const void* e1, const void* e2)
{
int* p1 = *(int**)e1;
int* p2 = *(int**)e2;
//如果右边界相同,那么比较左边界
return p1[1] == p2[1]? p1[0] - p2[0] : p1[1] - p2[1];
}
在排序状态下,分析区间:
int compare(const void* e1, const void* e2)
{
int* p1 = *(int**)e1;
int* p2 = *(int**)e2;
return p1[1] == p2[1]? p1[0] - p2[0] : p1[1] - p2[1];
}
int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize) {
*intervalsColSize = 2;
//int row = sizeof(intervals)/sizeof(intervals[0][0]);
qsort(intervals, intervalsSize, sizeof(intervals[0]), compare);
// for(int i = 0 ; i < intervalsSize; i++)
// {
// printf("No.%d = %d\n", i, intervals[i][1]);
// }
int end = intervals[0][1];
int count = 0;
for(int i = 1; i < intervalsSize; i++)
{
if(end <= intervals[i][0])//当前区间没有重复的,跳入下一个区间
{
end = intervals[i][1];
}
else
{
count++;//有重复的 加1
}
}
return count;
}
二、763.划分字母区间
划分字母区间,首先需要记录每个字母出现的最大位置,如果这个从开始遍历到最大位置,如果满足,那么就是一个区间。
int* partitionLabels(char* s, int* returnSize) {
int len = strlen(s);
*returnSize = 0;
if(len <= 0)
{
return 0;
}
int* result = (int*)calloc(501, sizeof(int));//malloc(sizeof(int) * 501);
int left = 0;
int right = 0;
int hash[27] = {0};
for(int i = 0; i < len; i++)
{
hash[s[i] - 'a'] = i;
}
for(int i = 0; i < len; i++)
{
right = right > hash[s[i] - 'a']? right : hash[s[i] - 'a'];
if(i == right)
{
result[(*returnSize)++] = right - left + 1;
left = i + 1;
}
}
return result;
}
三、56 合并区间
注意两点:1)按照左边界排序;2)如果有重复区域,更新右边界。
int compare(const void* e1, const void* e2)
{
int* p1 = *(int**)e1;
int* p2 = *(int**)e2;
return p1[0] - p2[0];
}
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {
*returnSize = 0;
*returnColumnSizes = (int*)calloc(intervalsSize, sizeof(int));
if(intervalsSize == 0)
{
return NULL;
}
int** result = (int**)malloc(sizeof(int*) * intervalsSize);
for(int i = 0; i < intervalsSize; i++)
{
result[i] = (int*)calloc(2, sizeof(int));//malloc(sizeof(int) * 2);
}
int count = 0;
qsort(intervals, intervalsSize, sizeof(intervals[0]), compare);
//memcpy(result[0], intervals[0], sizeof(int) * 2);
for(int i = 0; i < intervalsSize; i++)
{
// 记录区间的左右边界
int L = intervals[i][0], R = intervals[i][1];
// 如果count为0或者前一区间的右区间小于此时的左边,加入结果中
if (count == 0 || result[count - 1][1] < L) {
returnColumnSizes[0][count] = 2;
result[count][0] = L;
result[count][1] = R;
count++;
}
else{ // 更新右边界的值
result[count - 1][1] = R > result[count -1][1]? R : result[count - 1][1];
}
}
*returnSize = count;
return result;
}
四、单调递增数字
注意点:1 flag初始位置是在最末端,当发生非递增关系才会变化;
2 数字转字符串的方式;
3 字符串转数字。
int monotoneIncreasingDigits(int n) {
char str[11];
// 将数字转换为字符串
sprintf(str, "%d", n);
int len = strlen(str);
int flag = len;
for(int i = len -1; i > 0; i--)
{
if(str[i - 1] > str[i])
{
str[i - 1]--;
flag = i;
}
}
for(int i = flag; i < len; i++)
{
str[i] = '9';
}
return atoi(str);
}
五、968 监控二叉树
思路:局部最优:让叶子节点的父节点安摄像头,所用摄像头最少,整体最优:全部摄像头数量所用最少!
然后是分情况分析:
有如下三种:
- 该节点无覆盖
- 本节点有摄像头
- 本节点有覆盖
我们分别有三个数字来表示:
- 0:该节点无覆盖
- 1:本节点有摄像头
- 2:本节点有覆盖
int result;
int travel(struct TreeNode* cur)
{
if(!cur)
{
return 2;
}
int left = travel(cur->left);
int right = travel(cur->right);
//若左右孩子都可以被摄像头覆盖,将父亲结点状态设为0
if(left== 2 && right ==2)
{
return 0;
}
//若左右孩子有一个结点状态为没有被覆盖(0),则将父亲结点状态设置为摄像头
if(left == 0 || right == 0) {
result++;
return 1;
}
//若左右孩子有一个为摄像头,证明父亲结点可以被覆盖。将父亲结点状态变为2
if(left == 1 || right == 1)
return 2;
//逻辑不会走到-1,语句不会执行
return -1;
}
int minCameraCover(struct TreeNode* root) {
result = 0;
if(travel(root) == 0)
{
result++;
}
return result;
}