LeetCode:967连续查相同的数字（DFS）

题目

返回所有长度为 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);}}
}
}