七天算法训练营笔记

发表于 更新于 分类于 阅读次数：

数组

时间复杂度

操作 时间复杂度
查询 Lookup O(1)
插入 Insert O(n)
删除 Delete O(n)
前插 Prepend/Pushfront O(n)
后插 Append/Pushback O(1)

删除有序数组中的重复项

LC26题目链接

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public int removeDuplicates(int[] nums) {
        int cur = 0;
        for(int i = 1; i < nums.length; i++ ) {
            if(nums[i] != nums[cur]) nums[++cur] = nums[i];//如果当前nums[i]的值与已经存储的最后元素nums[cur]不等，则存入下一个位置, 第一个数肯定要
        }
        return cur+1;
    }
}

移动零

LC283题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public void moveZeroes(int[] nums) {
        int cur = 0;
        for(int i = 0; i < nums.length; i ++) {
            if(nums[i] != 0) nums[cur++] =  nums[i];
        }

        //补零
        while ( cur < nums.length ) {
            nums[cur] = 0;
            cur ++;
        }
    }
}

合并两个有序数组

LC88题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m -1, j = n -1, cur = m + n -1;
        while(i >= 0 || j >= 0) {
            if(j < 0 || (i >= 0 && nums1[i] >= nums2[j])){ // 在nums2已经越界或者i没越界且为大的时候，存入nums1[i]
                nums1[cur] = nums1[i];                
                i--;
            } else {
                nums1[cur] = nums2[j];
                j--;
            }
            cur--;
        }
    }
}

变长数组ArrayList设计题

如何实现一个变长数组？

  • 支持索引与随机访问
  • 分配多长的连续空间
  • 空间不够用了怎么办
  • 空间剩余很多如何回收

链表

单链表和双链表数据结构：

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

// 单链表
class MyLinkedListNode {
    int val;
    MyLinkedListNode next;
}

// 双链表
class MyDoubleLinkedListNode {
    int val;
    MyDoubleLinkedListNode next;
    MyDoubleLinkedListNode pre;
}


public static void main(String[] args) {
    // 具有保护节点的单链表 protect.next = head
    LinkedList protect = new LinkedList(0, null);

    // 

    // 具有保护节点组的双链表      
    LinkedList protectTail = new LinkedList(0, null);        
    LinkedList protectHead = new LinkedList(0, protectTail);
    protectTail.pre = proctedHead;
    protectedHead.pre = null;
}

时间复杂度

操作 时间复杂度
查询 Lookup O(n)
插入 Insert O(1)
删除 Delete O(1)
前插 Prepend/Pushfront O(1)
后插 Append/Pushback O(1)

反转链表问题

LC206题目链接

LC206

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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 reverseList(ListNode head) {
        ListNode last = null;
        while (head != null) {
            ListNode nextHead = head.next; // 缓存因为next会被修改
            head.next = last; // 跟新next指针
            last = head; //更新上一个节点为当前节点
            head = nextHead; // 更新当前节点 推进
        }

        return last;
    }
}

K个一组翻转链表

LC25题目链接

LC25

解题思路

  • 分组：每k个元素的头尾节点确定
  • 子问题：针对每一组k个元素的反转问题
  • 每组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
