阿星的学习笔记

0%

LeetCode题解(一):10, 15, 57, 59

发表于 更新于 分类于

题目名称

第10题：正则表达式匹配(困难)
第15题：三数之和(中等)
第57题：和为s的连续正数序列(简单)
第59题：II.队列的最大值(中等)

第10题：正则表达式匹配

题目描述

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.'和 '*'的正则表达式匹配。

'.'匹配任意单个字符
'*'匹配零个或多个前面的那个元素

说明

  • s 可能为空，且只包含从 a-z 的小写字母
  • p 可能为空，且只包含从 a-z 的小写字母，以及字符'.'和 '*'

解题思路

　　见到字符串匹配，字符串操作的题，第一反应就是DP。而且DP数组中的下标如i一般都代表匹配字符串的0: i - 1或者i: len - 1。
　　很显然，这道题可以用DP求解，dp[i][j]表示p[0: j-1]可以和s[0: i - 1]匹配。

数组初始化

  • dp[0][0] = true: 因为null匹配null
  • dp[0< i <= slen][0] = false: p为null， 无法匹配任何值
  • dp[0][0< j＜= plen]: 这个初始化稍微复杂一点，因为例如a*或者a*b*这种都是可以匹配null的，因此我们用一个循环来初始化这种状态。
1
2
3
for(int j = 1; j <= plen; j++){
	if(p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 2];
}

状态转移方程

　　这题最难的地方在状态转移方程的求解，即如何求得dp[i][j]？

  1. 第一种情况: s[i - 1] == p[j - 1] ||　ｐ[j - 1] == '.'，此时dp[i][j] = dp[i - 1][j - 1]
  2. 第二种情况: p[j - 1] == '*'，分别有两种可能需要考虑:
    • s[i - 1] == p[j - 2] || p[j - 2] == '.'，此时又有三种情况，只要一种成立即可:
      • * 匹配0次: dp[i][j] = dp[i][j - 2], 因为匹配0次的话，p[0: j]的作用等同于p[0: j - 2]
      • * 匹配1次: dp[i][j] = dp[i][j - 1], 这个很容易理解
      • * 匹配多次: dp[i][j] = dp[i - 1][j], 这是最难理解的，因为如果*匹配了多次，则s字符串增加一个与p[j - 2]相同的数并无影响
    • s[i - 1] != p[j - 2] || p[j - 2] != '.'，此时只可能有一种情况:
      • * 只能匹配0次: dp[i][j] = dp[i][j - 2]
  3. 其他情况: dp[i][j] = false

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isMatch(String s, String p) {
        int slen = s.length(), plen = p.length();
        // dq[i][j] means p[0 : j] matches s[0 : i]
        boolean[][] dp = new boolean[slen + 1][plen + 1]; 
        dp[0][0] = true;
        for(int j = 1; j <= plen; j++)
            if(p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 2];
        for(int i = 1; i <= slen; i++){
            for(int j = 1; j <= plen; j++){
                if(s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')
                    dp[i][j] = dp[i-1][j-1];
                else if(p.charAt(j - 1) == '*'){
                    if(p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)){
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 2] || dp[i][j - 1]; 
                    }else dp[i][j] = dp[i][j - 2];
                }
            }
        }
        return dp[slen][plen];
    }
  • 时间复杂度:
  • 空间复杂度:

补充

　　本题还可以用回溯法做，但是笔者特别讨厌用递归，虽然递归用起来很简洁，但是空间利用率实在是太感人了，计算起来也十分麻烦。笔者曾经用递归写过一个项目的方法，出现堆栈溢出问题的时候简直崩溃，因此立下flag：能不用递归就不用递归。因此回溯的算法就不写了。
回溯法思路：

  • 首字符匹配，且p的后一字符不是* : 匹配(s.substring(1), p.substring(1))
  • 首字符匹配，且p的后一字符是* : 匹配(s, p.substring(2)) ||　(ｓ.substring(1), p)
  • 首字符不匹配，且p的后一字符是* : 匹配(s, p.substring(2))
  • 递归出口:
    • 首字符不匹配，且p的后一字符不是* : return false
    • p为空: return s为空
    • 这里注意一下，s为空并不作为出口，而作为(首字符不匹配)的情况

遇到过的问题

  • 将*看成了匹配零次或无数次任意字符，导致直接做错
  • 匹配多次的方程没想出来

　

第15题：三数之和

题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意: 答案中不可以包含重复的三元组。

解题思路

