52. N-Queens II
Posted Updated LeetCode / Harda minute read (About 188 words)

52. N-Queens II

Question

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Solution

和昨天的题目51. N-Queens一样。
只是不需要转换并记录字符串了，递归结束时直接将res+1即可。

Code

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 {
    int target;
    int res;
    int[][] operations;
    public int totalNQueens(int n) {
        target = n;
        res = 0;
        operations = new int[][]{{-1,0},{-1,1},{-1,-1}};
        backtracking(new int[n][n], 0, 0);
        return res;
    }
    
    private void backtracking(int[][] board, int i, int n){
        if(n == target){
            res++;
            return;
        }
        for(int j = 0; j < target; j++){
            if(isValid(board, i, j)){
                board[i][j] = 1;
                backtracking(board, i+1, n+1);
                board[i][j] = 0;
            }
        }
    }
    
    private boolean isValid(int[][] board, int i, int j){
        for(int[] operation : operations){
            int p = i + operation[0], q = j + operation[1];
            while(p >= 0 && p < target && q >= 0 && q < target){
                if(board[p][q] == 1) return false;
                p += operation[0];
                q += operation[1];                
            }
        }
        return true;
    }
}
51. N-Queens
Posted Updated LeetCode / Hard / 复习5 minutes read (About 749 words)

51. N-Queens

Question

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Solution

话说今天出这道题真的不是搞事情嘛？

八皇后问题，回溯+剪枝。按顺序搜索可以减少情况的重复计算。
由于棋盘的大小为n * n，要放n个皇后，因此每一行（列）上都有且只有一位皇后。
我们可以依顺序逐行回溯，对逐行的每一列进行回溯。
由于每一行的可选位置都减少1，因此时间复杂度为O(N!)。

回溯

通过一个char数组board[][]记录棋子状态。将board[][]初始化为’.’。
遍历这一行的所有列，如果该位置有效，则board[i][j]改为’Q’，将这个点设置为有棋子，并递归下一行。
回溯，将board[i][j]重新设置为’.’。

当递归次数达到n时，将char[]数组转换为字符串加入答案。

辅助方法 isValid

检测该位置是否有效。即该位置的路径上是否已经有棋子，或该位置已经有棋子。
由于我们的回溯方法是逐行确定棋子位置，因此不需要查看全部八个方向，而是查看之前已经遍历过的行即可。

Code

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
class Solution {
    List<List<String>> ret;
    int size;
    int[][] operations;
    public List<List<String>> solveNQueens(int n) {
        ret = new ArrayList<>();
        size = n;
        operations = new int[][]{{-1,-1},{-1,1},{-1,0}};
        char[][] board = new char[n][n];
        for(char[] s : board){
            Arrays.fill(s,'.');
        }
        backtracking(board,0,0);
        return ret;
    }
    
    private void backtracking(char[][] board, int n, int i){
        if(n == size){
            List<String> ans = new ArrayList<>();
            for(char[] s : board) ans.add(new String(s));
            ret.add(ans);
            return;
        }

        for(int j = 0; j < size; j++){
            if(isValid(board, i, j)){
                board[i][j] = 'Q';
                backtracking(board, n+1, i+1);
                board[i][j] = '.';
            }
        }
    }
    
    private boolean isValid(char[][] board, int i, int j){
        for(int[] operation : operations){
            int p = i + operation[0];
            int q = j + operation[1];
            while(p >= 0 && p < size && q >= 0 && q < size){
                if(board[p][q] == 'Q') return false;
                p += operation[0];
                q += operation[1];
            }
        }
        return true;
    }
}

Solution 2

简单回溯。
在回溯时搜索二维位置，因此增加了时间复杂度，正常是过不了的。
通过按顺序进行搜索（只搜索当前行之后的位置）进行剪枝。

Code

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
class Solution {
    List<List<String>> ret;
    int size;
    int[][] operations;
    HashSet<String> set;
    public List<List<String>> solveNQueens(int n) {
        ret = new ArrayList<>();
        size = n;
        operations = new int[][]{{1,1},{1,-1},{1,0},{0,1},{0,-1}};
        backtracking(new int[n][n],0,0);
        return ret;
    }
    