55
56
57
58
59
/**
 * 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 reverseKGroup(ListNode head, int k) {
    ListNode protect = new ListNode(0, head);
    ListNode last = protect;
    while(head != null) {
        // 1. 分组：每k个元素的头尾节点确定
        ListNode groupEnd = getEnd(head, k);
        if(groupEnd == null) break;
        // 分组遍历逻辑
        ListNode cacheNexthead = groupEnd.next; // 后继结点会被跟新需要先缓存
        
        
        // 2. 子问题：针对每一组k个元素的反转问题
        reverseList(head, cacheNexthead);

        // 3. 每组k个元素的指向前一组tail，后一组head引用更新问题        
        last.next = groupEnd; // 前一组最后应指向本组的最后即变化后的头节点
        head.next = cacheNexthead; // 本组的最后一个节点应该指向下一组的head

         // 更新组头尾节点
            last = head; // last 应该指向调转后的head，groupEnd已经是新的链表头
            head = cacheNexthead; // head 应该指向下一组头节点
        }

        return protect.next;
    }

    public ListNode getEnd(ListNode head, int k) {
        while (head != null) {
            k--;            
            if(k == 0) return head;
            head = head.next; // 走k-1次，返回groupEnd
        }
        // 返回End, 但是复用LC206算法需要last.next
        return head;
    }

    public void reverseList(ListNode head, ListNode nextHead) {
        // 第一步跳过，因为第一个head的next会在第三步更新
        ListNode last = head;
        head = head.next;
        while (head != nextHead) {
            ListNode cacheNextHead = head.next; // 缓存因为next会被修改
            head.next = last; // 跟新next指针
            last = head; //更新上一个节点为当前节点
            head = cacheNextHead; // 更新当前节点 推进
        }
    }
}

邻值查找/双链表问题

ACWing题目链接

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
70
71
72
73
74

import java.util.Arrays;
import java.util.Scanner;

// ACWing need a class called Main for solution
// and all the input/output logic
public class Main {

    public static void main(String args[]) {
        // input the array
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int i = 0;
        Node[] nums = new Node[size], sorted = new Node[size];
        int[] diff = new int[size-1], pre = new int[size-1];
        while(i < size){
            int number = sc.nextInt();
            Node node = new Node(number, i);
            nums[i] = node;
            sorted[i] = node;
            i++;
        }
        // sort and add pre/post information to build a linked list;
        Arrays.sort(sorted);
        for(int j = 0; j < sorted.length; j++){
            if(j > 0) sorted[j].pre = sorted[j-1]; else sorted[j].pre = new Node(Integer.MIN_VALUE, -1);
            if(j < nums.length -1) sorted[j].post = sorted[j+1]; else sorted[j].post = new Node(Integer.MAX_VALUE, size);
        }

        // start from last of array nums, calc it's pre/post diff via Linked List, and remove that node in linked list;
        while(i > 1){
            i--;
            int preDiff = nums[i].pre.index >= 0 && nums[i].pre.index < size ? nums[i].value - nums[i].pre.value : Integer.MAX_VALUE;
            int postDiff = nums[i].post.index >= 0 && nums[i].post.index < size ? nums[i].post.value - nums[i].value: Integer.MAX_VALUE;
            diff[i-1] = Math.min(preDiff, postDiff);
            if(preDiff <= postDiff) pre[i-1] = nums[i].pre.index+1;
            else pre[i-1] =  nums[i].post.index+1;
            removeNode(nums[i]);
        }

        print(diff, pre);
    }

    private static void print(int[] diff, int[] pre){
        for(int i = 0; i < diff.length; i++){
            System.out.println(diff[i] + " " + pre[i]);
        }
    }

    private static void removeNode(Node node){
        Node postCache = node.post;
        node.pre.post = postCache;
        node.post.pre = node.pre;
    }

    static class Node implements  Comparable<Node>{
        int value;
        int index;
        public Node pre;
        public Node post;

        public Node(int value, int index){
            this.value = value;
            this.index = index;
        }


        @Override
        public int compareTo(Node other) {
            return this.value - other.value;
        }
    }
}

链表找环问题

LC141题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        do {
            if(fast == null || fast.next == null) return false; 
            fast = fast.next.next; // 快指针每次走两步
            slow = slow.next; // 慢指针每次走一步
        }
        while(fast != slow);
        return true;
    }
}

LC142题目链接

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

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        do {
            if(fast == null || fast.next == null) return null; 
            fast = fast.next.next; // 快指针每次走两步
            slow = slow.next; // 慢指针每次走一步
        }
        while(fast != slow);
        ListNode slow2 = head; 
        while (slow != slow2){ // 不能do while，因为有可能相遇的节点就正是环开始节点 [1, 2] 0
            slow = slow.next;
            slow2 = slow2.next;
        }
        return slow;
    }
}

合并两个有序链表

LC21题目链接

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 list1, ListNode list2) {
        ListNode cur1 = list1, cur2 = list2, nextHead2 = null, protect = new ListNode(0, list1),lastHead1 = protect;
        while(cur1 != null || cur2 != null) {           
            // 更新节点
            if(cur1 == null || (cur2 != null && cur1.val > cur2.val)){ // 取list2节点,cur2 推进
                // 先缓存即将推进的节点
                nextHead2 = cur2.next;
                // cur2 插入在cur1之前,lastHead1之后       
                cur2.next = cur1;               
                lastHead1.next = cur2;
                // 更新lastHead1 和cur2 指针          
                lastHead1 = cur2;
                cur2 = nextHead2;                
            } else { //取list1节点，cur1直接推进
                lastHead1 = cur1;
                cur1 = cur1.next;
            }
        }
        return protect.next;
    }
}

加一

LC66题目链接

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

class Solution {
    public int[] plusOne(int[] digits) {
        // 逆序+递归
        return plusOne(digits, digits.length -1);
    }

    public int[] plusOne(int[] digits, int pos){
        if(pos == -1) {
            int[] result = new int[digits.length+1];
            result[0] = 1;
            for(int i = 0; i < digits.length; i ++){
                result[i+1] = digits[i];
            }
            return result;
        }
        digits[pos] += 1;
        if(digits[pos]/10 == 1) {
            digits[pos] %= 10;
            return plusOne(digits, pos-1);
        }
        return digits;
    }
}

栈

后缀表达式求值

LC150题目链接

解题思路

建立一个用于存数的栈，逐一扫描后缀表达式中的元素。

  • 如果遇到一个数，则把该数入栈。
  • 如果遇到运算符，就取出栈顶的两个数进行计算，然后把结果入栈。
    扫描完毕后，栈中恰好剩下的一个数，就是该表达式的值。

时间复杂度为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
24
25
26
27
28
29
30
31
32

class Solution {
    public int evalRPN(String[] tokens) {
            int cur = 0;
            Stack<Integer> nums = new Stack<>();
            while(cur < tokens.length){
                if(tokens[cur].equals("+") || tokens[cur].equals("-") || tokens[cur].equals("*")  || tokens[cur].equals("/")){
                Integer operant1 = nums.pop();
                Integer operant2 = nums.pop();
                nums.push(calculate(operant1, operant2, tokens[cur]));
            }else nums.push(Integer.parseInt(tokens[cur]));
                cur ++;
            }
            return nums.peek();
        }

        public Integer calculate(Integer x, Integer y, String operator){
            switch(operator)
            {
                case "+":
                    return x + y;
                case "-":
                    return y - x;
                case "*":
                    return x * y;
                case "/":
                    return y/x;
            }
            return 0;
        }
}

中缀表达式：基本计算器I & II

LC227题目链接

解题思路一

中缀转后缀，然后计算：

  • 需要看下一个符号的优先级是否高于本符号。
  • 如果高于：需要一个操作符栈，低优先级符号先入栈，高优先级的符号后入栈，先出。
  • 如果低于：把操作符栈出放入后缀表达式队列。
  • 处理后缀表达式队列，参考上题。

3+2*2

运算符栈： + *

后缀表达式： 3 2 2 * +

3+2-2

运算符栈：

后缀表达式： 3 2 + 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
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
70
71
72
73
74
75
76
77
78
79
class Solution {
   public int calculate(String s) {
            s += " ";
            ArrayList<String> tokens = new ArrayList<>();
            Stack<Character> operators = new Stack<>();
            String number = "";
            boolean needsZero = true; // -4 * 9 需要补零
            for(int i = 0; i < s.length(); i ++){
                char ch = s.charAt(i);
                if (ch >= '0' && ch <= '9'){
                    number += ch;
                    needsZero = false; // 5-3 不需要补零
                    continue;
                } else if(!number.isEmpty()){
                    tokens.add(number);
                    number = "";
                }

                if (ch == ' ') continue;
                if (ch == '(') {
                    operators.push('(');
                    needsZero = true; // (-3) 需要补零
                    continue;
                }
               if (ch == ')') {
                    while (!operators.empty() && !operators.peek().equals('(')){
                        tokens.add(operators.pop().toString());
                    }
                    if (!operators.empty() && operators.peek().equals('(')){
                        operators.pop();// 不需要）
                    }
                    needsZero = false; // )-3 不需要补零
                    continue;
                }

                int currRank = getRank(ch);
                while (!operators.empty() && getRank(operators.peek()) >= currRank){
                    tokens.add(operators.pop().toString());
                }
                operators.push(ch);
                if(ch == '-' && needsZero) tokens.add(Integer.toString(0));
            }

            while (!operators.isEmpty()){
                tokens.add(operators.pop().toString());
            }

            return evalRPN(tokens);
        }

        public int getRank(char ch){
            if(ch == '+' || ch == '-' ) return 1;
            if(ch == '*' || ch == '/' ) return 2;
            return 0;
        }

        int evalRPN(ArrayList tokens){
            Stack<Integer> operants = new Stack<>();
            for(int i = 0; i < tokens.size(); i ++ ){
                String token = (String) tokens.get(i);
                if(token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")){
                    Integer operant1 = operants.pop();
                    Integer operant2 = operants.pop();
                    operants.push(calc(operant1, operant2, token));
                }else {
                    operants.push(Integer.parseInt(token));
                }
            }
            return operants.peek();
        }

        Integer calc(Integer x, Integer y, String token){
            if(token.equals("+")) return x +y;
            if (token.equals("-")) return y -x;
            if(token.equals("*")) return x *y;
            if (token.equals("/")) return y /x;
            return 0;
        }
}

解题思路二

表达式拆分，加减运算为低优先级运算，将操作数和符号一起入栈。乘除为高优先级运算，遇到则立刻处理。最后将所有操作数出栈相加，得到结果。

LC224题目链接

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
70
71
72
73
74
75
76
77
78
79
80
81

class Solution {
   public int calculate(String s) {
            s += " ";
            ArrayList<String> tokens = new ArrayList<>();
            Stack<Character> operators = new Stack<>();
            String number = "";
            boolean needsZero = true; // -4 * 9 需要补零
            for(int i = 0; i < s.length(); i ++){
                char ch = s.charAt(i);
                if (ch >= '0' && ch <= '9'){
                    number += ch;
                    needsZero = false; // 5-3 不需要补零
                    continue;
                } else if(!number.isEmpty()){
                    tokens.add(number);
                    number = "";
                }

                if (ch == ' ') continue;
                if (ch == '(') {
                    operators.push('(');
                    needsZero = true; // (-3) 需要补零
                    continue;
                }
               if (ch == ')') {
                    while (!operators.empty() && !operators.peek().equals('(')){
                        tokens.add(operators.pop().toString());
                    }
                    if (!operators.empty() && operators.peek().equals('(')){
                        operators.pop();// 不需要）
                    }
                    needsZero = false; // )-3 不需要补零
                    continue;
                }

                int currRank = getRank(ch);
                while (!operators.empty() && getRank(operators.peek()) >= currRank){
                    tokens.add(operators.pop().toString());
                }
                operators.push(ch);
                if(ch == '-' && needsZero) tokens.add(Integer.toString(0));
            }

            while (!operators.isEmpty()){
                tokens.add(operators.pop().toString());
            }

            return evalRPN(tokens);
        }

        public int getRank(char ch){
            if(ch == '+' || ch == '-' ) return 1;
            if(ch == '*' || ch == '/' ) return 2;
            return 0;
        }

        int evalRPN(ArrayList tokens){
            Stack<Integer> operants = new Stack<>();
            for(int i = 0; i < tokens.size(); i ++ ){
                String token = (String) tokens.get(i);
                if(token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")){
                    Integer operant1 = operants.pop();
                    Integer operant2 = operants.pop();
                    operants.push(calc(operant1, operant2, token));
                }else {
                    operants.push(Integer.parseInt(token));
                }
            }
            return operants.peek();
        }

        Integer calc(Integer x, Integer y, String token){
            if(token.equals("+")) return x +y;
            if (token.equals("-")) return y -x;
            if(token.equals("*")) return x *y;
            if (token.equals("/")) return y /x;
            return 0;
        }
}

柱状图中最大的矩形

LC84题目链接

单调栈算法, 维护一个单调递增高度的栈，当一个新的高度低于当前栈顶时，单调性被破坏，需要将被破坏的栈元素逐个出栈，直到入栈新元素时单调性恢复。出栈元素的宽度元素叠加到accumulatedWidth中，以被后面的元素可以计算矩形面积。时间复杂度时O(n)。

思维套路

  • 确定递增递减——关键在于考虑“前面不能影响到后面”的条件
  • 本题中若h[i-1]>h[i], 则h[i-1]这个高度就无法影响到后面，自然可以单独计算了

代码套路

  • for每个元素
    • while（栈顶与新元素不满足单调性）{弹栈，更新答案，累加“宽度”}
    • 入栈
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
class Solution {
    public int largestRectangleArea(int[] heights) {
            Stack<Rect> s = new Stack<>();
            int result = 0;
            for(int i = 0; i <= heights.length; i ++){
                int h = i == heights.length ? 0 : heights[i]; // 末尾补零，从而清空栈。
                int accumulatedWidth = 0;
                // 新的元素破坏单调性
                while(!s.isEmpty() && s.peek().height > h) {
                    accumulatedWidth += s.peek().width;
                    result = Math.max(result, s.peek().height * accumulatedWidth);
                    s.pop();
                }
                s.push(new Rect(accumulatedWidth + 1, h));
            }
            return result;
        }

        class Rect {
            int width;
            int height;

            Rect (int width, int height){
                this.width = width;
                this.height = height;
            }
        }
}

接雨水

LC42题目链接

思维套路

  • 确定递增递减——关键在于考虑“前面不能影响到后面”的条件
  • 本题中若h[i-1]< h[i], 则h[i-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
30
31
32
33
34

class Solution {
        public int trap(int[] heights) {
            int result = 0;
            for(int i = 0; i < heights.length; i++){
                int accumulatedWidth = 0;
                int height = heights[i];
                while(!s.isEmpty() && s.peek().height <= height) {
                    int bottom = s.peek().height;
                    accumulatedWidth += s.peek().width;
                    s.pop();
                    // 以bottom为底，accumulatedWidth为宽度，（左右两侧较小者）up为顶的长方形是累积的雨水横条
                    // 如果栈空，则高度为bottom，增加面积为0
                    int up = s.isEmpty() ? bottom : Math.min(height, s.peek().height);

                    result += accumulatedWidth * (up - bottom);
                }
                s.push(new Rect( accumulatedWidth + 1, height ));
            }
            return result;
        }

    class Rect {
        int width;
        int height;
        Rect(int width, int height){
                this.width = width;
                this.height = height;
            }
    }

    Stack<Rect> s = new Stack<>();
}

有效的括号

LC20题目链接

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
class Solution {
    public boolean isValid(String s) {
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(c == ')'){
                if(o.isEmpty() || !cleanUp("(")) return false;
            }else if(c == '}'){
                if(o.isEmpty() || !cleanUp("{")) return false;
            }else if(c == ']'){
                if(o.isEmpty() || !cleanUp("[")) return false;
            }else o.push(String.valueOf(c));
        }
        if(o.isEmpty()) return true;
        return false;
    }

    private boolean cleanUp(String match){
        while(!o.isEmpty()) {
            String x = o.pop();
            if(x.equals(match)) return true;
            else return false;
        }
        return false;
    }
    Stack<String> o = new Stack<>();
}

最小栈

LC155题目链接

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

class MinStack {

    public MinStack() {

    }
    
    public void push(int val) {
        // 单调递减栈
        if(min.isEmpty() || (!min.isEmpty() && min.peek() >= val)) {
            min.push(val);
        }
        s.push(val);
    }
    
    public void pop() {
        if(s.pop().equals(min.peek())) min.pop();
    }
    
    public int top() {
        return s.peek();
    }
    
    public int getMin() {
        return min.peek();
    }

    // 单调递减栈
    private Stack<Integer> min = new Stack<>();
    // 原栈
    private Stack<Integer> s = new Stack<>();
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

队

滑动窗口最大值

LC139题目链接

思维套路

  • 单调队列维护的是一个候选集和，前面的较旧，后边比较新（时间有单调性）
  • 候选项的某个属性也具有单调性（比如整数值）
  • 确定递增递减的方法——考虑任意连个候选项j1< j2，写出j1比j2优的条件

排除冗余的关键：若j1比j2差（nums[j1]< nums[j2]，且j1的生命周期比j2短，那j1就没有留在队列中的意义。

单调递减队列：需要维护一个单调递减队列，队尾插入新元素，当新元素大于队尾元素时，队尾元素出栈，直到满足单调条件。队首元素需要满足索引大于i-k条件。

代码套路

  • for每个元素
    1. while(队头过期) 队头出队
    2. 取队头为最佳选项，计算答案
    3. while（队尾与新元素不满足单调性）队尾出队
    4. 新元素入队

2和3的顺序取决于i是不是候选项。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            int[] result = new int[Math.max(nums.length - k + 1, 1 )];
            int cur = 0;
            for(int i = 0; i < nums.length; i ++){
                int number = nums[i];
                while(!q.isEmpty() && nums[q.peekFirst()] <= i - k) q.removeFirst();
                while(!q.isEmpty() && nums[q.peekLast()] < number) q.removeLast();

                q.add(i);
                // 单调递减队列，队首是最大值
                if(i >= k-1)  result[cur++] = nums[q.peekFirst()];
            }
        return result;
        }

        LinkedList<Integer> q = new LinkedList<>();
    }

设计循环双端队列

LC641题目链接

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
class MyCircularDeque {

    public MyCircularDeque(int k) {
            q = new LinkedList<Integer>();
            capacity = k;
        }

        public boolean insertFront(int value) {
            if(q.size() == capacity) return false;
            q.addFirst(value);
            return true;
        }

        public boolean insertLast(int value) {
            if(q.size() == capacity) return false;
            q.addLast(value);
            return true;
        }

        public boolean deleteFront() {
            if(q.isEmpty()) return false;
            q.removeFirst();
            return true;
        }

        public boolean deleteLast() {
            if(q.isEmpty()) return false;
            q.removeLast();
            return true;
        }

        public int getFront() {
            return q.isEmpty()? -1 : q.peekFirst();
        }

        public int getRear() {
            return q.isEmpty()? -1 : q.peekLast();
        }

        public boolean isEmpty() {
            return q.isEmpty();
        }

        public boolean isFull() {
            return q.size() == capacity;
        }

        private LinkedList<Integer> q ;
        private int capacity;
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 */

