LeeCode三百题-2

发表于 2021-04-22 更新于 2026-06-20 分类于 LeeCode三百题

[TOC]

代码工程获取

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

#11 盛最多水的容器

左右边界问题 —— 很容易想到双指针 —— 具体来说是 左右指针 依次向中间移动
用 while 来实现边界的连续位移
不用每次位移都做答案更新的判断
就是用 while (left < right && height[++left] < old); 代替 left++
就是用 while (left < right && height[--right] < old); 代替 right--
直到找到下一个可能是解的边界后，再做判断。
从 6ms => 19% 优化到了 3ms => 94.41%

package Order300;

public class T11_container_with_most_water {

  public static void main(String[] args) {
    System.out.println(
      new Solution().maxArea(new int[] { 0, 14, 6, 2, 10, 9, 4, 1, 10, 3 })
    );
  }

  static class Solution {

    public int maxArea(int[] height) {
      int left = 0;
      int right = height.length - 1;
      int answer = Math.min(height[left], height[right]) * (right - left);
      while (left < right) {
        if (height[left] < height[right]) {
          int old = height[left];
          while (left < right && height[++left] < old);
        } else {
          int old = height[right];
          while (left < right && height[--right] < old);
        }
        if (left >= height.length || right < 0) break;
        answer =
          Math.max(
            answer,
            Math.min(height[left], height[right]) * (right - left)
          );
      }
      return answer;
    }
  }
}

#12 整数转罗马数字

将规则稍加完善（指增加 900:CM 这样的映射）后，
遍历规则集，做贪心匹配，即
- 我们希望每次找到不大于目标值的最大映射对。
  - 理论上来说可以可以通过二分法更快的找到这样的最大映射对
  - 但是罗马数字的规则集有限。
  - 这个优化实在是没什么意义。
- 于是对有序数组（规则集应该是降序存储的）逐个遍历即可。
当然，硬编码数字也是一种解法。
- 对规则集进行全扩充，
- 实现 1:I 2:II 3:III 4:IV 这样的全映射
- 这也不失为一种解法
但是硬编码这一解法：
- 没有让代码量变得少
- 没有优化时间/空间复杂度
- 没有让后期维护更轻松
不会吧，不会真的有人做硬编码吧。。。【手动狗头】

package Order300;

public class T12_integer_to_roman {

  static class Solution {

    /**
     * 将规则稍加完善（指 增加 900:CM 这样的映射）后，
     * 遍历规则集，做贪心匹配，即
     * 我们希望每次找到不大于目标值的最大映射对。
     *
     * 理论上来说可以可以通过二分法更快的找到这样的最大映射对
     * 但是罗马数字的规则集有限。这个优化实在是没什么意义。
     *
     * 于是对有序数组（规则集应该是降序存储的）逐个遍历即可。
     * 
     * 
     * 当然，硬编码数字也是一种解法。
     * 对规则集进行全扩充，实现 1:I 2:II 3:III 4:IV 这样的全映射也不失为一种解法
     * 但是这这个解法：
     *  - 没有让代码量变得少
     *  - 没有优化时间/空间复杂度
     *  - 没有让后期维护更轻松
     * 不会吧，不会真的有人做硬编码吧。。。
     **/
    int[] values = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
    String[] symbols = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I",};

    public String intToRoman(int num) {
      StringBuilder sb = new StringBuilder();
      while (num > 0) {
        for (int i = 0; i < values.length; i++) {
          if (values[i] <= num) {
            num -= values[i];
            sb.append(symbols[i]);
            break;
          }
        }
      }
      return sb.toString();
    }
  }
}

#13 罗马数字转整数

第一步宏替换 IV 转为 IIII
第二步翻译即 OK
函数 + switch 并不是很高效，仅仅是写着方便。
- 4ms => 100% 失去了优化的兴致
- 毕竟这个题目，复杂度实在有限

package Order300;

public class T14_roman_to_integer {

  static class Solution {

    int val(char e) {
      switch (e) {
        case 'I': return 1;
        case 'V': return 5;
        case 'X': return 10;
        case 'L': return 50;
        case 'C': return 100;
        case 'D': return 500;
        case 'M': return 1000;
        default: return 0;
      }
    }