    private void backtracking(int[][] border, int n, int start){
        if(n == size){
            //print(border);
            List<String> ans = new ArrayList<>();
            for(int i = 0; i < size; i++){
                StringBuffer sb = new StringBuffer();
                for(int j = 0; j < size; j++){
                    if(border[i][j] == 1){
                        sb.append("Q");
                    }
                    else{
                        sb.append(".");
                    }
                }
                ans.add(sb.toString());
            }
            ret.add(ans);
            return;
        }
        
        for(int i = start; i < size; i++){
            for(int j = 0; j < size; j++){
                if(border[i][j] == 0){
                    border[i][j] = 1;
                    List<int[]> temp = new ArrayList<>();
                    for(int[] operation : operations){
                        int p = i, q = j;
                        while(p >= 0 && p < size && q >= 0 && q < size){
                            if(border[p][q] == 0){
                                border[p][q] = 2;
                                temp.add(new int[]{p,q});
                            }
                            p += operation[0];
                            q += operation[1];
                        }
                    }
                    backtracking(border, n+1, i+1);
                    for(int[] t : temp){
                        border[t[0]][t[1]] = 0;
                    }
                    border[i][j] = 0;
                }
            }
        }
    }
}
354. Russian Doll Envelopes
Posted Updated LeetCode / Hard / 复习7 minutes read (About 979 words)

354. Russian Doll Envelopes

Question

You are given a 2D array of integers envelopes where envelopes[i] = [w<sub>i</sub>, h<sub>i</sub>] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope’s width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

Solution 1

最长递增子数列

这道题是LIS问题（Longest Increasing Subsequence） 的升级版。
后一个数组中的两个元素应该同时严格大于前一个数组中的两个元素。
因此我们需要维护一个宽度和高度同时严格单调递增的数列。

排序

我们可以对数组以宽度进行比较排序。当二者的宽度相等时，以高度的倒序排序。
（采用倒序排序是为了下面处理时排除不严格大于上一个数组的情况。）

递增数列

我们可以维护一个递增动态数组arr，记录高度组成的单调递增数列。（LIS）
首先将数组中的第一个元素的高度加入动态数组。
然后遍历数组envelopes[]：

  • 如果当前数组的高度height大于单调递增数列的最大值：
    • 则当前的数组的宽度和高度均严格大于数组中最后一个高度对应的数组。
    • 数组是优先以宽度的顺序排列，相等时以高度的倒序排列。由于相同宽度时高度大的在前，因此当当前高度大于之前的最大高度，则宽度也一定大于之前的最大宽度。
  • 如果小于或者等于单调递增数列的最大值：
    • 单调数列中高度的增长越平缓，我们在后面找到更多严格大于height的可能性就越大，因此可以用贪心思想，更新单调数列中的第一个大于当前高度的值。
    • 由于单调递增数列是有序的，因此可以采用二分搜索来寻找第一个大于当前高度的值的下标，并将其更新为当前的height。

排序的时间复杂度为O(nlogn)，遍历数组的时间复杂度为O(n)，二分搜索的时间复杂度为O(logn)。
总的时间复杂度为O(nlogn)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a,b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
        
        List<Integer> arr = new ArrayList<>();
        arr.add(envelopes[0][1]);
        for(int i = 1; i < envelopes.length; i++){
            int height = envelopes[i][1];
            if(height > arr.get(arr.size()-1)){
                arr.add(height);
            }
            else{
                int index = Collections.binarySearch(arr, height);
                if(index < 0) index = -index-1;
                arr.set(index, height);
            }
        }
        return arr.size();
    }
}

Solution 2

注意这个方法在LeetCode中会超时，仅仅是记录一下思路，也可以采用动态规划的方法。
记忆化搜索剪枝。
记忆化搜索每个envelope。

