题目

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. Input: N = 3, K = 7
  2. Output: [181,292,707,818,929]
  3. Explanation: Note that 070 is not a valid number, because it has leading zeroes.

Example 2:

  1. Input: N = 2, K = 1
  2. 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位数，使得其中每一个数中的每相邻两个位的数字之差为K。

思路

用回溯法去生成每一个这样的N位数。需要注意的坑是N=1时要考虑0，以及K=0时注意剪枝。

代码实现

Java

  1. class Solution {
  2.     public int[] numsSameConsecDiff(int N, int K) {
  3.         List<Integer> list = new ArrayList<>();
  4.         for (int i = N == 1 ? 0 : 1; i < 10; i++) {
  5.             dfs(0, i, 1, N, K, list);
  6.         }
  7.         int[] ans = new int[list.size()];
  8.         int i = 0;
  9.         for (int num : list) {
  10.             ans[i++] = num;
  11.         }
  12.         return ans;
  13.     }
  15.     private void dfs(int num, int digit, int index, int N, int K, List<Integer> list) {
  16.         if (digit < 0 || digit > 9) {
  17.             return;
  18.         }
  19.         num = num * 10 + digit;
  21.         if (index == N) {
  22.             list.add(num);
  23.             return;
  24.         }
  26.         dfs(num, digit + K, index + 1, N, K, list);
  27.         if (K > 0) {
  28.             dfs(num, digit - K, index + 1, N, K, list);
  29.         }
  30.     }
  31. }