最大矩形

LC85题目链接

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
class Solution {
    public int maximalRectangle(char[][] matrix) {
        // 构造纵向连续1和二维数组S[rows][cols]
        // S[p][] 是一组子矩阵的纵向柱状图，求出最大矩形
        // 遍历所有p，得出最大矩阵所包含的最大矩形
        int rows = matrix.length, cols = matrix[0].length;
        int[][] S = new int[rows+1][cols];
        int[] max = new int[rows];
        int ans = 0;
        for(int r = 0; r <= rows; r ++) {            
            for(int c = 0; c < cols; c++) {
                if( r == 0 || matrix[r-1][c] == '0') {
                    S[r][c] = 0;
                    continue;
                } else S[r][c] = S[r-1][c]+1;
            }
        }

            for(int r = 1; r <= rows; r++) {
                max[r-1] = largestRectangleArea(S[r]);
                ans = Math.max(ans, max[r-1]);
            }

        return ans;
    }

    public int largestRectangleArea(int[] heights) {
            Stack<Rect> s = new Stack<>();
            int result = 0;
            for(int i = 0; i <= heights.length; i ++){
                int h = i == heights.length ? 0 : heights[i];  // 末尾补零，从而清空栈。
                int accumulatedWidth = 0;
                // 新的元素破坏单调性
                while(!s.isEmpty() && s.peek().height > h) {
                    accumulatedWidth += s.peek().width;
                    result = Math.max(result, s.peek().height * accumulatedWidth);
                    s.pop();
                }
                s.push(new Rect(accumulatedWidth + 1, h));
            }
            return result;
        }

