发表算法1 小时读完 (大约7456个字)0次访问

算法题型总结

一、链表常见题

1、链表翻转

方法

递归后序遍历进行处理

图示

image-20220212153731529

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
/**
* 25.K个一组反转链表
*/
public ListNode reverseKGroup(ListNode head, int k) {
    ListNode cursor = head;
    int count = 0;
    while (count < k && cursor != null) {
        cursor = cursor.next;
        count++;
    }
    if (count < k) {
        return head;
    }
    ListNode newHead = doReverse(head, cursor);
    ListNode next = reverseKGroup(cursor, k);
    head.next = next;
    return newHead;
}

private ListNode doReverse(ListNode node, ListNode target) {
    if (node.next == target) { // 最后一个节点
        return node;
    }

    ListNode head = doReverse(node.next, target);
    ListNode tmp = node.next.next;
    node.next.next = node;
    node.next = tmp;
    return head;
}

题目

2、链表合并

方法

空头节点、双指针、优先级队列

题目

3、链表遍历

方法

空头节点、快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* 287. 寻找重复数
* 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
* 假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
* 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
**/
public int findDuplicate(int[] nums) {
    int slow = 0;
    int fast = 0;
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while(slow != fast);

    fast = 0;
    while (slow != fast) {
        fast = nums[fast];
        slow = nums[slow];
    }
    return slow;
}

题目

二、字符串常见题

1、字符匹配

方法

动态规划+备忘录，KMP

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
public class KMP {
    private int[][] dp;
    private String pat;

    public KMP(String pat) {
        this.pat = pat;
        int M = pat.length();
        // dp[状态][字符] = 下个状态
        dp = new int[M][256];
        // base case
        dp[0][pat.charAt(0)] = 1;
        // 影子状态 X 初始为 0
        int X = 0;
        // 当前状态 j 从 1 开始
        for (int j = 1; j < M; j++) {
            for (int c = 0; c < 256; c++) {
                if (pat.charAt(j) == c) 
                    dp[j][c] = j + 1;
                else 
                    dp[j][c] = dp[X][c];
            }
            // 更新影子状态
            X = dp[X][pat.charAt(j)];
        }
    }

    public int search(String txt) {...}
}

题目

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
/**
* 32. 最长有效括号
*/
public int longestValidParentheses(String s) {
    Stack<Integer> stack = new Stack<>();
    // 以i结尾的有效长度
    int[] dp = new int[s.length()];
    int max = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            // 遇到左括号，记录索引
            stack.push(i);
            dp[i] = 0;
        } else {
            // 遇到右括号
            if (!stack.isEmpty()) {
                // 配对的左括号对应索引，[leftIndex, i] 是一个合法括号子串
                int left = stack.pop();
                dp[i] = i - left + 1;
                // 这个合法括号子串的长度
                if (left > 0) {
                    dp[i] += dp[left - 1];
                }
                max = Math.max(max, dp[i]);
            } else {            
                // 没有配对的左括号;
                dp[i] = 0;
            }
        }
    }

    return max;
}

/**
* 1541. 平衡括号字符串的最小插入次数
*/
public int minInsertions(String s) {
    int leftInsert = 0;
    int rightInsert = 0;
    int rightNeed = 0;
    int n = s.length();
    for (int i = 0; i < n; i++) {
        char c = s.charAt(i);
        if (c == '(') {
            if (rightNeed % 2 == 1) {
                rightInsert++;
                rightNeed++;
            } else {
                rightNeed += 2;
            }
        } else {
            if (rightNeed == 0) {
                leftInsert++;
                rightNeed++;
            } else {
                rightNeed--;
            }
        }
    }
    return leftInsert + rightInsert + rightNeed;
}

题目

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
/**
* 5.最长回文子串
*/
public String longestPalindrome(String s) {
    String ret = "";
    for (int i = 0; i < s.length(); i++) {
        String sub1 = lp(s, i, i);
        String sub2 = lp(s, i, i+1);
        if (sub1.length() < sub2.length()) {
            String tmp = sub1;
            sub1 = sub2;
            sub2 = tmp;
        }
        if (sub1.length() > ret.length()) {
            ret = sub1;
        }
    }
    return ret;
}

private String lp(String s, int left, int right) {
    while (left >= 0 && right < s.length()) {
        if (s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        } else {
            break;
        }
    }
    left++;
    if (right > left) {
        return s.substring(left, right);
    } else {
        return "";
    }
}

