[算法总结] 搞定 BAT 面试——几道常见的子符串算法题

1. KMP 算法

谈到字符串问题,不得不提的就是 KMP 算法,它是用来解决字符串查找的问题,可以在一个字符串(S)中查找一个子串(W)出现的位置。KMP 算法把字符匹配的时间复杂度缩小到 O(m+n) ,而空间复杂度也只有O(m)。因为“暴力搜索”的方法会反复回溯主串,导致效率低下,而KMP算法可以利用已经部分匹配这个有效信息,保持主串上的指针不回溯,通过修改子串的指针,让模式串尽量地移动到有效的位置。
具体算法细节请参考:
  • 字符串匹配的KMP算法:http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
  • 从头到尾彻底理解KMP: https://blog.csdn.net/vjulyv/article/details/7041827
  • 如何更好的理解和掌握 KMP 算法?: https://www.zhihu.com/question/21923021
  • KMP 算法详细解析: https://blog.sengxian.com/algorithms/kmp
  • 图解 KMP 算法: http://blog.jobbole.com/76611/
  • 汪都能听懂的KMP字符串匹配算法【双语字幕】: https://www.bilibili.com/video/av3246487/?from=search&seid=17173603269940723925
  • KMP字符串匹配算法1: https://www.bilibili.com/video/av11866460?from=search&seid=12730654434238709250
除此之外,再来了解一下BM算法!
BM算法也是一种精确字符串匹配算法,它采用从右向左比较的方法,同时应用到了两种启发式规则,即坏字符规则 和好后缀规则 ,来决定向右跳跃的距离。基本思路就是从右往左进行字符匹配,遇到不匹配的字符后从坏字符表和好后缀表找一个最大的右移值,将模式串右移继续匹配。 《字符串匹配的KMP算法》:http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

2. 替换空格

剑指offer:请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
这里我提供了两种方法:①常规方法;②利用 API 解决。
  1. //https://www.weiweiblog.cn/replacespace/
  2. publicclassSolution{
  3.    /**
  4.     * 第一种方法:常规方法。利用String.charAt(i)以及String.valueOf(char).equals(" "
  5.     * )遍历字符串并判断元素是否为空格。是则替换为"%20",否则不替换
  6.     */
  7.    publicstaticString replaceSpace(StringBuffer str){
  8.        int length = str.length();
  9.        // System.out.println("length=" + length);
  10.        StringBuffer result =newStringBuffer();
  11.        for(int i =0; i < length; i++){
  12.            char b = str.charAt(i);
  13.            if(String.valueOf(b).equals(" ")){
  14.                result.append("%20");
  15.            }else{
  16.                result.append(b);
  17.            }
  18.        }
  19.        return result.toString();
  20.    }
  21.    /**
  22.     * 第二种方法:利用API替换掉所用空格,一行代码解决问题
  23.     */
  24.    publicstaticString replaceSpace2(StringBuffer str){
  25.        return str.toString().replaceAll("\s","%20");
  26.    }
  27. }

3. 最长公共前缀

Leetcode: 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 “”。
示例 1:
  1. 输入:["flower","flow","flight"]
  2. 输出:"fl"
示例 2:
  1. 输入:["dog","racecar","car"]
  2. 输出:""
  3. 解释:输入不存在公共前缀。
思路很简单!先利用Arrays.sort(strs)为数组排序,再将数组第一个元素和最后一个元素的字符从前往后对比即可!
  1. //https://leetcode-cn.com/problems/longest-common-prefix/description/
  2. publicclassMain{
  3.    publicstaticString replaceSpace(String[] strs){
  4.        // 数组长度
  5.        int len = strs.length;
  6.        // 用于保存结果
  7.        StringBuffer res =newStringBuffer();
  8.        // 注意:=是赋值,==是判断
  9.        if(strs ==null|| strs.length ==0){
  10.            return"";
  11.        }
  12.        // 给字符串数组的元素按照升序排序(包含数字的话,数字会排在前面)
  13.        Arrays.sort(strs);
  14.        int m = strs[0].length();
  15.        int n = strs[len -1].length();
  16.        int num =Math.min(m, n);
  17.        for(int i =0; i < num; i++){
  18.            if(strs[0].charAt(i)== strs[len -1].charAt(i)){
  19.                res.append(strs[0].charAt(i));
  20.            }else
  21.                break;
  22.        }
  23.        return res.toString();
  24.    }
  25.     //测试
  26.    publicstaticvoid main(String[] args){
  27.        String[] strs ={"customer","car","cat"};
  28.        System.out.println(Main.replaceSpace(strs));//c
  29.    }
  30. }

4. 回文串

4.1. 最长回文串

