0%

LeetCode算法经典题集(三)

标注

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

32.最长有效括号(动态规划)

题目

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

示例 1:

输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”

示例 2:

输入: “)()())”
输出: 4
解释: 最长有效括号子串为 “()()”

题解

暴力法

遍历字符串,若是遇到左括号'('就进入另一层循环while,开始计算最大长度

这里设置两个参数来统计左右括号数量

left:左括号数目
right:右括号数目

每当left == right时,尝试更新最大长度

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
public int longestValidParentheses(String s) {
int len = s.length();
if (len == 0) {
return 0;
}
int ans = 0;
for (int i = 0; i < len; i++) {
if (s.charAt(i) == '(') {
int index = i + 1;
int left = 1;
int right = 0;
while (index < len) {
if (s.charAt(index) == '(') {
left++;
} else {
right++;
}
if (right > left) {
break;
}
if (left == right) {
ans = Math.max(ans, left * 2);
}
index++;
}
}
}
return ans;
}

算法分析:

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

动态规划

首先,定义一个dp[]数组,其中第 dp[i] 个元素表示以下标i为结尾的最长有效子串的长度

dp[]数组全部初始化为0

很明显,有效子串的结尾一定是右括号')'

这就可以推出:以左括号'('结尾的子串对应的dp[i] = 0

所以我们只需要更新右括号')'在数组dp[]中对应位置的值

接下来需要找出dp[i]的递推式

  1. s[i] == ')'s[i - 1] == '(',即子串形如"...()"
    dp[i] = 2 + dp[i - 2]
  2. s[i] == ')'s[i - 1] == ')',即子串形如"...))",可以得出
    • 如果满足s[i - 1 - dp[i - 1]] == '('
    • 那么有dp[i] = 2 + dp[i - 1] + dp[i - 2 - dp[i - 1]]

这里用图片解释一下第二点,一目了然

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int longestValidParentheses(String s) {
int maxans = 0;
int dp[] = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
// 情况 1
if (s.charAt(i - 1) == '(') {
// 防止越界
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
// 情况 2
dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
}
maxLen = Math.max(maxLen, dp[i]);
}
}
return maxLen;
}

算法分析:

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

针对该题,可以构造一个栈,在遍历给定字符串的过程中去判断到目前为止扫描的子字符串的有效性,首先将 −1 放入栈顶。

  • 对于遇到的每个'(',将它的下标放入栈中
  • 对于遇到的每个')',弹出栈顶的元素,并将当前元素的下标与弹出元素下标作差,得出当前有效括号字符串的长度

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int longestValidParentheses(String s) {
int maxans = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
// 这步比较巧妙,栈空时把对应右括号下标压栈
if (stack.empty()) {
stack.push(i);
} else {
maxans = Math.max(maxans, i - stack.peek());
}
}
}
return maxans;
}

一次遍历

该方法设置了两个计数器:leftright,然后分两步

  • 从左到右遍历字符串,对于遇到的每个左括号(,增加 left 计算器,对于遇到的每个右括号),我们增加 right 计数器。每当 left 计数器与 right 计数器相等时,计算当前有效字符串的长度,并且记录目前为止找到的最长子字符串。如果 right 计数器比 left 计数器大时,我们将 leftright 计数器同时变回 0
  • 再重置计数器,从右到左做类似操作

简单解释一下为什么要反方向做类似操作

整个括号串中,要么只多余左括号,要么只多余右括号

((())为例,从左向右统计

left = 3
right = 2
maxLen = 0

而从右向左的话

right = 2
left = 3
maxLen = 2

就不会遗漏情况,下面是代码

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
public int longestValidParentheses(String s) {
int left = 0, right = 0, maxlength = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = Math.max(maxlength, 2 * right);
} else if (right >= left) {
left = right = 0;
}
}
left = right = 0;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = Math.max(maxlength, 2 * left);
} else if (left >= right) {
left = right = 0;
}
}
return maxlength;
}

算法分析:

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

33.搜索旋转排序数组(二分查找)

题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

题解

这题就是普通的搜索,但是要求算法时间复杂度必须是 O(log2n)

这很明显是要用二分查找法降低复杂度,但显然常规的二分查找法是不行的,这里就需要先用二分法找到旋转中心

代码如下

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
* 找出数组的旋转点的坐标
*/
private int findRotateIndex(int[] nums, int left, int right) {
// 最左边的元素小于最右边的元素,说明数组没有被旋转过
if (nums[left] < nums[right]) {
return 0;
}
while (left <= right) {
int pivot = (left + right) / 2;
// 说明找到旋转点了
if (nums[pivot] > nums[pivot + 1]) {
return pivot + 1;
} else {
if (nums[pivot] < nums[left]) {
right = pivot - 1;
} else {
left = pivot + 1;
}
}
}
return 0;
}

/**
* 常规的二分查找
*/
private int search(int nums[], int target, int left, int right) {
while (left <= right) {
int pivot = (left + right) / 2;
if (nums[pivot] == target) {
return pivot;
} else {
if (target < nums[pivot]) {
right = pivot - 1;
} else {
left = pivot + 1;
}
}
}
return -1;
}

