力扣1215-步进数

  |  

摘要: 设计题

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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