LeetCode: 给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。在构造过程中,请注意区分大小写。比如 "Aa"不能当做一个回文字符串。注 意:假设字符串的长度不会超过 1010。
回文串:“回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。——百度百科 地址:https://baike.baidu.com/item/%E5%9B%9E%E6%96%87%E4%B8%B2/1274921?fr=aladdin
示例 1:
  1. 输入:
  2. "abccccdd"
  3. 输出:
  4. 7
  5. 解释:
  6. 我们可以构造的最长的回文串是"dccaccd",它的长度是7
我们上面已经知道了什么是回文串?现在我们考虑一下可以构成回文串的两种情况:
  • 字符出现次数为双数的组合
  • 字符出现次数为双数的组合+一个只出现一次的字符
统计字符出现的次数即可,双数才能构成回文。因为允许中间一个数单独出现,比如“abcba”,所以如果最后有字母落单,总长度可以加 1。首先将字符串转变为字符数组。然后遍历该数组,判断对应字符是否在hashset中,如果不在就加进去,如果在就让count++,然后移除该字符!这样就能找到出现次数为双数的字符个数。
  1. //https://leetcode-cn.com/problems/longest-palindrome/description/
  2. classSolution{
  3.    public  int longestPalindrome(String s){
  4.        if(s.length()==0)
  5.            return0;
  6.        // 用于存放字符
  7.        HashSet<Character> hashset =newHashSet<Character>();
  8.        char[] chars = s.toCharArray();
  9.        int count =0;
  10.        for(int i =0; i < chars.length; i++){
  11.            if(!hashset.contains(chars[i])){// 如果hashset没有该字符就保存进去
  12.                hashset.add(chars[i]);
  13.            }else{// 如果有,就让count++(说明找到了一个成对的字符),然后把该字符移除
  14.                hashset.remove(chars[i]);
  15.                count++;
  16.            }
  17.        }
  18.        return hashset.isEmpty()? count *2: count *2+1;
  19.    }
  20. }

4.2. 验证回文串

LeetCode: 给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。 说明:本题中,我们将空字符串定义为有效的回文串。
示例 1:
  1. 输入:"A man, a plan, a canal: Panama"
  2. 输出:true
示例 2:
  1. 输入:"race a car"
  2. 输出:false
  1. //https://leetcode-cn.com/problems/valid-palindrome/description/
  2. classSolution{
  3.    public  boolean isPalindrome(String s){
  4.        if(s.length()==0)
  5.            returntrue;
  6.        int l =0, r = s.length()-1;
  7.        while(l < r){
  8.            // 从头和尾开始向中间遍历
  9.            if(!Character.isLetterOrDigit(s.charAt(l))){// 字符不是字母和数字的情况
  10.                l++;
  11.            }elseif(!Character.isLetterOrDigit(s.charAt(r))){// 字符不是字母和数字的情况
  12.                r--;
  13.            }else{
  14.                // 判断二者是否相等
  15.                if(Character.toLowerCase(s.charAt(l))!=Character.toLowerCase(s.charAt(r)))
  16.                    returnfalse;
  17.                l++;
  18.                r--;
  19.            }
  20.        }
  21.        returntrue;
  22.    }
  23. }

4.3. 最长回文子串

Leetcode: LeetCode: 最长回文子串 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例 1:
  1. 输入:"babad"
  2. 输出:"bab"
  3. 注意:"aba"也是一个有效答案。
示例 2:
  1. 输入:"cbbd"
  2. 输出:"bb"
以某个元素为中心,分别计算偶数长度的回文最大长度和奇数长度的回文最大长度。给大家大致花了个草图,不要嫌弃!
  1. //https://leetcode-cn.com/problems/longest-palindromic-substring/description/
  2. classSolution{
  3.    privateint index, len;
  4.    publicString longestPalindrome(String s){
  5.        if(s.length()<2)
  6.            return s;
  7.        for(int i =0; i < s.length()-1; i++){
  8.            PalindromeHelper(s, i, i);
  9.            PalindromeHelper(s, i, i +1);
  10.        }
  11.        return s.substring(index, index + len);
  12.    }
  13.    publicvoidPalindromeHelper(String s,int l,int r){
  14.        while(l >=0&& r < s.length()&& s.charAt(l)== s.charAt(r)){
  15.            l--;
  16.            r++;
  17.        }
  18.        if(len < r - l -1){
  19.            index = l +1;
  20.            len = r - l -1;
  21.        }
  22.    }
  23. }

4.4. 最长回文子序列

