Category: 复习

Posted 2022-09-11Updated 2022-09-11LeetCode / Hard / 复习2 minutes read (About 349 words)

Question

You are given two integers n and k and two integer arrays speed and efficiency both of length n. There are n engineers numbered from 1 to n. speed[i] and efficiency[i] represent the speed and efficiency of the ith engineer respectively.

Choose at most k different engineers out of the n engineers to form a team with the maximum performance.

The performance of a team is the sum of their engineers’ speeds multiplied by the minimum efficiency among their engineers.

Return the maximum performance of this team. Since the answer can be a huge number, return it modulo 109 + 7.

Solution

排序，将所有工程师根据其效率降序排列。

此时遍历时后一个工程师的效率一定小于等于前一个工程师。

因此，此时遍历到每一个工程师，其前面所有的工程师的efficiency均大于等于其本身。
维护一个所有选取工程师的总速度ttSpd，每次计算并更新max的值。
用最小堆来维护选取的工程师速度，如果优先级队列的尺寸超过k-1，则poll掉队列内最低的速度。

Code

class Solution {
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        final int mod = (int) Math.pow(10, 9) + 7;
        int[][] engineer = new int[n][2];
        
        for(int i = 0; i < n; i++){
            engineer[i][0] = speed[i];
            engineer[i][1] = efficiency[i];
        }
        
        Arrays.sort(engineer, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return b[1] - a[1];
            }
        });
        
        long max = 0, ttSpd = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i = 0; i < n; i++){
            int s = engineer[i][0], e = engineer[i][1];
            ttSpd += s;
            max = Math.max(max, ttSpd * e);
            pq.add(s);
            if(pq.size() == k) ttSpd -= pq.poll();
        }
        
        return (int) (max % mod);
    }
}

Posted 2022-08-27Updated 2022-08-27LeetCode / Hard / 复习2 minutes read (About 231 words)

363. Max Sum of Rectangle No Larger Than K

Question

Given an m x n matrix matrix and an integer k, return the max sum of a rectangle in the matrix such that its sum is no larger than k.

It is guaranteed that there will be a rectangle with a sum no larger than k.

Solution

前缀和，计算矩阵中每个位置对应的方形的和。
遍历方形的两个对角线上的点。
其面积等于大块加小块的面积减去两个长方形的面积。
如果面积有小于k的，则记录其最大值并返回。

Code

class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int x = matrix.length, y = matrix[0].length, max = Integer.MIN_VALUE;
        int[][] sum = new int[x+1][y+1];
        
        for(int i = 1; i <= x; i++){
            int total = 0;
            for(int j = 1; j <= y; j++){
                total += matrix[i-1][j-1];
                sum[i][j] = sum[i-1][j] + total;
            }
        }
 
        for(int i = 0; i <= x; i++){
            for(int j = 0; j <= y; j++){
                for(int m = i + 1; m <= x; m++){
                    for(int n = j + 1; n <= y; n++){
                        int area = sum[m][n] + sum[i][j] - sum[m][j] - sum[i][n];
                        if(area <= k) max = Math.max(max, area);
                    }
                }
            }
        }
        return max;
    }
}

Posted 2022-07-04Updated 2022-07-04LeetCode / Hard / 复习2 minutes read (About 227 words)

135. Candy

Question

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.

Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Solution

双向遍历。
先从左至右遍历数组，如果上一个数值小于当前数值，则当前糖果等于上一个糖果数+1。
然后从右至左遍历数组，同理计算right的数值。
然后保存right与left[]里较大的数值，作为需要分配的糖果数加入到res。

Code

class Solution {
    public int candy(int[] ratings) {
        int[] left = new int[ratings.length];
        for(int i = 0; i < ratings.length; i++){
            if(i > 0 && ratings[i] > ratings[i-1]){
                left[i] = left[i-1] + 1;
            }
            else{
                left[i] = 1;
            }
        }
        
        int right = 0, res = 0;
        for(int i = ratings.length-1; i >= 0; i--){
            if(i < ratings.length-1 && ratings[i] > ratings[i+1]){
                right++;
            }
            else{
                right = 1;
            }
            res += Math.max(left[i], right);
        }
        return res;
    }
}

Posted 2022-06-26Updated 2022-06-25LeetCode / Hard / 复习3 minutes read (About 449 words)

2318. Number of Distinct Roll Sequences

Question

You are given an integer n. You roll a fair 6-sided dice n times. Determine the total number of distinct sequences of rolls possible such that the following conditions are satisfied:

The greatest common divisor of any adjacent values in the sequence is equal to 1.

There is at least a gap of 2 rolls between equal valued rolls. More formally, if the value of the ith roll is equal to the value of the jth roll, then abs(i - j) > 2.

Return the* total number** of distinct sequences possible*. Since the answer may be very large, return it modulo 109 + 7.

Two sequences are considered distinct if at least one element is different.

Solution

DFS+记忆化搜索剪枝。
辅助方法getValidNext计算前两个位置为last1和last2时的所有的下一个有效值，将返回值储存在next[][]数组中。

