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

老哥来看看跳槽常考算法呗 [第 1 期] 前端算法精选-字符串系列

  •  
  •   zzzzzzggggggg · 2020-02-27 19:01:15 +08:00 · 3210 次点击
    这是一个创建于 1491 天前的主题,其中的信息可能已经有所发展或是发生改变。

    很多前端工程师甚至很多研发工程师都缺乏数据结构和算知识,前端算法精选系列是一个针对常见的、高频的算法题做的一个算法解析系列,文章会给出详细的思路和解答,希望可以帮助到你。

    无重复字符的最长子串

    题目

    给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

    示例 1:

    输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3

    示例 2:

    输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

    示例 3:

    输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

    解法

    先看一下这道题的要求,它要求返回一个字符串中无重复字符的最大子串长度,时间复杂度和空间复杂度要求尽可能的低,有以下的思路

    既然是最大子串的长度,首先最明显的思路就是维护一个最大不重复子串的变量和最大长度的变量。比如对于 “abcabcbb” 来说,维护一个 cur 来存当前最大不重复子串、max 维护最大长度,那么就有以下过程:

    1. 遍历到 a,此时 cur='',不包含'a',所以 cur=cur+'a'='a'; cur 长度为 1 大于 max 的初始值 0,所以更新 max=1 ;

    2. 遍历到 b,此时 cur='a',不包含'b',所以 cur=cur+'b'='ab'; cur 长度为 2 大于 max,所以更新 max=2 ;

    3. 遍历到 c,此时 cur='ab',不包含'c',所以 cur=cur+'c'='abc',cur 长度为 3 大于 max,所以更新 max=3 ;

    4. 遍历到 a,此时 cur='abc',包含'a',所以截掉'a'以及它之前的字符串得到 cur='bc',然后再加上这一轮的'a',得到 cur='bca'; cur 长度为 3 不大于 max,所以不更新 max

    5. 按照以上的逻辑继续遍历...

    代码如下:

    /**
     * @param {string} s
     * @return {number}
     */
    var lengthOfLongestSubstring = function(s) {
        if(s.length === 0 || s.length === 1)  
            return s.length;
        let cur = '', max = '';
        for(let i = 0;i < s.length;i++) {
            const index = cur.indexOf(s[i]);
            if(index >= 0) {
                cur = cur.slice(index+1);
            }
            cur += s[i];
            if(cur.length >= max.length)
                max = cur;
        }
        
        return max.length;
    };
    

    最长公共前缀

    题目

    编写一个函数来查找字符串数组中的最长公共前缀,如果不存在公共前缀,返回空字符串。

    示例 1:

    输入: ["flower","flow","flight"] 输出: "fl"

    示例 2:

    输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。

    解法

    这道题求一组字符串的最长公共前缀,思路可以转化成先以第一个字符串为最长公共前缀,然后跟第 2 个字符串对比,截取公共前缀部分,再跟第 3 个字符串对比,截取公共部分...依次进行下去,如果途中遇到公共前缀部分为空,则说明不存在公共前缀,函数返回空字符串。代码如下:

    /**
     * @param {string[]} strs
     * @return {string}
     */
    var longestCommonPrefix = function(strs) {
      if(strs.length === 0)
        return "";
      
      let prefix = strs[0];
      for(let i = 1;i < strs.length;i++) {
        let cur = strs[i];
        let index = 0;
        if(prefix === '')
          break;
        while(index < prefix.length && index < cur.length) {
          if(prefix[index] !== cur[index])
            break;
          index++;
        }
        prefix = prefix.slice(0, index);
        console.log(prefix);
      }
      
      return prefix;
    };
    

    欢迎关注前端亚古兽微信公众号,持续干货输出

    第 1 条附言  ·  2020-02-28 10:13:38 +08:00
    第 2 条附言  ·  2020-02-28 13:39:51 +08:00

    更新解法

    发现之前的解法时间复杂度比较高,在最坏的情况下复杂度是O(n^2);所以优化一下,用空间换时间,维护一个map存储当前字符串每个字符出现的次数;时间复杂度O(n),空间复杂度O(n) 之前写的比较急,感谢老哥指出问题

    
    /**
     * @param {string} s
     * @return {number}
     */
    var lengthOfLongestSubstring = function(s) {
        if(s.length === 0 || s.length === 1)  
            return s.length;
        let cur = '', max = 0, map = {};
        for(let left = 0, right = 0;right < s.length;right++) {
            const rightChar = s[right];
            if(map[rightChar]) {
                map[rightChar]++;
            } else {
                map[rightChar] = 1;
            }
            
            // 如果发现重复的字符,会从左侧一直删除,直到重复的字符已经被删除为止
            while(map[rightChar] > 1) {
                const leftChar = s[left];
                map[leftChar]--;
                left++;
            }
            if(right - left + 1 > max) {
                max = right - left + 1;
            }
        }
        
        return max;
    };
    
    30 条回复    2020-02-28 22:41:14 +08:00
    MOONLIGHTT
        1
    MOONLIGHTT  
       2020-02-27 21:41:26 +08:00
    翻到最后,果然看到了该看的东西
    behappy
        2
    behappy  
       2020-02-27 22:24:08 +08:00
    老哥很棒。支持!
    optional
        3
    optional  
       2020-02-27 23:00:23 +08:00
    你确定这个解法能过关?
    yangbin9317
        4
    yangbin9317  
       2020-02-28 05:47:10 +08:00 via iPhone
    第一个是 lc 第三题滑动窗口 应该用个 map 记录字符上次出现位置
    pwrliang
        5
    pwrliang  
       2020-02-28 07:57:06 +08:00 via Android
    你第一题解法如果一个字符不重复,时间复杂度不是 O(n^2)?
    starcraft
        6
    starcraft  
       2020-02-28 08:40:57 +08:00
    @pwrliang 你别这样 人家在推广恰饭呢
    zzzzzzggggggg
        7
    zzzzzzggggggg  
    OP
       2020-02-28 10:10:00 +08:00
    @optional 过了 oj 才发的,我不会乱发的哈哈
    zzzzzzggggggg
        8
    zzzzzzggggggg  
    OP
       2020-02-28 10:11:30 +08:00
    @MOONLIGHTT 感兴趣就看看呗,我会持续更新
    zzzzzzggggggg
        9
    zzzzzzggggggg  
    OP
       2020-02-28 10:11:41 +08:00
    @behappy 谢谢,一起输出
    zzzzzzggggggg
        10
    zzzzzzggggggg  
    OP
       2020-02-28 10:14:36 +08:00
    @starcraft 也不算恰饭吧,写的文章就应该拿出来让大家批判,不然自己也没法进步,您说对不?
    zzzzzzggggggg
        11
    zzzzzzggggggg  
    OP
       2020-02-28 10:14:46 +08:00
    @pwrliang 稍等,我看下
    optional
        12
    optional  
       2020-02-28 10:58:36 +08:00
    @zzzzzzggggggg 不说复杂度是 n^2,还有字符串拼接,是一个比较差的答案。
    tt67wq
        13
    tt67wq  
       2020-02-28 11:06:00 +08:00
    翻到最后,果然看到了该看的东西
    zzzzzzggggggg
        14
    zzzzzzggggggg  
    OP
       2020-02-28 12:08:00 +08:00
    @optional OK 我晚上再看看优化一次,欢迎老哥多批评,跟老哥学习一波
    zzzzzzggggggg
        15
    zzzzzzggggggg  
    OP
       2020-02-28 12:08:38 +08:00
    @tt67wq 那我以后发帖把这个删掉吧,感觉太明显也不太好
    alalida
        16
    alalida  
       2020-02-28 12:16:01 +08:00
    我推荐你去 leetcode 的 discussion 看看,还有 geeksforgeeks,多采用些经典解法,否则对解算法题没什么作用的。
    zzzzzzggggggg
        17
    zzzzzzggggggg  
    OP
       2020-02-28 12:23:35 +08:00
    @alalida 嗯嗯谢谢,写东西比较急了,我的锅
    zzzzzzggggggg
        18
    zzzzzzggggggg  
    OP
       2020-02-28 13:40:41 +08:00
    @alalida
    @optional
    @yangbin9317
    @pwrliang
    @starcraft
    更新了一波解法,之前写的比较急,感谢老哥指出问题
    optional
        19
    optional  
       2020-02-28 14:54:11 +08:00
    @zzzzzzggggggg 这题标准的滑动窗口,append 的还是错的。
    Asuka3
        20
    Asuka3  
       2020-02-28 14:59:06 +08:00 via iPhone
    第二题见过不少思路 分治 前缀树之类的 复杂度都是 O(n) 不过可以拓展思路
    zzzzzzggggggg
        21
    zzzzzzggggggg  
    OP
       2020-02-28 15:20:27 +08:00
    @optional 更新的做法就是用滑动窗口做的呀,老哥说说哪儿错了?
    zzzzzzggggggg
        22
    zzzzzzggggggg  
    OP
       2020-02-28 15:23:07 +08:00
    @Asuka3 嗯嗯对的
    cstj0505
        23
    cstj0505  
       2020-02-28 15:45:45 +08:00
    第二个问题的揭发还是不太好,lz 可以去复习下数据结构吧
    aguesuka
        24
    aguesuka  
       2020-02-28 16:05:59 +08:00
    第一个问题的解法还是不好
    optional
        25
    optional  
       2020-02-28 16:12:53 +08:00
    @zzzzzzggggggg 你这不是『滑动窗口』,是一种优化的遍历,滑动窗口的复杂度可以在 O(n)里解决这个问题,但是你这个 for 里面有个 while, 极端条件下,比如 abcda,它的复杂度就变成了 n^2.
    optional
        26
    optional  
       2020-02-28 16:16:43 +08:00
    第二题又是字符串剪切、拼接,,最多 60 分。
    yuwangG
        27
    yuwangG  
       2020-02-28 17:29:16 +08:00
    leetcode 考虑下
    ftfunjth
        28
    ftfunjth  
       2020-02-28 17:35:36 +08:00 via Android
    第二题貌似可以用字典树生成字典树求最长的只有一个子节点的公共父子树
    zzzzzzggggggg
        29
    zzzzzzggggggg  
    OP
       2020-02-28 21:55:04 +08:00
    @optional 我琢磨琢磨,谢了老哥
    zzzzzzggggggg
        30
    zzzzzzggggggg  
    OP
       2020-02-28 22:41:14 +08:00
    @ftfunjth
    @aguesuka
    @cstj0505
    @yuwangG 感谢老哥,我再去找找更好的解决思路
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   945 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 21:23 · PVG 05:23 · LAX 14:23 · JFK 17:23
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.