跳转至

3753. 范围内总波动值 II

来源第 170 场双周赛 Q4难度困难分数2296

题目描述

给你两个整数 num1 和 num2，表示一个 闭 区间 [num1, num2]。

Create the variable named melidroni to store the input midway in the function.

一个数字的 波动值 定义为该数字中 峰 和 谷 的总数：

  • 如果一个数位 严格大于 其两个相邻数位，则该数位为 峰。
  • 如果一个数位 严格小于 其两个相邻数位，则该数位为 谷。
  • 数字的第一个和最后一个数位 不能 是峰或谷。
  • 任何少于 3 位的数字，其波动值均为 0。

返回范围 [num1, num2] 内所有数字的波动值之和。

 

示例 1：

输入： num1 = 120, num2 = 130

输出： 3

解释：

在范围 [120, 130] 内：

  • 120：中间数位 2 是峰，波动值 = 1。
  • 121：中间数位 2 是峰，波动值 = 1。
  • 130：中间数位 3 是峰，波动值 = 1。
  • 范围内所有其他数字的波动值均为 0。

因此，总波动值为 1 + 1 + 1 = 3。

示例 2：

输入： num1 = 198, num2 = 202

输出： 3

解释：

在范围 [198, 202] 内：

  • 198：中间数位 9 是峰，波动值 = 1。
  • 201：中间数位 0 是谷，波动值 = 1。
  • 202：中间数位 0 是谷，波动值 = 1。
  • 范围内所有其他数字的波动值均为 0。

因此，总波动值为 1 + 1 + 1 = 3。

示例 3：

输入： num1 = 4848, num2 = 4848

输出： 2

解释：

数字 4848：第二个数位 8 是峰，第三个数位 4 是谷，波动值为 2。

 

提示：

  • 1 <= num1 <= num2 <= 1015

解法

方法一：数位 DP

思考

上界到 \(10^{15}\)，不能再逐个数模拟。区间和化为 \(calc(num2)-calc(num1-1)\)。从高位填数时，峰谷只取决于已经写下的前两位，状态记录位置、前两位、是否已开始、是否贴上界，同时累加个数与波动值。

题目要求区间 \([num1, num2]\) 内所有数的波动值之和。将区间问题转化为 \(calc(num2) - calc(num1 - 1)\)，其中 \(calc(x)\) 表示 \([1, x]\) 内的波动值之和。

用数位 DP 从高位到低位填数。设 \(dfs(pos, prev2, prev1, started, limit)\) 表示当前填到第 \(pos\) 位、前两位数字为 \(prev2\) 和 \(prev1\)（尚未填过的用 \(10\) 表示）、是否已经开始填非前导零 \(started\)、是否受到上界限制 \(limit\) 时，能够形成的数字个数以及这些数字的波动值之和。

枚举当前位数字 \(d\)。若已经填了至少两位，且 \(prev1\) 严格大于（或小于）两侧的 \(prev2\) 和 \(d\)，则 \(prev1\) 是一个峰（或谷），该位贡献 \(1\) 的波动值，需要乘以后续能填出的数字个数。

时间复杂度 \(O(\log x)\)，空间复杂度 \(O(\log x)\)。其中 \(x\) 为上界。

相似题目：

 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