题目

三、数组/字符串通用解法

1、单调函数二分查找

二分查找法

1
2
3
4
5
6
7
8
9
10
11
// 单调递减函数上，搜索左侧值
while (left <= right) {
    int mid = left + (right - left) / 2;
    int midVal = func(mid);
    if (midVal > target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
}
return left;

题目

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
// 986. 区间列表的交集
public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
    int firstIndex = 0;
    int secondIndex = 0;
    List<int[]> ret = new ArrayList<>();
    while (firstIndex < firstList.length && secondIndex < secondList.length) {
        int[] first = firstList[firstIndex];
        int[] second = secondList[secondIndex];
        int[] intersect;
        if (first[1] < second[1]) {
            intersect = getIntersect(first, second);
            firstIndex++;
        } else {
            intersect = getIntersect(second, first);
            secondIndex++;
        }
        if (intersect != null) {
            ret.add(intersect);
        }
    }
    return ret.toArray(new int[][]{});
}

int[] getIntersect(int[] left, int[] right) {
    if (right[0] > left[1]) {
        return null;
    }
    int[] ret = new int[2];
    ret[1] = left[1];
    ret[0] = Math.max(left[0], right[0]);
    return ret;
}

题目

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
/**
* 1109.航班预定统计
*/
public int[] corpFlightBookings(int[][] bookings, int n) {
    int[] incSum = new int[n + 1];
    for (int[] booking : bookings) {
        int start = booking[0];
        int end = booking[1];
        incSum[start - 1] += booking[2];
        incSum[end] -= booking[2];
    }

    int[] ret = new int[n];
    ret[0] = incSum[0];
    for (int i = 1; i < n; i++) {
        ret[i] = ret[i - 1] + incSum[i];
    }   
    return ret;
}

/**
* 134.加油站
*/
public int canCompleteCircuit(int[] gas, int[] cost) {
    int min = Integer.MAX_VALUE;
    int cur = 0;
    int ret = -1;
    for (int i = 0; i < gas.length * 2; i++) {
        cur += gas[i % gas.length];
        cur -= cost[i % gas.length];

        if (i < gas.length) {
            if (cur < min) {
                min = cur;
                ret = (i + 1) % gas.length;
            }
        } else {
            if (cur < min) {
                return -1;
            }
        }
    }
    return ret;
}

题目

5、前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 560.和为K的连续子数组
*/
public int subarraySum(int[] nums, int k) {
    int[] sum = new int[nums.length + 1];
    for (int i = 0; i < nums.length; i++) {
        sum[i + 1] = sum[i] + nums[i];
    }
    int ret = 0;
    for (int i = 0; i < sum.length; i++) {
        for (int j = i + 1; j < sum.length; j++) {
            if (sum[j] - sum[i] == k) {
                ret++;
            }
        }
    }
    return ret;
}

6、用Map降低时间复杂度

经典题目：切分子数组

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
bool isPossible(vector<int>& nums) {
    unordered_map<int, int> freq;
    unordered_map<int, vector<vector<int>>> need;
    for (int v : nums) freq[v]++;
    for (int v : nums) {
        if (freq[v] == 0) {
            continue;
        }

        if (need.count(v) && need[v].size() > 0) {
            // v 可以接到之前的某个序列后面
            freq[v]--;
            // 随便取一个需要 v 的子序列
            vector<int> seq = need[v].back();
            need[v].pop_back();
            // 把 v 接到这个子序列后面
            seq.push_back(v);
            // 这个子序列的需求变成了 v + 1
            need[v + 1].push_back(seq);
        } else if (freq[v] > 0 && freq[v + 1] > 0 && freq[v + 2] > 0) {
            // 可以将 v 作为开头
            freq[v]--;
            freq[v + 1]--;
            freq[v + 2]--;
            // 新建一个长度为 3 的子序列 [v,v + 1,v + 2]
            vector<int> seq{v, v + 1, v + 2};
            // 对 v + 3 的需求加一
            need[v + 3].push_back(seq);
        } else {
            return false;
        }
    }

    // 打印切分出的所有子序列
    for (auto it : need) {
        for (vector<int>& seq : it.second) {
            for (int v : seq) {
                cout << v << " ";
            }
            cout << endl;
        }
    }

    return true;
}


