算法leetcode

力扣1215-步进数

字数统计: 542字   |   阅读时长: 2分
,

摘要: 设计题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们看一个搜索题，主要难点在于搜索过程中需要携带多种信息。

$1 题目

1219. 黄金矿工

如果一个整数上的每一位数字与其相邻位上的数字的绝对差都是 1，那么这个数就是一个「步进数」。

例如，321 是一个步进数，而 421 不是。

给你两个整数，low 和 high，请你找出在 [low, high] 范围内的所有步进数，并返回 排序后 的结果。

提示：

1
0 <= low <= high <= 2 * 10^9

示例：

输入：low = 0, high = 21
输出：[0,1,2,3,4,5,6,7,8,9,10,12,21]

$2 题解

算法: 搜索

从高位向低位搜索，搜索时需要的信息比较多：

1
void dfs(int i, int x, vector<int>& result, const int high)

各个参数的含义如下：

  • 当前的位置 i
  • 已经选中的高位构成的数 x
  • 上限 high
  • 搜到的答案列表 result

当 x = 0 时，当前的选择可以从 0,1,…,9 中选，只要 x <= high 就行。

当x != 0 时，当前的选择需要根据上一位的选择按照步进数的要求选。

代码 (C++)

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 {
public:
    vector<int> countSteppingNumbers(int low, int high) {
        vector<int> cand;
        dfs(9, 0, cand, high);
        vector<int> result;
        for(int x: cand)
        {
            if(x >= low)
                result.push_back(x);
        }
        return result;
    }

private:
    void dfs(int i, int x, vector<int>& result, const int high)
    {
        if(i == -1)
        {
            result.push_back(x);
            return;
        }
        if(x == 0)
        {
            dfs(i - 1, x, result, high);
            for(int d = 1; d <= 9; ++d)
                // if(x <= high - (d * pow(10, i)))
                    dfs(i - 1, x + (d * pow(10, i)), result, high);
            return;
        }
        // 上一位数
        int d = ((x / (int)pow(10, i + 1)) % 10);
        if(d > 0 && x <= high - ((d - 1) * pow(10, i)))
            dfs(i - 1, x + (d - 1) * pow(10, i), result, high);
        if(d < 9 && x <= high - ((d + 1) * pow(10, i)))
            dfs(i - 1, x + (d + 1) * pow(10, i), result, high);
    }
};
Share