力扣记录：Hot100（2）——20-42

20 有效的括号

• 之前做过，使用栈进行判断，遍历字符串，遇到左括号直接入栈，右括号则弹出栈顶元素并判断是否匹配，匹配则继续遍历否则返回false。遍历结束后如果栈内还有元素则返回false，否则返回true。可以定义一个HashMap存储括号对进行判断
  • 时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public boolean isValid(String s) {
        //定义栈进行判断
        Deque<Character> stack = new LinkedList<>();
        //遍历字符串
        for(int i = 0; i < s.length(); i++){
            //右括号则弹出栈顶元素并判断是否匹配，匹配则继续遍历否则返回false
            char c = s.charAt(i);
            if(c == ')'){
                if(!stack.isEmpty() && stack.pop() == '(') continue;
                return false;
            }else if(c == ']'){
                if(!stack.isEmpty() && stack.pop() == '[') continue;
                return false;
            }else if(c == '}'){
                if(!stack.isEmpty() && stack.pop() == '{') continue;
                return false;
            }else{//遇到左括号直接入栈
                stack.push(c);
            }
        }
        //最后返回true
        return stack.isEmpty();
    }
}
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

21 合并两个有序链表

• 双指针，参考剑指 Offer 25 合并两个排序的链表，首先将其中一个链表（较小的）设为起始链表，定义虚拟头节点和前一个节点，左右指针分别从两个链表头部出发，将前一个节点指向较小的指针，然后该指针移动，同时更新前一个节点。直到某一个链表结束，最后将不为空的链表直接接在后面前一个节点后
  • 时间复杂度O(m+n)，空间复杂度O(1)

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        //将list1设置为头节点值较小的链表，作为最后输出
        if(list1.val > list2.val){
            ListNode temp = list1;
            list1 = list2;
            list2 = temp;
        }
        //直接修改list1
        ListNode virtualHead = new ListNode(0, list1);
        ListNode pre = list1;   //初始化
        list1 = list1.next;  //已知list1较小
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                pre.next = list1;
                pre = list1;
                list1 = list1.next;
            }else{
                pre.next = list2;
                pre = list2;
                list2 = list2.next;
            }
        }
        //最后剩下list直接接到1后面
        if(list2 != null) pre.next = list2;
        if(list1 != null) pre.next = list1;
        return virtualHead.next;
    }
}
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

22 括号生成

• 回溯
  • 时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        StringBuilder sb = new StringBuilder();
        //回溯
        backtracking(result, sb, 0, 0, n);
        return result;
    }
    //回溯函数，输入结果数组，过程字符串，左括号个数，右括号个数，要求数量
    private void backtracking(List<String> result, StringBuilder sb, int left, int right, int n){
        //括号总数达到条件时返回
        if(sb.length() == n * 2){
            result.add(sb.toString());
            return;
        }
        //左括号数量不足先加左括号
        if(left < n){   
            sb.append('(');
            backtracking(result, sb, left + 1, right, n);  //递归
            sb.deleteCharAt(sb.length() - 1);   //回溯
        }
        //然后再加右括号，右括号数量不能大于左括号数量
        if(right < left){
            sb.append(')');
            backtracking(result, sb, left, right + 1, n);  //递归
            sb.deleteCharAt(sb.length() - 1);   //回溯
        }
    }
}
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

23 合并K个升序链表

