1、剑指 Offer 58 - II.左旋转字符串

1.1 题目

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。
示例 1：

输入: s = “abcdefg”, k = 2 输出: “cdefgab”

示例 2：

输入: s = “lrloseumgh”, k = 6 输出: “umghlrlose”

1.2 思路

没啥特别的，就substring方法的使用。

1.3 代码

  1. class Solution {
  2.     public String reverseLeftWords(String s, int n) {
  3.         return s.substring(n, s.length()) + s.substring(0, n);
  4.     }
  5. }

2、剑指 Offer 05.替换空格

2.1 题目

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。
示例1：

输入：s = “We are happy.” 输出：”We%20are%20happy.”

2.2 思路

遍历字符串中的每一个字符，遇到空格就用”%20”替换，用StringBuilder.append。

2.3 代码

  1. class Solution {
  2.     public String replaceSpace(String s) {
  3.         StringBuilder sb = new StringBuilder();
  4.         for (char ch: s.toCharArray()) {
  5.             if (ch == ' ') {
  6.                 sb.append("%20");
  7.             } else {
  8.                 sb.append(ch);
  9.             }
  10.         }
  11.         return sb.toString();
  12.     }
  13. }

3、剑指 Offer 50. 第一个只出现一次的字符

3.1 题目

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例 1:

输入：s = “abaccdeff” 输出：’b’

示例 2:

输入：s = “” 输出：’ ‘

3.2 思路

  1. 需要两次遍历，第一次遍历字符串获得字符串中每个字符出现的次数，存在哈希表中；
  2. 第二次遍历这个哈希表，找到第一个value为1的key，返回；

  3. 注意：因为要获取第一个出现次数为1的key，因此哈希表要维护k-v的插入顺序，因此选择LinkedHashMap。

    3.3 代码

    1. class Solution {
    2.  public char firstUniqChar(String s) {
    3.      LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();
    4.      char res = ' ';
    5.      for (Character ch: s.toCharArray()) {
    6.          map.put(ch, map.getOrDefault(ch, 0) + 1);
    7.      }
    9.      for (Map.Entry<Character, Integer> entry: map.entrySet()) {
    10.          int cnt = entry.getValue();
    11.          if (cnt == 1) {
    12.              return entry.getKey();
    13.          }
    14.      }
    15.      return res;
    16.  }
    17. }

    4、剑指 Offer 38. 字符串的排列

    4.1 题目

    输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
    示例：

    输入：s = “abc” 输出：[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]

4.2 思路

这道题是回溯算法的经典题目。但需要注意以下几点：

  1. 字符串s里可能出现重复字母，比如aab，此时如果对结果不去重，会出现两个aab和两个baa，因为两个a是下标区分的，因此结果可以用set去重；

  2. 由于字符串每个下标上的字母只能使用一次，因此需要维护一个visited数组，当下标对应的字母add进sb时，则visited数组对应下标记为1，代表当前字符串对应下标的字母已经被使用了，在回退时也要将visited数组对应下标的值恢复为0。

    4.3 代码

    1. class Solution {
    2.  public String[] permutation(String s) {
    3.      Set<String> set = new HashSet<>();
    4.      StringBuilder sb = new StringBuilder();
    5.      int[] visited = new int[s.length()];
    6.      trace(s, set, sb, visited);
    7.      return set.toArray(new String[0]);
    8.  }
    10.  private void trace(String s, Set<String> set, StringBuilder sb, int[] visited) {
    11.      if (sb.toString().length() == s.length()) {
    12.          set.add(sb.toString());
    13.          return;
    14.      }
    15.      for (int i = 0; i < s.length(); ++i) {
    16.          if (visited[i] == 1) {
    17.              continue;
    18.          }
    19.          sb.append(s.charAt(i));
    20.          visited[i] = 1;
    21.          trace(s, set, sb, visited);
    23.          // 回退
    24.          sb.deleteCharAt(sb.toString().length() - 1);
    25.          visited[i] = 0;
    26.      }
    27.  }
    28. }

    5、剑指 Offer 37.序列化二叉树

    5.1 题目

    请实现两个函数，分别用来序列化和反序列化二叉树。
    你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
    示例：
    字符串 - 图1

    输入：root = [1,2,3,null,null,4,5] 输出：[1,2,3,null,null,4,5]