/**
* 28.最长连续序列
*/
public int longestConsecutive(int[] nums) {
    Map<Integer, Integer> endLength = new HashMap<>();
    int max = 0;
    for (int num : nums) {
        if (!endLength.containsKey(num)) {
            int beforeEnd = num - 1;
            int curLength;
            if (endLength.containsKey(beforeEnd)) {
                curLength = endLength.get(beforeEnd) + 1;
            } else {
                curLength = 1;
            }
            endLength.put(num, curLength);
            max = Math.max(max, curLength);

            int nextEnd = num + 1;
            while(endLength.containsKey(nextEnd)) {
                int newLength = endLength.get(nextEnd) + curLength;
                endLength.put(nextEnd, newLength);
                nextEnd++;

                max = Math.max(max, newLength);
            }
        }
    }

    return max;
}

题目

7、DFS/回溯/深度遍历/暴力破解

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
// 695. 岛屿最大面积
public int maxAreaOfIsland(int[][] grid) {
    int max = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] != 0) {
                max = Math.max(max, dfs(grid, i, j));
            }
        }
    }
    return max;
}

int[] direction = new int[]{-1, 0, 1, 0, -1};
private int dfs(int[][] grid, int row, int col) {
    if (row < 0 || col < 0 || row >= grid.length || col >= grid[0].length || grid[row][col] == 0) {
        return 0;
    }

    int ret = 1;
    grid[row][col] = 0;
    for (int i = 0; i < 4; i++) {
        ret += dfs(grid, row + direction[i], col + direction[i + 1]);
    }
    return ret;
}

题目

8、数组排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 78.子集
public List<List<Integer>> subsets(int[] nums) {
    dfs(nums, 0, new LinkedList());
    return ret;
}

List<List<Integer>> ret = new ArrayList<>();

private void dfs(int[] nums, int i, LinkedList<Integer> route) {
    if (i == nums.length) {
        ret.add(new ArrayList(route));
        return;
    }

    dfs(nums, i + 1, route);
    route.add(nums[i]);
    dfs(nums, i + 1, route);
    route.removeLast();
}

题目

9、二维数组对角线遍历

通过row+col的和判断是处于向上/向下，来计算下个坐标。

题目

10、双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 82. 删除排序链表中重复元素
public ListNode deleteDuplicates(ListNode head) {
    ListNode dummy = new ListNode();
    dummy.next = head;
    ListNode slow = dummy;
    ListNode fast = head;
    while (fast != null) {
        if (fast.next != null && fast.val == fast.next.val) {
            int skipVal = fast.val;
            while (fast != null && fast.val == skipVal) {
                fast = fast.next;
            }
        } else {
            slow.next = fast;
            slow = slow.next;
            fast = fast.next;
        }
    }
    slow.next = null;
    return dummy.next;
}

题目

11、双指针+窗口

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
public boolean checkInclusion(String s1, String s2) {
    Map<Character, Integer> need = new HashMap<>();
    for (char c : s1.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }
    Map<Character, Integer> window = new HashMap<>();
    // 需要满足的字符数
    int target = need.keySet().size();
    int count = 0;
    int left = 0;
    int right = 0;
    while (right < s2.length()) {
        char c = s2.charAt(right++);
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c))) {
                count++;
            }
        }
        while (right - left > s1.length()) {
            char toDel = s2.charAt(left++);
            // 逻辑与上面对称
            if (need.containsKey(toDel)) {
                if (window.get(toDel).equals(need.get(toDel))) {
                    count--;
                }
                window.put(toDel, window.get(toDel) - 1);
            }
        }
        if (count == target && right - left == s1.length()) {
            return true;
        }
    }
    return false;
}

题目

12、单调队列

题目

13、单调栈

题目

14、负数代表下标存在

用元素的正负，替代Map来标识元素是否存在

题目

15、二维数组螺旋遍历

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
/**
* from https://labuladong.gitee.io/algo/2/21/57/
**/
List<Integer> spiralOrder(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int upper_bound = 0, lower_bound = m - 1;
    int left_bound = 0, right_bound = n - 1;
    List<Integer> res = new LinkedList<>();
    // res.size() == m * n 则遍历完整个数组
    while (res.size() < m * n) {
        if (upper_bound <= lower_bound) {
            // 在顶部从左向右遍历
            for (int j = left_bound; j <= right_bound; j++) {
                res.add(matrix[upper_bound][j]);
            }
            // 上边界下移
            upper_bound++;
        }

        if (left_bound <= right_bound) {
            // 在右侧从上向下遍历
            for (int i = upper_bound; i <= lower_bound; i++) {
                res.add(matrix[i][right_bound]);
            }
            // 右边界左移
            right_bound--;
        }

        if (upper_bound <= lower_bound) {
            // 在底部从右向左遍历
            for (int j = right_bound; j >= left_bound; j--) {
                res.add(matrix[lower_bound][j]);
            }
            // 下边界上移
            lower_bound--;
        }

        if (left_bound <= right_bound) {
            // 在左侧从下向上遍历
            for (int i = lower_bound; i >= upper_bound; i--) {
                res.add(matrix[i][left_bound]);
            }
            // 左边界右移
            left_bound++;
        }
    }
    return res;
}

