Medium

题目描述

给定两个整数 n 和 k，返回所有长度为 n 且相邻两位数字之差为 k 的整数数组。你可以按任意顺序返回答案。

注意，整数不能有前导零。像 02 和 043 这样的整数是不被允许的。

示例 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]

提示：

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

解题思路

这是一个典型的回溯/DFS问题，需要构造所有满足条件的n位数。

思路分析：

  1. 基本思想：从第一位数字开始（1-9，不能为0避免前导零），然后递归构造后续位数
  2. 状态转移：对于当前位数字 digit，下一位只能是 digit+k 或 digit-k（如果在0-9范围内）
  3. 特殊情况：当k=0时，所有位数字相同，避免重复添加

解法选择：

  • DFS/回溯法：从高位到低位逐步构造，时间复杂度较优
  • BFS法：逐层扩展，空间复杂度稍高但思路直观

推荐使用DFS回溯法，代码简洁且效率高。

实现要点：

  • 第一位数字从1开始（避免前导零）
  • 递归构造时检查下一位数字是否在[0,9]范围内
  • 当k=0时，只需要考虑一种情况避免重复

代码实现

class Solution {
public:
    vector<int> numsSameConsecDiff(int n, int k) {
        vector<int> result;
        
        function<void(int, int)> dfs = [&](int num, int remaining) {
            if (remaining == 0) {
                result.push_back(num);
                return;
            }
            
            int lastDigit = num % 10;
            
            // Try adding k
            if (lastDigit + k <= 9) {
                dfs(num * 10 + lastDigit + k, remaining - 1);
            }
            
            // Try subtracting k (avoid duplicate when k = 0)
            if (k != 0 && lastDigit - k >= 0) {
                dfs(num * 10 + lastDigit - k, remaining - 1);
            }
        };
        
        // Start with digits 1-9 (no leading zeros)
        for (int i = 1; i <= 9; i++) {
            dfs(i, n - 1);
        }
        
        return result;
    }
};

class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        result = []
        
        def dfs(num, remaining):
            if remaining == 0:
                result.append(num)
                return
            
            last_digit = num % 10
            
            # Try adding k
            if last_digit + k <= 9:
                dfs(num * 10 + last_digit + k, remaining - 1)
            
            # Try subtracting k (avoid duplicate when k = 0)
            if k != 0 and last_digit - k >= 0:
                dfs(num * 10 + last_digit - k, remaining - 1)
        
        # Start with digits 1-9 (no leading zeros)
        for i in range(1, 10):
            dfs(i, n - 1)
        
        return result

public class Solution {
    public int[] NumsSameConsecDiff(int n, int k) {
        List<int> result = new List<int>();
        
        void Dfs(int num, int remaining) {
            if (remaining == 0) {
                result.Add(num);
                return;
            }
            
            int lastDigit = num % 10;
            
            // Try adding k
            if (lastDigit + k <= 9) {
                Dfs(num * 10 + lastDigit + k, remaining - 1);
            }
            
            // Try subtracting k (avoid duplicate when k = 0)
            if (k != 0 && lastDigit - k >= 0) {
                Dfs(num * 10 + lastDigit - k, remaining - 1);
            }
        }
        
        // Start with digits 1-9 (no leading zeros)
        for (int i = 1; i <= 9; i++) {
            Dfs(i, n - 1);
        }
        
        return result.ToArray();
    }
}

var numsSameConsecDiff = function(n, k) {
    let result = [];
    
    function dfs(num, remaining) {
        if (remaining === 0) {
            result.push(num);
            return;
        }
        
        let lastDigit = num % 10;
        
        if (lastDigit + k <= 9) {
            dfs(num * 10 + lastDigit + k, remaining - 1);
        }
        
        if (k !== 0 && lastDigit - k >= 0) {
            dfs(num * 10 + lastDigit - k, remaining - 1);
        }
    }
    
    for (let i = 1; i <= 9; i++) {
        dfs(i, n - 1);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(2^n) - 每一位最多有2种选择，最坏情况下需要遍历所有可能的组合
空间复杂度O(2^n) - 存储结果数组和递归调用栈的空间