memorazation()方法，返回当前的envelope中可以包含的最大数量。
当数组memo[i]不等于0时，返回memo[i]。
否则初始化最大值max为1。
遍历数组中的所有元素，如果宽度于长度都大于envelopes[i]，则向下递归搜索该元素。
比较并更新max和递归结果的返回值+1。
最后将当前位置memo[i]设置为包含的最大数量max。

遍历所有元素时间复杂度O(n)。
记忆化搜索元素的子项时间复杂度O(n)。
时间复杂度为O(n2)。

Code

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 {
    int[][] dolls;
    int[] memo;
    
    public int maxEnvelopes(int[][] envelopes) {
        dolls = envelopes;
        memo = new int[dolls.length];
        int res = 0;
        for(int i = 0; i < dolls.length; i++){
            if(memo[i] != 0) continue;
            memorazation(i);
            res = Math.max(res, memo[i]);
        }
        return res;
    }
    
    private int memorazation(int i){
        if(memo[i] != 0){
            return memo[i];
        }
        int max = 1;
        for(int k = 0; k < dolls.length; k++){
            if(dolls[k][0] < dolls[i][0] && dolls[k][1] < dolls[i][1]){
                max = Math.max(max, memorazation(k) + 1);
            }
        }
        return memo[i] = max;
    }
}
32. Longest Valid Parentheses
Posted Updated LeetCode / Hard / 复习4 minutes read (About 611 words)

32. Longest Valid Parentheses

Question

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Solution

如果有右括号先出现于左括号，则其永远无法配对。
而如果是左括号先出现，则其有可能可以和之后的右括号进行配对。

因此我们可以将左括号的位置入栈，等待配对。
并记录上一个不能配对的右括号的位置。以此来确定当前位置的有效括号长度。

首先将上一个不能组队的右括号lastRightParenthese初始化为-1。
初始化一个最大有效长度best。

然后遍历字符串：

  • 当遇到左括号时：
    • 将当前下标i压入栈。（记录等待配对的左括号）
  • 遇到右括号时：
    • 如果栈为空，则更新上一个不能组队的右括号的位置为当前下标i。（此时出现的右括号一定无法配对）
    • 如果栈不为空，则挤出上一个左括号的下标，与右括号配对。
      • 挤出上一个左括号后，如果栈为空。则将当前的有效括号总长度为i - lastRightParenthese。（当前的右括号和上一个不能配对的右括号的差）
      • 否则当前的有效括号总长度为i - stack.peek()。（当前的右括号和上一个不配对的左括号的差。）

Code

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 int longestValidParentheses(String s) {
        Deque<Integer> stack = new LinkedList<>();
        int best = 0;
        int lastRightParenthese = -1;   //上一个不能配对的右括号位置，初始化为-1
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '('){ //如果当前位置是左括号，则将下标入栈
                stack.push(i);
            }
            else{   //如果当前位置是右括号...
                if(stack.isEmpty()){    //如果没有可以配对的左括号，则更新不能配对的右括号的位置
                    lastRightParenthese = i;
                }
                else{
                    stack.pop();    //如果有可以配对的右括号，则从栈中挤出
                    if(stack.isEmpty()){    //挤出后如果没有剩余的左括号了，则当前有效括号长度为当前位置减去上一个无法配对的右括号的位置
                        best = Math.max(best, i - lastRightParenthese);
                    }
                    else{   //如果挤出后栈内仍有剩余的左括号存在，则当前有效括号长度为当前位置减去栈顶的左括号的位置
                        best = Math.max(best, i - stack.peek());
                    }
                }
            }
        }
        return best;
    }
}
Posted Updated LeetCode / Hard / 复习6 minutes read (About 974 words)

2281. Sum of Total Strength of Wizards

Question

As the ruler of a kingdom, you have an army of wizards at your command.

You are given a 0-indexed integer array strength, where strength[i] denotes the strength of the i<sup>th</sup> wizard. For a contiguous group of wizards (i.e. the wizards’ strengths form a subarray of strength), the total strength is defined as the product of the following two values:

  • The strength of the weakest wizard in the group.
  • The total of all the individual strengths of the wizards in the group.