题目

四、二叉树

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
public List<List<Integer>> levelOrder(TreeNode root) {
    if (root == null) {
      return new ArrayList<>();
    }
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);

    List<List<Integer>> ret = new ArrayList<>();
    while (!queue.isEmpty()) {
      int size = queue.size();
      List<Integer> item = new ArrayList<>();
      ret.add(item);
      for (int i = 0; i < size; i++) {
        TreeNode node = queue.removeFirst();
        item.add(node.val);
        if (node.left != null) {
          queue.add(node.left);
        }
        if (node.right != null) {
          queue.add(node.right);
        }
      }
    }
    return  ret;
}

题目

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
// 662.二叉树最大宽度
public int widthOfBinaryTree(TreeNode root) {
    if (root == null) {
        return 0;
    }
    dfs(root, 1, 1);
    return max;
}

// 记录每层的最左节点位置
List<Integer> depthFirst = new ArrayList<>();
int max = 1;

private void dfs(TreeNode node, int depth, int id) {
    if (node == null) {
        return;
    }
    if (depthFirst.size() == depth - 1) {
        depthFirst.add(id);
    } else {
        max = Math.max(max, id - depthFirst.get(depth - 1) + 1);
    }
    dfs(node.left, depth + 1, id * 2);
    dfs(node.right, depth + 1, id * 2 + 1);
}

题目

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
// 96. 不同的二叉搜索树
public int numTrees(int n) {
    mentor = new int[n+1][n+1];
    return count(1, n);
}

int[][] mentor;
int count(int left, int right) {
    if (left >= right) {
        return 1;
    }

    if (mentor[left][right] != 0) {
        return mentor[left][right];
    }
    int ret = 0;
    for (int mid = left; mid <= right; mid++) {
        int leftNum = count(left, mid - 1);
        int rightNum = count(mid + 1, right);
        ret += leftNum * rightNum;
    }
    mentor[left][right] = ret;
    return ret;
}

// 95. 不同的二叉搜索树II，https://mp.weixin.qq.com/s/kcwz2lyRxxOsC3n11qdVSw
public List<TreeNode> generateTrees(int n) {
    if (n == 0) return new LinkedList<>();
    // 构造闭区间 [1, n] 组成的 BST
    return build(1, n);
}

/* 构造闭区间 [lo, hi] 组成的 BST */
List<TreeNode> build(int lo, int hi) {
    List<TreeNode> res = new LinkedList<>();
    // base case
    if (lo > hi) {
        res.add(null);
        return res;
    }

    // 1、穷举 root 节点的所有可能。
    for (int i = lo; i <= hi; i++) {
        // 2、递归构造出左右子树的所有合法 BST。
        List<TreeNode> leftTree = build(lo, i - 1);
        List<TreeNode> rightTree = build(i + 1, hi);
        // 3、给 root 节点穷举所有左右子树的组合。
        for (TreeNode left : leftTree) {
            for (TreeNode right : rightTree) {
                // i 作为根节点 root 的值
                TreeNode root = new TreeNode(i);
                root.left = left;
                root.right = right;
                res.add(root);
            }
        }
    }
    return res;
}

// 98. 验证二叉搜索树 - 后序遍历
boolean isValid = true;
public boolean isValidBST(TreeNode root) {
    dp(root);
    return isValid;
}
// 最小值和最大值
private int[] dp(TreeNode node) {
    int[] left = node.left == null ? new int[]{node.val, node.val} : dp(node.left);
    int[] right = node.right == null ? new int[]{node.val, node.val} : dp(node.right);
    if (!isValid) {
        return null;
    }
    if ((node.left != null && left[1] >= node.val) || (node.right != null && node.val >= right[0])) {
        isValid = false;
        return null;
    } else {
        return new int[]{left[0], right[1]};
    }
}

