Skip to content

Latest commit

 

History

History
252 lines (206 loc) · 5.83 KB

README.md

File metadata and controls

252 lines (206 loc) · 5.83 KB
comments difficulty edit_url tags
true
中等
广度优先搜索
回溯

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

我们可以枚举所有长度为 $n$ 的数字的第一个数字，然后使用深度优先搜索的方法，递归地构造所有符合条件的数字。

具体地，我们首先定义一个边界值 $\textit{boundary} = 10^{n-1}$，表示我们需要构造的数字的最小值。然后，我们从 $1$ 到 $9$ 枚举第一个数字，对于每一个数字 $i$，我们递归地构造以 $i$ 为第一个数字的长度为 $n$ 的数字。

时间复杂度 $(n \times 2^n \times |\Sigma|)$，其中 $|\Sigma|$ 表示数字集合，本题中 $|\Sigma| = 9$。空间复杂度 $O(2^n)$。

Python3

class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        def dfs(x: int):
            if x >= boundary:
                ans.append(x)
                return
            last = x % 10
            if last + k <= 9:
                dfs(x * 10 + last + k)
            if last - k >= 0 and k != 0:
                dfs(x * 10 + last - k)

        ans = []
        boundary = 10 ** (n - 1)
        for i in range(1, 10):
            dfs(i)
        return ans

Java

class Solution {
    private List<Integer> ans = new ArrayList<>();
    private int boundary;
    private int k;

    public int[] numsSameConsecDiff(int n, int k) {
        this.k = k;
        boundary = (int) Math.pow(10, n - 1);
        for (int i = 1; i < 10; ++i) {
            dfs(i);
        }
        return ans.stream().mapToInt(i -> i).toArray();
    }

    private void dfs(int x) {
        if (x >= boundary) {
            ans.add(x);
            return;
        }
        int last = x % 10;
        if (last + k < 10) {
            dfs(x * 10 + last + k);
        }
        if (k != 0 && last - k >= 0) {
            dfs(x * 10 + last - k);
        }
    }
}

C++

class Solution {
public:
    vector<int> numsSameConsecDiff(int n, int k) {
        vector<int> ans;
        int boundary = pow(10, n - 1);
        auto dfs = [&](this auto&& dfs, int x) {
            if (x >= boundary) {
                ans.push_back(x);
                return;
            }
            int last = x % 10;
            if (last + k < 10) {
                dfs(x * 10 + last + k);
            }
            if (k != 0 && last - k >= 0) {
                dfs(x * 10 + last - k);
            }
        };
        for (int i = 1; i < 10; ++i) {
            dfs(i);
        }
        return ans;
    }
};

Go

func numsSameConsecDiff(n int, k int) (ans []int) {
	bounary := int(math.Pow10(n - 1))
	var dfs func(int)
	dfs = func(x int) {
		if x >= bounary {
			ans = append(ans, x)
			return
		}
		last := x % 10
		if last+k < 10 {
			dfs(x*10 + last + k)
		}
		if k > 0 && last-k >= 0 {
			dfs(x*10 + last - k)
		}
	}
	for i := 1; i < 10; i++ {
		dfs(i)
	}
	return
}

TypeScript

function numsSameConsecDiff(n: number, k: number): number[] {
    const ans: number[] = [];
    const boundary = 10 ** (n - 1);
    const dfs = (x: number) => {
        if (x >= boundary) {
            ans.push(x);
            return;
        }
        const last = x % 10;
        if (last + k < 10) {
            dfs(x * 10 + last + k);
        }
        if (k > 0 && last - k >= 0) {
            dfs(x * 10 + last - k);
        }
    };
    for (let i = 1; i < 10; i++) {
        dfs(i);
    }
    return ans;
}

JavaScript

/**
 * @param {number} n
 * @param {number} k
 * @return {number[]}
 */
var numsSameConsecDiff = function (n, k) {
    const ans = [];
    const boundary = 10 ** (n - 1);
    const dfs = x => {
        if (x >= boundary) {
            ans.push(x);
            return;
        }
        const last = x % 10;
        if (last + k < 10) {
            dfs(x * 10 + last + k);
        }
        if (k > 0 && last - k >= 0) {
            dfs(x * 10 + last - k);
        }
    };
    for (let i = 1; i < 10; i++) {
        dfs(i);
    }
    return ans;
};