LeeCode三百题-1

发表于 更新于 分类于

[TOC]

代码工程获取

git clone --depth=1 https://gitee.com/SevDaisy/LeeCode300.git

#1 两数之和

  • 题目保证最多只有一个答案
    • 用HashMap<Integer, Integer>做查询即可。
    • HashMap的K-V存储内容为<value,index>
  • 题目要求数组中同一个元素在答案里不能重复出现
    • 先查看当前HashMap中有没有答案
    • 再将当前遍历对象加入HashMap
    • 如此可保证，返回的答案匹配肯定不会重复。
package Order300;

import java.util.HashMap;
import java.util.Map;

public class T1_two_sum {

  static class Solution {

    public int[] twoSum(int[] nums, int target) {
      Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
      for (int i = 0; i < nums.length; i++) {
        /**
         * 先判断有没有答案，再将当前元素加入hashtable
         * 如此，满足要求 `数组中同一个元素在答案里不能重复出现`
         **/
        if (hashtable.containsKey(target - nums[i])) {
          return new int[] { hashtable.get(target - nums[i]), i };
        }
        hashtable.put(nums[i], i);
      }
      return new int[0];
    }
  }
}

#2 两数相加

  • 同步遍历 l1 l2
    • 并相加配对节点
    • 若 l1 l2 长度不匹配则，长度不足者值取零
  • 因为不确定 l1 l2 谁更长。因此新建链表 head-tail 用于存储 l1 l2 节点配对相加的结果
    • head指针用于返回这个链表
    • tail指针用于执行尾插法
  • 对于 val1+val2 >= 10 的情况，在循环外保留变量 carry 用于保存上一次加法的进位值。
  • 也就是说 val1+val2+carry 才是真正的 sum
package Order300;

public class T2_add_two_numbers {

  static class ListNode {

    int val;
    ListNode next;

    ListNode() {}

    ListNode(int val) {
      this.val = val;
    }

    ListNode(int val, ListNode next) {
      this.val = val;
      this.next = next;
    }
  }

  static class Solution {

    static String printListNode(ListNode cur) {
      /* 无需 ListNode cur = in; 也不会产生对 cur 的副作用 */
      StringBuilder builder = new StringBuilder();
      while (cur != null) {
        builder.append(String.format("-> %d ", cur.val));
        cur = cur.next;
      }
      return builder.toString();
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
      /**
       * 同步遍历 l1 l2
       * - 并相加配对节点
       * - 若 l1 l2 长度不匹配则，长度不足者值取零
       * 因为不确定 l1 l2 谁更长。因此新建链表 head-tail 用于存储 l1 l2 节点配对相加的结果
       * - head指针用于返回这个链表
       * - tail指针用于执行尾插法
       *
       * 对于 val1+val2 >= 10 的情况，在循环外保留变量 carry 用于保存上一次加法的进位值。
       * 也就是说 val1+val2+carry 才是真正的 sum
       **/
      ListNode head = null, tail = null;
      int carry = 0;
      /* 只要 l1 l2 不为空，就可以继续遍历 */
      while (l1 != null || l2 != null || carry != 0) {
        /* 求和 保留进位 */
        int val1 = l1 != null ? l1.val : 0; // 取值
        int val2 = l2 != null ? l2.val : 0; // 取值
        int sum = val1 + val2 + carry; // 求和
        carry = sum / 10; // 保存进位值
        sum = sum % 10; // 更新和的值（处理进位以后）

        /* l1 l2 向后位移 */
        if (l1 != null) l1 = l1.next;
        if (l2 != null) l2 = l2.next;

        /* 更新out链表 */
        if (head != null) {
          tail.next = new ListNode(sum);
          tail = tail.next;
        } else head = tail = new ListNode(sum);
      }
      // System.out.println(printListNode(head));
      // System.out.println(printListNode(head));
      return head;
    }
  }
}

#3 无重复字符的最长子串

  • 滑动窗口类问题
  • 双指针 - 左右指针
  • 判断重复字符 HashSet<Character>