DFS搜索

DFS搜索，传入剩余骰子数量n，前两个骰子的值x和y。
从next[x][y]中得到所有有效值。并进行递归。
将返回结果加和并返回。
当n等于0时，只有一个组合，因此返回1。

记忆化搜索

在搜索时会重复计算很多相同的x，y与n的组合，因此可以采用记忆化搜索进行剪枝。
用memo[][][]数组记录x，y与n的状态。如果此前已经计算过其结果，则直接返回memo[x][y][n]。

Code

class Solution {
    List<Integer>[][] next;
    int[][][] memo;
    public int distinctSequences(int n) {
        next = new ArrayList[7][7];
        for(int i = 0; i <= 6; i++){
            for(int j = 0; j <= 6; j++){
                next[i][j] = getValidNext(i, j);
            }
        }
        memo = new int[7][7][10001];
        return count(n, 0, 0);
    }
    
    private int count(int n, int x, int y){
        if(n == 0) return 1;
        if(memo[x][y][n] != 0) return memo[x][y][n];
        List<Integer> validNext = next[x][y];
        int sum = 0;
        for(int z : validNext){
            sum += count(n-1, y, z);
            sum %= 1000000007;
        }
        memo[x][y][n] = sum;
        return sum;
    }
    
    private List<Integer> getValidNext(int last1, int last2){
        List<Integer> arr = new ArrayList<>();
        for(int i = 1; i <= 6; i++){
            if(last1 == 0 && last2 == 0) arr.add(i);
            else if(i == last1 || i == last2) continue;
            else if((last2 & 1) == 0 && (i & 1) == 0) continue;
            else if((last2 == 3 || last2 == 6) && (i == 3 || i == 6)) continue;
            else arr.add(i);
        }
        return arr;
    }
}

Posted 2022-06-24Updated 2022-06-24LeetCode / Hard / 复习2 minutes read (About 335 words)

630. Course Schedule III

Question

There are n different online courses numbered from 1 to n. You are given an array courses where courses[i] = [durationi, lastDayi] indicate that the ith course should be taken continuously for durationi days and must be finished before or on lastDayi.

You will start on the 1st day and you cannot take two or more courses simultaneously.

Return the maximum number of courses that you can take.

Solution

贪心算法，优先级队列实现。
优先选择截止日期更短的课程。
优先级队列pq记录当前已选课程，按持续时间从长到短排列。
同时维护当前的日期curDay。

当当前选择的课程截止日期晚于curDay加上当前的持续时间duration时，查看大根堆里最长的课程longestDuration。如果最长的时间大于当前时间，则将其挤出，并将当前课程加入。

如果当前课程截止日期晚于curDay，则直接将其加入队列中，并更新curDay。

Code

class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        int curDay = 0;
        for(int[] course : courses){
            int duration = course[0];
            int lastDay = course[1];
            
            if(curDay + duration > lastDay){    //大于截止日期
                if(pq.isEmpty()) continue;
                int longestDuration = pq.peek()[0];
                if(longestDuration > duration){ //替换到当前队列中持续日期最长的课程
                    curDay -= pq.poll()[0];
                    curDay += duration;
                    pq.offer(course);
                }
            }
            else{   //小于截止日期则加入选课
                curDay += duration;
                pq.offer(course);
            }
        }
        return pq.size();
    }
}

Posted 2022-06-04Updated 2022-06-05LeetCode / 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

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

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;
                }
            }
        }
    }
}

Posted 2022-05-25Updated 2022-09-11LeetCode / Hard / 复习7 minutes read (About 979 words)

354. Russian Doll Envelopes

Question

You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] 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

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

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;
    }
}

Posted 2022-05-24Updated 2022-05-25LeetCode / 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

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 2022-05-22Updated 2022-05-22LeetCode / 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 ith 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 109 + 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

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 2022-05-19Updated 2022-05-19LeetCode / 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

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;
    }
}

Posted 2022-05-18Updated 2022-05-18LeetCode / 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] = [ai, bi] represents a connection between servers ai and bi. 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

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);
        }
    }
}

Posted 2022-05-06Updated 2022-05-07LeetCode / Hard / 复习3 minutes read (About 423 words)

149. Max Points on a Line

Question

Given an array of points where points[i] = [xi, yi] 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

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θ$

Posted 2022-04-28Updated 2022-04-28LeetCode / 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。

/**
 * 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;
        }
    }
}

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

DFS搜索

记忆化搜索

Code

Question

Solution

Code

Question

Solution

回溯

辅助方法 isValid

Code

Solution 2

Code

Question

Solution 1

最长递增子数列

排序

递增数列

Code

Solution 2

Code

Question

Solution

Code

Question

Solution

单调栈

前缀和

Code

Question

Solution

记忆化搜索

Code

Question

Solution

时间戳

搜索树

追溯值

无向图的桥的判定法则

Code

Question

Solution

Code

Recents

Archives

Links