LeetCode: 最长回文子序列 给定一个字符串s,找到其中最长的回文子序列。可以假设s的最大长度为1000。最长回文子序列和上一题最长回文子串的区别是,子串是字符串中连续的一个序列,而子序列是字符串中保持相对位置的字符序列,例如,”bbbb”可以是字符串”bbbab”的子序列但不是子串。
给定一个字符串s,找到其中最长的回文子序列。可以假设s的最大长度为1000。
示例 1:
  1. 输入:
  2. "bbbab"
  3. 输出:
  4. 4
一个可能的最长回文子序列为 “bbbb”。
示例 2:
  1. 输入:
  2. "cbbd"
  3. 输出:
  4. 2
一个可能的最长回文子序列为 “bb”。
动态规划: dp[i][j] = dp[i+1][j-1] + 2 if s.charAt(i) == s.charAt(j) otherwise, dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
  1. classSolution{
  2.    publicint longestPalindromeSubseq(String s){
  3.        int len = s.length();
  4.        int[][] dp =newint[len][len];
  5.        for(int i = len -1; i>=0; i--){
  6.            dp[i][i]=1;
  7.            for(int j = i+1; j < len; j++){
  8.                if(s.charAt(i)== s.charAt(j))
  9.                    dp[i][j]= dp[i+1][j-1]+2;
  10.                else
  11.                    dp[i][j]=Math.max(dp[i+1][j], dp[i][j-1]);
  12.            }
  13.        }
  14.        return dp[0][len-1];
  15.    }
  16. }

5. 括号匹配深度

爱奇艺 2018 秋招 Java: 一个合法的括号匹配序列有以下定义:
  1. 空串””是一个合法的括号匹配序列
  2. 如果”X”和”Y”都是合法的括号匹配序列,”XY”也是一个合法的括号匹配序列
  3. 如果”X”是一个合法的括号匹配序列,那么”(X)”也是一个合法的括号匹配序列
  4. 每个合法的括号序列都可以由以上规则生成。
例如: “”,”()”,”()()”,”((()))”都是合法的括号序列 对于一个合法的括号序列我们又有以下定义它的深度:
  1. 空串””的深度是0
  2. 如果字符串”X”的深度是x,字符串”Y”的深度是y,那么字符串”XY”的深度为max(x,y)
  3. 如果”X”的深度是x,那么字符串”(X)”的深度是x+1
例如: “()()()”的深度是1,”((()))”的深度是3。牛牛现在给你一个合法的括号序列,需要你计算出其深度。
  1. 输入描述:
  2. 输入包括一个合法的括号序列s,s长度length(2 length 50),序列中只包含'('')'
  3. 输出描述:
  4. 输出一个正整数,即这个序列的深度。
示例:
  1. 输入:
  2. (())
  3. 输出:
  4. 2
思路草图:
代码如下:
  1. import java.util.Scanner;
  2.  
  3. publicclassMain{
  4.    publicstaticvoid main(String[] args){
  5.        Scanner sc =newScanner(System.in);
  6.        String s = sc.nextLine();
  7.        int count=0, max =0, i;
  8.        for(i =0; i < s.length();++i){
  9.            if(s.charAt(i)=='(')
  10.                count++;
  11.            else
  12.                count--;
  13.            max =Math.max(max, count);
  14.        }
  15.        sc.close();
  16.        System.out.println(max);
  17.    }
  18. }

6. 把字符串转换成整数

剑指offer: 将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能,但是string不符合数字要求时返回0),要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。
  1. //https://www.weiweiblog.cn/strtoint/
  2. publicclassMain{
  3.    publicstaticintStrToInt(String str){
  4.        if(str.length()==0)
  5.            return0;
  6.        char[] chars = str.toCharArray();
  7.        // 判断是否存在符号位
  8.        int flag =0;
  9.        if(chars[0]=='+')
  10.            flag =1;
  11.        elseif(chars[0]=='-')
  12.            flag =2;
  13.        int start = flag >0?1:0;
  14.        int res =0;// 保存结果
  15.        for(int i = start; i < chars.length; i++){
  16.            if(Character.isDigit(chars[i])){// 调用Character.isDigit(char)方法判断是否是数字,是返回True,否则False
  17.                int temp = chars[i]-'0';
  18.                res = res *10+ temp;
  19.            }else{
  20.                return0;
  21.            }
  22.        }
  23.        return flag ==1? res :-res;
  24.    }
  25.    publicstaticvoid main(String[] args){
  26.        // TODO Auto-generated method stub
  27.        String s ="-12312312";
  28.        System.out.println("使用库函数转换:"+Integer.valueOf(s));
  29.        int res =Main.StrToInt(s);
  30.        System.out.println("使用自己写的方法转换:"+ res);
  31.    }
  32. }
本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » [算法总结] 搞定 BAT 面试——几道常见的子符串算法题

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多