• 参考上面21 合并两个有序链表，先选出最小的链表作为头，然后遍历数组与其他链表进行合并。
  • 时间复杂度O(n * (k^2)，空间复杂度O(1)

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        //从最小的链表开始修改
        ListNode list1 = null;
        int min = Integer.MAX_VALUE;
        int index = 0;
        for(int i = 0; i < lists.length; i++){
            ListNode list = lists[i];
            if(list != null && min > list.val){
                min = list.val;
                list1 = list;
                index = i;
            }
        }
        ListNode virtualHead = new ListNode(0, list1);  //虚拟头节点
        //两两交换
        for(int i = 0; i < lists.length; i++){
            //跳过最小的链表
            if(i == index) continue;
            //合并两个链表
            ListNode list2 = lists[i];
            list1 = mergeTwoLists(list1, list2);
        }
        return virtualHead.next;
    }
    //合并两个升序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        //将list1设置为头节点值较小的链表，作为最后输出
        if(list1.val > list2.val){
            ListNode temp = list1;
            list1 = list2;
            list2 = temp;
        }
        //直接修改list1
        ListNode virtualHead = new ListNode(0, list1);
        ListNode pre = list1;   //初始化
        list1 = list1.next;  //已知list1较小
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                pre.next = list1;
                pre = list1;
                list1 = list1.next;
            }else{
                pre.next = list2;
                pre = list2;
                list2 = list2.next;
            }
        }
        //最后剩下list直接接到1后面
        if(list2 != null) pre.next = list2;
        if(list1 != null) pre.next = list1;
        return virtualHead.next;
    }
}
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

• 优化：将链表两两合并，然后再将合并后的链表两两合并（二分），直到最后全部合并
  • 时间复杂度O(n * k * logk)，空间复杂度O(logk)

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        //递归二分
        return merge(lists, 0, lists.length - 1);
    }
    //将链表两两合并，然后再将合并后的链表两两合并（二分）
    //输入节点列表，左右区间（左闭右闭）
    private ListNode merge(ListNode[] lists, int left, int right){
        if(left > right) return null;   //列表无元素
        if(left == right) return lists[left];   //只有一个链表直接返回
        //递归二分
        int mid = left + (right - left) / 2;
        ListNode leftNode = merge(lists, left, mid);
        ListNode rightNode = merge(lists, mid + 1, right);
        return mergeTwoLists(leftNode, rightNode);  //两两合并
    }
    //合并两个升序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        //将list1设置为头节点值较小的链表，作为最后输出
        if(list1.val > list2.val){
            ListNode temp = list1;
            list1 = list2;
            list2 = temp;
        }
        //直接修改list1
        ListNode virtualHead = new ListNode(0, list1);
        ListNode pre = list1;   //初始化
        list1 = list1.next;  //已知list1较小
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                pre.next = list1;
                pre = list1;
                list1 = list1.next;
            }else{
                pre.next = list2;
                pre = list2;
                list2 = list2.next;
            }
        }
        //最后剩下list直接接到1后面
        if(list2 != null) pre.next = list2;
        if(list1 != null) pre.next = list1;
        return virtualHead.next;
    }
}
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

31 下一个排列

• 两次遍历，第一次从后往前遍历，找到当前数与后面最接近的较大数交换，第二次遍历，将交换后的数后面的数升序排列（本来已经是降序排列），可直接双指针反序。
  • 时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public void nextPermutation(int[] nums) {
        //两次遍历
        int leng = nums.length;
        //第一次从后往前遍历，找到当前数与后面最接近的较大数交换
        int indexNow = 0;   //当前数下标
        int index = 0;  //后面最接近较大数下标
        int changeNum = Integer.MAX_VALUE;
        for(int i = leng - 2; i >= 0; i--){
            indexNow = i;
            for(int j = leng - 1; j >= i + 1; j--){  //j也从后向前遍历，保证交换后i以后的序列降序
                if(nums[j] > nums[i] && nums[j] < changeNum){
                    index = j;
                    changeNum = nums[j];
                }
            }
            if(index != 0) break;   //找到后结束循环
        }
        //交换
        if(index != 0){
            int temp = nums[indexNow];
            nums[indexNow] = nums[index];
            nums[index] = temp;
        }else{
            indexNow = -1;
        }
        //第二次遍历，将交换后的数后面的数升序排列（本来已经是降序排列），可直接双指针反序
        int left = indexNow + 1;
        int right = leng - 1;
        while(left < right){
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            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
30
31
32
33
34
35
36
37
38

32 最长有效括号

• 使用栈，记录当前长度和最大长度，遍历字符串，若当前字符为左括号则将下标入栈，若为右括号进行判断，栈内若无元素，则将下标入栈；若有元素则弹出：弹出后不为空栈顶为上一个右括号下标，当前长度为当前下标减去栈顶元素同时更新最大长度；弹出后为空则当前为右括号，下标入栈。注意：最开始栈内初始化入栈-1，以便计算开头的括号长度。
  • 时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public int longestValidParentheses(String s) {
        //使用栈，记录当前长度和最大长度
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1); //初始化
        int maxLength = 0;
        int leng = 0;
        //遍历字符串
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '('){ //左括号直接入栈
                stack.push(i);
            }else{  //右括号进行判断
                if(stack.isEmpty()){    //栈内若无元素，则将下标入栈
                    stack.push(i);
                }else{  //若有元素则弹出，当前长度为当前下标减去栈顶元素同时更新最大长度
                    stack.pop();
                    if(!stack.isEmpty()){   //弹出后不为空栈顶为上一个右括号下标
                        leng = i - stack.peek();
                        maxLength = Math.max(leng, maxLength);
                    }else{  //弹出后为空则当前为右括号，下标入栈
                        stack.push(i);
                    }
                }
            }
        }
        return maxLength;
    }
}
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