// 98. 验证二叉搜索树 - 先序遍历
public boolean isValidBST(TreeNode root) {
    return isValidBST(root, null, null);
}

/* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */
boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
    // base case
    if (root == null) return true;
    // 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
    if (min != null && root.val <= min.val) return false;
    if (max != null && root.val >= max.val) return false;
    // 限定左子树的最大值是 root.val，右子树的最小值是 root.val
    return isValidBST(root.left, min, root) && isValidBST(root.right, root, max);
}

题目

5、构造二叉树

题目

五、动态规划

方法

状态转移方程 + 状态压缩（可选）+ 正确遍历方向。

当有明显的一维/二维坐标规律移动，不是跳动的情况时，可以通过正向方式递推。否则使用自顶而下的递归更容易。如514. 自由之路不适合用正向。

1、01背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 518.零钱兑换
*/
public int change(int amount, int[] coins) {
    int n = coins.length;
    int[][] dp = new int[n + 1][amount + 1];
    // base case
    for (int i = 0; i <= n; i++) 
        dp[i][0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= amount; j++) {
            if (j - coins[i-1] >= 0) {
                // dp[i-1][j]不选择当前，dp[i][j-coins[i-1]]选择当前
                dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i-1]]; 
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[n][amount];
}

题目

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
// 855. 考场就坐
class ExamRoom {
    Queue<int[]> queue = new PriorityQueue<>((i1, i2) -> {
        int sub = distance(i2) - distance(i1);
        if (sub == 0) {
            return i1[0] - i2[0];
        } else {
            return sub;
        }
    });

    int n;
    Map<Integer, int[]> start = new HashMap<>();
    Map<Integer, int[]> end = new HashMap<>();

    public ExamRoom(int n) {
        this.n = n;
        // 开区间好运算
        queue.offer(new int[]{-1, n});
    }

    int distance(int[] interval) {
        int x = interval[0];
        int y = interval[1];
        if (x == -1) {
            return y;
        }
        if (y == n) {
            return n - 1 - x;
        }
        return (y - x) / 2;
    }

    void addInterval(int[] interval) {
        queue.offer(interval);
        start.put(interval[0], interval);
        end.put(interval[1], interval);
    }

    void delInterval(int[] interval) {
        queue.remove(interval);
        start.remove(interval[0]);
        end.remove(interval[1]);
    }

    public int seat() {
        int[] interval = queue.peek();
        int seat;
        if (interval[0] == -1) {
            seat = 0;
        } else if (interval[1] == n) {
            seat = n - 1;
        } else {
            seat = (interval[0] + interval[1]) / 2;
        }
        delInterval(interval);
        addInterval(new int[]{interval[0], seat});
        addInterval(new int[]{seat, interval[1]});
        return seat;
    }

    public void leave(int p) {
        int[] fromInterval = start.get(p);
        int[] toInterval = end.get(p);
        int[] merge = new int[]{toInterval[0], fromInterval[1]};
        delInterval(fromInterval);
        delInterval(toInterval);
        addInterval(merge);
    }
}

题目

七、算法

1、DIJKSTRA

题目

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
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] inbouds = new int[numCourses];
        List<Integer>[] srcTargetList = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            srcTargetList[i] = new ArrayList<>();
        }
        for (int[] pre : prerequisites) {
            inbouds[pre[0]]++;
            srcTargetList[pre[1]].add(pre[0]);
        }

        Queue<Integer> zeroInbounds = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (inbouds[i] == 0) {
                zeroInbounds.offer(i);
            }
        }

        int[] ret = new int[numCourses];
        int count = 0;
        while (!zeroInbounds.isEmpty()) {
            int cur = zeroInbounds.poll();
            ret[count++] = cur;
            for (int target : srcTargetList[cur]) {
                inbouds[target]--;
                if (inbouds[target] == 0) {
                    zeroInbounds.offer(target);
                }
            }
        }
        if (count == numCourses) {
            return ret;
        } else {
            return new int[]{};
        }
    }
}

题目

3、分治

题目

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
class UF {
    // 记录连通分量
    private int count;
    // 节点 x 的节点是 parent[x]
    private int[] parent;

    /* 构造函数，n 为图的节点总数 */
    public UF(int n) {
        // 一开始互不连通
        this.count = n;
        // 父节点指针初始指向自己
        parent = new int[n];
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;
        // 将两棵树合并为一棵
        parent[rootP] = rootQ;
        // parent[rootQ] = rootP 也一样
        count--; // 两个分量合二为一
    }

