这是一个创建于 2040 天前的主题，其中的信息可能已经有所发展或是发生改变。
本期涉及到的算法技巧为字符串回溯算法，字符串相乘进位处理等等。
复原 IP 地址
LeetCode.93 ，难度中等
题目
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
思路
对于 IP 地址来说，要注意的点是，地址分为 4 段，每一段不能大于 255，且每一段如果开头是 0 的话那只能有一位。
考虑可以用回溯的思路，比如第一段可以在 2、25、255 里面选，当第一段是 2 的时候，第二段可以在 5、55、552 （超过 255 不符合要求）里选，第二段是 5 的时候，第三段可以在 5、52、525 （超过 255 不符合要求）里选，第三段是 5 的时候，第四段可以在 2、25、255 里选，其他情况可以以此类推。
代码如下：
/** * @param {string} s * @return {string[]} */ const restoreIpAddresses = function(s) { let res = []; backtrack(0, '', s, 4, res); return res; }; /* pos：当前遍历到的位置 ip：当前构造出的 ip s：字符串 flag：当前是在处理第几段，ip 地址共 4 端 */ const backtrack = function(pos, ip, s, flag, res) { if(flag < 0) return; if(pos === s.length && flag === 0) { res.push(ip.substring(0, ip.length-1)); return; } for(let index = pos; index < pos+3;index++) { // 0 只能作为 IP 中的一段，不能出现 xx.01.xx.xx 这样的，所以 break if(index === pos && s[index] === '0') { backtrack(index + 1, ip + '0.', s, flag-1, res); break; } if(parseInt(s.substring(pos, index+1)) <= 255) { backtrack(index+1, ip + s.substring(pos, index+1) + '.', s, flag-1, res); } } } 二进制求和
LeetCode.67 ，难度简单，常见于腾讯面试
题目
给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
思路
依然是个字符串按位相加的例子，不过要注意二进制的加法进位逻辑和两个字符串不一定会一样长。
代码如下：
/** * @param {string} a * @param {string} b * @return {string} */ var addBinary = function(a, b) { if(a === "") return b; if(b === "") return a; let index1 = a.length-1; let index2 = b.length-1; let res = ""; let carry = false; // 进位 while(index1 >= 0 && index2 >= 0) { let cur = "0"; if(a[index1] === "1" && b[index2] === "1") { if(carry) { cur = "1"; } else { cur ="0"; } carry = true; } else if (a[index1] === "1" || b[index2] === "1") { if(carry) { cur = "0"; carry = true; } else { cur = "1"; } } else { if(carry) { cur = "1"; carry = false; } else { cur = "0"; } } index1--; index2--; res = cur + res; } let index = index1 >= 0 ? index1 : index2; let num = index1 >= 0 ? a : b; while(index >= 0) { let cur = ""; if(num[index] === "1") { if(carry) { cur = "0"; carry = true; } else { cur = "1"; carry = false; } } else { cur = carry ? "1" : "0"; carry = false; } index--; res = cur + res; } if(carry) { res = "1" + res; } return res; }; 感兴趣可关注我的公众号前端亚古兽
 | 1 woodensail 2020-03-11 11:27:36 +08:00 第二题哪儿这么麻烦，遍历一遍往数组塞不就行了。 function addBinary(a, b) { const lenA = a.length, lenB = b.length; const result = [0]; for (let i = 0; i < Math.max(lenA, lenB); i++) { result[i] = result[i] + (a[lenA - i - 1] === '1' ? 1 : '') + (b[lenB - i - 1] === '1' ? 1 : ''); result.push(result[i] > 1 ? 1 : 0); result[i] %= 2; } result.reverse(); return result.join('').replace(/^0+/g, ''); } |
| 2 woodensail 2020-03-11 11:27:49 +08:00 我去，空格怎么都被干掉了 |
 | 3 mskf 2020-03-11 13:54:55 +08:00 第一题个人认为在 backtrack 中反过来遍历效率会高一点 ``` let index = pos; index < pos+3;index++ `` 就是这边，从大到小遍历 |
 | 4 zzzzzzggggggg OP |
 | 5 purensong 2020-03-11 16:06:05 +08:00 我寻思算法也分前后端嘛 |
| 6 zzzzzzggggggg OP @purensong 不分，就是个名字而已嘛，老哥莫怪 |
| 7 zzzzzzggggggg OP @mskf 我分析了一下，反过来效率还是一样的，依旧是一次一次的回溯 |
| 8 zzzzzzggggggg OP @woodensail 试了下，你这个方法确实可以，我可以借鉴你的思路改造一下，就是把后面那两个 while 可以合入到第一个 while 的判断条件里面去 |
| 9 mskf 2020-03-18 12:25:34 +08:00 @zzzzzzggggggg 嗯，时间复杂度是一样的，我意思其实是 ip 地址三位数的多 |
Select Language