    /**
     * 第一步 宏替换 IV 转为 IIII
     * 第二步 翻译 即 OK
     **/
    public int romanToInt(String s) {
      int i = 0;
      int iMax = s.length();
      int answer = 0;
      while (i < iMax) {
        if (i + 1 < iMax) {
          if (val(s.charAt(i)) < val(s.charAt(i + 1))) {
            answer += (val(s.charAt(i + 1)) - val(s.charAt(i)));
            i += 2;
            continue;
          }
        }
        answer += val(s.charAt(i));
        i += 1;
      }
      return answer;
    }
  }
}

#14 最长公共前缀

题目不难，但是解法很多
- 横向比较 —— 字符串两两相比
- 纵向扫描 —— 固定索引同步扫描全部字符串，相同则索引前进，不同则返回结果
- 归并 —— 两两归并着“横向比较”
- 二分查找 —— 反正答案最大是 len(minist(str)) 最小是 0，对于每个可能的 answer 切分每个字符串并比较
  - 说它炫技吧，也没多炫
  - 说它还行吧，复杂度还比别的方法高
  - 给二分法一个面子。勉强算是一种解法。
各算法代码及解释详见官方题解
我懒得写。直接上官方代码。

package Order300;

public class T15_longest_common_prefix {

  static class Solution_横向扫描 {

    public String longestCommonPrefix(String[] strs) {
      if (strs == null || strs.length == 0) {
        return "";
      }
      String prefix = strs[0];
      int count = strs.length;
      for (int i = 1; i < count; i++) {
        prefix = longestCommonPrefix(prefix, strs[i]);
        if (prefix.length() == 0) {
          break;
        }
      }
      return prefix;
    }

    public String longestCommonPrefix(String str1, String str2) {
      int length = Math.min(str1.length(), str2.length());
      int index = 0;
      while (index < length && str1.charAt(index) == str2.charAt(index)) {
        index++;
      }
      return str1.substring(0, index);
    }
  }

  static class Solution_纵向扫描 {

    public String longestCommonPrefix(String[] strs) {
      if (strs == null || strs.length == 0) {
        return "";
      }
      int length = strs[0].length();
      int count = strs.length;
      for (int i = 0; i < length; i++) {
        char c = strs[0].charAt(i);
        for (int j = 1; j < count; j++) {
          if (i == strs[j].length() || strs[j].charAt(i) != c) {
            return strs[0].substring(0, i);
          }
        }
      }
      return strs[0];
    }
  }

  static class Solution_分治 {

    public String longestCommonPrefix(String[] strs) {
      if (strs == null || strs.length == 0) {
        return "";
      } else {
        return longestCommonPrefix(strs, 0, strs.length - 1);
      }
    }

    public String longestCommonPrefix(String[] strs, int start, int end) {
      if (start == end) {
        return strs[start];
      } else {
        int mid = (end - start) / 2 + start;
        String lcpLeft = longestCommonPrefix(strs, start, mid);
        String lcpRight = longestCommonPrefix(strs, mid + 1, end);
        return commonPrefix(lcpLeft, lcpRight);
      }
    }

    public String commonPrefix(String lcpLeft, String lcpRight) {
      int minLength = Math.min(lcpLeft.length(), lcpRight.length());
      for (int i = 0; i < minLength; i++) {
        if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {
          return lcpLeft.substring(0, i);
        }
      }
      return lcpLeft.substring(0, minLength);
    }
  }

  static class Solution_二分 {

    public String longestCommonPrefix(String[] strs) {
      if (strs == null || strs.length == 0) {
        return "";
      }
      int minLength = Integer.MAX_VALUE;
      for (String str : strs) {
        minLength = Math.min(minLength, str.length());
      }
      int low = 0, high = minLength;
      while (low < high) {
        int mid = (high - low + 1) / 2 + low;
        if (isCommonPrefix(strs, mid)) {
          low = mid;
        } else {
          high = mid - 1;
        }
      }
      return strs[0].substring(0, low);
    }