package Order300;

import java.util.HashSet;
import java.util.Set;

public class T3_longest_substring_without_repeating_characters {

  public static void main(String[] args) {
    System.out.println(new Solution().lengthOfLongestSubstring("aaa")); // -> 1
    System.out.println(new Solution().lengthOfLongestSubstring("abcde")); // -> 5
    System.out.println(new Solution().lengthOfLongestSubstring("")); // -> 0
    System.out.println(new Solution().lengthOfLongestSubstring("pwwkew")); // -> 3
  }

  static class Solution {

    /**
     * 滑动窗口类问题
     * 双指针 - 左右指针
     *
     * 判断重复字符 HashSet<Character>
     */
    public int lengthOfLongestSubstring(String s) {
      /* 字符串转字符数组以方便遍历 */
      char[] line = s.toCharArray();
      /* 左右指针 */
      int left = -1; // line[left]不在窗口中
      int right = -1; // line[right]在窗口中
      int out = 0; // 保存子串的最大长度。子串长度 = right-left
      /* 窗口数据 —— 需求是去重，所以用HashSet */
      Set<Character> window = new HashSet<>();

      while (left < line.length && right + 1 < line.length) {
        /* 窗口向右生长1位 => 右指针++ */
        right++;
        /**
         * 若 新元素line[right]未重复，则加入窗口，并进入下一个循环
         * 否则，窗口左边界向右收缩 => left++，直到当前元素不在窗口用有重复对象。
         */
        char cur = line[right]; // 这个元素只是为了程序的可读性。可以完全用line[right]替代。
        while (window.contains(cur)) {
          left++;
          window.remove(line[left]);
        }
        window.add(cur);
        out = Math.max(out, right - left);
      }
      return out;
    }
  }
}

#4 寻找两个正序数组的中位数 困难

  • 二叉搜索应用题
  • 二分搜索的基本操作：mid值的计算、 left/right 的转移、mid值的可能范围，仍相当不熟练
  • 中位数 => 概念转换为
    • => 数组左边的元素都不大于数组右边的元素
    • => 数据左边的元素至多比数据右边的元素多一个
package Order300;

public class T4_median_of_two_sorted_arrays {

  public static void main(String[] args) {
    System.out.println(
      new Solution()
      .findMedianSortedArrays(new int[] { 1, 2 }, new int[] { 3, 4 }) // -> 2.5
    );
  }

  static class Solution {

    /* 二分搜索 注意边界条件 */
    /* 二分搜索的基本操作：mid值的计算 left/right 的转移，mid值的可能范围，仍相当不熟练 */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
      /* 调整数组顺序，使得保证 nums1 不长于 nums2 */
      if (nums1.length > nums2.length) {
        int[] temp = nums1;
        nums1 = nums2;
        nums2 = temp;
      }

      /* 得到中位线左边的元素个数 leftCount */
      int l1 = nums1.length;
      int l2 = nums2.length;
      int leftCount = (l1 + l2 + 1) / 2;
      int p1; // nums1 上的中位线索引
      int p2; // nums2 上的中位线索引

      /* 在 nums1 上对索引 p1 进行范围为 [0,l1] 的二叉搜索 */
      int left = 0;
      int right = l1;
      /* 要求是 nums1[p1-1]<=nums2[p2] && nums2[p2-1]<=nums1[p1] */
      while (left < right) {
        p1 = left + ((right - left + 1) >> 1);
        p2 = leftCount - p1;
        if (nums1[p1 - 1] > nums2[p2]) {
          right = p1 - 1;
        } else {
          left = p1;
        }
      }
      /* 二叉搜索完毕，取出中位线的p1p2值 */
      p1 = left;
      p2 = leftCount - p1;
      int n1LeftMax = p1 == 0 ? Integer.MIN_VALUE : nums1[p1 - 1];
      int n1RightMin = p1 == l1 ? Integer.MAX_VALUE : nums1[p1];
      int n2LeftMax = p2 == 0 ? Integer.MIN_VALUE : nums2[p2 - 1];
      int n2RightMin = p2 == l2 ? Integer.MAX_VALUE : nums2[p2];

