304. Range Sum Query 2D - Immutable
Posted Updated LeetCode / Medium3 minutes read (About 432 words)

304. Range Sum Query 2D - Immutable

Question

Given a 2D matrix matrix, handle multiple queries of the following type:

  • Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Implement the NumMatrix class:

  • NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.
  • int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Solution

前缀和/动态规划，用一个dp[][]数组记录到matrix[0][0]到matrix[i][j]区域的和。

计算两个点之间形成的总数只需用外侧的位置的前缀和加上内侧位置的前缀和，然后减去两者交换长宽位置的前缀和即可。

递推公式

计算dp[][]数组时，需要将其上侧与左侧所有数字加和，并加上matrix[][]上该位置对应的元素。
用dp[i][j-1] - dp[i-1][j-1]计算出左侧所有数字之和，dp[i-1][j]则是上侧所有数字之和。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class NumMatrix {
    int[][] dp;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        dp = new int[m+1][n+1];
        
        for(int i = 1; i <= matrix.length; i++){
            for(int j = 1; j <= matrix[0].length; j++){
                dp[i][j] = dp[i][j-1] - dp[i-1][j-1] + dp[i-1][j] + matrix[i-1][j-1];
            }
        };
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row1][col1] + dp[row2+1][col2+1] - dp[row1][col2+1] - dp[row2+1][col1];
    }
}

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

Solution 2

暴力搜索，直接计算从row1, col1到row2, col2的元素加和。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class NumMatrix {
    int[][] mat;
    public NumMatrix(int[][] matrix) {
        mat = matrix;
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for(int i = row1; i <= row2; i++){
            for(int j = col1; j <= col2; j++){
                sum += mat[i][j];
            }
        }
        return sum;
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */
867. Transpose Matrix
Posted Updated LeetCode / Easya few seconds read (About 107 words)

867. Transpose Matrix

Question

Given a 2D integer array matrix, return the transpose of matrix.

The transpose of a matrix is the matrix flipped over its main diagonal, switching the matrix’s row and column indices.

Solution

记录一个新数组res[][]。

双重循环，交换下标将matrix[i][j]复制到res[j][i]，最后返回。

Code

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int[][] transpose(int[][] matrix) {
        int[][] res = new int[matrix[0].length][matrix.length];
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                res[j][i] = matrix[i][j];
            }
        }
        return res;
    }
}
1480. Running Sum of 1d Array
Posted Updated LeetCode / Easya few seconds read (About 85 words)

1480. Running Sum of 1d Array

Question

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

Solution

类似动态规划，遍历数组，并将当前位置的元素和上一个位置的元素进行加和。

Code

1
2
3
4
5
6
7
8
class Solution {
    public int[] runningSum(int[] nums) {
        for(int i = 1; i < nums.length; i++){
            nums[i] += nums[i-1];
        }
        return nums;
    }
}
1461. Check If a String Contains All Binary Codes
Posted Updated LeetCode / Medium3 minutes read (About 396 words)

1461. Check If a String Contains All Binary Codes

Question

Given a binary string s and an integer k, return true if every binary code of length k is a substring of s. Otherwise, return false.

Solution

位运算+哈希表，用整数num记录二进制编码并加入哈希表中。
首先将字符串内的前k位二进制码转换为整数。并将其数值添加到哈希表内。

滑动窗口遍历，维持num为k长度内二进制码所对应的整数，并在遍历时将num加入哈希集合。
如果哈希集合的size达到k长度对应的可组合数，则返回true，否则返回false。

位运算与掩码

为了维护整数num，首先将其二进制编码向左移动一位。
然后与mask进行按位与运算，屏蔽掉多余的位数。

mask的值为k长度对应的可组合数-1。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean hasAllCodes(String s, int k) {
        if(s.length() < k) return false;    //字符串长度不足则返回false
        char[] bin = s.toCharArray();
        int n = s.length(), m = (int) Math.pow(2, k);
        HashSet<Integer> set = new HashSet<>(); //哈希表记录访问过的数字
        
        int num = Integer.parseInt(s.substring(0,k), 2);    //字符串以二进制转换为整数
        int mask = m-1; //掩码等于寻找长度-1
        set.add(num);
        
        for(int i = k; i < s.length(); i++){  //位运算，维护窗口内整数的值
            num <<= 1;  //位运算左移一位
            num &= mask;    //出界的位置被掩码遮盖
            if(bin[i] == '1') num++;
            set.add(num);
            if(set.size() == m) return true;    //如果哈希表长度等于2^k，则已经遍历了所有组合，返回true
        }
        return false;
    }
}
29. Divide Two Integers
Posted Updated LeetCode / Medium / 复习4 minutes read (About 619 words)

29. Divide Two Integers

