0%

LeetCode算法经典题集(一)

标注

来源:力扣(LeetCode
链接:https://leetcode-cn.com/problemset/algorithms/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

3.无重复字符的最长子串(滑动窗口✓)

题目

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

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

题解

初次解题,解法偏暴力

通过集合的添加操作的返回的布尔值,来判断是否存在重复元素,并计算长度

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int lengthOfLongestSubstring(String s) {
int len = s.length();
int ans = 0;
for (int i = 0; i < len; i++) {
Set<Character> set = new HashSet<>();
int cnt = 0;
for (int j = i; j < len; j++) {
boolean b = set.add(s.charAt(j));
if (b) {
cnt++;
} else {
break;
}
}
ans = (ans < cnt) ? cnt : ans;
}

return ans;
}

算法分析:

  • 时间复杂度 O(n2)
  • 空间复杂度 O(n)

优化算法——滑动窗口

滑动窗口是数组/字符串问题中常用的抽象概念。
窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合,即 [i, j)(左闭,右开)。
而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如,我们将 [i, j) 向右滑动 1 个元素,则它将变为 [i+1, j+1)(左闭,右开)。
我们可以定义字符到索引的映射,而不是使用集合来判断一个字符是否存在。 当我们找到重复的字符时,我们可以立即跳过该窗口
也就是说,如果 s[j][i, j)范围内有与 j'重复的字符,我们不需要逐渐增加i 。 我们可以直接跳过 [i,j']范围内的所有元素,并将 i 变为 j' + 1

优化代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int lengthOfLongestSubstring(String s) {
int len = s.length();
int ans = 0;
Map<Character, Integer> map = new HashMap<>();

for (int i = 0, j = 0; i < len; i++) {
if (map.containsKey(s.charAt(i))) {
j = Math.max(j, map.get(s.charAt(i)));
}
map.put(s.charAt(i), i + 1);
ans = Math.max(ans, i - j + 1);
}

return ans;
}

算法分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(min(m, n))

5.最长回文子串(动态规划/中心扩展算法/Manacher算法✓)

题目

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。

题解

动态规划解法

我们可以把字符串s倒置得到revStr,然后找出两个字符串的最长公共子串
这里采用动态规划打表,空间换时间
定义一个 dp[][] 二维数组,该数组每个单元用来存储匹配子串的长度
由于java中没有赋值元素的默认为0,在二重循环遍历dp数组的时候,我们只需要处理s在其索引值irevStr在其索引值j处相等的时候的情况

  • i == 0 || j == 0:赋值1
  • 其他匹配情况:dp[i][j] = dp[i - 1][j - 1] + 1

匹配时记录索引坐标与匹配长度,去匹配长度最大值,执行相关操作

注意,当字符串s的其他部分中存在非回文子串的反向副本时,结果就会出错
例子:

s = "abacdfgdcaba"
revStr = "abacdgfdcaba"
srevStr 之间的最长公共子串为"abacd",显然,这不是回文

所以,为了解决这个问题,每当我们找到最长的公共子串的候选项时,都需要检查子串的索引是否与反向子串的原始索引相同:

  • 如果相同,那么我们尝试更新目前为止找到的最长回文子串
  • 如果不同,我们就跳过这个候选项并继续寻找下一个候选。

代码如下

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
public String longestPalindrome(String s) {
if (s.length() < 1) {
return "";
}

int len = s.length();
int maxLen = 0;
int[][] dp = new int[len][len];
int end = 0;
String revStr = new StringBuffer(s).reverse().toString();

for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
if (s.charAt(i) == revStr.charAt(j)) {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
}

if (dp[i][j] > maxLen) {
int bef = len - j - 1;
if (bef + dp[i][j] - 1 == i) {
maxLen = dp[i][j];
end = i;
}
}
}
}

return s.substring(end - maxLen + 1, end + 1);
}

算法分析:

  • 时间复杂度 O(n2)
  • 空间复杂度 O(n2)

中心扩展算法

很明显,回文中心的两侧互为镜像,从回文中心展开,有2n − 1个这样的中心

回文字符串长度可以是奇数也可以是偶数,故展开有2n − 1个中心

遍历字符串,消耗 O(n) 时间,通过方法expandAroundCenter从中心扩展字符串,符合条件s.charAt(L) == s.charAt(R)就继续扩展,其中又耗时 O(n)

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}

private static int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R - L - 1;
}

算法分析:

  • 时间复杂度:O(n2)
  • 空间复杂度:O(1)