      if ((l1 + l2) % 2 == 1) {
        return Math.max(n1LeftMax, n2LeftMax);
      } else {
        return (
          (Math.max(n1LeftMax, n2LeftMax) + Math.min(n1RightMin, n2RightMin)) /
          2.0
        );
      }
    }
  }
}

#5 最长回文子串

  • 有三种解法
    • 动态规划
    • 中心扩展 —— 我的直觉
    • Manacher 算法 —— 最难但是效果最好 —— 《左神》P535 有详细讲解
  • Manacher 太花时间了，先跳过。回头再补习Manacher算法
package Order300;

import java.util.ArrayList;
import java.util.List;

public class T5_longest_palindromic_substring {

  static class me_动态规划 {

    /**
     * 时间复杂度 O(n^2)
     * 空间复杂度 O(n^2)
     */
    public String longestPalindrome(String s) {
      int strLength = s.length();
      /* 若字符串长度小于2，则返回自身 */
      if (strLength < 2) {
        return s;
      }
      /* 否则，执行 DP 演算 */
      int maxLen = 1;
      int begin = 0;
      /* dp[i][j] 表示 s[i..j] 是否是回文串 */
      boolean[][] dp = new boolean[strLength][strLength];
      /* 初始化：所有长度为 1 的子串都是回文串 */
      for (int i = 0; i < strLength; i++) {
        dp[i][i] = true;
      }

      char[] charArray = s.toCharArray();
      /* 递推开始 */
      /* 先枚举子串长度 */
      for (int subLenLimit = 2; subLenLimit <= strLength; subLenLimit++) {
        /* 枚举左边界，左边界的上限设置可以宽松一些 */
        for (int left = 0; left < strLength; left++) {
          /* 对于固定的子串长度、自增的左索引，可以计算得对应的右索引 */
          int right = subLenLimit + left - 1;
          /* 如果右索引越界了，则退出当前循环 */
          if (right >= strLength) {
            break;
          }
          /* 如果对于当前状态，不满足 s[left] == s[right]，则dp数组[left][right]标记为 false */
          if (charArray[left] != charArray[right]) {
            dp[left][right] = false;
          } else {
            if (right - left < 3) {
              /* 在满足 s[left] == s[right] 时，若 s.subString().length() = 0～2 则，直接标记dp数组[left][right]=true */
              dp[left][right] = true;
            } else {
              /* 在满足 s[left] == s[right] 时，若 s.subString().length() >=3 则 需要 dp[left][right] = true&&dp[left + 1][right - 1] */
              dp[left][right] = dp[left + 1][right - 1];
            }
          }

          /* 更新：最长回文子串的长度 和 左索引 */
          if (dp[left][right] && right - left + 1 > maxLen) {
            maxLen = right - left + 1;
            begin = left;
          }
        }
      }
      return s.substring(begin, begin + maxLen);
    }
  }

  static class me_中心扩展法 {

    /* 最贴近我原生逻辑的写法 */

    /**
     * 时间复杂度 O(n^2) 其中 n 是字符串的长度。长度为 1 和 2 的回文中心分别有 n 和 n-1 个，每个回文中心最多会向外扩展 O(n) 次。
     * 空间复杂度 O(1)
     */
    public String longestPalindrome(String s) {
      /* 若 s.length() < 2, 则 return s */
      if (s == null || s.length() < 2) {
        return s;
      }
      int subLenMax = 0;
      int left = 0;
      for (int center = 0; center < s.length(); center++) {
        int subLenByCenter = Math.max(
          expandAroundCenter(s, center, center),
          expandAroundCenter(s, center, center + 1)
        );
        if (subLenByCenter > subLenMax) {
          subLenMax = subLenByCenter;
          left =
            center -
            (subLenByCenter - 1) /
            2;/* 这句话我需要用数学归纳法才能得出，不知道直接推导该如何得出 */
        }
      }
      return s.substring(left, left + subLenMax);
    }

