阿秀的学习笔记

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

力扣原题链接（点我直达） (opens new window)

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

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
1
2
3
4
5

示例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
1
2
3
4
5

示例 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
1
2
3
4
5

示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
1
2
3
4
5

示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
1
2
3
4
  • s 可能为空，且只包含从 a-z 的小写字母。
  • p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。

# 1、牛课上大佬写法

执行用时：20 ms, 在所有 C++ 提交中击败了53.68%的用户

内存消耗：6.1 MB, 在所有 C++ 提交中击败了100.00%的用户

bool isMatchCore( const char* s,  const char* p) {
	if (*s=='\0' && *p=='\0') return true;
	if (*s != '\0' && *p == '\0') return false;
	if (*(p+1) != '*') {
		if (*s == *p || (*s != '\0' && *p == '.'))  return isMatchCore(s + 1, p + 1);
		else
			return false;
	}
	else {
		if (*s == *p || (*s != '\0' && *p == '.')) return isMatchCore(s, p + 2) || isMatchCore(s + 1, p);
		else
			return isMatchCore(s, p + 2);
	}

}

bool isMatch(string s, string p) {
	
	return isMatchCore(s.c_str(), p.c_str());
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 32. 最长有效括号 这个真的难

力扣原题链接（点我直达） (opens new window)

# 字节面试4连击

https://mp.weixin.qq.com/s/ONRJviXVqmKimchyZLeJjg

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
1
2
3

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
1
2
3

# 第一版，自己写的，完全错误，没有意识到这是个DP问题

"()(()"

4

2

    int longestValidParentheses(string s) {
    stack<char> res;
	int cut = 0;
	for (auto& a : s) {
		if (res.empty() || a == '(') res.push(a);
		else if (a == ')') {
			if (res.top() == '(') {
				cut++;
				res.pop();
			}
		}


	}

	return 2 * cut;
        
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

我这样的算法相当于计算s中有多少个匹配的括号，并没有想到序列问题

# 第二版本，借助栈

执行用时 :4 ms, 在所有 cpp 提交中击败了96.32%的用户

内存消耗 :9.5 MB, 在所有 cpp 提交中击败了82.19%的用户

这道题的优化版本我们仍然是用栈来做，不过入栈的时候，不是让 "(" 入栈，而是让 "(" 的下标入栈。步骤如下：

1、先把 -1 放入栈内。（至于为什么？看到后面你就知道了） 2、、对于遇到的每个 '(' ，我们将它的下标放入栈中。 3、对于遇到的每个 ‘)’ ，我们弹出栈顶的元素并将当前元素的下标与弹出元素下标作差，得出当前有效括号字符串的长度。

通过这种方法，我们继续计算有效子字符串的长度，并最终返回最长有效子字符串的长度。

看不懂？没事，我弄个例子画几个图，例如 s = "( ) ) ( ( ) )"，并且用变量 max 来保存最长有效字符串的程度，i 表示当前字符串的下标

0、初始化：max = 0; i = 0。-1 放入栈内

在这里插入图片描述

1、i = 0，s[i] = '('，下标 i = 0 入栈

在这里插入图片描述

2、i = 1，s[i] = ')'，出栈; i - 栈顶元素 = 1 - (-1) = 2，此时 max = 2

在这里插入图片描述

3、i = 2，s[i] = ')'，出栈；：由于 -1 出栈后，栈顶没有元素了，所以这个时候我们必须把 ')' 的下标入栈，相当于最开始的初始化。

在这里插入图片描述

4、i = 3，s[i] = '('，入栈;

在这里插入图片描述

5、i = 4，s[i] = '('，入栈;

在这里插入图片描述

6、i = 5，s[i] = ')'，出栈；i - 栈顶 = 5 - 3 = 2；此时 max = 2;

在这里插入图片描述

7、i = 6，s[i] = ')'，出栈；i - 栈顶 = 6 - 2 = 4；此时 max = 4;

在这里插入图片描述

8、遍历结束，最长有效括号为 4。

    int longestValidParentheses(string s) {
	stack<int> res;
	int len = s.size(),maxNum=0;
	res.push(-1);
	for (int i = 0; i < len; ++i) {
		
		if (s[i] == '(') {
			//下标入栈
			res.push(i);
		}
		else {
			// 出栈
			res.pop();
			// 看栈顶是否为空，为空的话就不能作差了
			if (res.empty()) {
				res.push(i);
			}
			else {
				// i - 栈顶，获得档期有效括号长度
				maxNum = max(maxNum, i - res.top());
			}
		}
	}
		
	return maxNum;
        
    }
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
26
27

# 第二种栈的解法，其实更慢一点了

执行用时 :12 ms, 在所有 cpp 提交中击败了40.53%的用户

内存消耗 :11.7 MB, 在所有 cpp 提交中击败了5.54%的用户

对于这种括号匹配问题，一般都是使用栈

我们先找到所有可以匹配的索引号，然后找出最长连续数列！

例如：s = )(()())，我们用栈可以找到，

