Category: 复习

Posted 2022-06-11Updated 2022-06-10LeetCode / Medium / 复习2 minutes read (About 367 words)

1658. Minimum Operations to Reduce X to Zero

Question

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.

Return *the minimum number of operations to reduce x to exactly 0 if it is possible, otherwise, return *-1.

Solution

将原有问题的从两边减去一定的值，寻找加和为x的问题转换为寻找滑动窗口中的总和为total - x的新问题。

滑动窗口

初始化当前窗口内的sum，左侧指针left与右侧指针right。
每次将一个新的元素nums[right]加入窗口范围。

当当前的sum大于寻找的target，则将nums[left]滑出窗口，更新left与sum的值。

如果当前窗口内的sum等于寻找的target，则更新记录最小操作次数的min。

Code

class Solution {
    public int minOperations(int[] nums, int x) {
        int total = 0, min = Integer.MAX_VALUE;
        for(int num : nums){
            total += num;
        }
        int target = total - x; //将减去两侧元素并寻找和为x的结果的问题转换为用滑动窗口寻找total - x的结果。
        int sum = 0, left = 0, right = 0;
        while(right < nums.length){
            sum += nums[right]; //调整右侧范围，加入新元素到窗口
            right++;
            
            while(left < right && sum > target){ //如果窗口内的和大于目标，则调整左侧范围
                sum -= nums[left];
                left++;
            }
            if(sum == target){   //如果窗口内的和等于目标，则更新最小操作次数
                min = Math.min(min, nums.length - (right - left));
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
}

Posted 2022-05-31Updated 2022-05-31LeetCode / 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: [−231, 231 − 1]. For this problem, if the quotient is strictly greater than 231 - 1, then return 231 - 1, and if the quotient is strictly less than -231, then return -231.

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

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

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

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

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

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

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

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

Posted 2022-05-15Updated 2022-05-14LeetCode / Medium / 复习5 minutes read (About 773 words)

743. Network Delay Time

Question

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Solution

Dijkstra算法

此题可以转化为求起始节点到最远距离的节点的距离。单源最短路径问题，可以采用Dijkstra算法。

采用一个visited[]数组记录初始节点的访问状况。
同时dist[]数组记录到达这一节点的最小距离，初始化为无限大。

进行BFS搜索，每次优先访问当前节点的子节点的最近子节点，并更新子节点与初始节点距离。
最后遍历dist[]数组，如果有元素仍为无限大，则BFS搜索未遍历到，返回-1。
否则返回数组内最大的距离即可。

建立映射

首先通过哈希表，将起始节点与有向边建立起映射关系。列表中储存子节点和对应边上的权值。
注意由于index是-1的，因此在组成列表时需要将当前数字减一。

优先级队列

采用优先级队列组成小根堆，每次将当前的最小距离作为权值加入队列。
初始化队列时需要将起始节点（k-1）放入，此时的总距离为0。

当当前的子节点的cost加上起始节点的距离小于子节点的最小距离时，更新子节点最小距离。
同时将子节点当前最小距离作为比较对象传入优先级队列。

Code

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        HashMap<Integer, List<int[]>> edges = new HashMap<>(); 
        
        for(int[] time : times){    //建立有向边
            int source = time[0] - 1, kid = time[1] - 1, cost = time[2];    //注意index需要-1
            List<int[]> list = edges.getOrDefault(source, new ArrayList<>());
            list.add(new int[]{kid, cost});    //建立起点——终点映射
            edges.put(source, list);
        }
        
        int[] visited = new int[n];
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[1] - b[1]);    //优先级队列，最小堆每次访问距离最近的节点
        
        int start = k-1;
        dist[start] = 0;
        pq.offer(new int[]{start, 0});  //start为初始节点，后面的距离为了实现优先级队列
        
        while(!pq.isEmpty()){
            int[] curr = pq.poll();
            int source = curr[0];

            if(visited[source] == 1) continue;
            visited[source] = 1;
            
            List<int[]> children = edges.getOrDefault(source, new ArrayList<>());   //获取当前起点的所有边
            for(int[] child : children){
                int kid = child[0], cost = child[1];
                
                if(cost + dist[source] < dist[kid]){    //如果新的距离小于之前的最小距离，则更新距离并将新的起点加入优先级队列
                    dist[kid] = cost + dist[source];
                    pq.offer(new int[]{kid, dist[kid]});    //更新的距离是从出发节点到当前节点的距离，每次优先访问最近的节点
                }
            }
        }
        
        int res = 0;
        
        for(int d : dist){  //最后遍历，距离的最大值就是结果
            res = Math.max(res, d);
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

Posted 2022-05-11Updated 2022-05-12LeetCode / Medium / 复习2 minutes read (About 262 words)

1641. Count Sorted Vowel Strings

Question

Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

Solution

动态规划，创建数组dp[]记录以每个字符开头能组成的字符串数量。
由于当长度为1时，每个字符串都能组成一次，因此初始化所有值为1。

n增长时，每一个层级都等于该字符后的所有值相加。
最后得出的结果在下一个层级的第一位。（因为第一位是所有上一个层级加和）

Code

class Solution {
    public int countVowelStrings(int n) {
        int[] dp = new int[]{1,1,1,1,1};
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 5; j++){
                for(int k = j+1; k < 5; k++){
                    dp[j] += dp[k];
                }
            }
        }
        return dp[0];
    }
}

Solution

递归，使用成员变量计算有效递归次数。

Code

class Solution {
    int count;
    public int countVowelStrings(int n) {
        count = 0;
        count(n, 0);
        return count;
    }
    
