合理利用正则表达式搞定算法题

合理利用正则表达式搞定算法题
下面是网易的21年的笔试题,比较简单的两个。

1:给定两个字符串 s和 t ,判断 s是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度n ~= 500,000),而 s 是个短字符串(长度 <=100)。

字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,”ace”是”abcde”的一个子序列,而”aec”不是)。

进阶:时间复杂度O(n),空间复杂度O(n)。

(function(){
    function solution(s, t){
        let sl = s.length, tl = t.length, L = 0, R = 0;
        while (L < sl && R < tl) {
            if(s[L] === t[R]){
                L++;
                R++;
                if (L === sl) { // 子串匹配完成
                    return true;
                }
            }else {
                R++;
            }
        }
        return false;
    }
    let s = readline().trim(),t = readline().trim();
    print(solution(s.split(''), t.split('')))
})()

考虑到匹配子串,应该考虑正则是否可行。
如果将子串转换为正则,去匹配原串,则可以很方便得出答案。
正则表达式解法:

(function(){
    function solution(s, t){
        // 形如 /a[a-z]*b[a-z]*c/
        let reg = new RegExp(s.join('[a-z]*'));
        return reg.test(t);
    }
    let s = readline().trim(),t = readline().trim();
    print(solution(s.split(''), t))
})()

正则text()方法也是 O(N)的。

2:选座最大距离问题

疫情逐步缓和后,电影院终于开业了,但是由于当前仍处于疫情期间,应尽量保持人群不聚集的原则。
所以当小易来电影院选定一排后,尽量需要选择一个远离人群的位置。
已知由0和1组成的数组表示当前排的座位情况,其中1表示已被选座,0表示空座
请问小易所选座位和最近人的距离座位数最大是多少?
有如下假设:至少有一个人已选座,至少有一个空座位。

(function(){
    function solution(arr){
         let L = 0, max = 0, len = 0, border=0;
        while (L < arr.length) {
            if(arr[L] === '0') {
                len++;
                if(L === arr.length-1){  // 右边界
                    border = len > border ? len : border;
                }
            }else {
                if(L-len === 0){ // 左边界
                    border = len;
                }else {
                    max = len > max ? len : max;
                }
                len = 0;
            }
            L++;
        }
        return Math.max( border, (max+1) >> 1);
    }
    let str = readline().trim();
    print(solution(str.split(' ')))
     
})()

因为只有 0和1,可以考虑正则方式将1去掉,留下单独的0构成的数组。
也可以使用数组的split()拆分方法。

split拆分法:

function solution2 (arr) {
    let list = arr.join('').split('1');
    let max = Math.max(list[0].length, list[list.length-1].length);
    for (let i = 1; i < list.length-1; i++ ) {
        max  = Math.max((list[i].length+1) >> 1, max)
    }
    return max;
}

总结:
正则表达式功能太强大了,具体的细则也是耐人寻味。要想在算法中合理利用它还需要大量的实践和经验。

有问题反馈加微信:mue233 私聊送一本电子书,绝对受益良多! 微信公众号:慕意,分享创业、使用的软件和教程~
知识星球精选推荐 » 合理利用正则表达式搞定算法题