大良网站建设服务,怎么注册网店,网站收录大幅度下降,工程公司组织架构题目
返回所有长度为 n 且满足其每两个连续位上的数字之间的差的绝对值为 k 的 非负整数 。
请注意#xff0c;除了 数字 0 本身之外#xff0c;答案中的每个数字都 不能 有前导零。例如#xff0c;01 有一个前导零#xff0c;所以是无效的#xff1b;但 0 是有效的。
…题目
返回所有长度为 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如果k0那么递归只会有两个分支当前考虑的位置只会是prek或者pre-k如果k0那么只用考虑一个分支即prek或者pre-k否则会重复。 其次要注意本题的数据存储结构就好了。
代码
class Solution {ListInteger res new ArrayList();//额外开个全局变量存储所有答案是方便在DFS函数中使用。public int[] numsSameConsecDiff(int n, int k) {//因为n最小两位所以第一位数字不会是个位数字从1-9中选择就好了。for(int i1;i9;i){if(ik9i-k0) 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(prek9){//在范围内str.append(String.valueOf(prek));DFS(str, n, k);str.deleteCharAt(str.length()-1);}if(pre-k0k!0){//注意k0时才会有两个分支否则重复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 {ListInteger res new ArrayList();public int[] numsSameConsecDiff(int n, int k) {for(int i 1; i 9; i) {if(ik9i-k0) 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 {ListInteger res new ArrayList();public int[] numsSameConsecDiff(int n, int k) { for(int i1;i9;i){if(ik9i-k0) continue;DFS(new StringBuilder(String.valueOf(i)),n,k);}int[] ans new int[res.size()];for(int i0;ians.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(prek9){DFS(new StringBuilder(str).append(prek), n, k);}if(pre-k0k!0){DFS(new StringBuilder(str).append(pre-k), n, k);}}
}
}