    private void count(int n, int start){
        if(n == 0){
            count++;
            return;
        }
        for(int i = start; i < 5; i++){
            count(n-1, i);
        }
    }
}

Posted 2022-05-08Updated 2022-05-07LeetCode / Medium / 复习3 minutes read (About 404 words)

456. 132 Pattern

Question

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

Solution

单调栈，专门用于找某一个元素的左边/右边第一个比自己大/小的位置。
递增单调栈会提出波峰，留下波谷。递减单调栈会剔除波谷，留下波峰。

我们需要找到同时满足j < k和nums[k] <[j]情况的位置。因此采用单调栈正合适。
我们枚举132模式中的“3”，由于我们要找到波谷，因此可以采用递增栈。

递增单调栈的实现：

当遍历的当前值小于栈顶元素时，不满足递增规律，因此挤出栈顶。
循环此操作直至当前栈顶于当前值满足递增规律或栈空。
此时的当前值是nums[j]，而最后一个被挤出的值就是nums[k]。
由于递增单调栈的性质，此时的nums[k] < nums[j]且nums[k]大于被挤出的所有元素。

对于nums[i]，我们可以通过遍历nums[]数组，计算出其在i位置的最小值，并存在放minOfLeft[]中。

Code

class Solution {
    public boolean find132pattern(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int[] minOfLeft = new int[nums.length];
        minOfLeft[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            minOfLeft[i] = Math.min(minOfLeft[i-1], nums[i]);
        }

        for(int j = nums.length-1; j >= 0; j--){
            int k = Integer.MIN_VALUE;
            while(!stack.isEmpty() && nums[j] > stack.peek()){
                k = stack.pop();
            }
            if(minOfLeft[j] < k){
                return true;
            }
            stack.push(nums[j]);
        }
        return false;
    }
}

Posted 2022-05-07Updated 2022-05-08LeetCode / Medium / 复习5 minutes read (About 715 words)

450. Delete Node in a BST

Problem

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.

If the node is found, delete the node.

Solution

二叉搜索树（BST）的递增排序的访问顺序是中序遍历。（Left -> Root -> Right）

因此二叉搜索树的前驱者（小于当前节点的最大值）和继任者（大于当前节点的最小值）对于修改二叉树至关重要。

辅助方法getPredecessor() 和getSuccessor() 可以获得前驱者和继任者的值。
分别为当前根节点的左子节点的最右子节点（二叉搜索树下的最大值）和当前根节点右子节点的最左子节点。（二叉搜索树下的最小值）

deleteNode() 方法搜索key。如果当前值大于搜索值则搜索并修改其左子节点，反之搜索并修改右子节点。（由于要修改，因此向下递归子节点时需要将返回的结果传入该子节点。）

当搜索值等于当前值时，存在三种情况：
1.该子节点存在右子节点。此时我们将当前值设置为继任者的值，然后递归搜索右子节点中继任者的值进行删除。
2.该子节点存在左子节点。此时我们将当前值设置为前驱者的值，然后递归搜索左子节点中前驱者的值进行删除。
3.该子节点是叶子节点。直接删除当前节点。

最后返回修改后的根节点即可。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return null;     
        if(root.val > key) root.left = deleteNode(root.left, key);  //如果当前值大于搜索值则搜索左子节点，否则搜索右子节点
        else if(root.val < key) root.right = deleteNode(root.right, key);
        else{   //如果当前值等于搜索值，根据子节点情况删除节点
            if(root.right != null){ //右子节点不为空则将当前root的值设置为继任者的值，然后向下递归删除继任者
                root.val = getSuccessor(root);
                root.right = deleteNode(root.right, root.val);
            }
            else if(root.left != null){ //左子节点不为空则将当前root的值设置为前驱者的值，然后向下递归删除继任者
                root.val = getPredecessor(root);
                root.left = deleteNode(root.left, root.val);
            }
            else{
                root = null;
            }
        }
        return root;
    }
    
    private int getSuccessor(TreeNode root){
        root = root.right;
        while(root.left != null){
            root = root.left;
        }
        return root.val;
    }
    private int getPredecessor(TreeNode root){
        root = root.left;
        while(root.right != null){
            root = root.right;
        }
        return root.val;
    }
}