位置 2 和位置 3 匹配，

位置 4 和位置 5 匹配，

位置 1 和位置 6 匹配，

这个数组为：2,3,4,5,1,6 这是通过栈找到的，我们按递增排序！1,2,3,4,5,6

找出该数组的最长连续数列的长度就是最长有效括号长度！

所以时间复杂度来自排序：O(nlogn)

int longestValidParentheses(string s) { //   ())(())

	stack<int> res;
	vector<int> num;
	int len = s.size(),maxNum=0;
	for (int i = 0; i < len; ++i) {
		
		if (s[i] == '(') {
			//下标入栈
			res.push(i);
		}
		else {		
			// 出栈
			if (res.empty()) {
				res.push(i);
			}
			else if(s[res.top()]=='('){ //这一步很重要
				num.push_back(res.top());
				res.pop();
				num.push_back(i);
			}
		}
	}
	
	//for (auto& a : num) {
	//	cout << a<<endl;
	//}

	sort(num.begin(), num.end());

	//for (auto& a : num) {
	//	cout << a << endl;
	//}

	stack<int>().swap(res);
	for (auto& a : num) {
		if (res.empty())
			res.push(a);
		else if (a - res.top() == 1) {
			res.push(a);
		}
		else {

			maxNum = max(maxNum, static_cast<int>(res.size()));
			stack<int>().swap(res);
			res.push(a);
		}
	}
	maxNum = max(maxNum, static_cast<int>(res.size()));

	return maxNum;
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

# 第三版本，用变量代替栈的一个解法

用变量来代替栈来优化，不过这个时候我们需要两个变量，我们假设变量为 left 和 right。

我们在从从左到右遍历字符串的过程中，用 left 记录 '(' 的数量，用 right 记录 ')' 的数量。并且在遍历的过程中：

1、如果 left >= right，显然这个时候 right 个 ')' 都将一定能够得到匹配。所以当前的有效括号长度为 2 * right。然后更新 max。

2、如果 left < right，显然这个时候部分 ')' 一定得不到匹配，此时我们把 left 和 right 都置为 0。

**当遍历完字符串，我们是否就得到最大长度的有效括号了呢？**大家可以想一下

答是不可以的，我们还需要从右到左遍历计算一下。

为什么呢？

因为实际上 '(' 和 ')' 其实是等价的，为什么就不可以倒过来遍历计算呢？所以，千万别忽略了哈。

执行用时 :4 ms, 在所有 cpp 提交中击败了96.32%的用户

内存消耗 :9 MB, 在所有 cpp 提交中击败了98.50%的用户

int longestValidParentheses(string s) { //   ())(())

	int left = 0, right = 0, maxNum = 0;
	// 从左到右
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == '(') {
			left++;
		}
		else {
			right++;
		}
		if (left == right) {
			maxNum = max(maxNum, 2 * right);
		}
		else if (right > left) {
			left = right = 0;
		}
	}
	left = right = 0;
	// 从右到左
	for (int i = s.length() - 1; i >= 0; i--) {
		if (s[i] == '(') {
			left++;
		}
		else {
			right++;
		}
		if (left == right) {
			maxNum =max(maxNum, 2 * left);
		}
		else if (left > right) {
			left = right = 0;
		}
	}
	return maxNum;
}
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
26
27
28
29
30
31
32
33
34
35
36
37

这个问题可以通过动态规划解决。我们定义一个 \text{dp}dp 数组，其中第 ii 个元素表示以下标为 ii 的字符结尾的最长有效子字符串的长度。我们将 \text{dp}dp 数组全部初始化为 0 。现在，很明显有效的子字符串一定以 \text{‘)’}‘)’ 结尾。这进一步可以得出结论：以 \text{‘(’}‘(’ 结尾的子字符串对应的 \text{dp}dp 数组位置上的值必定为 0 。所以说我们只需要更新 \text{‘)’}‘)’ 在 \text{dp}dp 数组中对应位置的值。

# 887. 鸡蛋掉落 谷歌微软经典题目

力扣原题链接（点我直达） (opens new window)

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。

每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。

你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？

示例 1：

输入：K = 1, N = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。
1
2
3
4
5
6
7

示例 2：

输入：K = 2, N = 6
输出：3
1
2

示例 3：

输入：K = 3, N = 14
输出：4
1
2

提示：

  1. 1 <= K <= 100
  2. 1 <= N <= 10000