    /* 这个函数名字起的真合适，我就想不到 */
    public int expandAroundCenter(String s, int left, int right) {
      while (true) {
        if (
          s != null &&
          left <= right &&
          left >= 0 &&
          right < s.length() &&
          s.charAt(left) == s.charAt(right)
        ) {
          left--;
          right++;
        } else {
          break;
        }
      }
      /* 实际上是 (right - left + 1) - 2, 即当前长度减去2 */
      return right - left - 1;
    }
  }

  static class Solution_Manacher {

    /**
     * 时间复杂度 O(n)
     * 空间复杂度 O(n)
     */

    public String longestPalindrome(String s) {
      int start = 0, end = -1;
      StringBuffer t = new StringBuffer("#");
      for (int i = 0; i < s.length(); ++i) {
        t.append(s.charAt(i));
        t.append('#');
      }
      t.append('#');
      s = t.toString();

      List<Integer> arm_len = new ArrayList<Integer>();
      int right = -1, j = -1;
      for (int i = 0; i < s.length(); ++i) {
        int cur_arm_len;
        if (right >= i) {
          int i_sym = j * 2 - i;
          int min_arm_len = Math.min(arm_len.get(i_sym), right - i);
          cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len);
        } else {
          cur_arm_len = expand(s, i, i);
        }
        arm_len.add(cur_arm_len);
        if (i + cur_arm_len > right) {
          j = i;
          right = i + cur_arm_len;
        }
        if (cur_arm_len * 2 + 1 > end - start) {
          start = i - cur_arm_len;
          end = i + cur_arm_len;
        }
      }

      StringBuffer ans = new StringBuffer();
      for (int i = start; i <= end; ++i) {
        if (s.charAt(i) != '#') {
          ans.append(s.charAt(i));
        }
      }
      return ans.toString();
    }

    public int expand(String s, int left, int right) {
      while (
        left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)
      ) {
        --left;
        ++right;
      }
      return (right - left - 2) / 2;
    }
  }
}

#6 Z字形变换

我感觉更像是 N字形 变换

  • 关键是，数组中的掉头/拐弯问题的模范代码：
  • 循环之前，设置pos 初值为合法值
  • 循环中：
    • 先对pos位进行操作
    • 再看要不要变方向
      • 变方向的条件是 —— 用||连接
        • 正向且再走一步就是正向非法值
        • 逆向且再走一步就是逆向非法值
    • 最后，按方向前进一步
package Order300;

public class T6_zigzag_conversion {

  public static void main(String[] args) {
    System.out.println(new Solution().convert("PAYPALISHIRING", 3));
  }

  static class Solution {

    /**
     * 两种思路
     * 1. 模拟，Z字形走路过程，横向一行作为一个存储单位。最后遍历numRows个存储单位即可。
     * 2. 找规律。找到字符下标的对应关系，并通过这个关系来访问
     *
     * 方法二更麻烦，而且性能也没好多少 —— 顶多是，勉强算是省了点空间 —— 放弃方法二的代码实现
     **/
    public String convert(String s, int numRows) {
      if (numRows <= 1) return s;
      StringBuilder[] res = new StringBuilder[numRows];
      for (int i = 0; i < numRows; i++) {
        res[i] = new StringBuilder();
      }
      /* 数组中的 掉头/拐弯 问题模范代码 —— 厚着脸皮称自己的写的为模范代码 —— */
      int step = 1; // 方向 flag
      int pos = 0; // pos初值为合法值
      for (int i = 0; i < s.length(); i++) {
        // 先赋值
        res[pos].append(s.charAt(i));
        // 再看要不要换方向
        // 换方向的条件：
        // - 正向且再走一步就是正向非法值 或者 逆向且再走一步就是逆向非法值
        if (
          (step > 0 && pos + step == numRows) || (step < 0 && pos + step == -1)
        ) step = -step;
        // 再按方向前进
        pos += step;
      }
      StringBuilder out = new StringBuilder();
      for (int i = 0; i < numRows; i++) {
        out.append(res[i].toString());
      }
      return out.toString();
    }
  }
}