Manacher 算法

Manacher 算法可以称作“马拉车”算法,主要用于处理字符串中关于回文串的问题

回归题目,为了统一字符串长度的奇偶性,首先可以写一个方法process()在每个字符串的每个字符两侧加上一个分隔符,一般设置为'#',这样只需考虑长度是奇数的字符串了

由于可能还会出现越界问题,所以在字符串首部再加上一个字符$防止越界

样例:"babad"
处理后:$#b#a#b#a#d#

接着定义一个辅助数组p[i]p[i]表示以i为中心的最长回文半径
p[i]=1,回文子串就是其本身

例如

字符串 $ # b # a # b # a # d #
索引 0 1 2 3 4 5 6 7 8 9 10 11
p[i] / 1 2 1 4 1 4 1 2 1 1 2

我们需要设置两个变量,idmx

id表示最长回文子串的中心
mx表示最长回文子串的右半径

遍历处理过的子串ss
如果 i < mx,那么p[i] = min(p[2 * id - i], mx - i)

2 * id - ii关于id的对称点

关于为何p[i] = min(p[2 * id - i], mx - i)

mx是回文部分最右边界,id是中心,故在这个范围内,其以id为中心的右对称点i处的最大回文半径p[i]是等于左对称点的,后续要是可以扩展回文子串,附加一个while()循环即可

Java代码如下

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
public static String process(String s) {
int n = s.length();
String str = "$#";
for (int i = 0; i < n; i++) {
str += (s.substring(i, i + 1) + "#");
}
return str;
}

public static String longestPalindrome(String s) {
if (s.length() < 2) {
return s;
}

String ss = process(s);
int len = ss.length();
int maxLen = 0;
int id = 0;
int mx = 0;
int[] p = new int[len];

// 用来存回文子串的首尾坐标
int start = 0, end = 0;

for (int i = 1; i < len - 1; i++) {
if (i < mx) {
p[i] = Math.min(mx - i, p[2 * id - i]);
} else {
p[i] = 1;
}

// 扩展 p[i],不需要判断边界
while (i + p[i] < len && ss.charAt(i - p[i]) == ss.charAt(i + p[i])) {
p[i]++;
}

if (i + p[i] > mx) {
id = i;
mx = i + p[i];
}

if (p[i] - 1 > maxLen) {
maxLen = Math.max(maxLen, p[i] - 1);
start = i - maxLen;
end = i + maxLen;
}
}

return ss.substring(start, end).replaceAll("#", "");
}

算法分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

10.正则表达式匹配(动态规划/回溯法✓)

题目

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

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

说明:

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

示例 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 = “c*a*b”
输出: true
解释: 因为 ‘*’ 表示零个或多个,这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。

示例 5:

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

题解

活用 Java 库

String库的matches方法,或java.util.regex包下的Pattern类的matches方法,这个不介绍,了解一下有这个东西就行

一行代码即可,方法已经解决了正则表达式匹配问题

1
2
3
4
public boolean isMatch(String s, String p) {
//return s.matches(p);
return java.util.regex.Pattern.matches(p, s);
}

回溯法

思路:

  • 首先需要检验模式串pattern是否空,如果pattern空,那么’text’也得是空
  • 如果模式串pattern中没有星号'*'存在,那么只需逐个检查patterntext的每一个字符是否匹配
  • 当模式串pattern中有星号'*'时,就需要检查匹配串text中的不同后缀,以判断它们是否能匹配模式串pattern剩余的部分

如果模式串pattern中没有星号'*'时,代码可以像下面这么写

1
2
3
4
5
6
7
8
9
public boolean isMatch(String text, String pattern) {
if (pattern.isEmpty()) {
return text.isEmpty();
}
boolean first_match = (!text.isEmpty() &&
(pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));

return first_match && isMatch(text.substring(1), pattern.substring(1));
}

如果模式串中有星号,它只会出现在第二个位置,即pattern[1]