• 贪心，从左往右遍历字符串，记录左括号和右括号的数量，如果左右括号数量相等时，计算当前长度并更新最大长度；如果右括号数量大于左括号数量时，左右括号计数归零；同样地，从右往左遍历字符串，记录左括号和右括号的数量，如果左右括号数量相等时，计算当前长度并更新最大长度；如果左括号数量大于右括号数量时，左右括号计数归零。
  • 时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public int longestValidParentheses(String s) {
        //贪心
        int maxLength = 0;
        //从左往右遍历字符串，记录左括号和右括号的数量
        int left = 0;
        int right = 0;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '('){
                left++;
            }else{
                right++;
            }
            if(left == right){  //如果左右括号数量相等时，计算当前长度并更新最大长度
                maxLength = Math.max(left + right, maxLength);
            }else if(right > left){ //如果右括号数量大于左括号数量时，左右括号计数归零
                left = 0;
                right = 0;
            }
        }
        //同样地，从右往左遍历字符串，记录左括号和右括号的数量
        left = 0;
        right = 0;
        for(int i = s.length() - 1; i >= 0; i--){
            if(s.charAt(i) == '('){
                left++;
            }else{
                right++;
            }
            if(left == right){  //如果左右括号数量相等时，计算当前长度并更新最大长度
                maxLength = Math.max(left + right, maxLength);
            }else if(left > right){ //如果左括号数量大于右括号数量时，左右括号计数归零
                left = 0;
                right = 0;
            }
        }
        return maxLength;
    }
}
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

33 搜索旋转排序数组

• 二分查找，取中点后先判断左边或右边有序，然后判断目标是否在有序范围内，若是则普通二分，否则继续在另一返回内进行搜索。注意边界值设置。
  • 时间复杂度O(logn)，空间复杂度O(1)

