841. Keys and Rooms
Posted Updated LeetCode / Medium2 minutes read (About 268 words)

841. Keys and Rooms

Question

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

Solution

BFS，创建一个数组记录房间是否被访问。（用DFS搜素亦可。）

如果钥匙对应的房间已经访问过则跳过。
如果未访问过则记录为已访问并加入队列。

最后遍历一次访问状态，如果有没访问过的房间则返回false。反之返回true。

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 boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int[] visited = new int[rooms.size()];
        visited[0] = 1;
        Queue<List<Integer>> q = new LinkedList<>();
        q.add(rooms.get(0));
        
        while(!q.isEmpty()){
            List<Integer> keys = q.poll();
            for(int key : keys){
                if(visited[key] == 1) continue;
                visited[key] = 1;
                q.add(rooms.get(key));
            }
        }
        
        for(int i=1; i<rooms.size(); i++){
            if(visited[i] == 0) return false;
        }
        return true;
    }
}
1557. Minimum Number of Vertices to Reach All Nodes
Posted Updated LeetCode / 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

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
    }
}
997. Find the Town Judge
Posted Updated LeetCode / Easy / 复习a minute read (About 220 words)

997. Find the Town Judge

Question

In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

  1. The town judge trusts nobody.
  2. Everybody (except for the town judge) trusts the town judge.
  3. There is exactly one person that satisfies properties 1 and 2.

You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi.

Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

Solution

题目可以转换为计算各个顶点的入度和出度。

遍历每条边，并计算边上两个顶点的出度和入度。
如果某个节点的入度为n-1，出度为0，则符合有法官的条件。
否则没有法官，返回-1。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] inDegrees = new int[n];
        int[] outDegrees = new int[n];
        
        for(int[] edge : trust){
            outDegrees[edge[0]-1]++;
            inDegrees[edge[1]-1]++;
        }
        for(int i = 0; i < n; i++){
            if(outDegrees[i] == 0 && inDegrees[i] == n-1) return i+1;
        }
        return -1;
    }
}
72. Edit Distance
Posted Updated LeetCode / Hard2 minutes read (About 331 words)

72. Edit Distance

Question

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

You have the following three operations permitted on a word:

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

Solution

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

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

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        char[] bin1 = word1.toCharArray();
        char[] bin2 = word2.toCharArray();
        int[][] dp = new int[m+1][n+1];
        
        for(int i = 0; i <= m; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= n; j++){
            dp[0][j] = j;
        }
        
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(bin1[i-1] == bin2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }
                else{
                    dp[i][j] = Math.min(dp[i-1][j-1] + 1, Math.min(dp[i-1][j], dp[i][j-1]) + 1);
                }
            }
        }
        return dp[m][n];
    }
}
343. Integer Break
Posted Updated LeetCode / Medium3 minutes read (About 499 words)

343. Integer Break

Question

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

Solution

动态规划，用数组dp[]记录最大乘积。
在n < 4之前为特例，由于必须拆分，因此乘积小于自身。但由于之后的数字要用到拆分的特性，因此这三个数字要特殊设置为自身。
在此之后，每个数字可以拆分成两个数的加和，然后乘积等于对应两个数的乘积。
（dp[4]可以不设置计算得出，但是指定值的话可以加快速度。）

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 integerBreak(int n) {
        if(n <= 1) return 0;
        if(n == 2) return 1;
        if(n == 3) return 2;
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;
  
        for(int i = 4; i <= n; i++){
            for(int j = 1; j <= (i/2)+1; j++){
                int k = i - j;
                dp[i] = Math.max(dp[i], dp[j] * dp[k]);
            }
        }
        return dp[n];
    }
}

Solution 2

数学方法，当两数之和大于4时，拆分成两个更小的加和可以得到更大的乘积。
而当等于4时，可以拆分为两个2相乘。
因此，最终有意义的拆分结果只会有2和3。

拆分规则：

  1. 最优： 3 。把数字 n 可能拆为多个因子 3 ，余数可能为 0,1,2 三种情况。
  2. 次优： 2 。若余数为 2 ；则保留，不再拆为 1+1 。
  3. 最差： 1 。若余数为 1 ；则应把一份 3+1 替换为 2 + 22+2，因为 2 * 2 > 3 * 1

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int integerBreak(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int quotient = n / 3;
        int remainder = n % 3;
        if (remainder == 0) {
            return (int) Math.pow(3, quotient);
        }
        else if (remainder == 1) {
            return (int) Math.pow(3, quotient - 1) * 4;
        }
        else {
            return (int) Math.pow(3, quotient) * 2;
        }
    }
}

Solution 3

同样，我们可以将之前的结论用在动态规划上，j只取2或3，将时间复杂度从O(n^2)降低到O(n)。

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 integerBreak(int n) {
        if(n <= 1) return 0;
        if(n == 2) return 1;
        if(n == 3) return 2;
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;
  
        for(int i = 4; i <= n; i++){
            for(int j = 2; j <= 3; j++){
                int k = i - j;
                dp[i] = Math.max(dp[i], dp[j] * dp[k]);
            }
        }
        return dp[n];
    }
}
Follow

Recents

Archives

Links

×