　　这道题最主要的就是要想到用双指针的方法去求解twoSum，想到了就很简单。写博客的时候不小心写上了，改名字有点费事，所以就贴个代码上去。暴力求解这种基本谁都能想到，但是如果用暴力去做算法题的话，就失去了做算法题的意义，不是吗？

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // O(nlgn)
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        // O(n^2)
        for(int i = 0; i < nums.length - 2; i++){
            if(nums[i] > 0) break;
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int target = -nums[i], left = i+1, right = nums.length - 1;
            while(left < right){
                int twoSum = nums[left] + nums[right];
                if(twoSum == target){
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while(left + 1 < nums.length - 1 && nums[left] == nums[left+1]) left++;
                    while(right - 1 > i + 1 && nums[right] == nums[right-1]) right--;
                    left++;right--;
                }else if(twoSum > target) right--;
                else left++;
            }
        }
        return ans;
    }
  • 时间复杂度:
  • 空间复杂度:

第57题: 和为s的连续正数序列

题目描述

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

解题思路

　　这道题比较简单，采用滑动窗口法进行计算即可。笔者不擅长解答除了找规律外的数学问题，所以数学解法就不考虑了。数学解法固然巧妙，但是我为了找工作而刷题，就不需要整这些花里胡哨的了，只需要保证时间空间复杂度尽可能少一些就ok。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[][] findContinuousSequence(int target) {
        int left = 1, right = 2;
        List<int[]> ans = new ArrayList<>();
        if(target == 1) ans.add(new int[]{1});
        while(left < right && right <= target / 2 + 1){
            int sum = (left + right) * (right - left + 1) / 2;
            if(sum == target){
                int[] temp = new int[right - left + 1];
                for(int i = left; i <= right; i++) temp[i - left] = i;
                ans.add(temp);
                right++;
            }else if(sum > target) left++;
            else right++;
        }
        return (int[][]) ans.toArray(new int[ans.size()][]);
    }
}
  • 时间复杂度:
  • 空间复杂度: : 使用了一个数组来临时存储序列

踩过的坑

　　这道题很简单，但是笔者一开始并没有想到用滑动窗口法去解决问题，我第一反应是先固定左端的数，然后用二分查找的算法去找右边的数。算法是没错的，时间复杂度O(NlgN)也算马马虎虎，但是死活提交不过。后来Debug才发现，原来是计算的sum越界了，int最大能取到$ 2^{31} - 1 = 2147483647 = 0x7fffffff $, 如果再加1，就会变最小负值，然后就一直是负数了，除非再加一次最大值。随便举个例子: 计算1, 2, 3,..., 8000000就越界了。

第59题：II.队列的最大值

题目描述

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

解题思路

　　这道题卡了我很久，原因是我忽略了均摊时间复杂度的含义: 进行N次操作，其每次操作的平均复杂度为O(1)。
　　要解决这道题有两个很重要的点:

  1. 只要插入了一个最大值，在前面的值pop_front前，这个最大值就不会改变。
  2. 如何保证最大值被pop掉后，我们可以找到次大值？: 只需要将正常入队的序列进行某些操作后保存为一个非递增的辅助序列即可。
    • 解释：假设我们有序列xAyBzC，其中A > x; B > y; C > z; A > B > C，那么辅助序列ABC就是在进行max_value()操作中只可能出现的三个最大值，因为有了A，前面的x就失去了价值，而A一旦被pop后，A前面的数就不会在序列里了，子序列yBzC中最大的就是B，以此类推。因此这是一个线性问题。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class MaxQueue {
    Deque<Integer> aux;
    Deque<Integer> dq;

    public MaxQueue() {
        this.aux = new LinkedList<Integer>();
        this.dq = new LinkedList<Integer>();
    }
    
    public int max_value() {
        return aux.size() == 0 ? -1 : aux.peek();
    }
    
    public void push_back(int value) {
        dq.addLast(value);
        while(aux.peekLast() != null && aux.peekLast() < value) aux.pollLast();
        aux.addLast(value);
    }
    
    public int pop_front() {
        if(dq.size() == 0) return -1;
        // Integer 没进入常量池，不能用 == 来判断
        if(dq.peek().equals(aux.peek())) aux.pollFirst();
        return dq.pollFirst();
    }

踩过的坑

  1. 没理解均摊复杂度
  2. 没想到用非递增的辅助序列
  3. 两个没有拆箱的Integer对象，不能用==来判断其value是否相等。(基于这点，笔者想要写一篇文章来详细解析一下这种包装类，届时会放链接)