代码随想录算法训练营第三十一天 | 56、738

算法
, , ,

56. 合并区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package main

import "sort"

func merge(intervals [][]int) [][]int {
    // 如果区间数量小于等于 1，直接返回
    if len(intervals) <= 1 {
        return intervals
    }

    // 按区间的起始位置排序
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    // 初始化结果列表，先将第一个区间加入结果
    merged := [][]int{intervals[0]}

    // 从第二个区间开始遍历
    for i := 1; i < len(intervals); i++ {
        current := intervals[i]
        last := merged[len(merged)-1]

        // 如果当前区间与最后一个区间不重叠
        if current[0] > last[1] {
            merged = append(merged, current)
        } else {
            // 合并区间：更新最后一个区间的结束位置
            if current[1] > last[1] {
                merged[len(merged)-1][1] = current[1]
            }
        }
    }
    return merged
}

738. 单调递增的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package main

import (
    "strconv"
)

func monotoneIncreasingDigits(n int) int {
    if n == 0 {
        return 0
    }
    s := strconv.Itoa(n)
    arr := []byte(s)
    flag := len(arr) // 记录需要置 9 的起始位置

    // 从右向左遍历
    for i := len(arr) - 2; i >= 0; i-- {
        if arr[i] > arr[i+1] {
            arr[i]--     // 当前位减 1
            flag = i + 1 // 更新置 9 的起始位置
        }
    }

    // 从 flag 位置开始，将所有位置为 9
    for i := flag; i < len(arr); i++ {
        arr[i] = '9'
    }

    // 转换回整数
    res, _ := strconv.Atoi(string(arr))
    return res
}