# 第0版 最好懂，可是会超时

int superEggDrop(int K, int N)
{
	if (N == 0 || N == 1 || K == 1) {
		return N;
	}

	int minNum = N;
	for (int i = 1; i <= N; i++) {
		int tMin = max(superEggDrop(K - 1, i - 1), superEggDrop(K, N - i));
		minNum = min(minNum, 1 + tMin);
	}
	return minNum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 第一版，公众号解析

https://mp.weixin.qq.com/s/7PEBnUfIpiuw26lVeihlhA

# 第二版，换个思路解题

执行用时 :8 ms, 在所有 cpp 提交中击败了68.65%的用户

内存消耗 :8.3 MB, 在所有 cpp 提交中击败了93.34%的用户

从多少楼层多少个蛋最少要扔几次，转变为有多少个蛋扔几次可以测试出多少楼层。

执行用时 :8 ms, 在所有 cpp 提交中击败了68.65%的用户

内存消耗 :8.1 MB, 在所有 cpp 提交中击败了97.84%的用户

int help(int i, int K) {
	return (i == 1 || K == 1) ? i : help(i - 1, K - 1) + help(i - 1, K) + 1;
}


int superEggDrop(int K, int N) {
	int count = 1;
	while (help(count, K) < N) {
		count++;
	}
	return count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 第二版的第二种解释

上面的方法的思路，都还是顺着题目的思路的进行的，其实我们可以换一个思路来想：“求k个鸡蛋在m步内可以测出多少层”。我们令dp [k] [m]表示k个鸡蛋在m步内可以测出的最多的层数，那么当我们在第X层扔鸡蛋的时候，就有两种情况：

鸡蛋碎了，我们少了一颗鸡蛋，也用掉了一步，此时测出N - X + dp [k-1] [m-1]层，X和它上面的N-X层已经通过这次扔鸡蛋确定大于F； 鸡蛋没碎，鸡蛋的数量没有变，但是用掉了一步，剩余X + dp [k] [m-1]，X层及其以下已经通过这次扔鸡蛋确定不会大于F； 也就是说，我们每一次扔鸡蛋，不仅仅确定了下一次扔鸡蛋的楼层的方向，也确定了另一半楼层与F的大小关系，所以在下面的关键代码中，使用的不再是max，而是加法（这里是重点）。评论里有人问到为什么是相加，其实这里有一个惯性思维的误区，上面的诸多解法中，往往求max的思路是“两种方式中较大的那一个结果”，其实这里的相加，不是鸡蛋碎了和没碎两种情况的相加，而是“本次扔之后可能测出来的层数 + 本次扔之前已经测出来的层数”。

假设我们有 k 个鸡蛋可以移动 m 步，考虑某一步 t 应该在哪一层丢鸡蛋？一个正确的选择是在 dp [k-1] [t-1] + 1 层丢鸡蛋，结果分两种情况：

  1. 如果鸡蛋碎了，我们首先排除了该层以上的所有楼层（不管这个楼有多高），而对于剩下的 dp [k-1] [t-1] 层楼，我们一定能用 k-1 个鸡蛋在 t-1 步内求解。因此这种情况下，我们总共可以求解无限高的楼层。可见，这是一种非常好的情况，但并不总是发生。
  2. 如果鸡蛋没碎，我们首先排除了该层以下的 dp [k-1] [t-1] 层楼，此时我们还有 k 个蛋和 t-1 步，那么我们去该层以上的楼层继续测得 dp [k] [t-1] 层楼。因此这种情况下，我们总共可以求解 dp [k-1] [t-1] + dp [k] [t-1] + 1 层楼。

容易想象，在所有 m 步中只要有一次出现了第一种情况，那么我们就可以求解无限高的楼层。但“保证求解”的定义要求我们排除一切运气成分，因此我们只得认为每次移动都遇到第二种情况。于是得到递推公式：

dp [k ] [t] = dp [k-1] [t-1] + dp [k] [t-1] + 1

执行用时 :8 ms, 在所有 cpp 提交中击败了68.65%的用户

内存消耗 :31.8 MB, 在所有 cpp 提交中击败了25.89%的用户

int superEggDrop(int K, int N)
{
	vector<vector<int>>  dp(K + 1,vector<int>(N + 1,0));
	//当N=0时，K等于多少都是0，或者当K=1时，只能有K种解法了
	//dp[0][m] = 0; // zero egg
	for (int n = 1; n <= N; n++) {
		for (int k = 1; k <= K; k++) {
			dp[k][n] = dp[k][n - 1] + dp[k - 1][n - 1] + 1;
			if (dp[k][n] >= N) {
				return n;
			}
		}
	}
	return N;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1