Posted 2022-05-06Updated 2022-05-05LeetCode / Medium / 复习4 minutes read (About 538 words)

673. Number of Longest Increasing Subsequence

Question

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Solution

本题还有贪心算法+前缀和+二分查找的算法。

本题是300. Longest Increasing Subsequence的拓展。
同样采用动态规划，数组dp[i]记录到i为止最长递增数列长度。
可以用一个新的数组cnt[i]记录到i为止可以组成的最长递增数列的数量。

对于每个新位置i，cnt[i]的最小值为i。
遍历i之前的所有位置j。如果nums[j] < nums[i]，则i可以比dp[j]组成更长的递增数列，其长度为dp[j]+1。
如果dp[i] < dp[j]+1。则可以更新dp[i]。同时，cnt[i]可以从cnt[j]继承其计数。
如果dp[i] == dp[j]+1。则之前已经更新过dp[i]。说明有新的组合同样可以组成更长的递增数列。此时将cnt[j]加入当前的cnt[i]。

遍历完成i以内的所有j后，如果dp[i]大于当前的最长递增数列长度，则更新max。
同时更新长度的总数count为cnt[i]。
如果dp[i]等于max，则将cnt[i]加入计数count。
最后返回count。

Code

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] cnt = new int[n];
        int max = 0;
        int count = 0;
        
        for(int i = 0; i < n; i++){
            dp[i] = 1;
            cnt[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    if(dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j];    //如果后面的数字大于前面的，且可以组成更长的数列，则继承之前的计数。
                    }
                    else if(dp[j] + 1 == dp[i]){    //如果之前已经更新过dp[i]，则有新的组合长度一直，加和之前的计数。
                        cnt[i] += cnt[j];
                    }
                }
            }
            if(dp[i] > max){    //如果当前的长度大于之前的最大值，则更新。
                max = dp[i];
                count = cnt[i];  //同时将之前计算的计数记录。
            }
            else if(dp[i] == max){  //如果有同样达到最大值的情况，则加和计数。
                count += cnt[i];
            }
        }
        return count;
    }
}

Posted 2022-05-05Updated 2022-05-05LeetCode / Medium / 复习2 minutes read (About 260 words)

973. K Closest Points to Origin

Question

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Solution

此题可以采用快速排序的思想。可以在O(n)时间复杂度里完成排序。

Solution 2

优先级队列，根据每个点距离的平方排序。时间复杂度O(nlogk)。

Code

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int[][] ret = new int[k][2];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> squaredDistance(a) - squaredDistance(b));
        for(int[] point : points){
            pq.add(point);
        }
        for(int i = 0; i < k; i++){
            ret[i] = pq.poll();
        }
        return ret;
    }
    
    private int squaredDistance(int[] point){
        int x = point[0], y = point[1];
        return x * x + y * y;
    }
}

Solution 3

直接排序。时间复杂度为O(nlogn)。

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int[][] ret = new int[k][2];
        Arrays.sort(points, (a, b) -> squaredDistance(a) - squaredDistance(b));
        for(int i = 0; i < k; i++){
            ret[i] = points[i];
        }
        return ret;
    }
    
    private int squaredDistance(int[] point){
        int x = point[0], y = point[1];
        return x * x + y * y;
    }
}