这种情况下,我们有两种选择:

  • 直接忽略模式串中的这一部分(因为'*' 匹配零个或多个前面的那一个元素)
  • 删除匹配串的第一个字符(前提是它能够匹配模式串当前位置字符,即pattern[0]

如果两种操作中有任何一种使得剩下的字符串能匹配,那么初始时,匹配串和模式串就可以被匹配

完整代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean isMatch(String text, String pattern) {
if (pattern.isEmpty()) {
return text.isEmpty();
}
boolean first_match = (!text.isEmpty() &&
(pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));

if (pattern.length() >= 2 && pattern.charAt(1) == '*') {
return (isMatch(text, pattern.substring(2)) ||
(first_match && isMatch(text.substring(1), pattern)));
} else {
return first_match && isMatch(text.substring(1), pattern.substring(1));
}
}

算法分析:用 TP 分别表示匹配串和模式串的长度

  • 时间复杂度:O( (T + P)2T + P / 2 )
  • 空间复杂度:O( (T + P)2T + P / 2 )

动态规划

题目拥有 最优子结构optimal substructure

最优化原理:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略,即一个最优化策略的子策略总是最优的
一个问题满足最优化原理又称其具有最优子结构性质

思路:

  • 在题目拥有最优子结构的前提下,可以将中间结果保存起来
  • 通过用dp[i,j] 表示text[i:]pattern[j:] 是否能匹配
  • 这样就可以用更短的字符串匹配问题来表示原本的问题

这里利用上述的回溯方法。除此之外,因为函数 isMatch(text[i:], pattern[j:]) 只会被调用一次,我们用dp(i, j)来应对剩余相同参数的函数调用,这样可以节省字符串建立操作所需要的时间,也让我们可以将中间结果进行保存

自顶向下代码

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
enum Result {
TRUE, FALSE
}

Result[][] memo;

public boolean isMatch(String text, String pattern) {
memo = new Result[text.length() + 1][pattern.length() + 1];
return dp(0, 0, text, pattern);
}

public boolean dp(int i, int j, String text, String pattern) {
if (memo[i][j] != null) {
return memo[i][j] == Result.TRUE;
}
boolean ans;
if (j == pattern.length()) {
ans = i == text.length();
} else {
boolean first_match = (i < text.length() &&
(pattern.charAt(j) == text.charAt(i) ||
pattern.charAt(j) == '.'));

if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') {
ans = (dp(i, j+2, text, pattern) ||
first_match && dp(i+1, j, text, pattern));
} else {
ans = first_match && dp(i+1, j+1, text, pattern);
}
}
memo[i][j] = ans ? Result.TRUE : Result.FALSE;
return ans;
}

自底向上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean isMatch(String text, String pattern) {
boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
dp[text.length()][pattern.length()] = true;

for (int i = text.length(); i >= 0; i--){
for (int j = pattern.length() - 1; j >= 0; j--) {
boolean first_match = (i < text.length() &&
(pattern.charAt(j) == text.charAt(i) ||
pattern.charAt(j) == '.'));
if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') {
dp[i][j] = dp[i][j + 2] || first_match && dp[i + 1][j];
} else {
dp[i][j] = first_match && dp[i + 1][j + 1];
}
}
}
return dp[0][0];
}

算法分析:用 TP 分别表示匹配串和模式串的长度

  • 时间复杂度:O(T * P)
  • 空间复杂度:O(T * P)

11.盛最多水的容器(双指针法✓)

题目

给定 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

题解

暴力法

暴力枚举所有组合的矩形面积,然后找出其中的最大值

1
2
3
4
5
6
7
8
9
10
11
public static int maxArea(int[] height) {
int len = height.length;
int area = 0;
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
int tempArea = (j - i) * Math.min(height[i], height[j]);
area = Math.max(area, tempArea);
}
}
return area;
}

算法分析:

  • 时间复杂度:O(n2)
  • 空间复杂度:O(1)

优化解:双指针法

首先我们需要知道:

  • 两线段之间形成的区域总是会受到其中较短那条长度的限制
  • 两线段距离越远,得到的面积就越大

设置两个指针来索引数组height

  • 左指针:l = 0
  • 右指针:r = height.length - 1

l < r时,不断计算当前两条线段构成的最大面积,并更新最大面积maxarea

接着移动线段较短的索引的指针(为何?列举情况如下)

首先,不管移动哪一个,两指针之间的间距都-1
不妨设指针间距为矩形长,高度为宽
移动长的,由于短的线段高度不变,移动后新矩形长变短,面积必减少
移动短的,新矩形的长虽变短,但宽可能增大,面积也可能变大,故移动短的

所以,每次向内移动短的高度索引,消去的可能面积都不会包含面积的最大值

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int maxArea(int[] height) {
int maxarea = 0;
int l = 0, r = height.length - 1;
while (l < r) {
maxarea = Math.max(maxarea, Math.min(height[l], height[r]) * (r - l));
if (height[l] < height[r]) {
l++;
}
else {
r--;
}
}
return maxarea;
}

算法分析:

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)