起个简单枯燥的标题：找出连续差相同的数字

Python实战社群

Java实战社群

长按识别下方二维码，按需求添加

扫码关注添加客服

进Python社群▲

扫码关注添加客服

进Java社群▲

作者丨P.yh 

来源丨五分钟学算法

题目描述

返回所有长度为 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]

提示：

• 1 <= N <= 9

• 0 <= K <= 9

题目来源：https://leetcode-cn.com/problems/numbers-with-same-consecutive-differences/

题目解析

这道题题目的意思没有特别的明确，需要仔细读题才能理解。

题意是让你找符合条件的所有整数，这些整数的位数为 N，并且每一位与相邻位的绝对值为 K。

举个例子，输入条件是 N = 3，K = 7，那么 707 就是一个答案，818，181 也算是答案，但是左边打头的一位不能是 0，比如 070 就不是答案。

理解题意之后，你能明显感觉到，每个答案需要我们一位一位地去构建。

另外这个题还有一个特征，就是当你确定了最左边的那一位上的值后，后面的位就可以顺推。

当然，你确定最右边位上的值也可以反向推，但是这里题目规定最左边位上不能为 0，因此从最左边开始构建，程序相对来说会比较好实现。

确定了一位，推导下一位无非有两种情况

• 比当前位上的值大 K；

• 比当前位上的值小 K。

另外对位上的值也有限制，不能超过 9，也不能小于 0。

知道了上面的这些后，剩下的就是去实现一个递归函数。

实现的时候只需要注意两点即可，当构建的整数的长度等于 N 的时候，我们就可以把其加入到答案中去，另外就是需要特殊考虑 N = 1 这样的特殊情况。

参考代码

public int[] numsSameConsecDiff(int N, int K) {
    Set<Integer> set = new HashSet<>();

    if (N == 1) {
        set.add(0);
    }

    for (int i = 1; i <= 9; i++) {
        helper(set, i, K, N, 1);
    }

    int[] result = new int[set.size()];
    int index = 0;
    for (int ele : set) {
        result[index++] = ele;
    }

    return result;
}

private void helper(Set<Integer> result, int cur, int K, int N, int len) {
    if (len == N) {
        result.add(cur);
        return;
    }

    int lastDigit = cur % 10;

    if (lastDigit + K < 10) {
        helper(result, cur * 10 + lastDigit + K, K, N, len + 1);
    }

    if (lastDigit - K >= 0) {
        helper(result, cur * 10 + lastDigit - K, K, N, len + 1);
    }
}

程序员专栏 扫码关注填加客服 长按识别下方二维码进群

近期精彩内容推荐：   程序员写的这一行代码，被国家博物馆收藏了 2020 年 9 月程序员工资统计，我扯后腿了~ 提高国内访问 GitHub 的速度的 9 种方案 Python是强类型语言，还是弱类型语言？

在看点这里好文分享给更多人↓↓