        class Rect {
            int width;
            int height;

            Rect (int width, int height){
                this.width = width;
                this.height = height;
            }
        }
}

前缀和

前缀和思想是运用前缀和数组作为桥梁，取解决数组的各种子数组优化问题。已知数组A[ i]，

s[ i] = s[ i - 1] + A[ i]

字段和从l 到 r则表达为：

sum(l, r) = s[ r] - s[ l - 1]

当A中都是非负数时，前缀和数组s单调递增。这样子数组和问题就转化成了s数组元素的问题。

统计优美子数组

LC1248题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        int[] s = new int[nums.length+1];
        s[0] = 0;
        int[] count = new int[nums.length+1];
        count[0] = 1;
        for(int i = 1; i < count.length; i ++) count[i] = 0;
        for(int i = 1; i <= nums.length; i++) {
            s[i] = s[i-1] + nums[i-1]%2;
            count[s[i]]++;
        }
        // 存入count[s[i]]的个数
        // s[i] - s[j] == k 等价于
        // count[s[i] - k] 的个数
        int result = 0;
        for(int i = 0; i < s.length; i ++ ) {
            if(s[i] >=k ) result += count[s[i] - k];
        }
        return result;
    }
}

最大子序和

LC53题目链接

解题思路一

通过维护前缀和数组，和前缀最小和数组，两者差为子数组和，求最大值问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int maxSubArray(int[] nums) {
        int[] s = new int[nums.length+1];
        s[0]=0;
        int[] preMin = new int[nums.length+1];
        preMin[0] = 0;
        for(int i = 0; i < nums.length; i++) {
            s[i+1] = s[i] + nums[i];
        }
        int result = -10000;
        // preMin 是前缀和最小值，那么s[i] - preMin[j]则为最大子数组和。
        for(int i = 1; i < s.length; i ++) {
            preMin[i] = Math.min(preMin[i -1], s[i]);
            // 更新最大和 = s[i] - preMin[i-1] 至少包含第i个元素
            result = Math.max(result, s[i] - preMin[i-1]);
        }

        return result;        
    }
}

