【算法-LeetCode】93. 复原 IP 地址(回溯;递归)
2021/9/18 22:04:59
本文主要是介绍【算法-LeetCode】93. 复原 IP 地址(回溯;递归),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
93. 复原 IP 地址 - 力扣(LeetCode)
发布:2021年9月18日21:26:11
问题描述及示例
给定一个只包含数字的字符串,用以表示一个 IP 地址,返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 ‘.’ 分隔。
例如:“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址,但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
示例 1:
输入:s = “25525511135”
输出:[“255.255.11.135”,“255.255.111.35”]
示例 2:
输入:s = “0000”
输出:[“0.0.0.0”]
示例 3:
输入:s = “1111”
输出:[“1.1.1.1”]
示例 4:
输入:s = “010010”
输出:[“0.10.0.10”,“0.100.1.0”]
示例 5:
输入:s = “101023”
输出:[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/restore-ip-addresses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
提示:
0 <= s.length <= 3000
s 仅由数字组成
我的题解(回溯)
这应该是我在LeetCode碰到的第二个有关回溯的题目了,之前写过一个相关的题解博客:
参考:【算法-LeetCode】46. 全排列(回溯算法初体验)_赖念安的博客-CSDN博客
在我看来,其实回溯就是递归的一种应用,往往用在一些需要穷举所有可能的情况,而回溯和一般的递归的区别,我觉得就是所谓的“回溯”操作,也就是:当一层递归完成后,把程序中的某些变量(这些变量往往是全局的)恢复到递归前的状态。回溯操作的典型结构如下:
let globalVar; let globalVar2; ... globalVar2++; operateA(); // 在operateA之前,globalVar的状态是X;在operateA之后,globalVar的状态变为Y backtracking(params); operateB(); // 在operateB之前,globalVar的状态是Y;在operateB之后,globalVar的状态恢复为X globalVar2--; ...
也就是说,operateA()
和 operateB()
的操作效果刚好是相互抵消的。比如数组的 push()
和 pop()
方法。这就是回溯算法最精髓的部分:把状态恢复到递归前。
详细解释请看下方注释:
/** * @param {string} s * @return {string[]} */ var restoreIpAddresses = function (s) { if (s.length < 4 || s.length > 12) { return []; } let results = []; let ip = []; backtracking(s, 0); return results; function backtracking(str, start) { // 加上下面这个if判断,也可以优化性能 if(ip.length > 4) { return; } if (start === str.length) { if (ip.length === 4) { results.push(ip.join('.')); } return; } for (let i = start; i < str.length; i++) { let segment = str.substring(start, i + 1); if (!isValidSegment(segment)) { break; } ip.push(segment); backtracking(str, i + 1); ip.pop(); } } function isValidSegment(str) { if (!str || str.length > 3) { return false; } if (str[0] === '0') { return str.length > 1 ? false : true; } return Number(str) <= 255 ? true : false; } }; 提交记录 执行结果:通过 147 / 147 个通过测试用例 执行用时:76 ms, 在所有 JavaScript 提交中击败了67.63%的用户 内存消耗:39.3 MB, 在所有 JavaScript 提交中击败了55.32%的用户 时间:2021/09/18 21:35
官方题解
更新:2021年7月29日18:43:21
因为我考虑到著作权归属问题,所以【官方题解】部分我不再粘贴具体的代码了,可到下方的链接中查看。
更新:2021年9月18日21:35:40
参考:复原IP地址 - 复原 IP 地址 - 力扣(LeetCode)
【更新结束】
有关参考
更新:2021年9月18日21:34:22
参考:【算法-LeetCode】46. 全排列(回溯算法初体验)_赖念安的博客-CSDN博客
参考:String.prototype.substring() - JavaScript | MDN
这篇关于【算法-LeetCode】93. 复原 IP 地址(回溯;递归)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-07fastcgi 是什么-icode9专业技术文章分享
- 2024-10-07fastcgi 的详细使用教程介绍-icode9专业技术文章分享
- 2024-10-07git如何更新单个文件到本地-icode9专业技术文章分享
- 2024-10-07如何使用ASM(Abstract Syntax Tree Manipulation)技术来修改第三方AAR依赖中的函数-icode9专业技术文章分享
- 2024-10-07Activity 跳转时间耗时很长怎么优化解决-icode9专业技术文章分享
- 2024-10-07Androud Toast 有哪些常用的第三方组件-icode9专业技术文章分享
- 2024-10-07在viewmodel中怎么使用 mmkv?-icode9专业技术文章分享
- 2024-10-07MMKV.defaultMMKV() 是单例模式吗?-icode9专业技术文章分享
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享