当前位置：首页 > article >正文

leetcode day32 763+56

article 2025/4/2 12:48:42

763 划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

示例 2：

输入：s = "eccbbbbdec"
输出：[10]

思路：1、找每个字母出现的最远边界 $\rightarrow$ last[s[i]-'a']=i

2、遍历字符串，如果到达之前遍历的字符串最远位置，说明到了分割点

int max(int a,int b){
    return a>b?a:b;
}
int* partitionLabels(char* s, int* returnSize) {
    int len=strlen(s);
    int last[27]={0};//记录每个字符出现的最远位置
    for(int i=0;i<len;i++){
        last[s[i]-'a']=i;
    }
    int *result=malloc(sizeof(int)*len);
    *returnSize=0;
    int left=0,right=0;
    for(int i=0;i<len;i++){
        right=max(right,last[s[i]-'a']);//取最大值
        if(i==right){//到达最远位置
            result[(*returnSize)++]=right-left+1;
            left=i+1;
        }
    }
    return result;
}

56 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

二维数组按左边界从小到大排序

int cmp(const void *a,const void *b){

int *pa=*(int **)a;

int *pb=*(int **)b;

return pa[0]-pb[0];

}

与之前重复区间那道题类似。数组的大小作为 *returnColumnSizes 数组返回。

二维数组分配内存空间

int **result=(int **)malloc(sizeof(int*)*row);

*returnColumnSizes=malloc(sizeof(int)*row);

for(int i=0;i<row;i++){

result[i]=(int *)malloc(sizeof(int)*2);//分配列数

}

（1）没有重叠或者cnt=0，把左边界和右边界加入数组

（2）有重叠，只需要更新右边界即可。因为左边界已经排过序。

result[cnt-1][1]=max(end,result[cnt-1][1]);


//左边界从小到大排序
int cmp(const void *a,const void *b){
   int *pa=*(int **)a;
   int *pb=*(int **)b;
   return pa[0]-pb[0];
}
int max(int a,int b){
    return a>b?a:b;
}
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {
    int row=intervalsSize;
    //快排
    qsort(intervals,row,sizeof(int **),cmp);
   //分配内存空间
   int **result=(int **)malloc(sizeof(int*)*row);
   *returnColumnSizes=malloc(sizeof(int)*row);
   for(int i=0;i<row;i++){
     result[i]=(int *)malloc(sizeof(int)*2);//分配列数
   }
   //返回的列数
   int cnt=0;
   for(int i=0;i<row;i++){
      int start=intervals[i][0],end=intervals[i][1];
      //没有重叠
      if(cnt==0||result[cnt-1][1]<start){
            returnColumnSizes[0][cnt]=2;//列数为2
            result[cnt][0]=start;
            result[cnt][1]=end;
            cnt++;
      }else{
        //更新右边界的值
         result[cnt-1][1]=max(end,result[cnt-1][1]);
      }
   }
   *returnSize=cnt;//列数
    return result;
}

查看全文

http://www.kler.cn/a/613230.html