leetcode228：汇总区间（summary-ranges）

carloscn commented 1 year ago

问题描述

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

返回恰好覆盖数组中所有数字的最小有序区间范围列表。也就是说，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 按升序排列

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/summary-ranges

carloscn commented 1 year ago

问题分析：

设定一个伴随coherence值，跟着遍历数组，如果遇到不相等的，就记录字符串，并且记录头和尾的数据：

static inline void strmake(char *str, int64_t head, int64_t tail)
{
    if (head != tail) {
        sprintf(str, "%ld->%ld", head, tail);
    } else {
        sprintf(str, "%ld", head);
    }
}

static int32_t summary_ranges(int64_t *array,
                              size_t sz,
                              STRLIST_T *out_list)
{
    int32_t ret = 0;
    size_t i = 0;
    int64_t header = 0;
    int64_t coherence = 0;
    char buf[DEFAULT_STR_LEN] = { '0' };

    UTILS_CHECK_LEN(sz);
    UTILS_CHECK_PTR(array);
    UTILS_CHECK_PTR(out_list);

    header = coherence = array[0];
    for (i = 0; i < sz + 1; i ++, coherence ++) {
        if ((i > sz) ||
            (coherence != array[i])) {
            strmake(buf, header, array[i-1]);
            strlist_add(out_list, buf);
            coherence = header = array[i];
        }
    }

finish:
    return ret;
}

carloscn commented 1 year ago

code:

https://github.com/carloscn/structstudy/blob/master/c_programming/array/23_summary-ranges_228.c

carloscn / structstudy