leetcode 967

问题

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.

Example 1:

1
2
3
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.

Example 2:

1
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 <= 9s

分析

DFS注意corner case

代码

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
class Solution {
public:
    vector<int> numsSameConsecDiff(int N, int K) {
        if (N == 1) {
            return {0,1,2,3,4,5,6,7,8,9};
        }
        
        vector<int> ans;
        for (int i = 1; i <= 9; ++i) {
            dfs(ans, i, N-1, i, K);
        }
        return ans;
    }
    void dfs(vector<int> &ans, int num, int remain, int lastNumber, int K) {
        if (remain == 0) {
            ans.push_back(num);
            return;
        }
        if (K == 0) {  // corner case
            dfs(ans, num*10+lastNumber, remain-1, lastNumber, K);
            return;
        }
        for (auto k: {-K, K}) {
            int nextNumber = lastNumber + k;
            if (nextNumber >= 0 && nextNumber <= 9) {
                dfs(ans, num*10 + nextNumber, remain-1, nextNumber, K);
            }
        }
        return;
    }
};