解题思路二

通过贪心算法，维护双指针，当子数组和为负数，立即舍弃，慢指针前进，否则快指针已知前进直到数组尾。

二维前缀和

二维数组A (m*n)，其前缀和s[i]s[j]为第i行第j列元素左上角、子矩阵的各个元素之和。

递推关系

s[i][j]= s[i-1][j] +s[i][j-1] - s[i-1]s[j-1] + A[i][j]

子矩阵和

以[p][q]为左上角元素，[i][j]为右下角元素的子矩阵的元素和。

递推关系

sum(p,q,i,j) = s[i][j] +s[i][q-1] - s[p-1]s[j] + s[p-1][q-1]

其中，p，q总是需要减一。

二位区域和检索——矩阵不可变

LC304题目链接

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

class NumMatrix {

    public NumMatrix(int[][] matrix) {
        n = matrix.length;//row number;
        m = matrix[0].length; // col number;
        sum = new int[n+1][m+1];
        // 二维数组前缀和
        for(int i = 1; i <= n ; i ++){
            for(int j = 1; j <= m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j-1] -sum[i-1][j-1]+ matrix[i-1][j-1];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        row1++;
        row2++;
        col1++;
        col2++;
        // 索引加一，符合前缀和数组1开头算法。
        return sum[row2][col2] - sum[row1-1][col2] - sum[row2][col1-1] + sum[row1-1][col1-1];
    }

    int sum[][];
    int n, m;
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

差分

差分数组B是由数组的元素差组成的，其中第i元素等于原数组A第i元素与第i-1元素或0的差。

递推关系

B[1] = A[1]

B[i] = A[i -1]

  • 差分数组的前缀和就是原数组
  • 把A数组的第l到第r元素均加d，对应的B变化为B[l]加d，B[r+1]减d。

航班预定统计

LC1109题目链接

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
class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] delta = new int[n+2];
        for(int i = 0; i < n+2; i ++) delta[i] = 0;
        for(int i = 0; i < bookings.length; i++){
            int[] booking = bookings[i];
            int first = booking[0];
            int last = booking[1];
            int seats = booking[2];
            delta[first] += seats; // += 纵向累加delta，seats是diff booking[][first] - booking[first-1]
            delta[last+1] += -seats;  // -seats 是 booking[]last+1] - booking[last] 
        }
        int[] sum = new int[n];
        for(int i = 0;i < n; i++) sum[i] = delta[1];
        for(int i = 1; i < n; i++){
            sum[i] =  sum[i-1] + delta[i+1];
        }
        return sum;
    }
}

/* O(m+n)
1  2  3  4  5
10   -10
   20   -20
   25
10 55 45 25 25
*/

双指针扫描

两数之和II —— 输入有序数组

LC167题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int j = numbers.length -1;
        for(int i = 0; i < numbers.length; i++) {
            while(i < j && numbers[i] + numbers[j] > target) j--;
            if(i < j && numbers[i] + numbers[j] == target) {
                return new int[]{i+1, j+1};
            }
        }
        return new int[]{};
    }
// O(n)
// 2 7 11 15 17 target = 18
// i         j 小于18停止左移动j，检查
//   i j     
//     i  j    小于18停止左移动j，检查
// i 移动时，j单调递减、递增。

}

两数之和

LC1题目链接

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

class Solution {
    public int[] twoSum(int[] nums, int target) {
            Pair[] sorted = new Pair[nums.length];
            for(int i = 0; i < nums.length; i ++) sorted[i]= new Pair(i, nums[i]);
            Arrays.sort(sorted);
            int j = nums.length-1;
            for(int i = 0; i < nums.length; i++){
                while(i < j && sorted[i].value + sorted[j].value > target) j--;
                if(i < j && sorted[i].value + sorted[j].value == target) return new int[]{sorted[i].index, sorted[j].index};
            }
            return new int[]{};
        }
        

    static class Pair implements Comparable<Pair> {
        public final int index;
        public final int value;

        public Pair(int index, int value) {
            this.index = index;
            this.value = value;
        }

        @Override
        public int compareTo(Pair other) {
            //multiplied to -1 as the author need descending sort order
            return Integer.valueOf(this.value).compareTo(other.value);
        }
    }
}

三数之和

LC15题目链接

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

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);// 顺序不再重要
            List<List<Integer>> result = new ArrayList<>();
            for(int i = 0; i < nums.length; i++){
                if(i != 0 && nums[i] == nums[i-1]) continue;// 去除第一位重复
                List<List<Integer>> twoSumResults = twoSum(nums, i + 1, -nums[i]);
                for(List<Integer> twoSumResult : twoSumResults){
                    result.add(Arrays.asList(nums[i], twoSumResult.get(0), twoSumResult.get(1)));
                }


            }
            return result;
        }

        List<List<Integer>> twoSum(int[] nums, int start, int target) {
            List<List<Integer>> result = new ArrayList<>();
            int j = nums.length-1;
            for(int i = start; i < nums.length; i++){
                if(i != start && nums[i] == nums[i-1]) continue;// 去除第二位重复
                while(i < j && nums[i] + nums[j] > target) j--;
                if(i < j && nums[i] + nums[j] == target) {
                    List<Integer> finding = new ArrayList<>();
                    finding.add(nums[i]);
                    finding.add(nums[j]);
                    result.add(finding);
                }
            }
            return result;
        }
}

盛最多水的容器

LC11题目链接

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length-1, ans = 0;
        while( i < j){
            ans = Math.max(ans, Math.min(height[i], height[j])* (j-i));
            // i j 两个指针相遇问题，如果height[i]较矮，则前进i寻找更高的，否则前进j
            if(height[i] < height[j]) i++; else j--;
        }
        return ans;
    }
}

递归

递归的三个关键：

  • 定义需要递归的问题（重叠子问题）—— 数学归纳法思想
  • 确定递归边界
  • 保护与还原现场

递归实现的“暴力搜索”或者叫枚举、回溯方法的基本复杂度为：

递归形式 时间复杂度规模 问题举例
指数型 k^n 子集、大体积背包
排列型 n! 全排列、旅行商、N皇后
组合型 n!/(m!(n-m)!) 组合选数

子集