5.2 思路

采用深度优先搜索的思想。

  1. 序列化

前序遍历二叉树，将值用逗号分割开，叶子节点将null值也用null字符串返回，比如：”1,2,null,null,3,4,null,null,5,null.null”。注意在序列化的dfs函数里，只append root节点的值，左右子树仅递归，无需append。

  1. 反序列化

由于序列化生成的字符串是由先序遍历生成，因此反序列化里也采用先序遍历的dfs函数。每次dfs仅处理list链表的首元素，具体地：

  1. 当首元素为null字符串时，返回null的TreeNode，并且把这个首元素从list中移除；
  2. 以当前list链表的首元素来new一个TreeNode，先dfs左子树，后dfs右子树。

    5.3 代码

    ```java import java.util.Arrays; import java.util.LinkedList; import java.util.List;

public class Codec { public String serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); serializeDfs(root, sb); return sb.toString(); }

  1. private StringBuilder serializeDfs(TreeNode root, StringBuilder sb) {
  2.     if (root == null) {
  3.         sb.append("null").append(",");
  4.         return sb;
  5.     }
  6.     sb.append(root.val).append(",");
  7.     serializeDfs(root.left, sb);
  8.     serializeDfs(root.right, sb);
  9.     return sb;
  10. }
  12. public TreeNode deserialize(String data) {
  13.     String[] array = data.split(",");
  14.     LinkedList<String> list = new LinkedList<>(Arrays.asList(array));
  15.     return deserializeDfs(list);
  16. }
  18. private TreeNode deserializeDfs(List<String> list) {
  19.     if ("null".equals(list.get(0))) {
  20.         list.remove(0);
  21.         return null;
  22.     }
  23.     TreeNode root = new TreeNode(Integer.parseInt(list.get(0)));
  24.     list.remove(0);
  25.     root.left = deserializeDfs(list);
  26.     root.right = deserializeDfs(list);
  27.     return root;
  28. }

}

  1. <a name="oN3SK"></a>
  2. # 6、[剑指 Offer 45. 把数组排成最小的数](https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/)
  3. <a name="nmRLY"></a>
  4. ## 6.1 题目
  5. 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。<br />示例 1:
  6. > 输入: [10,2] 输出: "102"
  8. 示例 2:
  9. > 输入: [3,30,34,5,9] 输出: "3033459"
  11. <a name="HTV3L"></a>
  12. ## 6.2 思路
  13. 这个题的思路需要证明，感觉解法还是背下来吧......
  14. <a name="kyyz7"></a>
  15. ## 6.3 代码
  16. ```java
  17. class Solution {
  18.     public String minNumber(int[] nums) {
  19.         List<String> list = new ArrayList<>();
  20.         for (int num: nums) {
  21.             list.add(String.valueOf(num));
  22.         }
  23.         list.sort((o1, o2) -> (o1 + o2).compareTo(o2 + o1));
  24.         return String.join("", list);
  25.     }
  26. }

7、剑指 Offer 46. 把数字翻译成字符串

7.1 题目

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:

输入: 12258 输出: 5 解释: 12258有5种不同的翻译，分别是”bccfi”, “bwfi”, “bczi”, “mcfi”和”mzi”

7.2 思路

这道题是动态规划的思想。
令dp[i]表示前i个数字的翻译方法数目，状态转移方程为：
初始状态为：dp[0]=dp[1]=1。

关于dp[1]=1这个很好理解，dp[0]的值的确认，是基于状态转移方程，将i=1和i=2代入，返回得到的dp[0]的值。