Posted 2022-05-05Updated 2022-05-04LeetCode / Medium / 复习a minute read (About 202 words)

130. Surrounded Regions

Question

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Solution

首先对所有在边缘上的“O”进行BFS或DFS搜索，将和边缘连续的“O”改为“#”或任意其他字符。

然后遍历整个board，如果是“O”则改为“X”，如果是“#”则恢复为“O”。

Code

class Solution {
    public void solve(char[][] board) {
        for(int i = 0; i <board.length; i++){
            for(int j = 0; j <board[0].length; j++){
                boolean isEdge = (i == 0 || j == 0 || i == board.length-1 || j == board[0].length-1);
                if(isEdge && board[i][j] == 'O'){
                    bfs(board, i, j);
                }
            }
        }
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(board[i][j] == '#') board[i][j] = 'O';
                else if(board[i][j] == 'O') board[i][j] = 'X';
            }
        }
    }

    private void bfs(char[][] board, int x, int y){
        int m = board.length;
        int n = board[0].length;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y});
        int size = 1;
        while(!q.isEmpty()){
            for(int k = 0; k < size; k++){
                int[] curr = q.poll();
                int i = curr[0], j = curr[1];
                if( i<0 || j<0 || i>m-1 || j>n-1 || board[i][j] == 'X' || board[i][j] == '#' ) continue;
                board[i][j] = '#';
                q.add(new int[]{i+1,j});
                q.add(new int[]{i-1,j});
                q.add(new int[]{i,j+1});
                q.add(new int[]{i,j-1});
            }
            size = q.size();
        }
    }
}

Posted 2022-05-05Updated 2022-05-04LeetCode / Medium / 复习3 minutes read (About 384 words)

201. Bitwise AND of Numbers Range

Question

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Solution

进行按位和运算时，只要两个位不都是1就会为0。从left到right之间，如果left和right的前x位是一样的，那么两者之间必定有一个数字
在x位上为1，后面的位上为0。因此和这个数字进行按位和运算必定为0。
因此，我们只要保留前面两者相同的位的信息即可，后面均为0。

当left与right不相等时，将两者同时右移，并计算移动的总数。
当两者相等时，向左移动计算的总数的位数。就保留了其相同的前缀。

Code

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int count = 0;
        
        while(left != right){
            left >>= 1;
            right >>= 1;
            count++;
        }
        return left << count;
    }
}

Solution 2

利用一串只有一个1的32位数字作为掩码，获得两个数字单独的位信息。
32位整数的第一位是符号位。因此我们的掩码从第1位开始直到第31位。
当对left和right进行该位的掩码操作后，如果两者相同，则掩码右移一位。
并将答案和当前位进行位或运算。（相当于保存当前位的位信息。）

如果不同，或者掩码变为0，则返回结果。

Code

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int mask = 1 << 30;
        int ans = 0;
        
        while(mask > 0 && (mask & left) == (mask & right)){
            ans |= (mask & left);
            mask >>= 1;
        }
        return ans;
    }
}

Posted 2022-05-04Updated 2022-05-04LeetCode / Medium / 复习a minute read (About 158 words)

1557. Minimum Number of Vertices to Reach All Nodes

Question

Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [from i, to] represents a directed edge from node from i to node to i .

Find the smallest set of vertices from which all nodes in the graph are reachable. It’s guaranteed that a unique solution exists.

Notice that you can return the vertices in any order.

Answer

由于是有向无环图（Directed acyclic graph），因此直接计算图内的入度为0的节点即可。
每条路径都需要从入度为0的点开始。

Code

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        List<Integer> ret = new ArrayList<>();
        int[] inDegrees = new int[n];
        for(List<Integer> edge : edges){
            inDegrees[edge.get(1)]++;
        }
        for(int i = 0; i < n; i++){
            if(inDegrees[i] == 0) ret.add(i);
        }
        return ret;
    }
}

Posted 2022-05-03Updated 2022-05-04LeetCode / Medium / 复习3 minutes read (About 404 words)

581. Shortest Unsorted Continuous Subarray

Question

Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.

Return the shortest such subarray and output its length.

Solution

未排序子数组的左侧和右侧均为单调递增的区间。
我们的目标就是找到单调递增的边界。

