复原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; };