转移方程的推导见下图：
字符串 - 图2
还需注意以下几点，不然会有bug：

  1. dp[i]的定义是前i个数字对应的翻译方法，对应上图x的下标是从1而不是从0开始的，因此求i位数字对应的翻译方法是求dp[numStr.length()]，因此dp数组的长度是numStr.length() + 1；
  2. 注意Xi-1Xi为”06”这种情况，这种情况虽然6 < 25，但依然不能合并起来翻译，因此可以合并翻译的Xi-1Xi的取值范围是[10, 25]；
  3. 数字组成的字符串比较大小，有两个方案：
    1. 数字字符串转换成数字比较；
    2. 用字符串的compareTo方法，该方法如果返回值<0，则小于，=0，则等于。

      7.3 代码

      1. class Solution {
      2. public int translateNum(int num) {
      3.   String numStr = String.valueOf(num);
      4.   int[] dp = new int[numStr.length() + 1];
      5.   dp[0] = 1;
      6.   dp[1] = 1;
      7.   for (int i = 2; i <= numStr.length(); ++i) {
      8.       String tmpStr = numStr.substring(i - 2, i);
      9.       if (tmpStr.compareTo("10") >= 0 && tmpStr.compareTo("25") <= 0) {
      10.           dp[i] = dp[i - 1] + dp[i - 2];
      11.       } else {
      12.           dp[i] = dp[i - 1];
      13.       }
      14.   }
      15.   return dp[numStr.length()];
      16. }
      17. }

      8、剑指 Offer 48. 最长不含重复字符的子字符串

      8.1 题目

      请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
      示例1：

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

示例2：

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

示例3：

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

请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

8.2 思路

  1. 借助两种数据结构：
    1. set存储有哪些字母插进来了；
    2. stack存储无重复子串。

  2. 注意细节，比如stack和set要同时插入，同时移除。

    8.3 代码

    1. class Solution {
    2.  public int lengthOfLongestSubstring(String s) {
    3.      Set<Character> set = new HashSet<>();
    4.      LinkedList<Character> stack = new LinkedList<>();
    5.      int res = 0;
    7.      for (char ch: s.toCharArray()) {
    8.          while (!stack.isEmpty() && set.contains(ch)) {
    9.              set.remove(stack.peekLast());
    10.              stack.pollLast();
    11.          }
    12.          stack.addFirst(ch);
    13.          set.add(ch);
    14.          res = Math.max(res, stack.size());
    15.      }
    16.      return res;
    17.  }
    18. }

    9、剑指 Offer 58 - I. 翻转单词顺序

    9.1 题目

    输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。
    示例 1：

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

示例 2：

输入: “ hello world! “ 输出: “world! hello” 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: “a good example” 输出: “example good a” 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

9.2 思路

就正常的用代码翻译题目要求即可，注意两个点：

  • 字符串为空字符串和空格字符串，需要注意这种边界条件；
  • StringBuilder的lastIndexOf方法可以返回指定某个字符串最后出现的下标，用于最后一个空格字符串的处理。

    9.3 代码

    1. class Solution {
    2.   public String reverseWords(String s) {
    3.       StringBuilder sb = new StringBuilder();
    4.       String[] array = s.trim().split(" ");
    5.       for (int i = array.length - 1; i >= 0; --i) {
    6.           if (!array[i].equals("")) {
    7.               sb.append(array[i]).append(" ");
    8.           }
    9.       }
    10.       if (!sb.toString().equals("")) {
    11.           sb.deleteCharAt(sb.lastIndexOf(" "));
    12.       }
    13.       return sb.toString();
    14.   }
    15. }

    10、剑指 Offer 19.正则表达式匹配

    放弃，这dp太难了……

    10.1 题目

    请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但与”aa.a”和”ab*a”均不匹配。
    示例 1:
    输入:

    s = “aa” p = “a” 输出: false 解释: “a” 无法匹配 “aa” 整个字符串。

示例 2:
输入:

s = “aa” p = “a“ 输出: true 解释: 因为 ‘‘ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。

示例 3:

输入: s = “ab” p = “.“ 输出: true 解释: “.“ 表示可匹配零个或多个（’*’）任意字符（’.’）。

示例 4:

输入: s = “aab” p = “cab” 输出: true 解释: 因为 ‘*’ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。

示例 5:

输入: s = “mississippi” p = “misisp*.” 输出: false

10.2 思路

10.3 代码

11、剑指 Offer 67. 把字符串转换成整数

11.1 题目

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

  • 首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止；
  • 当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数；
  • 该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响；
  • 注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换；
  • 在任何情况下，若函数不能进行有效的转换时，请返回 0；
  • 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:

输入: “42” 输出: 42

示例 2:

输入: “ -42” 输出: -42 解释: 第一个非空白字符为 ‘-‘, 它是一个负号。我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

示例 3:

输入: “4193 with words” 输出: 4193 解释: 转换截止于数字 ‘3’ ，因为它的下一个字符不为数字。

示例 4:

输入: “words and 987” 输出: 0 解释: 第一个非空字符是 ‘w’, 但它不是数字或正、负号。因此无法执行有效的转换。

示例 5:

输入: “-91283472332” 输出: -2147483648 解释: 数字 “-91283472332” 超过 32 位有符号整数范围。 因此返回 INT_MIN (−231) 。

11.2 思路

这道题本身思路清晰，就是用代码翻译题目，但需要注意边界条件和一些特殊的测试用例：

  • 使用sign来表示符号值（-1、+1），默认值为1；使用startIndex来表示第一位有效数字的下标，默认值为0；
  • 由于字符串首尾可能有空格字符串，因此首先需要对str进行trim()；
  • 需要考虑字符串为空字符串的特殊情况；
  • 需要考虑字符串为”+-2”的特殊测试用例；

  • 需要考虑计算得到的值是否超过了32位有符号整数的范围，计算结果用long型存储，再与INT_MAX (231 − 1) 或 INT_MIN (−231)比较。

    11.3 代码

    1. class Solution {
    2.   public int strToInt(String str) {
    3.       String strTrim = str.trim();
    4.       if (strTrim.equals("")) {
    5.           return 0;
    6.       }
    7.       char first = strTrim.charAt(0);
    8.       int sign = 1, startIndex = 0;
    9.       if (!Character.isDigit(first)) {
    10.           if (first == '+') {
    11.               sign = 1;
    12.               startIndex = 1;
    13.           } else if (first == '-') {
    14.               sign = -1;
    15.               startIndex = 1;
    16.           } else {
    17.               return 0;
    18.           }
    19.       }
    21.       StringBuilder sb = new StringBuilder();
    22.       for (int i = startIndex; i < strTrim.length(); ++i) {
    23.           if (Character.isDigit(strTrim.charAt(i))) {
    24.               sb.append(strTrim.charAt(i));
    25.           }
    26.           else {
    27.               break;
    28.           }
    29.       }
    31.       long res = 0;
    32.       for (int i = sb.length() - 1, j = 0; i >= 0; --i, ++j) {
    33.           res += (sb.charAt(i) - '0') * Math.pow(10, j);
    34.       }
    35.       res = res * sign;
    36.       if (res > Integer.MAX_VALUE) {
    37.           return Integer.MAX_VALUE;
    38.       }
    39.       if (res < Integer.MIN_VALUE) {
    40.           return Integer.MIN_VALUE;
    41.       }
    42.       return (int) res;
    43.   }
    44. }

    12、剑指 Offer 20. 表示数值的字符串

    12.1 题目

    请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
    数值（按顺序）可以分成以下几个部分：

  1. 若干空格
  2. 一个 小数 或者 整数
  3. （可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数
  4. 若干空格

小数（按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（’+’ 或 ‘-‘）
  2. 下述格式之一：
    1. 至少一位数字，后面跟着一个点 ‘.’
    2. 至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
    3. 一个点 ‘.’ ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（’+’ 或 ‘-‘）
  2. 至少一位数字

