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);}}
}
}
相关文章:
LeetCode:967连续查相同的数字(DFS)
题目 返回所有长度为 n 且满足其每两个连续位上的数字之间的差的绝对值为 k 的 非负整数 。 请注意,除了 数字 0 本身之外,答案中的每个数字都 不能 有前导零。例如,01 有一个前导零,所以是无效的;但 0 是有效的。 …...
深入剖析NPM: Node包管理器的介绍和使用指南
导言:NPM(Node Package Manager)是JavaScript世界中最受欢迎的包管理器之一。它的出现大大简化了JavaScript开发过程中的依赖管理和模块化。本文将向您介绍NPM的基本概念、功能和常见用法,并为您提供一份详尽的NPM使用指南。 一、…...
AI视频-stable-video-diffusio介绍
介绍 stbilityai/stable-video-diffusion-img2vid-xt模型,由Stability AI开发和训练的基于散度的图像到视频生成模型。该模型可以接受一张静态图像作为条件,并生成出一个短视频。 该模型通过在SVD Image-to-Video [14帧]的基础上进行微调而来,可以生成576x1024分辨…...

day01-报表技术POI
前言 报表[forms for reporting to the higher organizations],就是向上级报告情况的表格。简单的说:报表就是用表格、图表等格式来动态显示数据,可以用公式表示为:“报表 多样的格式 动态的数据”。 1、开发环境搭建 功能说…...

如何预防最新的.locked、.locked1勒索病毒感染您的计算机?
尊敬的读者: 近期,网络安全领域迎来一股新潮——.locked、.locked1勒索病毒的威胁,其先进的加密技术令人生畏。本文将深入剖析.locked、.locked1勒索病毒的阴谋,提供特色数据恢复策略,并揭示锁定恶劣行径的先锋预防手…...
实现两张图片的接缝线拼接
使用ORB算法检测特征点,并通过BFMatcher进行特征点匹配。然后,根据Lowes ratio test选择好的匹配点,并使用findHomography计算单应性矩阵。最后,使用warpPerspective将图像进行透视变换,然后将第二张图像粘贴到变换后的…...
基于JNI 实现 嵌套 List 类型参数解析
基于JNI 实现 嵌套 List 类型参数解析 背景分析解决 背景 在前面两篇文章中,我们总结了Java 调用 C/C SDK 的几种方案,分享了JNI在实践过程中的一些踩坑点,而在这篇文章将继续分享针对Java List类型及其嵌套类型,我们的JNI如何接…...

探索灵活性与可维护性的利器:策略(Strategy)模式详解
目录 编辑 1. 策略模式概述: 2. 主要角色: 3. 实例场景: 4. 具体实现步骤: 步骤一:定义策略接口 5. 使用策略模式的客户端代码: 总结: 我的其他博客 1. 策略模式概述: 策…...

压缩包文件暴力破解 -Server2005(解析)
任务五十一: 压缩包文件暴力破解 任务环境说明:Server2005 1. 通过本地PC中渗透测试平台Kali使用Nmap扫描目标靶机服务版本信息,将 Telnet 版本信息字符串 作为 Flag 提交; flag:Microsoft Windows XP telnetd 2. 通过本地PC中渗透测试平台Kali对服务器场景Windows进行渗透测…...

mars3d加载arcgis发布的服务,⽀持4523坐标
问题 1.从这个服务地址加载,具体在哪⾥去转坐标呢? 加个 usePreCachedTilesIfAvailable:false 参数即可 坐标系为4490的arcgis影像服务图层,配置后瓦片加载不出来,没报错 甚至可以跳转 没有看出问题,或者测…...

『K8S 入门』二:深入 Pod
『K8S 入门』二:深入 Pod 一、基础命令 获取所有 Pod kubectl get pods2. 获取 deploy kubectl get deploy3. 删除 deploy,这时候相应的 pod 就没了 kubectl delete deploy nginx4. 虽然删掉了 Pod,但是这是时候还有 service,…...

十七、如何将MapReduce程序提交到YARN运行
1、启动某个节点的某一个用户 hadoopnode1:~$ jps 13025 Jps hadoopnode1:~$ yarn --daemon start resourcemanager hadoopnode1:~$ jps 13170 ResourceManager 13253 Jps hadoopnode1:~$ yarn --daemon start nodemanager hadoopnode1:~$ jps 13170 ResourceManager 15062 Jp…...
华为云CodeArts Deploy常见问答汇总
1.【Deploy】部署java项目,为什么通过springboot启动步骤启动失败了? 答:用户所部署的jar包源码并不是springboot框架,所以无法用springboot启动步骤启动,该步骤并不等同于java -jar 命令,需要使用shell脚…...

前后端交互—开发一个完整的服务器
代码下载 初始化 新建 apiServer 文件夹作为项目根目录,并在项目根目录中运行如下的命令,初始化包管理配置文件: npm init -y运行如下的命令,安装 express、cors: npm i express cors在项目根目录中新建 app.js 作为整个项目的入口文件&a…...

前端框架的虚拟DOM(Virtual DOM)
聚沙成塔每天进步一点点 ⭐ 专栏简介 前端入门之旅:探索Web开发的奇妙世界 欢迎来到前端入门之旅!感兴趣的可以订阅本专栏哦!这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域的朋友们量身打造的。无论你是完全的新手还是有一些基础的开发…...
什么是http状态码?
什么是http状态码? 当浏览者访问一个网页时,浏览者的浏览器会向网页所在服务器发出请求。当浏览器接收并显示网页前,此网页所在的服务器会返回一个包含 HTTP 状态码的信息头(server header)用以响应浏览器的请求。 ht…...
linux/CentOS 7安装Nginx
Nginx 是 C语言 开发,建议在 Linux 上运行,当然,也可以安装 Windows 版本,本篇则使用 CentOS 7 作为安装环境。 Nginx一般使用非root账号安装,如果还没有非root账号,先创建账号 创建账号 创建组…...

软件工程期末复习+数据仓库ETL
一、软件工程 请用基本路径测试方法为下列程序设计测试用例,并写明中间过程: 第1步:画出流程图 1.菱形用于条件判断。用在有分支的地方。 2.矩形表示一个基本操作。 3.圆形是连接点 第2步:计算程序环路复杂性 流图G的环路复杂…...
学习C语言——体会计算机中的0和1
/* 把hello隐写入一个整型数组,这个小程序可以考察是否清楚数据在内存中存储的具体细节。 具体的说,int类型在小端机器上的存储方式是高位在高地址,低位在低地址,从视觉习惯上和我们的日常书写习惯相反; char类型占用…...

PyTorch官网demo解读——第一个神经网络(1)
神经网络如此神奇,feel the magic 今天分享一下学习PyTorch官网demo的心得,原来实现一个神经网络可以如此简单/简洁/高效,同时也感慨PyTorch如此强大。 这个demo的目的是训练一个识别手写数字的模型! 先上源码: fr…...

wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...

Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...