字符串专题

2020/02/02 Prolems

目录

53. 最大子序和 简单

  • 题目描述

    「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。前五项如下:

    1. 1
    2. 11
    3. 21
    4. 1211
    5. 111221

    1 被读作  ”one 1”  (“一个一”) , 即 11。
    11 被读作 ”two 1s” (“两个一”), 即 21。
    21 被读作 ”one 2”,  ”one 1” (”一个二” ,  ”一个一”) , 即 1211。

    给定一个正整数 n(1 ≤ n ≤ 30),输出外观数列的第 n 项。

    Example:

    输入: 4
    输出: “1211”
    解释:当 n = 3 时,序列是 “21”,其中我们有 “2” 和 “1” 两组,”2” 可以读作 “12”,也就是出现频次 = 1 而 值 = 2;类似 “1” 可以读作 “11”。所以答案是 “12” 和 “11” 组合在一起,也就是 “1211”。

  • 解法

    挨个遍历字符,如果这个字符跟上一个字符不一样,输出数量加上一个字符。

  • 代码

      class Solution {
          public String countAndSay(int n) {
              if(n==0) return "";
              String res = "1";
              for(int i=1;i<n;i++){
                  res = helper(res.toCharArray());
              }
              return res;
          }
          public String helper(char[] cs){
              StringBuilder sb = new StringBuilder();
              char pre = cs[0]; //前一个字符
              int count = 1;
              for(int i=1;i<cs.length;i++){
                  if(pre==cs[i]){
                      count++;
                  }else{
                      sb.append(count);
                      sb.append(pre);
                      count=1;
                  }
                  pre = cs[i];
              }
              sb.append(count);
              sb.append(pre);
              return sb.toString();
          }
      }
    

49. 字母异位词分组 中等

  • 题目描述

    给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

    Example:

    输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
    输出:
    [
    [“ate”,”eat”,”tea”],
    [“nat”,”tan”],
    [“bat”]
    ]

  • 解法

    将字符串转换为数组后排序在转字符串(不能用数组取 Hash),这样放到 hashmap 中就可以记录了。

  • 代码

      class Solution {
          public String countAndSay(int n) {
              if(n==0) return "";
              String res = "1";
              for(int i=1;i<n;i++){
                  res = helper(res.toCharArray());
              }
              return res;
          }
          public String helper(char[] cs){
              StringBuilder sb = new StringBuilder();
              char pre = cs[0]; //前一个字符
              int count = 1;
              for(int i=1;i<cs.length;i++){
                  if(pre==cs[i]){
                      count++;
                  }else{
                      sb.append(count);
                      sb.append(pre);
                      count=1;
                  }
                  pre = cs[i];
              }
              sb.append(count);
              sb.append(pre);
              return sb.toString();
          }
      }
    

151. 翻转字符串里的单词 中等

  • 题目描述

    给定一个字符串,逐个翻转字符串中的每个单词。

    Example:

    输入: “the sky is blue”
    输出: “blue is sky the”

  • 解法

    最简单方法可以放到一个栈中,遇到空格就把栈里面内容都输出来。

    如果不能用辅助空间,可以先把字符串完全 reverse,再把每个单词 reverse。

  • 代码

      class Solution {
          public String reverseWords(String s) {
              // 先全转过来,再把单词转过来
              String temp = s.trim();
              if(temp.equals("")) return "";
              String allReverse = new StringBuffer(temp).reverse().toString();
              String[] ss = allReverse.split(" ");
              StringBuilder sb = new StringBuilder();
              for(String s2:ss){
                  if(s2.equals("")) continue;
                  sb.append(new StringBuilder(s2).reverse());
                  sb.append(" ");
              }
              return sb.substring(0,sb.length()-1);
          }
          // public String reverseWords(String s) {
          //     // 先全转过来,再把单词转过来
          //     String temp = s.trim();
          //     if(temp.equals("")) return "";
          //     char[] cs = temp.toCharArray();
          //     reverse(cs,0,cs.length-1);
          //     int start = 0;
          //     for(int i=0;i<cs.length;i++){
          //         if(cs[i]==' '){
          //             reverse(cs,start,i-1);
          //             start = i+1;
          //         }
          //     }
          //     reverse(cs,start,cs.length-1);
          //     return String.valueOf(cs);
          // }
          // public void reverse(char[] cs,int start,int end){
          //     char[] res = new char[end-start+1];
          //     int j = 0;
          //     for(int i=end;i>=start;i--){
          //         res[j++] = cs[i];
          //     }
          //     j = 0;
          //     for(int i=start;i<=end;i++){
          //         cs[i] = res[j++];
          //     }
          // }
      }
    