部分数值列举如下：

[“+100”, “5e2”, “-123”, “3.1416”, “-1E-16”, “0123”]

部分非数值列举如下：

[“12e”, “1a3.14”, “1.2.3”, “+-5”, “12e+5.4”]

12.2 思路

这题太恶心了，没做的必要。

12.3 代码

  1. class Solution {
  2.     public boolean isNumber(String s) {
  3.         Map[] states = {
  4.             new HashMap<>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
  5.             new HashMap<>() {{ put('d', 2); put('.', 4); }},                           // 1.
  6.             new HashMap<>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
  7.             new HashMap<>() {{ put('d', 3); put('e', 5); put(' ', 8); }},              // 3.
  8.             new HashMap<>() {{ put('d', 3); }},                                        // 4.
  9.             new HashMap<>() {{ put('s', 6); put('d', 7); }},                           // 5.
  10.             new HashMap<>() {{ put('d', 7); }},                                        // 6.
  11.             new HashMap<>() {{ put('d', 7); put(' ', 8); }},                           // 7.
  12.             new HashMap<>() {{ put(' ', 8); }}                                         // 8.
  13.         };
  14.         int p = 0;
  15.         char t;
  16.         for(char c : s.toCharArray()) {
  17.             if(c >= '0' && c <= '9') t = 'd';
  18.             else if(c == '+' || c == '-') t = 's';
  19.             else if(c == 'e' || c == 'E') t = 'e';
  20.             else if(c == '.' || c == ' ') t = c;
  21.             else t = '?';
  22.             if(!states[p].containsKey(t)) return false;
  23.             p = (int)states[p].get(t);
  24.         }
  25.         return p == 2 || p == 3 || p == 7 || p == 8;
  26.     }
  27. }

13、49. 字母异位词分组

13.1 题目

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
示例 1:

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

示例 2:

输入: strs = [“”] 输出: [[“”]]

示例 3:

输入: strs = [“a”] 输出: [[“a”]]

13.2 思路

本题就按暴力破解的思路遍历strs即可。

  1. 先找到字母异位词的特点表示，以aet为例，有两种思路：
    1. 由于是26个小写字母，可以申请一个长度为26的int数组，对应的字母 - ‘a’就是在这个数组的下标，令下标对应的值为1，比如acb对应数组[1,1,1,0,0…0];
    2. 对待处理的字符str，将其转换成字符数组，然后对字符数组按字符的ASCII码升序排序，将升序排序后的数组再转换成一个字符串，这个字符串就是字母异位词共同对应的字符串。
  2. 维护一个map，这个map的key是字母异位词对应的字符串，value是对应这个字符串的字母异位词组成的列表；
  3. 遍历这个map，把每个k-v的v作为一个元素放到res列表中；

  4. 返回res。

    13.3 代码

    1. class Solution {
    2.  public List<List<String>> groupAnagrams(String[] strs) {
    3.      List<List<String>> res = new ArrayList<>();
    4.      Map<String, List<String>> map = new HashMap<>();
    6.      for (String str: strs) {
    7.          String helperStr = helper(str);
    8.          if (map.containsKey(helperStr)) {
    9.              map.get(helperStr).add(str);
    10.          } else {
    11.              List<String> list = new ArrayList<>();
    12.              list.add(str);
    13.              map.put(helperStr, list);
    14.          }
    15.      }
    17.      map.forEach((k, v) -> res.add(v));
    18.      return res;
    19.  }
    21.  private String helper(String str) {
    22.      char[] array = str.toCharArray();
    23.      Arrays.sort(array);
    24.      return new String(array);
    25.  }
    26. }

    14、647. 回文子串

    14.1 题目

    给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。回文字符串 是正着读和倒过来读一样的字符串。子字符串 是字符串中的由连续字符组成的一个序列。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
    示例 1：

    输入：s = “abc” 输出：3 解释：三个回文子串: “a”, “b”, “c”

示例 2：

输入：s = “aaa” 输出：6 解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