class Solution {
    public int search(int[] nums, int target) {
        //二分
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] <= nums[right]){   //右边有序
                if(target > nums[mid] && target <= nums[right]){//往有序部分二分，注意等于
                    left = mid + 1;
                }else if(target == nums[mid]){
                    return mid;
                }else{//往另一边继续搜索
                    right = mid - 1;
                }
            }else{  //左边有序
                if(target < nums[mid] && target >= nums[left]){//往有序部分二分，注意等于
                    right = mid - 1;
                }else if(target == nums[mid]){
                    return mid;
                }else{//往另一边继续搜索
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
}
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

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

• 之前做过，两次二分，第一次二分查找元素开始位置，第二次二分查找元素结束位置，可写为一个二分查找函数，注意返回值。
  • 时间复杂度O(logn)，空间复杂度O(1)

class Solution {
    public int[] searchRange(int[] nums, int target) {
        //两次二分
        int[] result = new int[]{-1, -1};
        //第一次二分查找元素开始位置
        result[0] = binarySearch(nums, target, true);
        if(result[0] == -1) return result;
        //第二次二分查找元素结束位置
        result[1] = binarySearch(nums, target, false);
        return result;
    }
    //二分查找，输入排序数组，目标值和查找开始(true)/结束(flase)
    private int binarySearch(int[] nums, int target, boolean flag){
        int left = 0;
        int right = nums.length - 1;
        int mid = -1;
        boolean find = false;   //判断是否找到
        while(left <= right){
            if(nums[left] > target || nums[right] < target) break;
            mid = left + (right - left) / 2;
            if(nums[mid] > target){
                right = mid - 1;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                find = true;
                if(flag){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }
        }
        if(!find) return -1;
        return mid;
    }
}
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

39 组合总和

• 回溯，之前做过，定义全局数组和全局二维数组存放结果和当前路径。从数组第0位开始，for循环遍历数组，递归时同样从当前位开始（可以重复）；当和等于目标值时，将结果保存到数组集合，然后返回，当和大于目标值时，直接返回。
• 注意：将路径添加到结果时需要新建列表对象（之后的遍历同样修该路径）。
  • 时间复杂度O(可行解长度之和)，空间复杂度O(target)

class Solution {
    List<List<Integer>> result;
    List<Integer> path;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //回溯
        result = new ArrayList<>();
        path = new ArrayList<>();
        backtracking(candidates, target, 0);
        return result;
    }
    //回溯函数
    private void backtracking(int[] candidates, int target, int start){
        //终止条件
        if(target < 0) return;
        if(target == 0){
            result.add(new ArrayList<>(path));  //注意：这里需要新建ArrayList对象
            return;
        }
        //遍历
        for(int j = start; j < candidates.length; j++){
            path.add(candidates[j]);
            backtracking(candidates, target - candidates[j], j);
            path.remove(path.size() - 1);   //回溯
        }
    }
}
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

42 接雨水

• 之前做过，双指针，遍历每一列，分别找出当前列左右两边的最高列（比当前列高）的较小值，雨水量为该值-当前列高度。
  • 时间复杂度O(n^2)，空间复杂度O(1)

class Solution {
    public int trap(int[] height) {
        //双指针
        int sum = 0;
        for(int i = 1; i < height.length - 1; i++){
            int left = height[i];
            int right = height[i];
            //分别找出当前列左右两边的最高列
            for(int j = i - 1; j >= 0; j--){
                left = Math.max(left, height[j]);
            }
            for(int k = i + 1; k < height.length; k++){
                right = Math.max(right, height[k]);
            }
            //雨水量为较小值-当前列高度
            sum += Math.min(left, right) - height[i];
        }
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 单调栈，存储下标，栈头对应的值最小，按行计算，如果当前元素高度小于栈头元素高度，则直接入栈；如果当前元素高度大于栈头元素高度，则栈头位置可以接雨水，雨水量为（栈头下一个元素和当前元素高度的较小值减去栈头元素高度）*（当前下标-栈头下一个元素下标-1），计算结束后弹出栈头元素直到当前元素（大于当前元素或为空）入栈，否则弹出一个计算一次雨水量；如果当前元素高度和栈头元素高度相等，则替换栈头为当前元素。
  • 时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public int trap(int[] height) {
        //单调栈，存储下标，栈头对应的值最小，按行计算
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);  //初始化
        int sum = 0;
        for(int i = 1; i < height.length; i++){
            //如果当前元素高度小于栈头元素高度，则直接入栈
            if(height[stack.peek()] > height[i]){
                stack.push(i);
            }else if(height[stack.peek()] == height[i]){//如果当前元素高度和栈头元素高度相等，则替换栈头为当前元素。
                stack.pop();
                stack.push(i);
            }else{//如果当前元素高度大于栈头元素高度，则栈头位置可以接雨水
                //弹出一个计算一次雨水量
                while(!stack.isEmpty() && height[stack.peek()] < height[i]){
                    //雨水量为（栈头下一个元素和当前元素高度的较小值减去栈头元素高度）
                    //*（当前下标-栈头下一个元素下标-1）
                    int cur = stack.pop();
                    if(!stack.isEmpty()){
                        int h = Math.min(height[stack.peek()], height[i]) - height[cur];
                        int w = i - stack.peek() - 1;
                        int rain = h * w;
                        if(rain > 0) sum += rain;
                    }
                }
                //计算结束后弹出栈头元素直到当前元素（高度递增）入栈
                stack.push(i);
            }
        }
        return sum;
    }
}
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