V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
zzzzzzggggggg
V2EX  ›  程序员

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

  •  1
     
  •   zzzzzzggggggg · 2020-03-10 22:59:05 +08:00 · 1299 次点击
    这是一个创建于 837 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

    9 条回复    2020-03-18 12:25:34 +08:00
    woodensail
        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, '');
    }
    woodensail
        2
    woodensail  
       2020-03-11 11:27:49 +08:00
    我去,空格怎么都被干掉了
    mskf
        3
    mskf  
       2020-03-11 13:54:55 +08:00
    第一题个人认为在 backtrack 中反过来遍历效率会高一点
    ```
    let index = pos; index < pos+3;index++
    ```
    就是这边,从大到小遍历
    zzzzzzggggggg
        4
    zzzzzzggggggg  
    OP
       2020-03-11 13:58:49 +08:00
    @woodensail
    @mskf
    哈哈,v 站的网友素质还是高的,稍等我晚上吃完饭看看你们的方法,感谢关注!
    purensong
        5
    purensong  
       2020-03-11 16:06:05 +08:00
    我寻思算法也分前后端嘛
    zzzzzzggggggg
        6
    zzzzzzggggggg  
    OP
       2020-03-11 17:44:11 +08:00
    @purensong 不分,就是个名字而已嘛,老哥莫怪
    zzzzzzggggggg
        7
    zzzzzzggggggg  
    OP
       2020-03-15 12:59:48 +08:00
    @mskf 我分析了一下,反过来效率还是一样的,依旧是一次一次的回溯😄
    zzzzzzggggggg
        8
    zzzzzzggggggg  
    OP
       2020-03-15 13:13:04 +08:00
    @woodensail 试了下,你这个方法确实可以,我可以借鉴你的思路改造一下,就是把后面那两个 while 可以合入到第一个 while 的判断条件里面去
    mskf
        9
    mskf  
       2020-03-18 12:25:34 +08:00
    @zzzzzzggggggg 嗯,时间复杂度是一样的,我意思其实是 ip 地址三位数的多
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1958 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 16:38 · PVG 00:38 · LAX 09:38 · JFK 12:38
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.