165. 比较版本号 中等

  • 题目描述

    比较两个版本号 version1 和 version2。

    如果 version1 > version2 返回 1,如果 version1 < version2 返回 -1, 除此之外返回 0。

    你可以假设版本字符串非空,并且只包含数字和 . 字符。

     . 字符不代表小数点,而是用于分隔数字序列。

    例如,2.5 不是“两个半”,也不是“差一半到三”,而是第二版中的第五个小版本。

    你可以假设版本号的每一级的默认修订版号为 0。例如,版本号 3.4 的第一级(大版本)和第二级(小版本)修订号分别为 3 和 4。其第三级和第四级修订号均为 0。

    Example:

    输入: version1 = “1.0.1”, version2 = “1”
    输出: 1

  • 解法

    先把版本号按 . 分割,然后比较每个版本的大小

  • 代码

      class Solution {
          public int compareVersion(String version1, String version2) {
              String[] v1 = version1.split(" ");
              String[] v2 = version2.split(" ");
              int i=0;
              int j=0;
              while (i < v1.length || j < v2.length) {
                  String num1 = i < v1.length ? v1[i] : "0";
                  String num2 = j < v2.length ? v2[j] : "0";
                  int res = compare(num1, num2);
                  if (res == 0) {
                      i++;
                      j++;
                  } else {
                      return res;
                  }
              }
              return 0;
          }
          public int compare(String num1,String num2){
              String n1 = removeFrontZero(num1);
              String n2 = removeFrontZero(num2);
              if (num1.length() > num2.length()) {
                  return 1;
              } else if (num1.length() < num2.length()) {
                  return -1;
              } else {
                  //长度相等的时候
                  for (int i = 0; i < num1.length(); i++) {
                      if (num1.charAt(i) - num2.charAt(i) > 0) {
                          return 1;
                      } else if (num1.charAt(i) - num2.charAt(i) < 0) {
                          return -1;
                      }
                  }
                  return 0;
              }
          }
          private String removeFrontZero(String num) {
              int start = 0;
              for (int i = 0; i < num.length(); i++) {
                  if (num.charAt(i) == '0') {
                      start++;
                  } else {
                      break;
                  }
              }
              return num.substring(start);
          }
      }
    

5. 最长回文子串 中等

  • 题目描述

    给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

    Example:

    输入: “babad”
    输出: “bab”
    注意: “aba” 也是一个有效答案。

  • 解法

    回文需要考虑两种可能性,第一种是一个字符作为中间数,第二种是两个数作为中间数。然后以中间数为中心往两边扩展,两边数一样就还是回文。

  • 代码

      class Solution {
          public String longestPalindrome(String s) {
              if(s.equals("")) return "";
              if(s.length()==1) return s;
              // 两种情况,一种是以中间一个词为中心。另一种是中间两个词为中心
              char[] cs = s.toCharArray();
              int max = 1;
              String res = s.substring(0,1);
              boolean[][] dp = new boolean[cs.length][cs.length];
              for(int i=0;i<dp.length;i++){
                  dp[i][i] = true;
                  if(i>0 && cs[i]==cs[i-1]){
                      dp[i-1][i] = true;
                      max = 2;
                      res = s.substring(i-1,i+1);
                  }
              }
              for(int i=0;i<cs.length;i++){
                  int k=1;
                  while(i-k>=0 && i+k<cs.length){
                      if(dp[i-k+1][i+k-1]==true && cs[i-k]==cs[i+k]){
                          dp[i-k][i+k] = true;
                          if(k*2+1>max){
                              max = k*2+1;
                              res = s.substring(i-k,i+k+1);
                          }
                          k++;
                      }else{
                          break;
                      }
                  }
              }
              for(int i=0;i<cs.length-1;i++){
                  int k=1;
                  while(i-k>=0 && i+1+k<cs.length){
                      if(dp[i-k+1][i+k]==true && cs[i-k]==cs[i+1+k]){
                          dp[i-k][i+k+1] = true;
                          if(k*2+2>max){
                              max = k*2+2;
                              res = s.substring(i-k,i+k+2);
                          }
                          k++;
                      }else{
                          break;
                      }
                  }
              }
              return res;
          }
      }
    