Question

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Return *the quotient after dividing dividend by *divisor.

**Note: **Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2<sup>31</sup>, 2<sup>31</sup><span> </span>− 1]. For this problem, if the quotient is strictly greater than 2<sup>31</sup><span> </span>- 1, then return 2<sup>31</sup><span> </span>- 1, and if the quotient is strictly less than -2<sup>31</sup>, then return -2<sup>31</sup>.

Solution

解题思路类似于快速幂。

使用快速乘法来快速的获得商。

计算过程相当于：
60/8 = (60-32)/8 + 4 = (60-32-16)/8 + 2 + 4 = 1 + 2 + 4 = 7

需要注意的是由于只使用了整数（int）而不是长整数（long）储存数据，因此计算时需要处理各种溢出问题。

整数溢出

由于采用32位整数记录数字，负数要比正数的值范围大1。
因此当divisor为负数时，如果负数为整数最小值，则需要返回对应的整数最大值。

同时，为了在计算时防止整数溢出，因此将被除数与除数统一转为负数计算。（负数的数值比整数范围大）
当向下递归时，要保持dividend和divisor的正负性不变。

快速乘

只要被除数大于除数，则商至少为1。
循环，当被除数大于两倍的除数时，则商的结果可以直接翻倍。

否则将被除数减去当前的除数，然后向下递归新的被除数和除数。
最后返回快速乘中计算出的商加上向下递归返回的结果。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int divide(int dividend, int divisor) {
        if(dividend == 0) return 0;
        if(divisor == 1) return dividend;
        if(divisor == -1) return dividend == Integer.MIN_VALUE ? Integer.MAX_VALUE : -dividend; //当dividend为最小整数时，其负数溢出，此时返回Integer.MAX_VALUE
        int a = dividend, b = divisor;
        int sign = a > 0 && b > 0 || a < 0 && b < 0 ? 1 : -1;   //记录除数与被除数是否同号
        if(dividend > 0) a = -a;    //将除数与被除数转换为负数，因为负数能记录的数值比正数大1，防止溢出
        if(divisor > 0) b = -b;
        if(a > b) return 0; //被除数小于除数时返回0
        int res = 1;
        while(a <= b+b && b+b < 0){ //算法核心，快速乘法
            b += b; //除数每次翻倍，直到大于被除数
            res += res; //商的结果翻倍
        }
        res = sign == 1 ? res : -res;   //根据是否同号记录商
        
        divisor = dividend > 0 ? -divisor : divisor;  //当原有被除数是正数时，要将除数取反
        return res + divide(a-b, divisor);
    }
}
318. Maximum Product of Word Lengths
Posted Updated LeetCode / Medium / 复习2 minutes read (About 373 words)

318. Maximum Product of Word Lengths

Question

Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.

Solution

正常的思路可能是用哈希表保存字符串中出现过的字符。此时表的大小是26也是一个常数。

我们可以采用位运算进行状态压缩，通过一个整数的二进制位保存二十六个字符的存在状态。

状态压缩

我们采用一个整数数组bin[]储存状态压缩后的整数。

遍历每个字符串，在字符串中遍历每一个字符。
初始化整数bit为0。在遍历字符时计算当前字符与字符’a’距离的差n，然后将1左移n位，填入（或运算）整数bit中。

比较

遍历words[]中的两个字符串，当bin[i]与bin[j]进行与运算结果为0时，则两个字符串没有共同字符。
此时更新二者长度乘积的最大值max。

最后返回max即可。

时间复杂度：O(L + n2)。L为所有字符的总长度。

Code

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 maxProduct(String[] words) {
        
        int max = 0;
        int bin[] = new int[words.length];
        
        for(int i = 0; i < words.length; i++){
            int bit = 0;
            for(int j = 0; j < words[i].length(); j++){
                bit |= (1 << (words[i].charAt(j) - 'a'));
            }
            bin[i] = bit;
        }
        
        for(int i = 0; i < words.length; i++){
            for(int j = i+1; j < words.length; j++){
                if((bin[i] & bin[j]) == 0) max = Math.max(max, words[i].length() * words[j].length());
            }
        }
        return max;
    }
}
268. Missing Number
Posted Updated LeetCode / Easya minute read (About 220 words)

268. Missing Number

Question

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Solution 1

采用数学方法，从0到n的和减去从nums中的每个元素的和，得到的即是缺失的数字。
循环所有下标，每次在结果上加上下标的值，并减去下标对应的元素。最后需要再加上nums内元素数量+1的值。

Code

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int missingNumber(int[] nums) {
        int sum = nums.length;
        for(int i = 0; i < nums.length; i++){
            sum -= nums[i];
            sum += i;
        }
        
        return sum;
    }
}

Solution 2