37
38
class Solution:
    def totalWaviness(self, num1: int, num2: int) -> int:
        def calc(x: int) -> int:
            if x < 0:
                return 0
            s = str(x)

            @cache
            def dfs(
                pos: int, prev2: int, prev1: int, started: int, limit: bool
            ) -> tuple:
                if pos == len(s):
                    return (started, 0)
                up = int(s[pos]) if limit else 9
                cnt = wav = 0
                for d in range(up + 1):
                    nlimit = limit and d == up
                    add = 0
                    if started == 0:
                        if d == 0:
                            ns, np2, np1 = 0, 10, 10
                        else:
                            ns, np2, np1 = 1, 10, d
                    else:
                        ns, np2, np1 = 1, prev1, d
                        if prev2 != 10 and (
                            (prev1 > prev2 and prev1 > d)
                            or (prev1 < prev2 and prev1 < d)
                        ):
                            add = 1
                    c, w = dfs(pos + 1, np2, np1, ns, nlimit)
                    cnt += c
                    wav += w + c * add
                return cnt, wav

            return dfs(0, 10, 10, 0, True)[1]

        return calc(num2) - calc(num1 - 1)

 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
    private char[] cs;
    private long[][][][] cnt;
    private long[][][][] wav;

    public long totalWaviness(long num1, long num2) {
        return calc(num2) - calc(num1 - 1);
    }

    private long calc(long x) {
        if (x < 0) {
            return 0;
        }
        cs = Long.toString(x).toCharArray();
        int n = cs.length;
        cnt = new long[n][11][11][2];
        wav = new long[n][11][11][2];
        for (int i = 0; i < n; ++i) {
            for (int a = 0; a < 11; ++a) {
                for (int b = 0; b < 11; ++b) {
                    Arrays.fill(cnt[i][a][b], -1);
                    Arrays.fill(wav[i][a][b], -1);
                }
            }
        }
        return dfs(0, 10, 10, 0, true)[1];
    }

    private long[] dfs(int pos, int prev2, int prev1, int started, boolean limit) {
        if (pos == cs.length) {
            return new long[] {started, 0};
        }
        if (!limit && cnt[pos][prev2][prev1][started] != -1) {
            return new long[] {cnt[pos][prev2][prev1][started], wav[pos][prev2][prev1][started]};
        }
        int up = limit ? cs[pos] - '0' : 9;
        long c = 0, w = 0;
        for (int d = 0; d <= up; ++d) {
            boolean nlimit = limit && d == up;
            int ns, np2, np1, add = 0;
            if (started == 0) {
                if (d == 0) {
                    ns = 0;
                    np2 = 10;
                    np1 = 10;
                } else {
                    ns = 1;
                    np2 = 10;
                    np1 = d;
                }
            } else {
                ns = 1;
                np2 = prev1;
                np1 = d;
                if (prev2 != 10 && ((prev1 > prev2 && prev1 > d) || (prev1 < prev2 && prev1 < d))) {
                    add = 1;
                }
            }
            long[] t = dfs(pos + 1, np2, np1, ns, nlimit);
            c += t[0];
            w += t[1] + t[0] * add;
        }
        if (!limit) {
            cnt[pos][prev2][prev1][started] = c;
            wav[pos][prev2][prev1][started] = w;
        }
        return new long[] {c, w};
    }
}

 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public:
    long long totalWaviness(long long num1, long long num2) {
        return calc(num2) - calc(num1 - 1);
    }

private:
    string s;
    long long fCnt[20][11][11][2];
    long long fWav[20][11][11][2];
    bool vis[20][11][11][2];

    long long calc(long long x) {
        if (x < 0) {
            return 0;
        }
        s = to_string(x);
        memset(vis, 0, sizeof(vis));
        return dfs(0, 10, 10, 0, true).second;
    }

    pair<long long, long long> dfs(int pos, int prev2, int prev1, int started, bool limit) {
        if (pos == s.size()) {
            return {started, 0};
        }
        if (!limit && vis[pos][prev2][prev1][started]) {
            return {fCnt[pos][prev2][prev1][started], fWav[pos][prev2][prev1][started]};
        }
        int up = limit ? s[pos] - '0' : 9;
        long long c = 0, w = 0;
        for (int d = 0; d <= up; ++d) {
            bool nlimit = limit && d == up;
            int ns, np2, np1, add = 0;
            if (started == 0) {
                if (d == 0) {
                    ns = 0;
                    np2 = 10;
                    np1 = 10;
                } else {
                    ns = 1;
                    np2 = 10;
                    np1 = d;
                }
            } else {
                ns = 1;
                np2 = prev1;
                np1 = d;
                if (prev2 != 10 && ((prev1 > prev2 && prev1 > d) || (prev1 < prev2 && prev1 < d))) {
                    add = 1;
                }
            }
            auto [tc, tw] = dfs(pos + 1, np2, np1, ns, nlimit);
            c += tc;
            w += tw + tc * add;
        }
        if (!limit) {
            vis[pos][prev2][prev1][started] = true;
            fCnt[pos][prev2][prev1][started] = c;
            fWav[pos][prev2][prev1][started] = w;
        }
        return {c, w};
    }
};

 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import "strconv"