14.2 思路

  1. 首先需要明确回文串有两种：长度为奇数的回文串和长度为偶数的回文串，这两种回文串的判定起始位置是不一样的；
  2. 如何判定一个字符串是否是回文串：从字符串的中间位置（如果字符串是奇数，则从中间一个点；如果字符串是偶数，从中间的两个挨着的点）向两边扩散，依次比较左右两边的字符是否相等，相等则继续遍历，不相等则直接返false。

回文子串的题目，都可以用这种解法，因为这种解法可以获取当前字符串的所有回文子串，然后在此基础上变形。

14.3 代码

  1. class Solution {
  2.     private int cnt;
  4.     public int countSubstrings(String s) {
  5.         for (int i = 0; i < s.length(); ++i) {
  6.             // 回文串为奇数
  7.             count(s, i, i);
  8.             // 回文串为偶数
  9.             count(s, i, i + 1);
  10.         }
  11.         return cnt;
  12.     }
  14.     private void count(String s, int start, int end) {
  15.         while (start >= 0 && end < s.length() && s.charAt(start--) == s.charAt(end++)) {
  16.             ++cnt;
  17.         }
  18.     }
  19. }

15、5. 最长回文子串

15.1 题目

给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：

输入：s = “babad” 输出：”bab” 解释：”aba” 同样是符合题意的答案。

示例 2：

输入：s = “cbbd” 输出：”bb”

15.2 思路

就是上面回文子串的变形，只不过需要维护一个长度最大的回文子串。

15.3 代码

  1. class Solution {
  2.     private String res;
  3.     private int len = Integer.MIN_VALUE;
  5.     public String longestPalindrome(String s) {
  6.         for (int i = 0; i < s.length(); ++i) {
  7.             // 回文串为奇数
  8.             count(s, i, i);
  9.             // 回文串为偶数
  10.             count(s, i, i + 1);
  11.         }
  12.         return res;
  13.     }
  15.     private void count(String s, int start, int end) {
  16.         while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
  17.             int len = end - start + 1;
  18.             if (len > this.len) {
  19.                 this.len = len;
  20.                 this.res = s.substring(start, end + 1);
  21.             }
  22.             --start;
  23.             ++end;
  24.         }
  25.     }
  26. }

16、394. 字符串解码

16.1 题目

给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
image.png

16.2 思路

用栈的思想，实现时用LinkedList的API更方便。

16.3 代码

  1. import java.util.LinkedList;
  3. class Solution {
  4.     public String decodeString(String s) {
  5.         LinkedList<Character> stack = new LinkedList<>();
  6.         for (char ch: s.toCharArray()) {
  7.             if (ch != ']') {
  8.                 stack.addLast(ch);
  9.             } else {
  10.                 LinkedList<Character> list = new LinkedList<>();
  11.                 while (stack.getLast() != '[') {
  12.                     list.addFirst(stack.removeLast());
  13.                 }
  14.                 stack.removeLast();
  15.                 LinkedList<Character> cntList = new LinkedList<>();
  16.                 while (!stack.isEmpty() && stack.getLast() >= '0' && stack.getLast() <= '9') {
  17.                     cntList.addFirst(stack.removeLast());
  18.                 }
  19.                 int cnt = 0;
  20.                 for (int i = cntList.size() - 1, j = 1; i >= 0; --i) {
  21.                     cnt += (cntList.get(i) - '0') * j;
  22.                     j *= 10;
  23.                 }
  24.                 for (int i = 0; i < cnt; ++i) {
  25.                     for (int j = 0; j < list.size(); ++j) {
  26.                         stack.addLast(list.get(j));
  27.                     }
  28.                 }
  29.             }
  30.         }
  31.         StringBuilder sb = new StringBuilder();
  32.         while (!stack.isEmpty()) {
  33.             sb.append(stack.pollFirst());
  34.         }
  35.         return sb.toString();
  36.     }
  37. }

17、438. 找到字符串中所有字母异位词

17.1 题目

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:

