LeetCode:967连续查相同的数字(DFS)

发布时间:2023年12月17日

题目

返回所有长度为 n 且满足其每两个连续位上的数字之间的差的绝对值为 k 的 非负整数 。

请注意,除了 数字 0 本身之外,答案中的每个数字都 不能 有前导零。例如,01 有一个前导零,所以是无效的;但 0 是有效的。

你可以按 任何顺序 返回答案。

示例 1:
输入:n = 3, k = 7
输出:[181,292,707,818,929]
解释:注意,070 不是一个有效的数字,因为它有前导零。

示例 2:
输入:n = 2, k = 0
输出:[11,22,33,44,55,66,77,88,99]

提示:
2 <= n <= 9
0 <= k <= 9

思路

首先要清楚的是,0只可能出现在个位数上。其次,这种N位数的每一位仅与前一位相关,十分适合采用DFS递归方法。设上一位数字为pre,如果k!=0,那么递归只会有两个分支,当前考虑的位置只会是pre+k或者pre-k,如果k==0,那么只用考虑一个分支,即pre+k或者pre-k,否则会重复。
其次要注意本题的数据存储结构,就好了。

代码

class Solution {
    List<Integer> res = new ArrayList<>();//额外开个全局变量存储所有答案,是方便在DFS函数中使用。
    public int[] numsSameConsecDiff(int n, int k) {
    //因为n最小两位,所以第一位数字不会是个位数字,从1-9中选择就好了。
        for(int i=1;i<=9;i++){
            if(i+k>9&&i-k<0) continue;//分支不在0到9范围内,直接剪枝
            DFS(new StringBuilder(String.valueOf(i)), n, k);

        }
        int[] nums = new int[res.size()];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = res.get(i);
        }
        return nums;
    }
    private void DFS(StringBuilder str,int n,int k){
        if(str.length()==n){//如果答案长度达到要求,直接返回
            res.add(Integer.parseInt(str.toString()));
            return;
        }
        int pre = str.charAt(str.length()-1)-'0';//获得当前考虑的位置的上一位数字
        if(pre+k<=9){//在范围内
            str.append(String.valueOf(pre+k));
            DFS(str, n, k);
            str.deleteCharAt(str.length()-1);
        }
        if(pre-k>=0&&k!=0){//注意k==0时才会有两个分支,否则重复
            str.append(String.valueOf(pre-k));
            DFS(str, n, k);
            str.deleteCharAt(str.length()-1);
        }
    }
}

效率

执行用时分布3ms,击败57.32%使用 Java 的用户。还需要优化。
可以看到代码中数据存储结构太过复杂,为此我们做出如下改进:
1、在DFS函数中,通过传递数字而不是字符串,可以减少每次的转换开销。
2、使用%运算符获取数字的最后一位,而不是通过字符串操作。
3、不再使用StringBuilder来处理字符串,而是直接进行数字运算。
4、赋值给最终数组时的循环不再用List的size方法,而是数组本身长度

特别是第四点,会使得效率相差很大,由2ms提升为1ms。

第二版代码

class Solution {
    List<Integer> res = new ArrayList<>();
    public int[] numsSameConsecDiff(int n, int k) {
        for(int i = 1; i <= 9; i++) {
        if(i+k>9&&i-k<0) continue;
            DFS(i, n, k);
        }
        int[] nums = new int[res.size()];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = res.get(i);
        }
        return nums;
    }
    
    private void DFS(int num, int n, int k) {
        if(String.valueOf(num).length() == n) {
            res.add(num);
            return;
        }
        int pre= num % 10;
        if(pre + k <= 9) {
            DFS(num * 10 + pre + k, n, k);
        }
        if(pre - k >= 0 && k != 0) {
            DFS(num * 10 + pre - k, n, k);
        }
    }
}

效率

执行用时分布1ms,击败98.79%使用 Java 的用户。可以不用再优化了。

第三版代码

注意第二版代码中在两个if中都没有进行显式地回溯,这是因为回溯直接在循环里面实现了,相当于隐形地回溯。因为函数执行完毕时不会将修改的结果带回去,所以虽然if里面进入了下一层,但是结束函数时还是在上一层。
而第一版代码之所以需要显式地进行回溯,是因为StringBuilder它底层实际上相当于一个数组指针,在函数执行完毕时更改的结果依旧存在。
但我们也可以不显式地进行回调,只需要传入DFS时手动给他再新建一个StringBuilder,那么函数执行完毕时就也不会将修改的结果带回去了。

代码

class Solution {
    List<Integer> res = new ArrayList<>();
    public int[] numsSameConsecDiff(int n, int k) {  
        for(int i=1;i<=9;i++)
        {
            if(i+k>9&&i-k<0) continue;
            DFS(new StringBuilder(String.valueOf(i)),n,k);
        }
        int[] ans= new int[res.size()];
        for(int i=0;i<ans.length;i++){
            ans[i]=res.get(i);
        }
        return ans;
    }

    public void DFS(StringBuilder str, int n,int k){
        if(str.length()==n) {
            res.add(Integer.parseInt(String.valueOf(str)));
            return;
        }
        int pre = str.charAt(str.length()-1)-'0';
        if(pre+k<=9){
            DFS(new StringBuilder(str).append(pre+k), n, k);
        }
        if(pre-k>=0&&k!=0){
            DFS(new StringBuilder(str).append(pre-k), n, k);
        }

    }
}
}
文章来源:https://blog.csdn.net/zhiaidaidai/article/details/135039980
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。