Hexo

Posted 2022-05-20Updated 2022-05-20LeetCode / Medium2 minutes read (About 235 words)

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 * 109.

Solution

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

Code

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

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

Posted 2022-05-15Updated 2022-05-14LeetCode / Medium2 minutes read (About 242 words)

2275. Largest Combination With Bitwise AND

Problem

The bitwise AND of an array nums is the bitwise AND of all integers in nums.

For example, for nums = [1, 5, 3], the bitwise AND is equal to 1 & 5 & 3 = 1.

Also, for nums = [7], the bitwise AND is 7.

You are given an array of positive integers candidates. Evaluate the bitwise AND of every combination of numbers of candidates. Each number in candidates may only be used once in each combination.

Return *the size of the largest combination of candidates with a bitwise AND greater than *0.

Solution

相当于将各个数字进行掩码操作，计算各个数组的同一个位上1的数量即可。

bin[]数组记录各个数字的各个位上的1的数量。
如果当前数字与1进行掩码操作后等于1，则将该位数量加一。
然后将当前数字向右移动一位，直至将所有的位都统计完。

最后返回各个位上的最大值即可。

Code

class Solution {
    public int largestCombination(int[] candidates) {
        int[] bin = new int[31];
        int res = 0;
        for(int candidate : candidates){
            int count = 0;
            while(count < 31){
                if((candidate & 1) == 1){
                    bin[count]++;
                }
                candidate = candidate >> 1; 
                count++;
            }
        }
        for(int time : bin){
            res = Math.max(res, time);
        }
        return res;
    }
}

Question

Solution

Code

Question

Solution

记忆化搜索

Code

Question

Solution

时间戳

搜索树

追溯值

无向图的桥的判定法则

Code

Question

Solution

Code

Problem

Solution

Code

Recents

Archives

Links