Return the sum of the total strengths of all contiguous groups of wizards. Since the answer may be very large, return it modulo 10<sup>9</sup><span> </span>+ 7.

A subarray is a contiguous non-empty sequence of elements within an array.

Solution

参考连接

根据题意，我们需要的结果是所有子数列乘以该子数列中最小值之和。

数组strength[]中的每一个元素，都充当一定范围内的子数列的最小值。因此我们需要**确定每个元素充当最小值的范围(left, right)**。然后计算这个元素可以组成的子数列的和与这个元素的乘积。

我们的问题相当于确定下一个更小元素，而单调栈专门处理这一类问题——“下一个更大/更小元素”
496. Next Greater Element I

通过单调栈，我们可以确定最小值为strength[i]的子数列的范围(left, right)，并将其保存在两个数组left[]与right[]中。

最后通过前缀和的计算，来确定(left, right)范围内的子数列之和。

单调栈

新建两个数组left[]， right[]保存以strength[i]为最小值的范围。

维护两个单调栈，保证下列关系：
strength[left] < strength[i]
strength[right] <= strength[i]

其中，left取小于号，而right可以等于是为了取值不重复。

注意，单调栈保存的是下标，这样使用起来更加灵活。

前缀和

为了得到范围（left, right）内的所有子数列之和。我们可以观察left, i, right之间的关系。

…left-1, left, left + 1, left + 2, … i-1, i, i+1, … right-1, right, right+1…

  • 开始于 left+1的子数列:
    sum(left+1, … i) = prefix[i + 1] - prefix[left + 1]
    sum(left+1, … i+1) = prefix[i + 2] - prefix[left + 1]
    …
    sum(left+1, … right-1) = prefix[right] - prefix[left + 1]
  • 开始于left+2的子数列:
    sum(left+2, … i) = prefix[i + 1] - prefix[left + 2]
    sum(left+2, … i+1) = prefix[i + 2] - prefix[left + 2]
    …
    sum(left+2, … right-1) = prefix[right] - prefix[left + 2]
    …
  • 开始于i的子数列:
    sum(i, … i) = prefix[i + 1] - prefix[i]
    sum(i, … i+1) = prefix[i + 2] - prefix[i]
    …
    sum(i, … right-1) = prefix[right] - prefix[i]

合并这些式子，我们可以得到：

  • 正数 部分:
    (prefix[i + 1] + prefix[i + 2] + ... + prefix[right]) * (i - left)
  • 负数 部分:
    (prefix[left + 1] + prefix[left + 2] + ... + prefix[i]) * (right - i)

最后我们可以提前计算前缀和的前缀和来优化计算步骤，注意计算时需要将各个部分模除以保证不超过范围。
正数部分模除后需要加上MOD以保证其减去负数部分的结果大于0。

Code

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
class Solution {
    public int totalStrength(int[] strength) {
        long MOD = 1_000_000_007;
        int n = strength.length;
        
        Deque<Integer> mono = new ArrayDeque<>();
        int[] left = new int[n], right = new int[n];
        
        for(int i = 0; i < strength.length; i++){   //单调栈，记录比当前元素strength[i]小的第一个左侧位置strength[left]
            while(!mono.isEmpty() && strength[mono.peek()] >= strength[i]){
                mono.pop();
            }
            left[i] = mono.isEmpty() ? -1 : mono.peek();
            mono.push(i);
        }
        mono.clear();
        for(int i = n-1; i >=0; i--){   //单调栈，记录比当前元素strength[i]小的第一个右侧位置strength[right]
            while(!mono.isEmpty() && strength[mono.peek()] > strength[i]){
                mono.pop();
            }
            right[i] = mono.isEmpty() ? n : mono.peek();
            mono.push(i);
        }
        
        long[] prefix = new long[n+1], prefix_sum = new long[n+2];
        
        for(int i = 1; i <= strength.length; i++){  //计算前缀和
            prefix[i] = (prefix[i-1] + strength[i-1]) % MOD;
        }
        
        for(int i = 2; i <= strength.length+1; i++){    //计算前缀和的前缀和
            prefix_sum[i] = (prefix_sum[i-1] + prefix[i-1]) % MOD;
        }
        
        long res = 0;
        
        for(int i = 0; i < n; i++){
            res += ((prefix_sum[right[i] + 1] - prefix_sum[i + 1]) * (i - left[i]) % MOD + MOD -    //这里加MOD是为了保证前项大于后项，防止出现负数
                    (prefix_sum[i + 1] - prefix_sum[left[i] + 1]) * (right[i] - i) % MOD ) * strength[i];
            res %= MOD;
        }
        
        return (int) res;
    }
}
Posted Updated LeetCode / Hard / 复习3 minutes read (About 488 words)