    public boolean isCommonPrefix(String[] strs, int length) {
      String str0 = strs[0].substring(0, length);
      int count = strs.length;
      for (int i = 1; i < count; i++) {
        String str = strs[i];
        for (int j = 0; j < length; j++) {
          if (str0.charAt(j) != str.charAt(j)) {
            return false;
          }
        }
      }
      return true;
    }
  }
}

#15 三数之和

a+b+c=0 => a = -b-c => 两值转一值 —— 双指针 —— 意义就是：O(n²) => O(n)
答案中不可以包含重复的三元组 —— 则排序 + 遍历时跳过相同对象
重点：ci 的值不应该在 b-for 中被重置
- 否则 b、c 双指针将毫无意义。
- 优化后 23~25ms => 80%~57.49%

遍历时跳过相同对象，值得一品

for (int ai = 0; ai < iMax; ai++) {
  /* a 跳过重复对象 */
  if (ai > 0 && nums[ai - 1] == nums[ai]) {
    continue;
  }
}

for (int bi = ai + 1; bi < ci; bi++) {
  /* b 跳过重复对象 */
  if (bi > ai + 1 && nums[bi - 1] == nums[bi]) {
    continue;
  }
}

while (bi < ci && nums[bi] + nums[ci] > target) {
  /* c 跳过重复对象 这毫无实用价值。只会让时间复杂度变高 */
  do {
    ci--;
  } while (bi < ci && nums[ci] == nums[ci + 1]);
}

跳过重复对象的意义在于，用简单的条件判断运算，代替了复杂的求解运算
因为，c本身并没有求解运算，仅有 ci--
对于是否跳过重复c的判断，计算量大大超过了单纯的 ci--
因此，c 无需跳过重复对象。

package Order300;

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

public class T15_3sum {

  public static void main(String[] args) {
    for (List<Integer> tuple : new Solution().threeSum(new int[] { 1, 1, 1 })) {
      // for (List<Integer> tuple : new Solution().threeSum(new int[] { -1, 0, 1, 2, -1, -4 })) {
      // for (List<Integer> tuple : new Solution().threeSum(new int[] { -2, 0, 1, 1, 2 })) {
      for (int nums : tuple) {
        System.out.printf("%d\t", nums);
      }
      System.out.println();
    }
  }

  static class Solution {

    public List<List<Integer>> threeSum(int[] nums) {
      /* 答案中不可以包含重复的三元组,那么 排序+遍历时跳过重复对象 */
      Arrays.sort(nums);

      List<List<Integer>> out = new ArrayList<List<Integer>>(16);
      /* a + b + c = 0 => a+c = -b*/
      int iMax = nums.length;
      for (int ai = 0; ai < iMax; ai++) {
        /* a 跳过重复对象 */
        if (ai > 0 && nums[ai - 1] == nums[ai]) {
          continue;
        }
        int ci = iMax - 1;
        // int bi = ai + 1;
        int target = -nums[ai];/* b+c = -a */
        for (int bi = ai + 1; bi < ci; bi++) {
          /* b 跳过重复对象 */
          if (bi > ai + 1 && nums[bi - 1] == nums[bi]) {
            continue;
          }
          while (bi < ci && nums[bi] + nums[ci] > target) {
            ci--;
          }
          /**
           * 如果 bi == ci
           * 则，首先，bi ci 重复使用了同一元素，因此不能作为答案
           * 其次，下一次循环中 bi++，则 ci-while 循环动弹不得。
           * 也就是说，这样的 bi ≥ bi_now 都不会再有答案了，可以终止这样的 bi-for。
           */
          if (bi == ci) break;
          if (nums[bi] + nums[ci] == target) {
            List<Integer> ans = new ArrayList<>(4);
            ans.add(nums[ai]);
            ans.add(nums[bi]);
            ans.add(nums[ci]);
            out.add(ans);
          }
        }
      }
      return out;
    }
  }
}

#16 最接近的三数之和

这题我都能从 12:48 写到 14:45 这是我实在是没想到的。
双指针左右指针相向而行的情况，以后还是用 while(left<right) 来处理，写起来更方便

关于跳过重复对象，学到了一种更明白的写法，同时方便配合 while(left<right) 使用。