#7 整数反转

  • 前导0、后缀0的管理 —— 其实不是问题
  • 溢出处理 —— 需要返回0 —— 溢出条件还蛮有意思的。
  • 负数的处理 —— 不用 flag 反而更方便
  • 提取变量(常量)来简化过长的条件表达式。
package Order300;

public class T7_reverse_integer {

  public static void main(String[] args) {
    System.out.println(new Solution().reverse(1147483647));
  }

  static class Solution {

    /**
     * 坑点有两个
     * - 后缀0转前导0 —— 处理很简单
     * - 2147483647 倒转以后是 7463847412 是溢出的，需要处理为 0 —— 正负数的溢出都是返回0
     */
    public int reverse(int x) {
      int out = 0;
      /* 把 max 和 min 保存在变量中，而不是写在条件判断里。为了方便和程序可读性。 */
      int max = Integer.MAX_VALUE / 10;
      int min = Integer.MIN_VALUE / 10;
      while (x != 0) {
        int cur = x % 10;
        x /= 10;
        if (out > max || (out == max && cur > 7)) return 0; else if (
          out < min || (out == min && cur < -8)
        ) return 0; else out = out * 10 + cur;
      }
      return out;
    }
  }
}

#8 字符串转换整数 (atoi)

  • 可以正常做输入流匹配
  • 当然也可以，有限自动机 安排
<space> + or - Number else
==start== start sign num end
==sign== end end num end
==num== end end num end
==end== end end end end

  • 溢出判断 的错误写法

    int old = this.val;
    int cur = this.val * 10 + (c - '0');
    if ((cur - (c - '0')) / 10 != old) {
      overflow = true;
    }

    即使溢出了，(cur - (c - '0')) / 10 == old 依旧成立

  • 正确的溢出判断：

    • 使用Long存储this.val，并用 Math.max(val,Integer.MIN_VALUE) 和 Math.min(...) 来做截断
    • 使用int32存储 this.val，并在其接近 Integer.MIN_VALUE/10 的时候判断溢出
package Order300;

public class T7_reverse_integer {

  public static void main(String[] args) {
    System.out.println(new Solution().reverse(1147483647));
  }

  static class Solution {

    /**
     * 坑点有两个
     * - 后缀0转前导0 —— 处理很简单
     * - 2147483647 倒转以后是 7463847412 是溢出的，需要处理为 0 —— 正负数的溢出都是返回0
     */
    public int reverse(int x) {
      int out = 0;
      /* 把max和min保存在变量中，而不是写在条件判断里。为了方便和程序可读性。 */
      int max = Integer.MAX_VALUE / 10;
      int min = Integer.MIN_VALUE / 10;
      while (x != 0) {
        int cur = x % 10;
        x /= 10;
        if (out > max || (out == max && cur > 7)) return 0; else if (
          out < min || (out == min && cur < -8)
        ) return 0; else out = out * 10 + cur;
      }
      return out;
    }
  }
}

#9 回文数

  • 利用特殊情况，过滤掉一些不需要计算的查询
    • x == 0
    • x < 0 || x % 10 == 0
  • 字符串法 10~12ms
  • 数学演算法 150+ms
package Order300;

public class T9_palindrome_number {

  public static void main(String[] args) {
    // new Solution().isPalindrome(1234321);
    // new Solution().isPalindrome(123321);
    new Solution().isPalindrome(0);
  }

  static class Solution {

    public boolean isPalindrome(int x) {
      /* 特别的，对于负数和整十的数(0除外)，不可能是回文数 */
      if (x == 0) return true;
      if (x < 0 || x % 10 == 0) return false;

      /* 字符串法 10~12ms 10ms => 73% */
      char[] line = String.valueOf(x).toCharArray();
      int len = line.length;
      for (int i = 0; i < len / 2; i++) {
        if (line[i] != line[len - 1 - i]) {
          return false;
        }
      }
      return true;
      /* 数学演算法 150ms+ => 5.51%  */
      // int reverseNum = 0;
      // while (reverseNum < x) {
      //   reverseNum = reverseNum * 10 + x % 10;
      //   x /= 10;
      //   System.out.println(reverseNum + "\t" + x);
      // }
      // return reverseNum == x || reverseNum / 10 == x;
    }
  }
}