LC78题目链接

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

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        n = nums.length;
        recur(nums,0);
        return ans;
    }

    void recur(int[] nums, int i){
        // 递归边界
        if(i == n) {
            ans.add(new ArrayList<>(chosen));// 不可加入引用必须复制副本
            return;
        }

        // i 不选
        recur(nums, i+1);

        // i 选中
        chosen.add(nums[i]);
        recur(nums, i+1);
        chosen.remove(chosen.size()-1);
    }


    private int n;
    List<Integer> chosen = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();
}

组合

LC77题目链接

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

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        recur(1);
        return ans;
    }

    void recur( int i){
        if(chosen.size() > k || chosen.size() + (n -i + 1) <k ) return; // *** 提早退出，剪枝，已经超过k个，或者剩下全选也不够k个
        // 递归边界
        if(i == n+1 ) {
            if(chosen.size() == k) ans.add(new ArrayList<>(chosen));// 不可加入引用必须复制副本
            return;
        }

        // i 不选
        recur(i+1);

        // i 选中
        chosen.add(i);
        recur(i+1);
        chosen.remove(chosen.size()-1);
    }


    private int n, k;
    List<Integer> chosen = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();
}

全排列

LC46题目链接

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

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        this.n = nums.length;
        this.used = new boolean[n];
        recur(nums, 0);
        return ans;
    }
    
    void recur(int[] nums, int pos) {
        // pos 为选中的数字个数
        if(pos == n) {
            ans.add(new ArrayList<>(a));
            return;
        }

        for(int i = 0; i < n; i++) {
            if(!used[i]){
                a.add(nums[i]);
                used[i] = true;
                recur(nums, pos +1 );
                // 还原，从而其他递归分支可以继续计算。
                used[i] = false;
                a.remove(a.size()-1);
            }
        }
    }
    boolean[] used;
    List<Integer> a = new ArrayList<>();
    int n;
    List<List<Integer>> ans = new ArrayList<>();
}

全排列II

LC47题目链接

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

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        this.n = nums.length;
        this.used = new boolean[n];
        Arrays.sort(nums);
        // nums 排序，则在used统计中，要检查所有同样的数字的used情况
        // 拆分成第一个数，和剩下的全排列
        // 如果已经算过该数了，则跳过
        recur(nums, 0);       
        return ans;
    }

    void recur(int[] nums, int pos) {
        // pos 为选中的数字个数
        if(pos == n) {
            ans.add(new ArrayList<>(a));
            return;
        }

        for(int i = 0; i < n; i++) {
            //if(!used[i]){
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                continue;
            }
            a.add(nums[i]);
            used[i] = true;
            recur(nums, pos +1 );
            // 还原，从而其他递归分支可以继续计算。
            used[i] = false;
            a.remove(a.size()-1);
            //}
        }
    }
    boolean[] used;
    List<Integer> a = new ArrayList<>();
    int n, first;
    List<List<Integer>> ans = new ArrayList<>();
    Map<Integer, Boolean> record = new HashMap<>();
}

树

反转二叉树

LC226题目链接

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode cache = root.left;
        root.left = root.right;
        root.right = cache;

        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

验证二叉搜索树

LC98题目链接

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
     public boolean isValidBST(TreeNode root) {
         // 注意Integer.MIN_VALUE-1 与Integer.MAX_VALUE+1越界问题，用long
            return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
        }

        boolean isValidBST(TreeNode root, long low, long up) {
            if(root == null ) return true;

            if (root.val > up || root.val < low) return false;
            return isValidBST(root.left, low, (long)root.val -1) && isValidBST(root.right, (long)root.val + 1, up);
        }
}

二叉树的最大、最小深度

LC104题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) +1;
    }
}

LC111题目链接

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null) return minDepth(root.right)+1;
        
        if (root.right == null) return minDepth(root.left)+1;
        
        return Math.min(minDepth(root.left), minDepth(root.right)) +1;
    }
}

分治

把原问题划分成若干个同类子问题，分别解决后，再把结果合并起来。

关键点：
原问题和各个子问题都是重复的（同类的）——递归定义
除了向下递归“问题”，还要向上合并“结果”

分治算法一般用递归实现，分为三步骤：

  • 递归边界定义
  • split：分解成多个子问题
  • merge：合并子问题结果

Pow(x,n)

LC50题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public double myPow(double x, int n) {
        // 边界问题
        // 停止
        if(n == 0) return 1;
        // 负数边界，必须再负数之前，否则StackOverflow
        if (n == Integer.MIN_VALUE) return 1.0/ (myPow(x, -(n + 1)) *x);
         // 负数
        if (n < 0) return 1.0/ myPow(x, -n);
        double temp = myPow(x, n/2);
        double ans = temp * temp;
        // 奇数，除以2取整，然后补一个*x
        // 偶数，直接相乘
        if(n%2 == 1) ans *= x;
        return ans;
    }
}

括号生成

LC22题目链接

组合型递归问题。

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

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
            // boundary
            if(n == 0) return Arrays.asList(new String[]{""});
            if (store.containsKey(n)) return store.get(n);
            // split
            for (int k =1; k <= n; k++ ){ // 加法原理
                List<String> A = generateParenthesis(k-1);
                store.put(k-1, A);
                List<String> B = generateParenthesis(n-k);
                store.put(n-k, B);
                // S=(A)B merge
                // 乘法原理
                for(String a : A ){
                    for(String b: B) {
                        ans.add("(" + a + ")" + b);
                    }
                }
            }
            return ans;
        
    }

    Map<Integer, List<String>> store = new HashMap<>();
}

/*
n = 3

((()))
(()())


(())()
()()()

n = 3

重复问题
--|---- ()(()) ()()()
----|-- (())() ()()()

解决办法：找到第一个不可划分的整体

左侧第一个被一组括号包住，左侧k个括号则为(k-1个括号组合)n-k个括号组合
S (A) B
n k-1 n-k

k=1 (A) A=0对括号       B=n-k=2对括号 ()() (())
()()()  ()(())

k=2 (A) A=1对括号 (())  B=n-k=1对括号 ()
(())()

k=3 (A) A=2对括号 (()())  ((()))  B=n-k=0对括号
(()())   ((()))

总共2+1+2=5种
*/

搜索二维矩阵

LC74题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 按行搜索直到 target>= matrix[i-1][0] && target <= matrix[i][0]
        // 按列搜索直到 target == matrix[i-1][j]
        int i = 0;
        for( ;i < matrix.length; i++) {
            if(target >= matrix[i][0] && ( i == matrix.length -1 || target < matrix[i+1][0])) break;
        }

        for(int j = 0; j < matrix[0].length; j++) {
            if(i < matrix.length && target == matrix[i][j]) return true;
        }
        return false;
    }
}