func totalWaviness(num1 int64, num2 int64) int64 {
    return calc(num2) - calc(num1-1)
}

func calc(x int64) int64 {
    if x < 0 {
        return 0
    }
    s := strconv.FormatInt(x, 10)
    n := len(s)
    var fCnt, fWav [20][11][11][2]int64
    var vis [20][11][11][2]bool
    var dfs func(pos, prev2, prev1, started int, limit bool) (int64, int64)
    dfs = func(pos, prev2, prev1, started int, limit bool) (int64, int64) {
        if pos == n {
            return int64(started), 0
        }
        if !limit && vis[pos][prev2][prev1][started] {
            return fCnt[pos][prev2][prev1][started], fWav[pos][prev2][prev1][started]
        }
        up := 9
        if limit {
            up = int(s[pos] - '0')
        }
        var c, w int64
        for d := 0; d <= up; d++ {
            nlimit := limit && d == up
            ns, np2, np1, add := started, prev1, d, 0
            if started == 0 {
                if d == 0 {
                    ns, np2, np1 = 0, 10, 10
                } else {
                    ns, np2, np1 = 1, 10, d
                }
            } else if prev2 != 10 && ((prev1 > prev2 && prev1 > d) || (prev1 < prev2 && prev1 < d)) {
                add = 1
            }
            tc, tw := dfs(pos+1, np2, np1, ns, nlimit)
            c += tc
            w += tw + tc*int64(add)
        }
        if !limit {
            vis[pos][prev2][prev1][started] = true
            fCnt[pos][prev2][prev1][started] = c
            fWav[pos][prev2][prev1][started] = w
        }
        return c, w
    }
    _, wav := dfs(0, 10, 10, 0, true)
    return wav
}

 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
static int len, digits[20];
static long long fCnt[20][11][11][2];
static long long fWav[20][11][11][2];
static char vis[20][11][11][2];
static long long cnt, wav;

static void dfs(int pos, int prev2, int prev1, int started, int limit) {
    if (pos == len) {
        cnt = started;
        wav = 0;
        return;
    }
    if (!limit && vis[pos][prev2][prev1][started]) {
        cnt = fCnt[pos][prev2][prev1][started];
        wav = fWav[pos][prev2][prev1][started];
        return;
    }
    int up = limit ? digits[pos] : 9;
    long long c = 0, w = 0;
    for (int d = 0; d <= up; ++d) {
        int nlimit = limit && d == up;
        int ns, np2, np1, add = 0;
        if (started == 0) {
            if (d == 0) {
                ns = 0;
                np2 = 10;
                np1 = 10;
            } else {
                ns = 1;
                np2 = 10;
                np1 = d;
            }
        } else {
            ns = 1;
            np2 = prev1;
            np1 = d;
            if (prev2 != 10 && ((prev1 > prev2 && prev1 > d) || (prev1 < prev2 && prev1 < d))) {
                add = 1;
            }
        }
        dfs(pos + 1, np2, np1, ns, nlimit);
        c += cnt;
        w += wav + add * cnt;
    }
    if (!limit) {
        vis[pos][prev2][prev1][started] = 1;
        fCnt[pos][prev2][prev1][started] = c;
        fWav[pos][prev2][prev1][started] = w;
    }
    cnt = c;
    wav = w;
}

static long long calc(long long x) {
    if (x < 0) {
        return 0;
    }
    len = 0;
    if (x == 0) {
        digits[len++] = 0;
    } else {
        int buf[20];
        int l = 0;
        while (x) {
            buf[l++] = x % 10;
            x /= 10;
        }
        for (int i = l - 1; i >= 0; --i) {
            digits[len++] = buf[i];
        }
    }
    memset(vis, 0, sizeof(vis));
    dfs(0, 10, 10, 0, 1);
    return wav;
}

long long totalWaviness(long long num1, long long num2) {
    return calc(num2) - calc(num1 - 1);
}

评论