    /* 返回某个节点 x 的根节点 */
    private int find(int x) {
        // 根节点的 parent[x] == x
        while (parent[x] != x)
            x = parent[x];
        return x;
    }

    /* 返回当前的连通分量个数 */
    public int count() { 
        return count;
    }
}

优化版：

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
class UF {
    // 连通分量个数
    private int count;
    // 存储一棵树
    private int[] parent;
    // 记录树的「重量」
    private int[] size;

    // n 为图中节点的个数
    public UF(int n) {
        this.count = n;
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    // 将节点 p 和节点 q 连通
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;

        // 小树接到大树下面，较平衡
        if (size[rootP] > size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        } else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        // 两个连通分量合并成一个连通分量
        count--;
    }

    // 判断节点 p 和节点 q 是否连通
    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    // 返回节点 x 的连通分量根节点
    private int find(int x) {
        while (parent[x] != x) {
            // 进行路径压缩
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    // 返回图中的连通分量个数
    public int count() {
        return count;
    }
}

题目

5、贪心

题目

八、数学

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
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
// 772.计算器III
public int calculate(String s) {
    LinkedList<Character> list = new LinkedList<>();
    for (char c : s.toCharArray()) {
        list.add(c);
    }
    return dp(list);
}

private int dp(LinkedList<Character> list) {
    LinkedList<Integer> valueStack = new LinkedList<>();
    LinkedList<Character> signStack = new LinkedList<>();
    while (list.size() != 0) {
        char c = list.removeFirst();
        Integer val = null;
        if (c == '(') {
            val = dp(list);
        } else if (c == '+' || c == '-' || c == '*' || c == '/') {
            signStack.add(c);
        } else if (c == ')') {
            break;
        } else {
            val = 0;
            while (true) {
                val = val * 10 + (c - '0');
                if (list.size() != 0 && Character.isDigit(list.get(0))) {
                    c = list.removeFirst();
                } else {
                    break;
                }
            }
        }
        if (val == null) {
            continue;
        }

        valueStack.add(val);
        while (!signStack.isEmpty() && (signStack.getLast() == '*' || signStack.getLast() == '/')) {
            int num2 = valueStack.removeLast();
            int num1 = valueStack.removeLast();
            char signChar = signStack.removeLast();
            if (signChar == '*') {
                valueStack.add(num1 * num2);
            } else {
                valueStack.add(num1 / num2);
            }
        }
    }

    while (signStack.size() != 0) {
        char signChar = signStack.removeFirst();
        int num1 = valueStack.removeFirst();
        int num2 = valueStack.removeFirst();
        if (signChar == '+') {
            valueStack.push(num1 + num2);
        } else {
            valueStack.push(num1 - num2);
        }
    }
    return valueStack.get(0);
}

题目

2、随机数

题目

3、字典序

力求局部递增/递减 or 多叉树计算前缀根的节点数

题目

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
// 870.优势洗牌-田忌赛马  https://labuladong.gitee.io/algo/2/22/64/
public int[] advantageCount(int[] nums1, int[] nums2) {
    int n = nums1.length;
    // 给 nums2 降序排序
    PriorityQueue<int[]> maxpq = new PriorityQueue<>(
            (int[] pair1, int[] pair2) -> {
                return pair2[1] - pair1[1];
            }
    );
    for (int i = 0; i < n; i++) {
        maxpq.offer(new int[]{i, nums2[i]});
    }
    // 给 nums1 升序排序
    Arrays.sort(nums1);

    // nums1[left] 是最小值，nums1[right] 是最大值
    int left = 0, right = n - 1;
    int[] res = new int[n];

    while (!maxpq.isEmpty()) {
        int[] pair = maxpq.poll();
        // maxval 是 nums2 中的最大值，i 是对应索引
        int i = pair[0], maxval = pair[1];
        if (maxval < nums1[right]) {
            // 如果 nums1[right] 能胜过 maxval，那就自己上
            res[i] = nums1[right];
            right--;
        } else {
            // 否则用最小值混一下，养精蓄锐
            res[i] = nums1[left];
            left++;
        }
    }
    return res;
}

题目

5、脑筋急转弯

题目

九、编程细节

1、Integer类型用equals进行判断相等

2、Interger类型用Integer.compare方法进行比较，防止直接减溢出。

3、链表操作时，可增加一个空头节点，易处理第一个节点的删除情况。

评论

×