3. 无重复字符的最长子串 中等

  • 题目描述

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

    Example:

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

  • 解法

    双指针,记录一个开始位置,用一个 map 记录所有的出现过的字符。当一个字符发现在 start 后出现过了,就把 start 移到出现过的位置下一个。

  • 代码

      class Solution {
          public int lengthOfLongestSubstring(String s) {
              int start = 0;// 双指针,另一个指针是 i
              int max = 0;
              Map<Character,Integer> map = new HashMap<>();
              char[] cs = s.toCharArray();
              for(int i=0;i<cs.length;i++){
                  Character c = cs[i];
                  Integer po = map.get(c);
                  if(po!=null && po>=start){ //一定要有后面的判断,因为随着 start 位置的更新,map 中有些位置的 index 已经在 start 后了,其实也就没有这个重复的字符了
                      max = Math.max(max, i-start);
                      start = po+1;//之前出现的位置的下一个位置是新的起点
                  }
                  map.put(c,i); //要把此时的位置更新进去
              }
              max = Math.max(max, s.length()-start);
              return max;
          }
      }
    

208. 实现 Trie (前缀树) 中等

  • 题目描述

    实现一个 Trie (前缀树),包含 insert, search, 和 startsWith 这三个操作。

    Example:

    Trie trie = new Trie();
    trie.insert(“apple”);
    trie.search(“apple”); // 返回 true
    trie.search(“app”); // 返回 false
    trie.startsWith(“app”); // 返回 true
    trie.insert(“app”);
    trie.search(“app”); // 返回 true

  • 解法

    每一个节点保存 26 个子节点。

  • 代码

      class Trie {
    
          TrieNode root = new TrieNode();
          /** Initialize your data structure here. */
          public Trie() {
                
          }
            
          /** Inserts a word into the trie. */
          public void insert(String word) {
              root.insert(word,0);
          }
            
          /** Returns if the word is in the trie. */
          public boolean search(String word) {
              TrieNode trie = root.findChar(word,0);
              if(trie!=null && trie.wordEnd == true) return true;
              return false;
          }
            
          /** Returns if there is any word in the trie that starts with the given prefix. */
          public boolean startsWith(String prefix) {
              TrieNode trie = root.findChar(prefix,0);
              if(trie!=null) return true;
              return false;
          }
      }
    
      class TrieNode{
          TrieNode[] children = new TrieNode[26];
          boolean wordEnd = false;
          public void insert(String word, int index){
              if(index == word.length()){
                  wordEnd = true;
                  return;
              }
              int pos = word.charAt(index)-'a';
              if(children[pos]==null){
                  children[pos] = new TrieNode();
              }
              children[pos].insert(word, index+1);
          }
            
          public TrieNode findChar(String word, int index){
              if(index == word.length()){
                  return this;
              }
              int pos = word.charAt(index)-'a';
              if(children[pos]==null) return null;
              return children[pos].findChar(word,index+1);
          }
      }
    
      /**
      * Your Trie object will be instantiated and called as such:
      * Trie obj = new Trie();
      * obj.insert(word);
      * boolean param_2 = obj.search(word);
      * boolean param_3 = obj.startsWith(prefix);
      */
    

Search

    Table of Contents