// 右指针向左 跳过重复项
int tmp_ci = ci - 1;
while (bi < tmp_ci && nums[ci] == nums[tmp_ci]) {
  tmp_ci--;
}
ci = tmp_ci;

// 左指针向右 跳过重复项
int tmp_bi = bi + 1;
while (tmp_bi < ci && nums[bi] == nums[tmp_bi]) {
  tmp_bi++;
}
bi = tmp_bi;

package Order300;

import java.util.Arrays;

public class T16_3sum_closest {

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

  static class Solution {

    int abs(int x) {
      return x > 0 ? x : -x;
    }

    public int threeSumClosest(int[] nums, int target) {
      Arrays.sort(nums);
      int iMax = nums.length;
      int distance = Integer.MAX_VALUE;
      int sum_3 = 0;
      for (int ai = 0; ai < iMax; ai++) {
        if (ai > 0 && nums[ai - 1] == nums[ai]) {
          continue;
        }
        int bi = ai + 1;
        int ci = iMax - 1;
        /* bi,ci 双指针 左右指针相向而行 */
        while (bi < ci) {
          /* 对于当前 <ai>[bi,ci] 更新 cur distance sum_3  */
          int cur = nums[ai] + nums[bi] + nums[ci];
          if (abs(cur - target) < distance) {
            distance = abs(cur - target);
            sum_3 = cur;
          }
          /* 如果当前状态是最优解 直接返回, 否则，调整bi,ci */
          if (distance == 0) {
            return sum_3;
          }
          /* 如果当前状态值过大，则 ci左移 —— 可以跳过重复项 */
          /* 否则当前状态值过小，则 bi右移 —— 可以跳过重复项 */
          if (cur > target) {
            int tmp_ci = ci - 1;
            while (bi < tmp_ci && nums[ci] == nums[tmp_ci]) {
              tmp_ci--;
            }
            ci = tmp_ci;
          } else {
            int tmp_bi = bi + 1;
            while (tmp_bi < ci && nums[bi] == nums[tmp_bi]) {
              tmp_bi++;
            }
            bi = tmp_bi;
          }
        }
      }
      return sum_3;
    }
  }
}

#17 电话号码的字母组合

从前一直分不清 DFS/BFS 和 回溯
这题，一开始也是想，不就是对一颗树做全遍历么，DFS/BFS五分钟搞定
后来才想明白：
- 如果需要全排列，那么首先考虑回溯算法
- 回溯首先是 DFS/BFS 的必要手段，其次是方便保存从起点至今的路径
DFS/BFS 是保证访问过每个节点
而对于DFS/BFS 而言，
- 如果想要保存从起点至今的路径
- 那么节点上除了保存节点的值 节点是否被访问
- 还需要额外保存 从起点至此节点的路径
- 节点变复杂了，Stack/Queue 里存放的元素也需要变得复杂
- 写起来就没那么方便了。
回溯函数——仍需多练：回溯函数的编写，远不及 DFS/BFS 的迭代实现来得熟练，还需多加练习。

package Order300;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class T17_letter_combinations_of_a_phone_number {

  public static void main(String[] args) {
    for (String s : new Solution().letterCombinations("23")) {
      System.out.println(s);
    }
  }

  static class Solution {

    static final Map<Character, String> MAP = new HashMap<Character, String>() {
      {
        put('2', "abc");
        put('3', "def");
        put('4', "ghi");
        put('5', "jkl");
        put('6', "mno");
        put('7', "pqrs");
        put('8', "tuv");
        put('9', "wxyz");
      }
    };

    public List<String> letterCombinations(String digits) {
      List<String> answerList = new ArrayList<>(256);
      if (digits.length() == 0) {
        return answerList;
      }
      backtrack(answerList, MAP, digits, 0, new StringBuilder());
      return answerList;
    }

    public void backtrack(
      List<String> walkedList, // 所有走完的路径，保存在此
      Map<Character, String> map, // 每个节点的下一条路可以怎么选
      String goal,// 总共要走完的 深度/目标
      int pos, // 当前是 第几步/第几层
      StringBuilder path // 从起点至今的节点路径
    ) {
      if (pos == goal.length()) {
        /* 若已经走完了，则保存结果 */
        walkedList.add(path.toString());
      } else {
        /* 看看下一步能怎么走 */
        char cur = goal.charAt(pos);
        String subPaths = map.get(cur);
        int subPathCnt = subPaths.length();
        for (int i = 0; i < subPathCnt; i++) {
          /* 对于每一种子路线 尝试访问之 */
          path.append(subPaths.charAt(i));
          backtrack(walkedList, map, goal, pos + 1, path);
          path.deleteCharAt(pos);
        }
      }
    }
  }
}