public int search(int[] nums, int target) {
int n = nums.length;
if (n == 0) {
return -1;
}
if (n == 1) {
return nums[0] == target ? 0 : -1;
}

int rotateIndex = findRotateIndex(nums, 0, n - 1);

// target 恰好是旋转点
if (nums[rotateIndex] == target) {
return rotateIndex;
}
// 数组没有旋转过
if (rotateIndex == 0) {
return search(nums, target, 0, n - 1);
}
// 目标值小于第一位的值,就应该查找右部分
if (target < nums[0]) {
return search(nums, target, rotateIndex, n - 1);
}
// 查找左部分
return search(nums, target, 0, rotateIndex);
}

算法分析:

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

34.在排序数组中查找元素的第一个和最后一个位置(二分查找)

题目

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值,返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

题解

循环二分查找

这是我自己的做法,在题库上运行时间击败了100%的用户(😉)

先写一个常规的二分查找函数search

接着初次查找pivot,如果返回-1,直接return

设置两个标识startend

start = end = pivot

然后,分两部分查找

startend分别作为接下来查找的右、左边界

  • 对左部分右边界start递减进行二分查找
  • 对右部分左边界end递增进行二分查找

完整代码如下

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
private int search(int nums[], int target, int left, int right) {
while (left <= right) {
int pivot = (left + right) / 2;
if (nums[pivot] == target) {
return pivot;
} else if (nums[pivot] < target) {
left = pivot + 1;
} else {
right = pivot - 1;
}
}
return -1;
}

public int[] searchRange(int[] nums, int target) {
int[] result = {-1, -1};
if (nums.length == 0) {
return result;
}
int left = 0;
int right = nums.length - 1;
int pivot = search(nums, target, left, right);
if (pivot == -1) {
return result;
}
int start, end;
start = end = pivot;
while (true) {
start = search(nums, target, left, start);
if (start == -1) {
break;
}
result[0] = start;
start--;
}
while (true) {
end = search(nums, target, end, right);
if (end == -1) {
break;
}
result[1] = end;
end++;
}
return result;
}

算法分析:

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

官方答案

参考链接:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-yi-/

代码详解见链接

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
class Solution {
// returns leftmost (or rightmost) index at which `target` should be
// inserted in sorted array `nums` via binary search.
private int extremeInsertionIndex(int[] nums, int target, boolean left) {
int lo = 0;
int hi = nums.length;

while (lo < hi) {
int mid = (lo + hi) / 2;
if (nums[mid] > target || (left && target == nums[mid])) {
hi = mid;
}
else {
lo = mid+1;
}
}

return lo;
}

public int[] searchRange(int[] nums, int target) {
int[] targetRange = {-1, -1};

int leftIdx = extremeInsertionIndex(nums, target, true);

// assert that `leftIdx` is within the array bounds and that `target`
// is actually in `nums`.
if (leftIdx == nums.length || nums[leftIdx] != target) {
return targetRange;
}

targetRange[0] = leftIdx;
targetRange[1] = extremeInsertionIndex(nums, target, false)-1;

return targetRange;
}
}

算法分析:

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

36.有效的数独(位运算)

题目

判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

题解

一次迭代

代码如下

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
public boolean isValidSudoku(char[][] board) {
// init data
HashMap<Integer, Integer>[] rows = new HashMap[9];
HashMap<Integer, Integer>[] columns = new HashMap[9];
HashMap<Integer, Integer>[] boxes = new HashMap[9];
for (int i = 0; i < 9; i++) {
rows[i] = new HashMap<Integer, Integer>();
columns[i] = new HashMap<Integer, Integer>();
boxes[i] = new HashMap<Integer, Integer>();
}
// validate a board
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char num = board[i][j];
if (num != '.') {
int n = (int)num;
int box_index = (i / 3 ) * 3 + j / 3;
// keep the current cell value
rows[i].put(n, rows[i].getOrDefault(n, 0) + 1);
columns[j].put(n, columns[j].getOrDefault(n, 0) + 1);
boxes[box_index].put(n, boxes[box_index].getOrDefault(n, 0) + 1);
// check if this value has been already seen before
if (rows[i].get(n) > 1 || columns[j].get(n) > 1 || boxes[box_index].get(n) > 1) {
return false;
}
}
}
}
return true;
}

算法分析:

  • 时间复杂度:O(92)
  • 空间复杂度:O(9 * 3)

通过位运算判重(✔)

思路

为了省空间,我们只设置一个int型数组store[]来存放遍历的结果

假设遍历索引为for_ifor_j,那么board[i][j]可以对应三个内容

  1. i行的元素
  2. j列的元素
  3. i / 3 * 3 + j / 3个九宫格的元素

解释一下第 3 点

如图,很清楚大九宫格被分为了 0 ~ 8 八个区域
由于iint型的,所以i / 3只有0、1、2三个取值
i / 3 * 3就对应了0、3、6三个区域
再加上j / 3,即精确到了各个小九宫格

在存储时,先定义一个变量value