329. Longest Increasing Path in a Matrix

Question

Given an m x n integers matrix, return *the length of the longest increasing path in *matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

Solution

第一次就通过DFS和DP的知识自己摸索出了记忆化搜索，非常开心！: )

记忆化搜索，采用DFS搜索，并动态规划的思想保存搜索结果。

递归计算从x, y点出发的最大长度，并在递归中记录子位置的最大长度。
通过子位置的最大长度对递归树进行剪枝。

记忆化搜索

初始化一个memo[][]数组，记录已经搜索过的x, y位置的最大长度。
对所有下一个位置进行DFS搜索，如果越界或不满足递增规律，则返回最大长度1。
（这里应该返回0，但是为了下一步的记忆化搜索判断的遍历因此返回1。如果返回0的话则后面返回最大值不需要-1，但此时由于会重复搜索因此速度会降低。）

如果x, y的位置已经搜索过了（即memo[x][y] != 0），则直接返回memo[x][y]的值+1。

搜索完所有位置的最大长度，将其中的最大值保存在memo[][]中。
最后返回最大值+1。

将每个位置遍历，返回memo[][]中的最大值。

Code

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 {
    int[][] mat, memo, moves = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int m, n, max;
    
    public int longestIncreasingPath(int[][] matrix) {
        mat = matrix;
        m = matrix.length;
        n = matrix[0].length;
        memo = new int[m][n];
        
        max = 0;
        for(int x = 0; x < m; x++){
            for(int y = 0; y < n; y++){
                dfs(x, y, -1);
                max = Math.max(max, memo[x][y]);
            }
        }
        return max;
    }
    
    private int dfs(int x, int y, int parent){
        if(x < 0 || y < 0 || x >= m || y >= n || parent >= mat[x][y]) return 1;
        if(memo[x][y] != 0) return memo[x][y] + 1;
        int best = 0;
        for(int[] move : moves){
            int count = dfs(x + move[0], y + move[1], mat[x][y]);
            best = Math.max(best, count);
        }
        memo[x][y] = best;
        return best + 1;
    }
}
1192. Critical Connections in a Network
Posted Updated LeetCode / Hard / 复习4 minutes read (About 544 words)

1192. Critical Connections in a Network

Question

There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [a<sub>i</sub>, b<sub>i</sub>] represents a connection between servers a<sub>i</sub> and b<sub>i</sub>. Any server can reach other servers directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network in any order.

Solution

参考：# 60 分钟搞定图论中的 Tarjan 算法

根据connections建立图（采用数组记录图速度比用哈希表实现快）。
然后采用Tarjon算法寻找图中的桥。

时间戳

按访问顺序为数组dfn[]添加顺序。
(dfn = depth first (traversal) number)

搜索树

在无向图中，每一次从u节点出发进行DFS搜索，每个节点只访问一次，所有被访问过的节点与边构成一棵树，称之为“无向连通图的搜索树”

追溯值

数组low[]记录从当前节点u出发时，能够访问到的所有节点中，时间戳最小的值。

无向图的桥的判定法则

在一张无向图中，判断边 e （其对应的两个节点分别为 u 与 v）是否为桥，需要其满足如下条件即可：dfn[u] < low[v]

Code

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
class Solution {
    int num;
    int[] visited;
    int[] dfn;
    int[] low;
    List<List<Integer>> ret;
    List<Integer>[] graph;
    
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        num = 0;
        ret = new ArrayList<>();
        visited = new int[n];
        dfn = new int[n];
        low = new int[n];
        graph = new ArrayList[n];
        