遍历，采用一个数组found[]记录是否访问过。
再次遍历，如果存在未访问过的位置，则返回下标。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int missingNumber(int[] nums) {
        int res = 0;
        int[] found = new int[nums.length+1];
        for(int i = 0; i < nums.length; i++){
            found[nums[i]] = 1;
        }
        
        for(int i = 0; i <= nums.length; i++){
            if(found[i] == 0) res = i;
        }
        return res;
    }
}
1342. Number of Steps to Reduce a Number to Zero
Posted Updated LeetCode / Easya few seconds read (About 97 words)

1342. Number of Steps to Reduce a Number to Zero

Question

Given an integer num, return the number of steps to reduce it to zero.

In one step, if the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.

Solution

循环，当num不等于零时，如果为奇数则减一，如果为偶数则除以2。
每次循环记录次数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int numberOfSteps(int num) {
        int count =0;
        while(num != 0){
            count++;
            if((num & 1) == 0){
                num/=2;
            }
            else{
                num--;
            }
        }
        return count;
    }
}
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;
    }
}
474. Ones and Zeroes
Posted Updated LeetCode / Medium / 复习7 minutes read (About 1000 words)

474. Ones and Zeroes

Question

You are given an array of binary strings strs and two integers m and n.

Return the size of the largest subset of strs such that there are at most m 0‘s and n 1‘s in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

Solution 1

0-1背包问题的升级版。经典的背包问题只有一种容量，而这个问题实际等于有两种容量。

经典背包问题需要用二维数组动态规划，分别为物品和容量。
而这道题需要用三维数组动态规划，分别为字符串，0的容量和1的容量。

我们采用一个三维数组dp[i][j][k]保存可取最多物品的数量。
对于每个物品i，我们都可以取（数量+1）或不取（保持上一个物品的状态）。
j和k相当于分别记录了取“0”的总数和“1”的总数

遍历三个维度，并计算字符串中0和1的个数。

  • 如果当总容量大于当前物品中zeros和ones的数量，则可以取当前的物品。

    • 如果取当前的物品，则dp[]数组的总数等于上一个物品的状态加一，即dp[i-1][j-zeros][k-ones]。
    • 也可以不取当前的物品，则dp[]数组的总数直接保持上一个物品的状态。

  • 如果当前背包总容量小于zeros和ones的数量，则不能取当前物品。

    • 数组dp[]保持上一个物品的状态。

时间复杂度：O(lmn + L)，L是数组中所有字符串长度之和。
空间复杂度：O(lmn)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][][] dp = new int[strs.length+1][m+1][n+1];
        
        for(int i = 1; i <= strs.length; i++){
            int zeros = 0, ones = 0;
            for(char c : strs[i-1].toCharArray()){
                if(c == '0') zeros++;
                else ones++;
            }
            
            for(int j = 0; j <= m; j++){
                for(int k = 0; k <= n; k++){
                    if(j - zeros >= 0 && k - ones >=0) dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-zeros][k-ones] + 1);
                    else dp[i][j][k] = dp[i-1][j][k];
                }
            }
        }
        return dp[strs.length][m][n];
    }
}

Solution 2

由于dp[i][][]的上一个状态只涉及到dp[i-1][][]，因此我们可以采用滚动数组，去掉数组的一个维度，压缩空间。
此时需要从m到zeros，从n到ones倒序遍历，保证dp[i][][]转移过来的是dp[i-1][][]的元素。

此时的空间复杂度降低为O(mn)。

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 findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        
        for(String s : strs){   //记录每个位置对应的0和1数量
            int zeros = 0, ones = 0;
            for(char c : s.toCharArray()){
                if(c == '0') zeros++;
                else ones++;
            }
            
            for(int i = m; i >= zeros; i--){
                for(int j = n; j >= ones; j--){
                    dp[i][j] = Math.max(dp[i][j], dp[i-zeros][j-ones] + 1);
                }
            }
        }
        return dp[m][n];
    }
}

Solution 3

递归+记忆化搜索，保存并返回每个位置的最大长度。
如果位置越界则返回0。
如果memo[i][zero][one]不为0，则返回memo[i][zero][one]。

如果当前字符串的“0”和“1”的个数大于剩余的“0”和“1”的个数，则可以取当前字符串，递归下一个位置并加一。
也可以不取当前的字符串，递归下一个位置。当前位置memo[i][zero][one]等于两者中的最大值。

否则无法取当前字符串，直接递归下一个位置。当前位置等于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
class Solution {
    String[] s;
    int[] zeros, ones;
    int[][][] memo;
    public int findMaxForm(String[] strs, int m, int n) {
        s = strs;
        zeros = new int[strs.length];
        ones = new int[strs.length];
        memo = new int[strs.length][m+1][n+1];
        
        for(int i = 0; i < strs.length; i++){   //记录每个位置对应的0和1数量
            for(int j = 0; j < strs[i].length(); j++){
                if(s[i].charAt(j) == '0') zeros[i]++;
                else ones[i]++;
            }
        }
        return dfs(0, m, n);
    }
    
