Question

967. 连续差相同的数字

English Version

题目描述

返回所有长度为 n 且满足其每两个连续位上的数字之间的差的绝对值为 k 的 非负整数 。

请注意，除了 数字 0 本身之外，答案中的每个数字都 不能 有前导零。例如，01 有一个前导零，所以是无效的；但 0 是有效的。

你可以按 任何顺序 返回答案。

 

示例 1：

输入：n = 3, k = 7
输出：[181,292,707,818,929]
解释：注意，070 不是一个有效的数字，因为它有前导零。

示例 2：

输入：n = 2, k = 1
输出：[10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

示例 3：

输入：n = 2, k = 0
输出：[11,22,33,44,55,66,77,88,99]

示例 4：

输入：n = 2, k = 2
输出：[13,20,24,31,35,42,46,53,57,64,68,75,79,86,97]

 

提示：

• 2 <= n <= 9
• 0 <= k <= 9

解法

方法一

class Solution:
  def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
    ans = []

    def dfs(n, k, t):
      if n == 0:
        ans.append(t)
        return
      last = t % 10
      if last + k <= 9:
        dfs(n - 1, k, t * 10 + last + k)
      if last - k >= 0 and k != 0:
        dfs(n - 1, k, t * 10 + last - k)

    for i in range(1, 10):
      dfs(n - 1, k, i)
    return ans

class Solution {
  public int[] numsSameConsecDiff(int n, int k) {
    List<Integer> res = new ArrayList<>();
    for (int i = 1; i < 10; ++i) {
      dfs(n - 1, k, i, res);
    }
    int[] ans = new int[res.size()];
    for (int i = 0; i < res.size(); ++i) {
      ans[i] = res.get(i);
    }
    return ans;
  }

  private void dfs(int n, int k, int t, List<Integer> res) {
    if (n == 0) {
      res.add(t);
      return;
    }
    int last = t % 10;
    if (last + k <= 9) {
      dfs(n - 1, k, t * 10 + last + k, res);
    }
    if (last - k >= 0 && k != 0) {
      dfs(n - 1, k, t * 10 + last - k, res);
    }
  }
}

class Solution {
public:
  vector<int> ans;

  vector<int> numsSameConsecDiff(int n, int k) {
    for (int i = 1; i < 10; ++i)
      dfs(n - 1, k, i);
    return ans;
  }

  void dfs(int n, int k, int t) {
    if (n == 0) {
      ans.push_back(t);
      return;
    }
    int last = t % 10;
    if (last + k <= 9) dfs(n - 1, k, t * 10 + last + k);
    if (last - k >= 0 && k != 0) dfs(n - 1, k, t * 10 + last - k);
  }
};

func numsSameConsecDiff(n int, k int) []int {
  var ans []int
  var dfs func(n, k, t int)
  dfs = func(n, k, t int) {
    if n == 0 {
      ans = append(ans, t)
      return
    }
    last := t % 10
    if last+k <= 9 {
      dfs(n-1, k, t*10+last+k)
    }
    if last-k >= 0 && k != 0 {
      dfs(n-1, k, t*10+last-k)
    }
  }

  for i := 1; i < 10; i++ {
    dfs(n-1, k, i)
  }
  return ans
}