Question

967. Numbers With Same Consecutive Differences

中文文档

Description

Given two integers n and k, return _an array of all the integers of length _n_ where the difference between every two consecutive digits is _k. You may return the answer in any order.

Note that the integers should not have leading zeros. Integers as 02 and 043 are not allowed.

 

Example 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.

Example 2:

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

 

Constraints:

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

Solutions

Solution 1

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
}