#10 正则表达式匹配

  • 两个办法

    • 自动机 （双指针+DFS+回溯）

    • 动态规划 —— 官方题解写的还好，不过留给读者的问题我觉得是骗人的

      在上面的状态转移方程中，如果字符串 pp 中包含一个「字符 + 星号」的组合（例如 a*），那么在进行状态转移时，会先将 a 进行匹配（当 p[j]p[j] 为 a 时），再将 a* 作为整体进行匹配（当 p[j]p[j] 为 * 时）。然而，在题目描述中，我们必须将 a* 看成一个整体，因此将 a 进行匹配是不符合题目要求的。看来我们进行了额外的状态转移，这样会对最终的答案产生影响吗？这个问题留给读者进行思考。

      因为它代码里的dp数组是从 [i][j] 向 [0][0] 遍历的，根本不存在所谓的 因此将 a 进行匹配

  • 坑点 —— 自动机原理，双指针+DFS+回溯：

    • 因为：* 是0次或无数次
    • 所以。如果mode中当前位没能匹配——如果mode的下一位是*的话，就可以跳过mode中的当前位了
    • 所以。每次*位出现，若匹配成功，有 用 和 不用 在两个选择。
    • 所以。遇到的即使是.，也需要考虑要不要用后面的'*'来跳过这个 .

  • 关键

    • 动态规划的时候，要设计好方向
    • 比如这题。从尾部往前转移，是非常好的想法，大大简化了状态转移方程

  • ==动态规划算法，回头再看==

    • 这个状态转移方程好晕啊。这题从昨天晚上写到现在21:58快写吐了。
    • 等以后熟练一点再回来看吧。怂。
package Order300;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

public class T10_regular_expression_matching {

  public static void main(String[] args) {
    System.out.println(new Solution_dp().isMatch("aa", "a"));
    System.out.println(new Solution_dp().isMatch("aa", "a*"));
    System.out.println(new Solution_dp().isMatch("ab", ".*"));
    System.out.println(new Solution_dp().isMatch("mississippi", "mis*is*p*"));

    // bug case ↓↓↓
    System.out.println(new Solution_dp().isMatch("aab", "c*a*b"));
    System.out.println(new Solution_dp().isMatch("aaa", "a*a"));
    System.out.println(new Solution_dp().isMatch("a", "ab*"));
    System.out.println(new Solution_dp().isMatch("bbbba", ".*a*a"));
  }

  static class Solution_dp {

    public boolean isMatch(String s, String p) {
      int sMax = s.length();
      int pMax = p.length();

      boolean[][] dp = new boolean[sMax + 1][pMax + 1];
      dp[0][0] = true;
      for (int si = 0; si <= sMax; ++si) {
        for (int pi = 1; pi <= pMax; ++pi) {
          if (p.charAt(pi - 1) == '*') {
            dp[si][pi] = dp[si][pi - 2];
            if (matches(s, p, si, pi - 1)) {
              dp[si][pi] = dp[si][pi] || dp[si - 1][pi];
            }
          } else {
            if (matches(s, p, si, pi)) {
              dp[si][pi] = dp[si - 1][pi - 1];
            }
          }
        }
      }
      return dp[sMax][pMax];
    }

    public boolean matches(String s, String p, int si, int pi) {
      if (si == 0) {
        return false;
      }
      if (p.charAt(pi - 1) == '.') {
        return true;
      }
      return s.charAt(si - 1) == p.charAt(pi - 1);
    }
  }

  /**
   * 自动机原理，双指针+DFS+回溯
   */
  static class Solution_me {

    static class AutoState {

