LeetCode Hot 100 刷题 [11-20]
2023-07-15 17:48:48
LeetCode Hot 100 [11-20]
刷完了《剑指Offer》,下一阶段,开始 LeetCode Hot 100。 之前一直都用思维导图记录,今天发现思维导图可以导出成markdown,简单编辑一下就可以成为文章。相比Xmind,博客文章打开和查看更加方便,所以之后每次Xmind记录之后,会再在这里同时同步一下
前言
HOT100,之前的文章传送门
LeetCode Hot 100 刷题 [1-10]
11. 合并两个有序链表
题目
- 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
- 输入:1->2->4, 1->3->4
- 输出:1->1->2->3->4->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/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode tempHead = new ListNode(1);
ListNode curr = tempHead;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
curr.next = l1;
l1 = l1.next;
}else{
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
if(l1 == null){
curr.next = l2;
}else {
curr.next = l1;
}
return tempHead.next;
}
}复杂度
- 时间复杂度O(M+N)
递归实现
思路与过程
- 将两个链表合并的过程看作,
- 先选出一个较小头节点
- 再对剩余节点进行合并,结果赋值给较小节点的next
- 当l1头节点较小时,l1.next = recur(l1.next, l2)
- 当l2头节点较小时,l2.next = recur(l1,l2.next)
- 将两个链表合并的过程看作,
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next,l2);
return l1;
}else{
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
}复杂度
- 时间复杂度O(M+N)
- 空间复杂度O(M+N)
12.括号生成
题目
- 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
- 输入:n = 3
- 输出:
1
2
3
4
5
6
7[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
] - 题目地址
解题思路
思路一:排列组合问题
- 属于括号的排列组合, 但不是所有的排列都满足要求
- 通过DFS实现排列组合的遍历过程
- 回溯:试过左括号之后,再尝试右括号,需要回溯之前的变更
- 剪枝:当肯定不满足时,剪枝
- 当右括号数目大于左括号数目,则必不行
- 判定括号是否匹配
- balance
- 左括号+1
- 右括号-1
- 遍历字符串过程中,balance必须大于等于0, 出现小于0,则不匹配
- 且最终balance=0, 才能保障括号匹配
- 代码实现
1 | class Solution { |
- 复杂度
- 时间复杂度O(2^N)
- 空间复杂度O(2^N)
思路二:动态规划问题
13.合并k个有序链表
题目
- 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
- 输入:
1
2
3
4
5[
1->4->5,
1->3->4,
2->6
] - 输出:
1->1->2->3->4->4->5->6
- 题目地址
解题思路
思路1:归并合并
k个有序链表,两两组合,进行合并
在对合并后的两个链表,再此进行两两合并,得到最终的结果
代码实现
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/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int index = 0;
int len = lists.length;
while (len > 1){
for (int i = 0; i < len; i++) {
int pos = 2 * i;
if(pos+1 < len){
lists[index] = mergeTwoLists(lists[pos],lists[pos+1]);
index++;
}else if(pos < len){
lists[index] = lists[pos];
index++;
break;
}
}
len = index;
index=0;
}
return lists.length==0?null : lists[0];
}
// 21题中的两两合并
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode tempHead = new ListNode(1);
ListNode curr = tempHead;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
if (l1 == null) {
curr.next = l2;
} else {
curr.next = l1;
}
return tempHead.next;
}
}复杂度
- 时间复杂度O(kNlogK)
思路2: 优先级队列
和合并两个有序链表相比,不同的地方
- 两个链表中选择最小的头节点
- k个链表中选择最小的头节点
k个中选最小,可以通过最小堆来实现PriorityQueue
- 需要提供Comparator
- int compare(o1, o2)
- o1 - o2 < 0 则o1优先级更高
代码实现
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/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode result = new ListNode(1);
ListNode curr = result;
PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(new Comparator<ListNode>() {
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
});
for (int i = 0; i < lists.length; i++) {
if(lists[i] != null){
queue.add(lists[i]);
}
}
while (!queue.isEmpty()){
ListNode node = queue.poll();
if(node.next != null){
queue.add(node.next);
}
node.next=null;
curr.next=node;
curr = curr.next;
}
return result.next;
}
}复杂度
- 时间复杂度 O(kNlogk)
- 空间复杂度O(k)
14.下一个排列
题目
- 实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
- 如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
- 必须原地修改,只允许使用额外常数空间。
- 以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
1
2
31,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1 - 题目地址
解题思路
这道题需要观察总结排列数生成中的过程和规律,然后编码实现该过程
基础原理就是将第一个大于其前一个的数换到前边,得到稍大于当前排列的值
思路与过程
- 从右向左遍历排列,找到第一个山峰(即由递增转递减)
- 如果该元素为最左边元素,则直接对整个数组进行排序即可
- 如果该元素为最右边元素,则将该元素与倒数第二个元素交换即可
- 其他,则走一下步骤
- 查找到山峰索引为pos,接下来需要从[pos,end]区间中选择一个合适的元素,与 pos-1 位置的交换,(即,选出新的较大的前者)
- 该元素首先必须要比 pos-1 位置的要大,满足字典增序的要求
- 该元素为[ pos, end ] 区间中满足上输条件的最小值,即最接近 pos-1 的值
- 将新元素和 pos-1 交换之后,对 [ pos-1 , 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
37class Solution {
public void nextPermutation(int[] nums) {
if(nums.length <= 1) return;
// 从右向左,第一个增序变减序
int pos = nums.length-1;
while(pos > 0){
if(nums[pos] > nums[pos-1]){
break;
}
pos--;
}
if(pos == 0) {
Arrays.sort(nums);
return;
}
if(pos == nums.length-1) {
swap(nums,pos,pos-1);
return;
}
// 从pos之后选择大于其前边数字的最小数
int selectIndex = pos;
for(int i = pos+1; i < nums.length; i++){
if(nums[i] > nums[pos-1] && nums[i] < nums[selectIndex]){
selectIndex = i;
}
}
swap(nums,selectIndex,pos-1);
Arrays.sort(nums,pos,nums.length);
return;
}
private void swap(int [] nums, int aIndex, int bIndex){
int temp = nums[aIndex];
nums[aIndex] = nums[bIndex];
nums[bIndex] = temp;
}
}复杂度分析
- 时间复杂度:O(NlogN)
15. 最长有有效括号
题目
- 给定一个只包含 ‘(‘ 和 ‘)’ 的字符串,找出最长的包含有效括号的子串的长度。
- 输入: “(()”
- 输出: 2
- 解释: 最长有效括号子串为 “()”
- 题目地址
解题思路
思路0. 如何判断括号串是否有效
- balance变量
- 左括号,balance++
- 右括号,balance–
- 遍历过程中,如果balance出现 < 0,则必不是有效的
- 遍历结束,只有当balance=0,才说明是有效的
思路1. 左右指针遍历
思路与过程
- 先从左向右遍历,统计balance
- left、right初始均为0
- 如果balance == 0,则计算一次length,更新maxLength
- 如果balance < 0,则 left和right直接跳到下一个字符重新统计
- 再从右向左遍历,统计balance
- 因为遍历时候,只有当balance==0的时候,才会统计length
- 如果遍历结束,最终balance一直维持在 > 0,则不会被统计lenth
- 但,balance > 0 不代表没有有效括号,只是很多的左括号没有右括号来匹配它就结束了
- 所以需要再从右向左遍历一次,判断过程和从左向右恰好相反
- 先从左向右遍历,统计balance
代码实现
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
40public int longestValidParentheses(String s) {
int maxLength = 0;
int left = 0, right =0;
int balance = 0;
while(right < s.length()){
if(s.charAt(right) == '('){
balance++;
}else {
balance--;
if(balance== 0){
int length = right - left + 1;
maxLength = Math.max(maxLength,length);
}else if(balance < 0){
left = right+1;
balance=0;
}
}
right++;
}
// 逆序再来一次
left = s.length() -1;
right = left;
balance = 0;
while(left >= 0 ){
if(s.charAt(left) == ')'){
balance++;
}else {
balance--;
if(balance== 0){
int length = right - left + 1;
maxLength = Math.max(maxLength,length);
}else if(balance < 0){
right = left - 1;
balance=0;
}
}
left--;
}
return maxLength;
}
思路2. 动态规划
dp[ i ] 表示以 i 为结尾的最长有效括号的长度
递推方程:dp[ i ] =
- 0
- 当s[ i ] == ‘ ( ‘,以左括号结尾,长度肯定为0
- dp[ i-2 ] + 2
- 以 ‘ ) ‘ 结尾,且,前一个括号为 ‘ ( ‘
- 在原有长度上,续上2
- 其实这种场景下,dp[ i-1 ] 必定为0
- dp[ i-1 ] + 2 + dp[ i - dp[i-1] + 1 ]
- 以 )结尾,且前一个括号为)
- 跳过dp[ i-1 ]对应子串的长度,查看该子串的前一个字符是否是 (,如果是,则可以和目前的)匹配
- 匹配,则+2
- 同时,匹配后,可能将(前边的子串能连续起来,所以,再加上 ( 前边位置的子串长度,即+dp[ i - dp[i-1] + 1 ]
- 0
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public int longestValidParentheses(String s) {
int [] dp = new int[s.length()];
//dp[i] 表示以下标 ii 字符结尾的最长有效括号的长度
int maxLength = 0;
for(int i = 1; i< s.length(); i++){
if(s.charAt(i) == ')' && s.charAt(i-1) == ')'){
int len = dp[i-1];
int pre = i - len - 1; // 前一个待匹配的左括号
if( pre < 0) continue;
if(s.charAt( pre ) == '('){
int preDP = pre == 0? 0: dp[pre-1];
dp[i] = dp[i-1] + 2 + preDP;
}
}else if(s.charAt(i) == ')' && s.charAt(i-1) == '('){
dp[i] = i==1 ? 2: dp[i-2] + 2;
}
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength;
}复杂度分析
- 时间复杂度O(N)
- 空间复杂度O(N)
思路3. 栈实现
栈中存储的元素为读取到的括号所对应的索引下标
思路与过程
- 用栈来记录左右符号的匹配过程
- 过程
- 如果读取到左括号,则将该左括号的索引入栈
- 如果读取到右括号,则弹出栈顶元素与其进行匹配
- 同时计算已经匹配的子串的长度
- length = 右括号索引 - 前一个左括号索引
- 前一个左括号索引,即栈中左括号的下一个元素
- 在生成length过程中,记录最大值即可
- 当读取到右括号,且栈为空,将右括号索引入栈
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public int longestValidParentheses(String s) {
// 用栈来实现
Stack<Integer> stack = new Stack();
stack.push(-1);
int maxLength = 0;
for(int i = 0; i<s.length(); i++ ){
if(s.charAt(i) == '('){
stack.push(i);
}else{
if(!stack.isEmpty()){
stack.pop();
if(!stack.isEmpty()){
int pos = stack.peek();
int length = i - pos;
maxLength = Math.max(maxLength, length);
}else{
stack.push(i);
}
}
}
}
return maxLength;
}复杂度分析
- 时间复杂度O(N)
- 空间复杂度O(N)
16. 搜索旋转排序数组
题目
- 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
- ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
- 搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。
- 你可以假设数组中不存在重复的元素。
- 你的算法时间复杂度必须是 O(log n) 级别。
- 输入: nums = [4,5,6,7,0,1,2], target = 0
- 输出: 4
- 题目地址
解题思路
- 排序数组、O(logN):显而易见,基于二分查找解题
- 查找元素,所以基于模板一
- 旋转数组,需要额外考虑旋转点的位置
1.思路与过程
- 如果 mid 位置等于 target,直接返回 mid
- 如果 mid 位置大于 target
- 正常情况下,接下来应该选择左侧区间
- 考虑选择右边区间的情况
- target元素被包含在较小段,并被旋转到了数组右边了
- 两种情况
- 旋转点在mid右侧
- 只有这种情况下,才是向右搜索
- 判断条件
- nums[ left ] <= nums[ mid ]
- 左边是单调递增的
- 说明旋转点在右区间
- 需要包括等于的情况,否则会死循环
- 没有左区间的时候,向右搜索,避免进入死循环
- 因为mid向下取整,当区间长度为2的时候,left == mid
- nums[left] > target
- 左边最小比target大
- 说明更小的被旋转到右边了
- 左边最小比target大
- nums[ left ] <= nums[ mid ]
- 旋转点在mid左侧
- 还是向左搜索,所以只要排除上一种情况即可
- 旋转点在mid右侧
- 如果 mid 位置小于 target
- 正常情况下,接下来应该选择右侧区间
- 考虑选择左侧区间的情况,即,旋转点位于mid左侧,target在左侧的大值区间中
- 判断条件
- nums[ right ] > nums [ mid ]
- 右侧区间是单调的,说明旋转点在mid或者mid左侧
- nums[ right ] < target
- 右侧的最大值比target小,所以右侧肯定搜索不到
- nums[ right ] > nums [ mid ]
- 搜索左侧
- right = mid - 1
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public int search(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right-left )/2;
if(nums[mid] == target){
return mid;
}else if(nums[mid] < target){
if(nums[mid] < nums[left] && nums[right] < target){
right = mid -1;
}else{
left = mid+1;
}
}else{
if(nums[mid] >= nums[left] && nums[left] > target){
left = mid+1;
}else{
right = mid -1;
}
}
}
return -1;
} - 时间复杂度O(logN)
17.在排序数组中查找元素的第一个和最后一个
题目
- 给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
- 你的算法时间复杂度必须是 O(log n) 级别。
- 如果数组中不存在目标值,返回 [-1, -1]。
- 题目地址
解题思路
- 最最典型的二分查找模板二的用法
- 找第一个: 即查找大于等于target元素的下标
- 即排除小于target的
- 找最后一个:即查找小于等于target元的的下标
- 即排除大于target的
- 代码实现
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// 找第一个大于等于
private int findLowBound(int[] nums, int target){
int left = 0, right = nums.length-1;
while (left<right){
int mid = left + (right-left) / 2;
if(nums[mid] < target){
left = mid + 1;
}else {
right = mid;
}
}
return nums[left] != target? -1:left;
}
// 第一个小于等于
private int findUpBound(int [] nums,int target){
int left = 0, right = nums.length-1;
while (left<right){
int mid = left + (right-left+1) / 2;
if(nums[mid] > target){
right = mid - 1;
}else {
left = mid;
}
}
return nums[left] != target? -1:left;
}
18.组合总和
题目
- 给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
- 所有数字(包括 target)都是正整数。
- candidates 中的数字可以无限制重复被选取。
- 解集不能包含重复的组合。
- 输入:candidates = [2,3,6,7], target = 7,
- 所求解集为:
[
[7],
[2,2,3]
]
1 | - [题目地址](https://leetcode-cn.com/problems/combination-sum) |
- 复杂度分析
- 时间复杂度,O(N^k)
- 空间复杂度,O(1)
19.全排列
题目
- 给定一个 没有重复 数字的序列,返回其所有可能的全排列。
- 输入: [1,2,3]
- 输出:
1
2
3
4
5
6
7
8[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
] - 题目地址
解题思路
- 这是典型的全排列问题
思路一:DFS + 回溯+解决重复问题
思路过程
- path存储一次排列结果,path长度 == length时候,添加到结果列表中
- 每次排列从数组中选择一个数,并添加到path中
- 避免重复:添加之前,需要检查path中是否已经有该元素了
- 回溯刚才选择的元素,尝试添加下一个
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13private void dfs(int [] nums, List<Integer> path ){
if(path.size() == nums.length){
result.add(new ArrayList<>(path));
return;
}
for (int num:nums) {
if(!path.contains(num)){
path.add(num);
dfs(nums,path);
path.remove(path.size()-1);
}
}
}复杂度分析
- 时间复杂度O(N! * N)
- 空间复杂度O(N!)
思路二:基于标记的回溯
- 通过一个标记数组来决定当前数是否被选择过,以此来解决重复问题
- 每次遍历选择一个没有被标记的元素
- 和思路一基本类似,只是通过一个标记数组来判断该元素是否使用过了
思路三:基于交换的回溯
- 空间复杂度最低,直接基于已有的数组
- 不过最终的排序结果不是按字典序排列的,如果需要,请使用思路一或者二
- index表示当前在尝试第几个位置的元素
- 代码实现
1
2
3
4
5
6
7
8
9
10
11private void dfs(int [] nums,int index ){
if(index == nums.length){
result.add(IntStream.of(nums).boxed().collect(Collectors.toList()));
return;
}
for(int i=index; i< nums.length; i++){
swap(nums,index,i);
dfs(nums,index+1);
swap(nums,index,i);
}
}
20.最大子序和
题目
- 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
- 输入: [-2,1,-3,4,-1,2,1,-5,4]
- 输出: 6
- 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
- 题目地址
解题思路
思路一:动态规划
- dp[ i ] 表示以 i 位置为结尾的数列的最大子序和
- dp[ i ] =
- num[ i ] ,当dp[ i-1 ] <= 0
- dp[ i-1 ] + nums[ i ] ,当dp[ i-1 ] > 0
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14public int maxSubArray(int[] nums) {
int [] dp = new int [nums.length];
dp[0] = nums[0];
int maxSum = dp[0];
for(int i = 1; i<nums.length; i++){
if(dp[i-1] > 0){
dp[i] = dp[i-1] + nums[i];
}else{
dp[i] = nums[i];
}
maxSum = Math.max(maxSum, dp[i]);
}
return maxSum;
}
思路二:分治算法,线段树
- 待定
下个路口见
HOT100依然在继续,写在下一篇文章中。传送门