README.md

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

解法

DFS。

Python3

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

Java

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);
        }
    }
}

C++

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);
    }
};

Go

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
}

...