合并K个升序链表

LC23题目链接

拆分问题，先合成两个k/2组成的链表,把这两个链表合成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
/**
 * 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 mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length -1);
    }

    public ListNode merge(ListNode[] lists, int start, int end) {
        if( start == end) return lists[start];
        if ( start > end ) return null;
        int mid = (start + end) /2;
        return mergeTwoLists(merge(lists, start, mid), merge(lists, mid +1, end));
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode cur1 = list1, cur2 = list2, nextHead2 = null, protect = new ListNode(0, list1),lastHead1 = protect;
        while(cur1 != null || cur2 != null) {           
            // 更新节点
            if(cur1 == null || (cur2 != null && cur1.val > cur2.val)){ // 取list2节点,cur2 推进
                // 先缓存即将推进的节点
                nextHead2 = cur2.next;
                // cur2 插入在cur1之前,lastHead1之后       
                cur2.next = cur1;               
                lastHead1.next = cur2;
                // 更新lastHead1 和cur2 指针          
                lastHead1 = cur2;
                cur2 = nextHead2;                
            } else { //取list1节点，cur1直接推进
                lastHead1 = cur1;
                cur1 = cur1.next;
            }
        }
        return protect.next;
    }
}

为运算表达式设计优先级

LC241题目链接

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
70
71
72
73
74
75
class Solution {

    static final int ADDITION = -1;
        static final int SUBTRACTION = -2;
        static final int MULTIPLICATION = -3;

        public List<Integer> diffWaysToCompute(String expression) {
            ArrayList<Integer> ops = new ArrayList<>();
            // 创建操作数数组 [ 2, -, 1, -, 1]
            for(int i =0; i < expression.length();) {
                if(expression.charAt(i) == '+'){
                    ops.add(ADDITION);
                }else if (expression.charAt(i) == '-'){
                    ops.add(SUBTRACTION);
                }else if (expression.charAt(i) == '*' ){
                    ops.add(MULTIPLICATION);
                }else {
                    int number = 0;
                    while(i < expression.length() && expression.charAt(i) <= '9' && expression.charAt(i) >= '0' ){
                        // 表达式要正确
                        number = 10 * number +  expression.charAt(i) - '0';
                        i++;
                    }
                    ops.add(number);
                    continue;
                }
                i++;
            }

            // 分治法合并表达式
            // split 拆分成两个子数组, [start, mid] [mid + 2, end] 分别得到结果
            // merge 用 mid +1 的符号合并左右子数组的所有可能结果
            // 对于每一层，共有 (start + end )/2 种拆分方式，每次步长为2

            // 缓存结果达到剪枝效果
            // 注意for循环时候不能修改dp本身

            List<Integer>[][] dp = new List[ops.size()][ops.size()];
            for (int i = 0; i < ops.size(); i++) {
                for (int j = 0; j < ops.size(); j++) {
                    dp[i][j] = new ArrayList<Integer>();
                }
            }

            return dfs(dp, 0, ops.size() -1, ops);
        }

        public List<Integer> dfs(List<Integer>[][] dp, int start, int end, List<Integer> ops){
            if( start > end) return new ArrayList<>();
            if(!dp[start][end].isEmpty()) return dp[start][end];
            // boundary
            if( start == end) {
                dp[start][end].add(ops.get(start));
                return Arrays.asList(ops.get(start));
            }
            // split
            for(int mid = start; mid < end; mid+=2){
                List<Integer> leftResults = dfs(dp, start, mid, ops);
                List<Integer> rightResults = dfs(dp, mid+2, end, ops);


                // merge
                for(Integer left : leftResults){
                    for(Integer right : rightResults){
                        if(ops.get(mid+1) == ADDITION) dp[start][end].add(left + right);
                        if(ops.get(mid+1) == SUBTRACTION) dp[start][end].add(left - right);
                        if(ops.get(mid+1) == MULTIPLICATION) dp[start][end].add(left * right);
                    }
                }
            }
            return dp[start][end];
        }

    }

给表达式添加运算符

LC282题目链接

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
70
71
72
73
74
75
76
77
78
79
80

class Solution {

        List<String> ans = new ArrayList<>();
        int n, target;
        String num;
        public List<String> addOperators(String num, int target) {
            this.n = num.length();
            this.target = target;
            this.num = num;
            long sum = 0, pre = 0;
            dfs(0, 0, "", 0);
            return ans;
        }

        private void dfs(long sum, long pre, String exp, int start){
            //boundary
            if(start == n) {
                if(sum == target)
                    ans.add(exp);
                return;
            }

            // main logic, loop from start to n-1 with sum = xxx
            // 右操作数有四种选择
            // 直接拼接
            // + - *
            // int val 会有越界问题
            long val = 0 ;
            for(int i = start; i < n; i++) {
                // 开头是0 (num.charAt(start) 则不处理拼接的情况。
                if(i != start && num.charAt(start) == '0')
                    break;

                val = val* 10 + num.charAt(i) - '0';

                if(start == 0) {
                    dfs(val, val, exp + val, i+1);
                }else {
                    // sum[i] =  sum[i-1] + val
                    dfs(sum + val, val, exp + "+" + String.valueOf(val), i+1);
                    // sum[i] =  sum[i-1] - val
                    dfs(sum - val, -val, exp + "-" + String.valueOf(val), i+1);
                    // sum[i] =  sum[i-1] - pre + val*pre
                    dfs(sum - pre + pre * val, pre * val, exp + "*" + String.valueOf(val), i+1);
                }
            }
        }
/*

  递归法解决问题：

  num拆分成字符串，长度为n。

  第i-1层到第i层递进递归：

  1. 边界
    如果start == n 及 存入满足target条件的表达式。
  2. split
    需要知道当前层的和，i-1 层的乘积，当前表达式，把运算结果直接当参数传入下层，从而减轻解析计算复杂度。
    dfs(long sum, long pre, String exp, int start)

    123 为例 展开为：

    1 + f(23)
    1 + f(2) + f(3)
    12 + f(3)
// 提示：
具体来说，我们枚举连续数字(即一个数字段)的长度(长度大于111，即中间什么都不插入)，然后考虑和上一段数字之间中间的二元运算符是什么。

假如递归枚举到第iii段数字的时候，考虑二元运算符三种情况。设前i−1i-1i−1段数字的表达式和为sumsumsum。

第一种，中间是+++，则sumsumsum加上第iii段数字。
第二种，中间是−-−，则sumsumsum减去第iii段数字。
第三种，中间是×××，则sumsumsum减去上一段连续乘的值(因此我们需要在递归的时候记录上一段的值，对于第iii段数字，即记录第i−1i-1i−1的数字是多少)，再加上 第i−1i-1i−1段数字×第iii段数字。(例如，1+2×3×41+2×3×41+2×3×4，假设当前枚举3和4之间的运算符，是×运算符，则sumsumsum减去2×3=62×3=62×3=6，然后加上2×3×4=242×3×4=242×3×4=24)。
注意，连续000的情况要特殊处理。
*/

    }

