class Solution {
public:
vector<int> numsSameConsecDiff(int n, int k) {
}
};
967. 连续差相同的数字
返回所有长度为 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 <= 90 <= k <= 9原站题解
python3 解法, 执行用时: 64 ms, 内存消耗: 16.2 MB, 提交时间: 2023-06-08 11:43:28
class Solution:
def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
def dfs(tmp):
if len(tmp) == n:
res.append(int(''.join(tmp)))
return
l = int(tmp[-1]) - k # 每次根据最后一位 +k、-k 的情况进行 dfs
r = int(tmp[-1]) + k
if r <= 9:
dfs(tmp + [str(r)])
if l != r and 0 <= l: # 注意 k == 0 的情况，方法是增加l != r
dfs(tmp + [str(l)])
res = []
for i in range(1, 10): # 从第一位开始 dfs，目的是排除首位 0 的情况
dfs([str(i)])
return res
python3 解法, 执行用时: 52 ms, 内存消耗: 16.5 MB, 提交时间: 2023-06-08 11:43:13
def cal(s):
res = 0
for t in s:
res = res * 10 + t
return res
class Solution:
def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
Q = collections.deque()
for i in range(1, 10):
Q.append([i])
res = []
while Q:
v = Q.popleft()
if len(v) == n:
res.append(cal(v))
elif k == 0:
v.append(v[-1])
Q.append(v)
else:
if v[-1] - k >= 0:
t = v.copy()
t.append(t[-1] - k)
Q.append(t)
if v[-1] + k < 10:
t = v.copy()
t.append(t[-1] + k)
Q.append(t)
return res
golang 解法, 执行用时: 0 ms, 内存消耗: 2.4 MB, 提交时间: 2023-06-08 11:42:28
func numsSameConsecDiff(n int, k int) []int {
var result []int=[]int{}
var dfs func(level,cur int)
dfs =func(level,cur int){
// fmt.Printf("level=%d,cur=%d\n",level,cur)
if level==n-1{
result=append(result,cur)
return
}
//排除最高位是0的节点，剪枝。
if cur*10==cur{return}
prev:=cur%10
if prev>=k{
dfs(level+1,cur*10+prev-k)
}
if k>0&&prev+k<10 {
dfs(level+1,cur*10+prev+k)
}
}
for i:=0;i<10;i++{
dfs(0,i)
}
return result
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.7 MB, 提交时间: 2023-06-08 11:42:06
func numsSameConsecDiff(n int, k int) []int {
nums := make([]int, 10)
for i := 0; i < 10; i++ {
nums[i] = i
}
track, result := []int{}, []int{}
backtrack(0, n, k, track, &result, nums)
return result
}
func backtrack(idx, n, k int, track []int, result *[]int, nums []int) {
// track 中的元素个数（即所求的有效数字的位数）已经满足 n 位的要求，此时将处理后的结果加入 result 并终止回溯
if len(track) == n {
digit := 0
for i := 0; i < len(track); i++ {
digit = digit*10 + track[i]
}
*result = append(*result, digit)
return
}
for i := idx; i < len(nums); i++ {
digit := nums[i]
// 两种情况下不能将新的数字加入到track中：1. track中没有元素，此时的digit为0，即最终的数字含有前导0；2. 最后两个数字差的绝对值不等于k.
if len(track) == 0 && digit == 0 || len(track) >= 1 && abs(digit, track[len(track)-1]) != k {
continue
}
track = append(track, digit)
backtrack(0, n, k, track, result, nums)
track = track[:len(track)-1]
}
return
}
func abs(x, y int) int {
if x - y < 0 {
return y - x
}
return x - y
}
golang 解法, 执行用时: 4 ms, 内存消耗: 2.6 MB, 提交时间: 2023-06-08 11:41:47
func numsSameConsecDiff(n int, k int) []int {
var s = []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
for i := 1; i < n; i++ { // n位
var res []int
for _, v := range s {
d := v % 10 //尾数
if math.Abs(float64(d-k)) < 10 && int(math.Abs(float64(d-k))) != d+k && d >= k {
res = append(res, v*10+int(math.Abs(float64(d-k))))
}
if d+k < 10 {
res = append(res, v*10+(d+k))
}
}
s = res
}
return s
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 7 MB, 提交时间: 2023-06-08 11:41:18
/**
* dp[i][j]：表示i位数（满足题意的数）中第j个数字
* dp[i-1][m]：表示i-1位数（满足题意的数）中第m个数字
**/
class Solution {
public:
vector<int> numsSameConsecDiff(int N, int K) {
if (N == 1) { return { 0,1,2,3,4,5,6,7,8,9 };}
vector<vector<int>> dp(N + 1);
dp[1] = { 1,2,3,4,5,6,7,8,9 };
int start = 0, end = 0;
for (int i = 2; i <= N; i++) {
for (int j = 0; j < dp[i - 1].size(); j++) {
if (K == 0) {
dp[i].push_back(dp[i - 1][j] * 10 + dp[i - 1][j] % 10);
}
else {
if (dp[i - 1][j] % 10 + K <= 9) {
dp[i].push_back(dp[i - 1][j] * 10 + dp[i - 1][j] % 10 + K);
}
if (dp[i - 1][j] % 10 - K >= 0) {
dp[i].push_back(dp[i - 1][j] * 10 + dp[i - 1][j] % 10 - K);
}
}
}
}
return dp[N];
}
};
java 解法, 执行用时: 3 ms, 内存消耗: 40.9 MB, 提交时间: 2023-06-08 11:40:10
class Solution {
public int[] numsSameConsecDiff(int N, int K) {
Set<Integer> cur = new HashSet();
for (int i = 1; i <= 9; ++i)
cur.add(i);
for (int steps = 1; steps <= N-1; ++steps) {
Set<Integer> cur2 = new HashSet();
for (int x: cur) {
int d = x % 10;
if (d-K >= 0)
cur2.add(10*x + (d-K));
if (d+K <= 9)
cur2.add(10*x + (d+K));
}
cur = cur2;
}
if (N == 1)
cur.add(0);
int[] ans = new int[cur.size()];
int t = 0;
for (int x: cur)
ans[t++] = x;
return ans;
}
}
python3 解法, 执行用时: 52 ms, 内存消耗: 15.9 MB, 提交时间: 2023-06-08 11:39:53
class Solution:
def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
ans = {x for x in range(1, 10)}
for _ in range(n-1):
ans2 = set()
for x in ans:
d = x % 10
if d - k >= 0:
ans2.add(10*x + d-k)
if d + k <= 9:
ans2.add(10*x + d+k)
ans = ans2
if n == 1:
ans.add(0)
return list(ans)