        buildGraph(n, connections);
        tarjan(0, -1);
        
        return ret;

    }
    
    private void tarjan(int u, int parent){
        dfn[u] = low[u] = num++;    //记录节点遍历的顺序并初始化low值
        visited[u] = 1;
        for(Integer v : graph[u]){
            if(v == parent) continue;
            if(visited[v] == 0){    //搜索未搜索过的相邻节点
                tarjan(v, u);
                low[u] = Math.min(low[u], low[v]);  //搜索相邻节点后，更新访问的最小值
                if(dfn[u] < low[v]){    //满足桥的定义时添加结果
                    List<Integer> e = new ArrayList<>();
                    e.add(u);
                    e.add(v);
                    ret.add(e);
                }
            }
            else{
                low[u] = Math.min(low[u], dfn[v]);  //如果搜索过相邻节点，则判断这两个值得最小值并更新
            }
        }
    }
    
    private void buildGraph(int n, List<List<Integer>> connections){
        for(int i = 0; i < n; i++){
            graph[i]=new ArrayList<>();
        }
        
        for(List<Integer> e : connections){
            int v1 = e.get(0);
            int v2 = e.get(1);
            graph[v1].add(v2);
            graph[v2].add(v1);
        }
    }
}
149. Max Points on a Line
Posted Updated LeetCode / Hard / 复习3 minutes read (About 423 words)

149. Max Points on a Line

Question

Given an array of points where points[i] = [x<sub>i</sub>, y<sub>i</sub>] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Solution

首先选取一个点，然后创建哈希表。记录这个点与其他点的斜率关系与出现次数。记录一个出现次数最多的max值，如果当前次数大于max则更新max。

注意计算斜率时对y == 0和 x == 0时要返回无穷大和0，否则会有精度问题。
最后返回max + 1。

可以优化的地方是，当max大于总点数的一半，或者max大于剩余的点时，因为已经找到了最大的max值，可以直接返回答案。

Code

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 maxPoints(int[][] points) {
        int n = points.length;
        if(n == 1) return 1;
        else if(n == 2) return 2;
        int max = 0;
        
        for(int i = 0; i < points.length; i++){
            if(max > points.length / 2) break;
            if(max > points.length - i) break;
            HashMap<Double, Integer> map = new HashMap<>();
            
            for(int j = i+1; j < points.length; j++){
                double k = getSlope(points[i], points[j]);
                int count = map.getOrDefault(k, 0) + 1;
                max = Math.max(max, count);
                map.put(k, count);
            }
        }
        return max + 1 ;
        
    }
    
    private double getSlope(int[] p1, int[] p2){
        double x1 = p1[0], y1 = p1[1], x2 = p2[0], y2 = p2[1];
        if(y1-y2 == 0) return Double.MAX_VALUE;
        if(x1-x2 == 0) return 0;
        double k = (x1 - x2) / (y1 - y2);
        return k;
    }
}

叉乘计算可以判断两个向量是否重合。
由于叉乘乘积（$|a||b|sinθ$）的模等于两个向量组成的平行四边形的面积，因此当两者乘积为0时，则两个向量重合。



点乘乘积得到的是向量在另一个向量上的投影的乘积，$|a||b|cosθ$

297. Serialize and Deserialize Binary Tree
Posted Updated LeetCode / Hard4 minutes read (About 589 words)

297. Serialize and Deserialize Binary Tree

Question

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Solution

编码过程

编码时采用BFS搜索，将二叉树按层级组成字符串。
当当前节点不等于null时，添加当前节点的值和一个符号。
然后将其左右子节点加入队列。
当当前节点为null时，添加一个非数字字符和一个符号。

解码过程

解码时同样采用BFS搜索，按层级恢复二叉树。
首先将字符串根据符号进行分割，变为字符串数组。
如果第一个字符表示为null，返回null。

