本期涉及到的算法技巧为字符串回溯算法，字符串相乘进位处理等等。

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

感兴趣可关注我的公众号——前端亚古兽

[第 4 期] 前端算法精选-字符串

复原 IP 地址

题目

思路

二进制求和

题目

思路