【LeetCode#第228题】汇总区间(简单题)

发布于:2025-06-23 ⋅ 阅读:(22) ⋅ 点赞:(0)

228. 汇总区间 - 力扣(LeetCode)

给定一个  无重复元素 的 有序 整数数组 nums 。

区间 [a,b] 是从 a 到 b(包含)的所有整数的集合。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说,nums 的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个区间但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出:

  • "a->b" ,如果 a != b
  • "a" ,如果 a == b
示例 1:

输入:nums = [0,1,2,4,5,7]
输出:["0->2","4->5","7"]
解释:区间范围是:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"
示例 2:

输入:nums = [0,2,3,4,6,8,9]
输出:["0","2->4","6","8->9"]
解释:区间范围是:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"
 

提示:

0 <= nums.length <= 20
-231 <= nums[i] <= 231 - 1
nums 中的所有值都 互不相同
nums 按升序排列

算法设计

在开始设计之前,我们必须明确一点,题目上说的是有序整数,传达了两个信息:

1. 输入数组中的元素是按从小到大顺序排列的,我们在分割区间时无需考虑大小混乱问题

2. 泛指了所有的整数,包括十进制表述下位数较大的数,和负数,这就需要我们合理的选择整形元素转化为字符串的方法

在C99标准中有一个函数叫做sprintf,原型sprintf(char* head, char* inputstr, int dval, char cval...)

所以 如果我们想表示-2048 -> 0 就可以写为

static int a= -2048;
static int b;
static char* pointer=(char *)malloc(sizeof(char)*25);
sprintf(pointer, "%d->%d", a, b);

此外,在做这道题之前,我们必须对堆段内存分配和二维数组(指针的指针)进行深入的理解。

首先,题目没有给我们返回数组,我们必须在函数中用malloc在堆段内开一片内存用来存放区间字符串,而区间字符串必须以二维结构存储。这要求我们做以下步骤:

1. 声明一个指针的指针

char** ret=NULL;

2. 对二级指针进行初始化(代表行),相当于先用malloc在堆开辟一块用于存字符串首地址的内存,把这片内存本身的首地址赋给在静态段/栈段的二维指针变量

*(ret)=malloc(20*sizeof(char *));

3. 对一级指针进行初始化,把字符串首地址给存首地址的指针变量。

(*(ret)+n)=(char*)malloc(25*sizeof(char))

4. 返回ret指向的所有内容

5. free掉所有字符串内存和存储首地址的指针内存(考试时可能不需要)

好的,那么接下来规划以下我们的算法

1. 定义一个慢指针slow,快指针fast,慢指针负责保持目前区间的下限,快指针负责寻找上线

2. 进入循环fast=0开始,直到fast遍历完表尾

3. 如果在表尾,则判断目前fast是否和slow重合(重合说明是单元素,而非区间),若重合,则将重合指向的元素装入对应字符串,若不重合,则将fast与slow指向的元素以->区间形式装入字符串

4. 如果非表尾,则重复3中的判断,但在末尾需要对slow移动(3 4分开写的原因是,如果表尾移动slow可能会访问越界)

5. 赋值大小,返回指针

char** summaryRanges(int* nums, int numsSize, int* returnSize) {
    int slow=0,fast;
    int rows=0;
    char** Ranges=malloc(20*sizeof(char*));
    for(fast=0; fast<numsSize; fast++){
        if(fast==numsSize-1){
            *(Ranges+rows)=(char*)malloc(sizeof(char)*25);
            if(fast==slow){
                sprintf(*(Ranges+rows), "%d", *(nums+slow));
            }
            else{
               sprintf(*(Ranges+rows), "%d->%d",*(nums+slow),*(nums+fast));
            }
            rows++;
        }
        else if(*(nums+fast)!=*(nums+fast+1)-1){
            *(Ranges+rows)=(char*)malloc(sizeof(char)*25);
            if(fast==slow){
                sprintf(*(Ranges+rows), "%d", *(nums+slow));
            }
            else{
               sprintf(*(Ranges+rows), "%d->%d",*(nums+slow),*(nums+fast));
            }
            rows++;
            slow=fast+1;
        }
    }
    *(returnSize)=rows;
    return Ranges;
}


网站公告

今日签到

点亮在社区的每一天
去签到