数组中的第K个最大元素

LC215题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int findKthLargest(int[] nums, int k) {
        Pair[] sorted = new Pair[nums.length];
        for(int i = 0; i < nums.length ; i++) sorted[i] =  new Pair(i, nums[i]);
        Arrays.sort(sorted);
        return sorted[k-1].value;
    }

    static class Pair implements Comparable<Pair>{
        int index, value;
        public Pair(int index, int value) {
            this.index = index;
            this.value = value;
        }

        @Override
        public int compareTo(Pair other){
            return other.value - this.value;
        }
    }
}

综合习题

和为 K 的子数组

LC560题目链接

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

class Solution {
    public int subarraySum(int[] nums, int k) {
        int[] s = new int[nums.length+1];
        s[0] = 0;
        Map<Integer, Integer> count = new HashMap<>();
        count.put(0, 1);
        // 前缀和
        int result = 0;
        for(int i = 1; i <= nums.length; i++) {
            s[i] = s[i-1] + nums[i-1];            
            // !!必须在没有全部s数组前机型计算，避免各种边界，例如i< j, k =0 之类
            result += count.getOrDefault(s[i] - k, 0);
            count.put(s[i], count.getOrDefault(s[i], 0)+1);
        }
        // 存入count[s[i]]的个数
        // s[i] - s[j] == k 等价于
        // count[s[i] - k] 的个数
        // i 必须 >= j
        return result;
    }


}

最接近原点的 K 个点

LC973题目链接

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

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        // this.k = k;
        sorted = new Pair[points.length];
        // 存入所有distance，排序后取前k个。
        for(int i = 0; i < points.length; i++) {
            enqueue(points, i);
        }
        Arrays.sort(sorted);
        int[][] result = new int[k][2];
        int current = 0;
        for(int j = 0; j < k;j++){
            result[current][0] = points[sorted[j].index][0];
            result[current][1] = points[sorted[j].index][1];
            current ++;
        }
        return result;
    }

    private void enqueue(int[][] points, int index) {
        int distance = getDistance(points, index);
        sorted[index] = new Pair(index, distance);
        //dMap.put(index, distance);
        // 算法超时： // 找到第一个小于的位置放入，保证队列不找过k个元素。
        // int r;
        // for(r = 0; r < q.size() && !q.isEmpty(); r++) {
        //     if(distance <= dMap.get(q.get(r))) {
        //         q.add(r, index);
        //         if(q.size() > k) q.removeLast();
        //         break;
        //     }
        // }

        // if(q.isEmpty()) q.add(index);
        // if(q.size() < k && r == q.size()) q.addLast(index);
    }

    private int getDistance(int[][] points, int index) {
        return points[index][0]*points[index][0] + points[index][1]*points[index][1];
    }
    // 单调递减队列，只有k个容量
    LinkedList<Integer> q = new LinkedList<>();
    // Map<Integer,Double> dMap = new HashMap<>();
    Pair[] sorted;
    // int k ;

    static class Pair implements Comparable<Pair> {
        public final int index;
        public final int value;

        public Pair(int index, int value) {
            this.index = index;
            this.value = value;
        }

        @Override
        public int compareTo(Pair other) {
            //multiplied to -1 as the author need descending sort order
            return Integer.valueOf(this.value).compareTo(other.value);
        }
    }
}

鸡蛋掉落

LC887题目链接

解题思路：

  1. 回溯：递归展开，dp归纳法得出最优解
  2. 记忆化剪枝优化
  3. 根据其单调性二分查找快速定位最大值。
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
70
71
72
73
74
75
76

class Solution {
    public int superEggDrop(int k, int n) {
        return recur(k, n); 
    }
    
    private int recur(int K, int N) {
        // boundary
        // K == 1 needs tranverse every floor with the only egg
        // N == 0 or 1 needs 1 time to do
        if(K == 1 || N == 0 || N == 1) {
            return N;
        }
        
        //Pair key = new Pair(K, N);
        int key = 1000*N +K;
        if(memo2.containsKey(key)) return memo2.get(key);
        // dp
        /* transition function
        searchTime(K, N) = max( searchTime(K-1, X-1), searchTime(K, N-X) )
        min = min(searchTime(K, N), min)
        */
        //int min = N;    // inital max is N
        
        // recur(K -1, X-1) means egg breaks
        // recur(K, N - X) means egg not break
        // sequential search time exceeded!
        // binary search as recur(K-1, X-1) monolithic increasing with X grow
        // max KN should be around middle
        //for(int X = 1; X <= N; X++){
        int low = 1, high = N;
        int X = 0;
        while(low +1 < high){
            X = (low + high)/2;
            int KNlow = recur(K-1, X-1);
            int KNhigh = recur(K, N-X);
            if(KNlow < KNhigh) low = X;
            else if(KNlow > KNhigh) high = X;
            else low = high = X;
            
        }
        
        int KN = Math.max( recur(K-1, low-1), recur(K, N-low) );
        int KN2 = Math.max(recur(K-1, high-1), recur(K, N-high));
        // KN + 1 means executed once;
        int min = Math.min(KN, KN2)+1;
        //}
        
        // K = 2, N = 3
        // X = 1; r(1, 0)=0 r(2, 2)=? 2
        // X = 2; r(1, 1)=1 r(2, 1)=1
        // K = 2, N = 2
        // X = 1; r(1, 0)=1 r(2, 1)=2
        // X = 2; r(1, 1)=2 r(2, 0)=1
        // r(2, 2) = 1
        // cache result 
        memo2.put(key, min);
        return min;
    }
    
    //Map<Pair, Integer> memo = new HashMap<>();
    Map<Integer, Integer> memo2 = new HashMap<>();
    
    // static class Pair{
    //     int K, N;
    //     public Pair(int K, int N){
    //         this.K = K;
    //         this.N = N;
    //     }
        
    //     @Override
    //     public int hashCode(){
    //         return 100 * N + K;
    //     }
    // }
}