中段由于是乱序的，因此其最大值与最小值必定不在中段的两端。
因此我们可以从左至右的遍历数组，不断地维护一个当前的最大值max。
由于只有中段是无序的，因此只有此时后面的数值才可能小于前面的最大值max。
当这种情况发生时，则记录当前节点位置。
同理，我们也可以从右至左遍历，维护一个当前的最小值min。
只有在中段时，前面的数值才可能大于后面的最大值min。
当这种情况发生时，则记录当前节点位置。

最后如果两个指针的位置相同，则返回0。（此时数组完全有序，指针未移动。）
如果两个指针的位置不同，则返回两者的差+1。（即两者的宽度。）

Code

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int start = 0;
        int end = 0;
        
        for(int i = 0; i < nums.length; i++){
            if(nums[i] < max) end = i;
            else max = nums[i];
            
            int j = nums.length - i - 1;
            if(nums[j] > min) start = j;
            else min = nums[j];
        }
        if(start == end) return 0;
        return end - start + 1;
    }
}

Posted 2022-05-03Updated 2022-05-02LeetCode / Medium / 复习5 minutes read (About 767 words)

105. Construct Binary Tree from Preorder and Inorder Traversal

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

先序遍历时，访问的顺序是[根节点 - 左子节点 - 右子节点]。
中序遍历时，访问的顺序是[左子节点 - 根节点 - 右子节点]。
可以注意到根节点与左子节点的顺序是相反的，因此我们可以利用栈将节点储存起来，当挤出时顺序自然是调转的。

按照先序遍历来创建树，遍历先序数组。同时将指针指向中序遍历的数组的头部。
先创建根节点，并将其放入栈中。分为两种情况讨论。

情况一，处理当前根节点的左子节点，并将其入栈：

当栈顶的节点值与中序遍历当前的节点值不同时，说明当前的根节点仍有左子节点。

先序：[根节点 - 左子节点 - 右子节点]
中序：[左子节点 - 根节点 - 右子节点]

此时将栈顶的节点的左子节点设置为先序数组对应的节点，继续遍历下一个先序数组。

栈内：[根节点 - 左子节点]
先序：[根节点 - 左子节点 - 右子节点]
中序：[左子节点 - 根节点 - 右子节点]

情况二，寻找栈内节点们的右子节点：

当栈顶的节点与中序遍历当前的节点值相同时，说明我们经过了当前根节点的先序遍历中的最后一个左子节点。
当前先序数组指针指向了当前栈内节点一个右子节点。

栈内：[根节点 - 左子节点]
先序：[根节点 - 左子节点 - 右子节点]
中序：[左子节点 - 根节点 - 右子节点]

此时我们开始向右移动中序遍历的指针，寻找先序遍历指针中的节点应该是当前栈内哪一个节点的右子节点。
此时栈内节点的顺序，与中序遍历的左子节点顺序正好相反。当栈顶与中序遍历的指针相等时，挤出栈顶并将中序指针右移，直到两者不相等或栈空。
此时将最后挤出的根节点的右子节点设置为当前先序数组对应的节点，继续遍历下一个先序数组。

当遍历完成后，返回根节点即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int j = 0;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = new TreeNode(preorder[0]);
        stack.add(root);
        
        for(int i = 1; i < preorder.length; i++){
            TreeNode curr = new TreeNode(preorder[i]);
            TreeNode prev = stack.peek();
            if(inorder[j] != prev.val){
                prev.left = curr;
                stack.add(curr);
            }
            else{
                while(!stack.isEmpty() && inorder[j] == stack.peek().val){
                    prev = stack.pop();
                    j++;
                }
                prev.right = curr;
                stack.add(curr);
            }
        }
        return root;
    }
}

Question

Solution

滑动窗口

Code

Question

Solution

整数溢出

快速乘

Code

Question

Solution

状态压缩

比较

Code

Question

Solution 1

Code

Solution 2

Code

Solution 3

Code

Question

Solution

Dijkstra算法

建立映射

优先级队列

Code

Question

Solution

Code

Solution

Code

Question

Solution

Code

Problem

Solution

Code

Question

Solution

Code

Question

Solution

Solution 2

Code

Solution 3

Question

Solution

Code

Question

Solution

Code

Solution 2

Code

Question

Answer

Code

Question

Solution

Code

Recents

Archives

Links