否则将第一个数字组成根节点并加入队列。创建一个指针i记录位置。
当队列不为空，且指针i未越界时，根据指针i上的字符串创建当前节点的左子节点。
将指针右移，如果没有越界则创建当前节点的右子节点，然后将指针右移。

Code

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder data = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode curr = q.poll();
            if(curr == null) data.append("n,");
            else {
                data.append(curr.val + ",");
                q.add(curr.left);
                q.add(curr.right);
            }
        }
        return data.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] values = data.split(",");
        if(values[0].equals("n")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int i = 1;     
        while(!q.isEmpty() && i < values.length){
            TreeNode curr = q.poll();
            curr.left = values[i].equals("n") ? null : new TreeNode(Integer.parseInt(values[i]));
            if(i++ < values.length) curr.right = values[i].equals("n") ? null : new TreeNode(Integer.parseInt(values[i]));
            if(curr.left != null) q.add(curr.left);
            if(curr.right != null) q.add(curr.right);
            i++;
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
72. Edit Distance
Posted Updated LeetCode / Hard2 minutes read (About 331 words)

72. Edit Distance

Question

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

  • Insert a character
  • Delete a character
  • Replace a character

Solution

本题和583. Delete Operation for Two Strings大同小异。

动态规划，两个字符串的分别以长宽组成一个矩阵，记录该位置得编辑距离。
将初始的编辑距离dp[i][0]一行和dp[0][j]一列按照对应的位置i和j填写。

双重遍历矩阵的坐标。
当两个字符相等时，编辑距离等于对角线方向的状态的编辑距离（即两个字符都没有取得上一个状态）。
当两个字符不相等时，编辑距离等于左边，上边（少取一个字符的状态）以及对角线方向（两个字符都不取的状态）的编辑距离中得最小值再加上1。

Code

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 int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        char[] bin1 = word1.toCharArray();
        char[] bin2 = word2.toCharArray();
        int[][] dp = new int[m+1][n+1];
        
        for(int i = 0; i <= m; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= n; j++){
            dp[0][j] = j;
        }
        
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(bin1[i-1] == bin2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }
                else{
                    dp[i][j] = Math.min(dp[i-1][j-1] + 1, Math.min(dp[i-1][j], dp[i][j-1]) + 1);
                }
            }
        }
        return dp[m][n];
    }
}
Posted Updated LeetCode / Hard / 复习3 minutes read (About 474 words)

25. Reverse Nodes in k-Group

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

采用直接更改节点的方法可以使用O(1)的空间完成操作。

递归，DFS搜索，首先初始化一个哨兵节点。
将哨兵节点记录为first，下一个节点记录为second。

将first与second传入递归方法。
向下递归下一个节点，并将长度k-1。
当长度k等于1时，则递归到当前所需的栈底。将当前节点指向上一个节点，并将当前节点记录为last，下一个节点记录为next，返回true。
当curr为null时，返回false。

当递归返回为true时（即剩余的链表有k个节点以供翻转），上级的节点们都指向其前一个节点。当返回到的栈顶（即k等于最开始的值）时，将first指向last，将second指向next。

继续向下递归first与second。

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
/**
 * 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 {
    int K;
    ListNode next;
    ListNode prev;
    ListNode last;
    ListNode first;
    ListNode second;
    public ListNode reverseKGroup(ListNode head, int k) {
        if(k == 1) return head;
        
        K = k;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        prev = dummy;
        next = null;
        last = null;
        first = prev;
        second = prev.next;
        
        reverse(prev, dummy.next, k);
        
        return dummy.next;
    }
    
    private boolean reverse(ListNode prev, ListNode curr, int k){
        if(curr == null) return false;
        if(k == 1){
            last = curr;
            next = curr.next;
            curr.next = prev;
            return true;
        }
        
        if( reverse(curr, curr.next, k-1) ){
            curr.next = prev;
            if(k == K){
                first.next = last;
                second.next = next;
                first = curr;
                second = curr.next;
            
                reverse(first, second, k);
            }
            return true;
        }
        return false;
    }
    
    private void print(ListNode root){
        while(root != null){
            root = root.next;
        }
    }
}
Follow

Recents

Archives

Links

×