输入: s = “cbaebabacd”, p = “abc” 输出: [0,6] 解释: 起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。 起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

示例 2:

输入: s = “abab”, p = “ab” 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。 起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。 起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。

17.2 思路

整体思路还是滑动窗口方法，比较滑窗内的子串与p是否构成异位词。
如何判断子串与p构成异位词？由于子串都是小写字母，初始化一个int[26]的数组，数组中每一个元素代表对于字母出现的次数，比如aab对应数组[2, 1, 0, 0, …0]，这个长度为26的int数组就是子串对应的特征数组，如果子串的特征数组与p的特征数组相等，说明子串与p构成异位词。

判断两个数组是否相等：Arrays.equals()，源码实现很简单。

17.3 代码

  1. class Solution {
  2.     public List<Integer> findAnagrams(String s, String p) {
  3.         List<Integer> res = new ArrayList<>();
  4.         int len = p.length();
  5.         int[] pattern = helper(p, 0, p.length() - 1);
  6.         for (int i = 0; i <= s.length() - len; ++i) {
  7.             if (Arrays.equals(helper(s, i, i + len - 1), pattern)) {
  8.                 res.add(i);
  9.             }
  10.         }
  11.         return res;
  12.     }
  14.     private int[] helper(String s, int left, int right) {
  15.         int[] nums = new int[26];
  16.         for (int i = left; i <= right; ++i) {
  17.             nums[s.charAt(i) - 'a'] += 1;
  18.         }
  19.         return nums;
  20.     }
  21. }

18、20. 有效的括号

18.1 题目

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合;
  2. 左括号必须以正确的顺序闭合。

示例 1：

输入：s = “()” 输出：true

示例 2：

输入：s = “()[]{}” 输出：true

示例 3：

输入：s = “(]” 输出：false

示例 4：

输入：s = “([)]” 输出：false

示例 5：

输入：s = “{[]}” 输出：true

18.2 思路

整体还是一个栈的思想。注意最后返回的结果，不是直接返回true，而是返回stack.isEmpty()，即如果字符串整体还是左括号多，也非法。

18.3 代码

  1. class Solution {
  2.     public boolean isValid(String s) {
  3.         Map<Character, Character> map = new HashMap<>();
  4.         map.put(']', '[');
  5.         map.put('}', '{');
  6.         map.put(')', '(');
  8.         LinkedList<Character> stack = new LinkedList<>();
  9.         for (char ch: s.toCharArray()) {
  10.             if (ch == '[' || ch == '(' || ch == '{') {
  11.                 stack.addFirst(ch);
  12.             } else {
  13.                 if (stack.isEmpty()) {
  14.                     return false;
  15.                 } else {
  16.                     char value = stack.removeFirst();
  17.                     if (map.get(ch) != value) {
  18.                         return false;
  19.                     }
  20.                 }
  21.             }
  22.         }
  23.         return stack.isEmpty();
  24.     }
  25. }

19、415. 字符串相加

滴滴国际支付二面算法题之一，当时直接按简单题用int接了，也是因为这个题被二面挂了……

19.1 题目

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
示例 1：

输入：num1 = “11”, num2 = “123” 输出：”134”

示例 2：

输入：num1 = “456”, num2 = “77” 输出：”533”

示例 3：

输入：num1 = “0”, num2 = “0” 输出：”0”

19.2 思路

该题重点考察的是字符串是没有位数限制的，而int、long这些是有位数限制的，而且不能使用BigInteger等大数计算类。
主要思路是模拟两个数相加的过程，每一位上的数字相加，再加上进位，但是要注意两个数字字符串的长度可能不同，需要处理。关键是while条件：while (i >= 0 || j >= 0 || cin != 0)
类似的模拟相加的问题还有（尤其是链表中的两数相加这道题）：
剑指 Offer 65. 不用加减乘除做加法
剑指 Offer II 025. 链表中的两数相加