      int si;
      int pi;

      public AutoState(int si, int pi) {
        this.si = si;
        this.pi = pi;
      }

      @Override
      public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + pi;
        result = prime * result + si;
        return result;
      }

      @Override
      public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        AutoState other = (AutoState) obj;
        if (pi != other.pi) return false;
        if (si != other.si) return false;
        return true;
      }
    }

    public boolean isMatch(String s, String p) {
      char[] line = s.toCharArray();
      char[] mode = p.toCharArray();
      Stack<AutoState> stack = new Stack<>();
      Set<AutoState> visited = new HashSet<>(128);
      int sMax = s.length();
      int pMax = p.length();
      stack.push(new AutoState(/* si */0, /* pi */0));
      while (!stack.isEmpty()) {
        AutoState cur = stack.pop();
        if (visited.contains(cur)) {
          continue;
        } else {
          visited.add(cur);
        }
        /* 看看当前状态需不需要下一步的判断 */
        if (cur.si >= sMax && cur.pi >= pMax) {
          /* 如果 s,p 均已经遍历完毕，则返回 匹配成功 */
          return true;
        } else if (cur.si >= sMax) {
          /**
           * '.' 匹配任意单个字符
           * '*' 匹配零个或多个前面的那一个元素
           * 因此，当剩下的是一个 "*" ".*" "a*b*c*" 这种的东西的时候，可以考虑下一步
           */
          if ((mode[cur.pi] == '*')) {
            stack.add(new AutoState(cur.si, cur.pi + 1));
          } else if (pMax > cur.pi + 1 && mode[cur.pi + 1] == '*') {
            stack.add(new AutoState(cur.si, cur.pi + 2));
          }
          continue;
        } else if (cur.pi >= pMax) {
          /* 如果 p 已经遍历完毕,则说明这个状态不行,继续检索下一个状态即可 */
          continue;
        }

        /* 查看下一步能不能走 */
        switch (mode[cur.pi]) {
          case '.':
            stack.add(new AutoState(cur.si + 1, cur.pi + 1));
            if (pMax > cur.pi + 1 && mode[cur.pi + 1] == '*') {
              stack.add(new AutoState(cur.si, cur.pi + 2));
            }
            break;
          case '*':
            /* 题目明文 “保证每次出现字符 * 时，前面都匹配到有效的字符” */
            if (mode[cur.pi - 1] == '.') {
              /* 如果这个 * 其实是 .* 那么，可匹配任意字符。si前进一位，pi不变 */
              stack.add(new AutoState(cur.si + 1, cur.pi));
            } else {
              /**
               * 需要查看 s 中的上一个字符与当前字符是否相同
               * 因此 先确认 s 有没有 “上一个” 字符
               * 不过，既然 mode 中每次出现字符 * 时，前面都匹配到有效的字符，而pi指针指向了当前的 ‘*’
               * 说明，s 中必然有 “上一个” 字符 和 mode 中的 “上一个” 字符匹配了
               * 结论 s 中必有 “上一个” 字符
               */
              if (line[cur.si - 1] == line[cur.si]) {
                /* 如果当前字符和上一个字符相同，则匹配成功。*/
                stack.add(new AutoState(cur.si + 1, cur.pi)); // 用 '*' 匹配
              }
            }
            /* 无论匹配成功不成功，只要当前是 '*',就可以选择不用这个 '*' 来匹配 */
            stack.add(new AutoState(cur.si, cur.pi + 1)); // 不用 '*' 匹配
            break;
          default:
            /* mode[pi] 是普通字符 */
            if (line[cur.si] == mode[cur.pi]) {
              stack.add(new AutoState(cur.si + 1, cur.pi + 1));
            }
            /* 如果mode的下一个'*'意为0个 也可以算作被匹配了 */
            if (cur.pi + 1 < pMax && mode[cur.pi + 1] == '*') {
              stack.add(new AutoState(cur.si, cur.pi + 2));
            }
            break;
        }
      }
      return false;
    }
  }
}