    private int dfs(int i, int zero, int one){
        if(i >= s.length){
            return 0;
        }
        if(memo[i][zero][one] != 0) return memo[i][zero][one];
        
        int maxPossibleSubset = 0;
        
        if(zero-zeros[i] >= 0 && one-ones[i] >= 0){
            maxPossibleSubset = 1 + dfs(i+1, zero-zeros[i], one-ones[i]);
        }
        memo[i][zero][one] = Math.max(maxPossibleSubset, dfs(i+1, zero, one));
        return memo[i][zero][one];
        
    }
}
647. Palindromic Substrings
Posted Updated LeetCode / Medium3 minutes read (About 404 words)

647. Palindromic Substrings

Question

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Solution

Manacher算法，与5. Longest Palindromic Substring的实现方法相同。

首先处理字符串。
然后采用中心拓展计算各个位置的拓展长度，并维护c与r。
每次遍历时计算结果，将当前可扩展长度加一然后除以二后加入结果。

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
class Solution {
    int n;
    int[] p;
    String newString;
    public int countSubstrings(String s) {
        n = s.length();
        StringBuffer sb = new StringBuffer();
        if(n == 0) {   //对字符串进行处理
            sb.append("^$");
        }
        else{
            sb.append("^");
            for(int i = 0; i < s.length(); i++){
                sb.append('#');
                sb.append(s.charAt(i));
            }
            sb.append("#$");
        }
        p = new int[sb.length()];
        newString = sb.toString();
        
        return manacher();
    }
    
    private int manacher(){
        int res = 0, c = 0, r = 0;
        for(int i = 1; i < newString.length()-1; i++){
            int m = 2 * c - i;
            if(i < r) p[i] = Math.min(r-i, p[m]);
            
            while(newString.charAt(i+p[i]+1) == newString.charAt(i-p[i]-1)){    //中心拓展
                p[i]++;
            }
            
            if(i+p[i] > r){ //更新c与r
                c = i;
                r = i + p[i];
            }
            res += (p[i]+1)/2;  //向上取整
        }
        return res;
    }
}

Solution 2

中心拓展，辅助方法count()用来计算每个字符可以组成的最大回文数。

注意每次需要计算奇数长度回文和偶数长度回文两种情况。
遍历所有字符并加和，返回总数。

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 {
    String word;
    public int countSubstrings(String s) {
        word = s;
        int ret = 0;
        for(int i = 0; i < s.length(); i++){
            ret+=count(i);
        }
        return ret;
    }
    
    private int count(int i){
        int count = 1, left = i-1, right = i+1;

        while(left >= 0 && right < word.length() && word.charAt(left) == word.charAt(right)){
            count++;
            left--;
            right++;
        }
        
        left = i;
        right = i+1;
        
        while(left >= 0 && right < word.length() && word.charAt(left) == word.charAt(right)){
            count++;
            left--;
            right++;
        }
        return count;
    }
}
63. Unique Paths II
Posted Updated LeetCode / Medium2 minutes read (About 235 words)

63. Unique Paths II

Question

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m-1][n-1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 10<sup>9</sup>.

Solution

机器人只朝向一个方向移动，不存在折返。
因此可以采用动态规划，直接记录到某个点的总路线数。
当遇到障碍时（即当前访问的格子为1）则不更新dp[]数组。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        
        int[][] dp = new int[m+1][n+1];
        dp[0][1] = 1;
        
        for(int x = 1; x < m+1; x++){
            for(int y = 1; y < n+1; y++){
                if(obstacleGrid[x-1][y-1] == 0){
                    dp[x][y] = dp[x][y-1] + dp[x-1][y];
                }
            }
        }
        return dp[m][n];
    }
}
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);
        }
    }
}
1379. Find a Node of a Binary Tree in a Clone Tree
Posted Updated LeetCode / Medium2 minutes read (About 234 words)

1379. Find a Node of a Binary Tree in a Clone Tree

Question

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

Solution

DFS搜索，同步递归original和cloned的子节点。
当在original里找到target的时候返回当前的cloned节点。

注意可以先判断一个分支中的返回值是否为空，如果不为空则直接返回。反之则返回另一个分支。这样操作可以进行一部分剪枝。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        if(original == null) return null;
        if(original.equals(target)) return cloned;
        
        TreeNode left = getTargetCopy(original.left, cloned.left, target);
        if(left != null) return left;
        else return getTargetCopy(original.right, cloned.right, target);
    }
}
Follow

Recents

Archives

Links

×