19.3 代码

  1. class Solution {
  2.     public String addStrings(String num1, String num2) {
  3.         if (num1 == null) {
  4.             return num2;
  5.         }
  6.         if (num2 == null) {
  7.             return num1;
  8.         }
  9.         StringBuilder sb = new StringBuilder();
  10.         int i = num1.length() - 1, j = num2.length() - 1, cin = 0;
  11.         while (i >= 0 || j >= 0 || cin != 0) {
  12.             int x = i >= 0? num1.charAt(i) - '0': 0;
  13.             int y = j >= 0? num2.charAt(j) - '0': 0;
  14.             int result = x + y +cin;
  15.             sb.append(result % 10);
  16.             cin = result / 10;
  17.             --i;
  18.             --j;
  19.         }
  20.         return sb.reverse().toString();
  21.     }
  22. }

20、139. 单词拆分

20.1 题目

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：

输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

示例 2：

输入: s = “applepenapple”, wordDict = [“apple”, “pen”] 输出: true 解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。 注意，你可以重复使用字典中的单词。

示例 3：

输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”] 输出: false

20.2 思路

动态规划的题。

  1. 转态定义：定义dp[i]表示s字符串下标从0到i - 1的子串是否满足单词拆分的要求，dp为boolean类型数组，dp[0]表示空串。dp数组的长度为s.length() + 1，这是由返回值决定的；
  2. 转移方程：求dp[i]，即s字符串下标从0到 i -1的字符子串是否满足单词拆分要求，用一个j枚举从0到i - 1之间的点，判断左边0到j - 1下标的子串是否满足单词拆分要求，即dp[j]，判断右边的子串（从下标j到下标i - 1）是否在dict字典中，如果左右两边的条件都为true，即当前dp[i]的值为true，进入下一个dp[i + 1]的计算中；
  3. 初始状态：dp[0] = true，表示空串为true，比如s = leet, dict = leet，则当j = 0时，dp[0] = true，leet在dict中，取了完整的leet判断是否在dict中，因此dp[0]不应参与实际的判断，为true；

  4. 返回值：dp[s.length]。

    20.3 代码

    1. class Solution {
    2.  public boolean wordBreak(String s, List<String> wordDict) {
    3.      int len = s.length();
    4.      boolean[] dp = new boolean[len + 1];
    5.      dp[0] = true;
    6.      Set<String> set = new HashSet<>(wordDict);
    8.      for (int i = 1; i <= len; ++i) {
    9.          for (int j = 0; j < i; ++j) {
    10.              if (dp[j] && set.contains(s.substring(j, i))) {
    11.                  dp[i] = true;
    12.                  break;
    13.              }
    14.          }
    15.      }
    16.      return dp[len];
    17.  }
    18. }

    21、3. 无重复字符的最长子串

    21.1 题目

    给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
    示例 1:

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

示例 2:

输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

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

21.2 思路

本题用一个set记录出现的字符，将字符串s中的字符依次放入一个双向队列LinkedList。

  1. 遍历字符串中的每个字符，如果当前字符没有在set中，直接向set和list中插入；
  2. 如果当前字符在set中，则将list的队首元素出队，队首元素在set中的元素也删除，直到set中没有当前字符，再将当前字符入队，set中也插入对应的字符；
  3. 遍历字符串的过程中维护一个最长子串的长度res，每遍历完一个字符，就取一次最大值res = Math.max(res, list.size())。

    21.3 代码

    1. class Solution {
    2.  public int lengthOfLongestSubstring(String s) {
    3.      Set<Character> set = new HashSet<>();
    4.      LinkedList<Character> list = new LinkedList<>();
    5.      int res = 0;
    6.      for (Character ch: s.toCharArray()) {
    7.          while (!list.isEmpty() && set.contains(ch)) {
    8.              set.remove(list.peekFirst());
    9.              list.removeFirst();
    10.          }
    11.          list.addLast(ch);
    12.          set.add(ch);
    13.          res = Math.max(res, list.size());
    14.      }
    15.      return res;
    16.  }
    17. }