#18 四数之和

all distinct [a b c d] in [nums...] where a+b+c+d=target
第一种解法时间O(n³) 空间O(n)
- a-for b-for 常规嵌套循环
- while (c < d) 双指针实现
第二种解法时间O(n²) 空间O(n²)
- a-for b-for 常规嵌套循环保存组合值[a+b]
- c-for d-for 常规嵌套循环保存组合值[c+d]
- [a+b]for [c+d]for 常规嵌套循环，检查 a+b+c+d ?= target
- 省去这个写法的代码实现，思路懂就好了，不想写这个实现。

关键第一种解法时间O(n³) 空间O(n) 中的 a-for b-for 常规嵌套循环可以优化

for (int ai = 0; ai < iMax - 3; ai++) {
        if (ai > 0 && nums[ai - 1] == nums[ai]) {
          continue;
        }
        /* 若 ai，最小的解 ai,ai+1,ai+2,ai+3 已经大于 target 则 ai 已经太大了，没救了 break ai-for */
        if (
          nums[ai] + nums[ai + 1] + nums[ai + 2] + nums[ai + 3] > target
        ) break;
        if (
          nums[ai] + nums[iMax - 3] + nums[iMax - 2] + nums[iMax - 1] < target
        ) continue;
        /* 若 ai，最大的解 ai,iMax-3,iMax-2,iMax-1 已经大于 target 则 ai 还太小，还得再大一点 continue ai-for */
        for (int bi = ai + 1; bi < iMax - 2; bi++) {
          if (bi > ai + 1 && nums[bi - 1] == nums[bi]) {
            continue;
          }
          ... ...

ai 跳过重复
ai 最大值为 iMax-3
ai 太小则跳往下一个ai
ai 太大则跳出 a-for
ai 最大值为 iMax-2

package Order300;

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

public class T18_4sum {

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

  static class Solution {

    public List<List<Integer>> fourSum(int[] nums, int target) {
      List<List<Integer>> answers = new ArrayList<List<Integer>>();
      Arrays.sort(nums);
      int iMax = nums.length;
      for (int ai = 0; ai < iMax - 3; ai++) {
        if (ai > 0 && nums[ai - 1] == nums[ai]) {
          continue;
        }
        /* 若 ai，最小的解 ai,ai+1,ai+2,ai+3 已经大于 target 则 ai 已经太大了，没救了 break ai-for */
        if (
          nums[ai] + nums[ai + 1] + nums[ai + 2] + nums[ai + 3] > target
        ) break;
        if (
          nums[ai] + nums[iMax - 3] + nums[iMax - 2] + nums[iMax - 1] < target
        ) continue;
        /* 若 ai，最大的解 ai,iMax-3,iMax-2,iMax-1 已经大于 target 则 ai 还太小，还得再大一点 continue ai-for */
        for (int bi = ai + 1; bi < iMax - 2; bi++) {
          if (bi > ai + 1 && nums[bi - 1] == nums[bi]) {
            continue;
          }
          int ci = bi + 1;
          int di = iMax - 1;
          while (ci < di) {
            int cur = nums[ai] + nums[bi] + nums[ci] + nums[di];
            if (cur == target) {
              // ArrayList<Integer> ans = new ArrayList<>(4);
              // ans.add(nums[ai]);
              // ans.add(nums[bi]);
              // ans.add(nums[ci]);
              // ans.add(nums[di]);
              // answers.add(ans);
              /* 答案不用修改，所以可以用 Arrays.asList() */
              answers.add(
                Arrays.asList(nums[ai], nums[bi], nums[ci], nums[di])
              );
              /* 可能在这个 while 内还有 ci,di 的其他可行解，因此answers.add()后，不能break也不能continue，而应该是重排 ci,di */
              while (ci < di && nums[ci] == nums[ci + 1]) {
                ci++;
              }
              ci++;
              while (ci < di && nums[di] == nums[di - 1]) {
                di--;
              }
              di--;
            } else if (cur < target) {
              /* 省去跳跃重复是速度优化 */
              ci++;
            } else {
              /* 省去跳跃重复是速度优化 */
              di--;
            }
          }
        }
      }
      return answers;
    }
  }
}

#19 删除链表的倒数第N个节点

方法一：两次扫描 —— 第一次获取总长度 —— 第二次获取倒数第N个节点
方法二：倒数 —— 联想到栈 —— 第一次遍历，节点逐个入栈 —— 然后 pop N次
方法三：双指针 —— 快慢指针（感觉叫抢跑指针更合适哈哈哈）
- 快指针抢跑N位，然后快慢指针同速前进
- 快指针到终点时，慢指针在倒数第N个
方法二栈，缺点是空间复杂度达到了O(n) —— 方法三快慢指针空间复杂度 O(1)
哨兵节点以 dummy 为名（直译为假人）
哨兵节点指向头节点。即使头节点被删，也不影响返回dummy.next

/* class ListNode {
  int val;
  ListNode next;
  ListNode() {}
  ListNode(int val) {    this.val = val;  }
  ListNode(int val, ListNode next) {    this.val = val;    this.next = next;  }
  List<Integer> toList() {
    List<Integer> out = new ArrayList<Integer>();
    ListNode cur = this;
    do {      out.add(cur.val);      cur = cur.next;    } while (cur != null);    return out;  }
  ListNode add(int val) {    this.next = new ListNode(val);    return this.next;  }} */
package Order300;

import Order300.T2_add_two_numbers.ListNode;

public class T19_remove_nth_node_from_end_of_list {

  public static void main(String[] args) {
    ListNode list = new ListNode(1);
    list.add(2).add(3).add(4).add(5).add(6);
    System.out.println(list.toList());
    System.out.println((new Solution().removeNthFromEnd(list, 2).toList()));
    System.out.println((new Solution().removeNthFromEnd(list, 2).toList()));
    System.out.println((new Solution().removeNthFromEnd(list, 2).toList()));
    System.out.println((new Solution().removeNthFromEnd(list, 1).toList()));
    System.out.println((new Solution().removeNthFromEnd(list, 1).toList()));
    System.out.println((new Solution().removeNthFromEnd(list, 1).toList()));
  }

  static class Solution {

    public ListNode removeNthFromEnd(ListNode head, int n) {
      /* 哨兵节点 以 dummy 为名（直译为 假人） */
      ListNode dummy = new ListNode(0, head);
      ListNode fast, slow;
      fast = slow = dummy;
      while (n-- != 0) {
        fast = fast.next;
      }
      while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
      }
      slow.next = slow.next.next;
      return dummy.next;
    }
  }
}

#20 有效的括号

括号匹配 —— 对称性匹配 —— 栈
图方便用函数代替了HashSet
还OK的啦～ 2ms => 77.11%
stack.pop() 前要记得确保栈非空
判断奇偶：x & 1 和 x % 2 是等价的

package Order300;

import java.util.Stack;

public class T20_valid_parentheses {

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

  static class Solution {

    char pair(char right) {
      switch (right) {
        case ')':
          return '(';
        case ']':
          return '[';
        case '}':
          return '{';
        default:
          return right;
      }
    }

    boolean left(char x) {
      if (x == '(' || x == '[' || x == '{') return true; else return false;
    }

    public boolean isValid(String s) {
      int iMax = s.length();
      /* 判断奇偶 这样写也可以 */
      if ((s.length() & 1) != 0) {
        return false;
      }
      Stack<Character> stack = new Stack<>();
      for (int i = 0; i < iMax; i++) {
        if (left(s.charAt(i))) {
          stack.push(s.charAt(i));
        } else if (
          stack.isEmpty() || stack.pop() != pair(s.charAt(i))
        ) return false;
      }
      return stack.isEmpty();
    }
  }
}