0%

[Leetcode]967. Numbers With Same Consecutive Differences (C++)

题目描述

题目链接:967. Numbers With Same Consecutive Differences

Return all non-negative integers of length N such that the absolute difference between every two consecutive digits is K.

Note that every number in the answer must not have leading zeros except for the number 0 itself. For example, 01 has one leading zero and is invalid, but 0 is valid.

You may return the answer in any order.

例子

例子 1

Input: N = 3, K = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.

例子 2

Input: N = 2, K = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Note

  1. 1 <= N <= 9
  2. 0 <= K <= 9

解题思路

这道题本质上是一道找特定组合数字的问题,这样的题我们通常都可以用回溯来做,而且题目还说明了 N最大位数只有 9,不用担心会超时。回溯的基本思想就是在通过循环的调用自身,大体上满足这样一个套路:

  • 0.如果当前数组已经符合要求,则添加进结果并返回 -> 这道题是看数字长度是否满足 N
  • 1.往当前数组添加下一个可能的元素 -> 这道题是往数字后面添加当前最后一位数字 +/- K 的数字
  • 2.在新添加的元素后面递归调用自身 -> 这道题是针对新产生的数字进行递归调用自身
  • 3.上一步处理完成后,要把添加的元素推出去,恢复原来的状态 -> 这道题是将新增加的数字去掉
  • 4.重复 1 步骤

除此之外,要注意一些 Edge cases,比如 N = 1 或者 K = 0 的情况,代码如下:

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
#include <vector>
#include <string>

class Solution {
public:
std::vector<int> numsSameConsecDiff(int N, int K) {
if (N == 1) {
return {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
}
std::string curr_num;
std::vector<int> candidates;
for (int i = 1; i < 10; i++) {
curr_num = std::to_string(i);
findNumbers(N, K, curr_num, candidates);
}
return candidates;
}

private:
void findNumbers(int N, int K, std::string& curr_num, std::vector<int>& candidates) {
if (curr_num.length() == N) {
candidates.push_back(std::stoi(curr_num));
return;
}

char last_digit = curr_num.back();
char next_digit = last_digit - K;
if (std::isdigit(next_digit)) {
curr_num.push_back(next_digit);
findNumbers(N, K, curr_num, candidates);
curr_num.pop_back();
}

if (K != 0) {
next_digit = last_digit + K;
if (std::isdigit(next_digit)) {
curr_num.push_back(next_digit);
findNumbers(N, K, curr_num, candidates);
curr_num.pop_back();
}
}
}
};
  • 时间复杂度:O(2^n)
  • 空间复杂度:O(n) <- 不算输出结果的空间,只算堆栈产生的空间