int型整数是32位的,我们取其后27位来存放元素

  1. 末尾9位存放每个元素的行号
  2. 中间9位存放每个元素的列号
  3. 首部9位存放每个元素对应的九宫格的序号

这里是通过1 << x来实现位存储的
代表1的二进制01向前移动x
比如1 << 2结果为4,因为01变成了0100

然后得出的value与对应的store[index]相与,相与结果为0,说明没有重复过

简单提一下与&操作,以615为例

6的二进制为0110
15的二进制为1111

首先需要知道

  • 1 & 1 = 1
  • 1 & 0 = 0

从而6 & 15 就相当于 0110 & 1111 = 0110

0 1 1 0
& 1 1 1 1
result 0 1 1 0

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean isValidSudoku(char[][] board) {
int[] store = new int[9];
for (int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
if(board[i][j] != '.') {
// board[i][j] - '1' 保证索引范围在 0 ~ 8 不会越界
int index = board[i][j] - '1';
// 通过位运算存储数值
int value = (1 << i) // 末尾九位存放行号
| (1 << (j + 9)) // 中间九位存放列号
| (1 << (i / 3 * 3 + j / 3 + 18)); // 首部九位存放九宫格序号
int pre = store[index];
// 两者相与若为0,说明结果没有重复过
if ((pre & value) == 0) {
store[index] = pre | value;
} else { // 不为 0 则说明重复了
return false;
}
}
}
}
return true;
}

算法分析:

  • 时间复杂度:O(91)
  • 空间复杂度:O(9)

37.解数独(回溯法)

题目

编写一个程序,通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则:

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

题解

最初的想法便是暴力法,暴力生成所有可能填满空白格,然后筛选出有效的,但是,这种操作时间复杂度巨高无比,一共 981 种可能,不太现实的解法,所以需要对其优化,很显然,回溯法可以处理掉很多赘余操作

讲回溯法之前,提两个小概念

  1. 约束编程(Constraint programming)

    是一种编程典范,在这种编程范式中,变量之间的‘关系’是以约束的形式陈述(组织)的。这些‘关系(约束)’和命令式编程语言元素不同的是:它们并非明确说明了要去执行的步骤中的某一步,而是规范其解的一些属性。这样看来,约束编程是一种声明式的编程范式 // 摘录自百度百科

    针对这题,基本的意思是在放置每个数字时都设置约束,在数独上放置一个数字后立即排除当前 子方块 对该数字的使用。这会传播 约束条件 并有利于减少需要考虑组合的个数

  2. 回溯

    回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标 // 摘录自百度百科

    针对该题,假设已经在空格种放置了几个数字,当当前组合不是最优的并且不能继续放置数字了,就回溯到上一步,改变之前放置的数字并继续尝试,如果还不行,就再次回溯

上一题提过了枚举子方块索引的式子

index = 行 / 3 * 3 + 列 / 3
/代表整除

接下来理一下思路

  1. 设置一个数组store[]来存放原有元素
  2. 先遍历大九宫格,存放原有元素到数组store[]
  3. 接着进入回溯算法backtrace,从19迭代,尝试把数字存入大九宫格,方法:placeNumber
    • 如果存入成功,那么存下一格placeNextNumber
    • 如果失败,换一个数字继续尝试
  4. 当其中某种尝试达到了大九宫格末尾结束了,即得出结果

代码如下

在官方题解的基础上优化了空间复杂度,也做了其他小修改

官方题解链接

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
char[][] board;
int N = 9;
int[] store = new int[N];
boolean solved = false;

private void removeNumber(int index, int row, int col) {
int value = (1 << row)
| (1 << (col + 9))
| (1 << (row / 3 * 3 + col / 3 + 18));
store[index] ^= value;
board[row][col] = '.';
}

private void placeNextNumber(int row, int col) {
if ((row == N - 1) && (col == N - 1)) {
solved = true;
} else if (col == N - 1) {
backtrack(row + 1, 0);
} else {
backtrack(row, col + 1);
}
}

private boolean placeNumber(int index, int row, int col) {
int value = (1 << row) // 末尾九位存放行号
| (1 << (col + 9)) // 中间九位存放列号
| (1 << (row / 3 * 3 + col / 3 + 18)); // 首部九位存放九宫格序号
int pre = store[index];
if ((pre & value) != 0) {
return false;
}
store[index] = pre | value;
board[row][col] = (char)(index + '1');
return true;
}

private void backtrack(int row, int col) {
if (board[row][col] == '.') {
for (int index = 0; index < N; index++) {
if (placeNumber(index, row, col)) {
placeNextNumber(row, col);
if (!solved) {
removeNumber(index, row, col);
}
}
}
} else {
placeNextNumber(row, col);
}
}

public void solveSudoku(char[][] board) {
this.board = board;
// 首先记录一下已填数字
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
char e = board[i][j];
if (e != '.') {
int index = e - '1';
// 这里肯定不会重复,忽略返回值
placeNumber(index, i, j);
}
}
}
backtrack(0, 0);
}
}

算法分析:

  • 时间复杂度:O( (9!)9 )
  • 空间复杂度:O(9)