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;
    }
}
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];
    }
}
322. Coin Change
Posted Updated LeetCode / Medium2 minutes read (About 231 words)

322. Coin Change

Question

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Solution

动态规划，首先将amount长度的数组填满最大值。
双重遍历数组和硬币，不取当前硬币的上一个状态加一（dp[i - coin]+1）就是当前可取的最小值。
注意先取硬币，将amount的起始值设置为硬币面值可以增快速度。（减少了面值大于总额的情况。）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount == 0) return 0;
        int dp[] = new int[amount+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int coin : coins){
            for(int i = coin; i <= amount; i++){
                if(dp[i-coin] != Integer.MAX_VALUE)
                dp[i] = Math.min(dp[i],dp[i - coin]+1);
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}
581. Shortest Unsorted Continuous Subarray
Posted Updated LeetCode / 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
    }
}
236. Lowest Common Ancestor of a Binary Tree
Posted Updated LeetCode / Medium2 minutes read (About 337 words)

236. Lowest Common Ancestor of a Binary Tree

Question

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Solution

DFS搜索，后序遍历。
当当前节点是p或者q，返回节点自身，代表已经找到节点。（如两个节点最终只访问了一个，说明那一个节点本身就是LCA。）

分别递归搜索左右子节点。

如果左子节点为空，则返回右子节点，反之亦然，保证找到的节点可以被返回。
如果左右子节点均不等于null，则当前节点是最低公共祖先（LCA），返回当前节点。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
        if(root == null) return null;
        if(root == p) return p; //found target and return
        if(root == q) return q; //found target and return
        
        TreeNode left = lowestCommonAncestor(root.left, p, q);  //search left branch
        TreeNode right = lowestCommonAncestor(root.right, p, q);    //search right branch
           
        if(left == null) return right;  //if left not found target, return the right branch
        else if(right == null) return left; //if right not found target, return the left branch
        else return root;   //if both found target, return the root
    }
}
Posted Updated LeetCode / 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.

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

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

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

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

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

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

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

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

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

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

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

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

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
/**
 * 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;
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 295 words)

583. Delete Operation for Two Strings

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.

In one step, you can delete exactly one character in either string.

动态规划，创建数组dp[][]，长宽分别为两个字符串的长度。
在dp中填入子字符串修改成另一个子字符串时需要删除的数量。
如果两个字符相同，则相对于上一个状态不需要增加数量。因此可以直接等于对角线方向上的值。
如果两个字符串不同，则取上方向和左方向中的较小值，然后+1。（由于题目只允许删除操作，不允许修改操作，因此不能从字符串左上角取值。）
最后返回dp中右下角的值。

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
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m+1][n+1];
        char[] bin1 = word1.toCharArray();
        char[] bin2 = word2.toCharArray();
        
        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++){
            char k = bin1[i-1];
            for(int j = 1; j <= n; j++){
                if(k == bin2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }
                else{
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 275 words)

1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, “ace” is a subsequence of “abcde”.
A common subsequence of two strings is a subsequence that is common to both strings.

动态规划，dp的长和宽分别为两个字符串的长度。
遍历dp字符串的长和宽。（注意在第一层遍历时先保存当前选择的字符可以提升速度。）
当两个字符串相同时，则可以从上一个状态+1。
注意状态转移方程的上一个状态应该是从对角线方向+1。
当两个字符串不同时，则继续保存之前的最大长度。

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 longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m+1][n+1];
        char[] bin1 = text1.toCharArray();
        char[] bin2 = text2.toCharArray();

        for(int i = 1; i <= m; i++){
            int k = bin1[i-1];
            for(int j = 1; j <= n ; j++){
                if(k == bin2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
}
Posted Updated LeetCode / Mediuma minute read (About 173 words)

199. Binary Tree Right Side View

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

BFS搜索。层级遍历各个节点，当节点为该层级最后一个节点时，将其值加入返回列表。

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
/**
 * 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 List<Integer> rightSideView(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int size = 1;
        while(!q.isEmpty()){
            for(int i = 0; i < size; i++){
                TreeNode curr = q.poll();
                if(i == size - 1) ret.add(curr.val);
                if(curr.left != null) q.add(curr.left);
                if(curr.right != null) q.add(curr.right);
            }
            size = q.size();
        }
        return ret;
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 294 words)

113. Path Sum II

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

回溯，每次将root的值添加到list中。并计算新的sum值。分别向左右子节点进行递归，然后回溯。
当节点没有左右子节点，且sum等于targetSum则将新建的list添加到结果中。
（注意这一步内也需要进行回溯操作。）

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
/**
 * 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 {
    List<List<Integer>> ret;
    int target;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        ret = new ArrayList<>();
        if(root == null) return ret;
        target = targetSum;
        backTrack(root, 0, new ArrayList<>());
        return ret;
    }
    
    private void backTrack(TreeNode root, int sum, List<Integer> nodes){
        if(root.left == null && root.right == null){
            sum += root.val;
            if(sum == target){
                nodes.add(root.val);
                ret.add(new ArrayList<Integer>(nodes));
                nodes.remove(nodes.size()-1);
            }
            return;
        }
        nodes.add(root.val);
        sum += root.val;
        if(root.left != null) backTrack(root.left, sum, nodes);
        if(root.right != null) backTrack(root.right, sum, nodes);
        nodes.remove(nodes.size()-1);
        sum -= root.val;
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 463 words)

103. Binary Tree Zigzag Level Order Traversal

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

BFS搜索，每次遍历挤出整层的节点。
根据真值reverse来判断列表顺序。
当reverse为真，则每次添加元素到列表头。
反之则添加元素到列表尾。

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
/**
 * 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 List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Deque<TreeNode> q = new LinkedList<>();
        q.add(root);
        int size = 1;
        boolean reverse = false;
        
        while(!q.isEmpty()){
            List<Integer> level = new ArrayList<Integer>();
            for(int i = 0; i < size; i++){
                TreeNode curr = q.poll();
                if(reverse){
                    level.add(0, curr.val);
                } 
                else{
                    level.add(curr.val);
                } 
                if(curr.left != null) q.add(curr.left);
                if(curr.right != null) q.add(curr.right);
                    
            }

            reverse = !reverse;
            ret.add(level);
            size = q.size();
        }
        return ret;
    }
}

双端队列，根据真值reverse来判断是取队头还是取队尾。
每层级需要遍历所有的节点。
注意添加节点时也需要根据reverse来决定加入对头还是队尾。
（从一个层级取出时，加入下一个层级元素需要从队列另一边压入。）
同时左右节点的加入顺序也需要调整。

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
/**
 * 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 List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Deque<TreeNode> dq = new LinkedList<>();
        dq.add(root);
        int size = 1;
        boolean reverse = false;
        
        while(!dq.isEmpty()){
            List<Integer> temp = new ArrayList<Integer>();
            for(int i = 0; i < size; i++){
                if(reverse){
                    TreeNode curr = dq.removeLast();
                    if(curr.right != null) dq.offerFirst(curr.right);
                    if(curr.left != null) dq.offerFirst(curr.left);
                    temp.add(curr.val);
                } 
                else{
                    TreeNode curr = dq.removeFirst();
                    if(curr.left != null) dq.offerLast(curr.left);
                    if(curr.right != null) dq.offerLast(curr.right);
                    temp.add(curr.val);
                } 
            }

            reverse = !reverse;
            ret.add(temp);
            size = dq.size();
        }
        return ret;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 285 words)

139. Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

动态规划，创建一个数组dp[]，长度为字符串长度+1，记录是否可以达到。
将dp[0]设置为1，表示可以达到。

从可取长度为1开始，遍历直到可取长度为字符串的长度。
用下一个遍历j将字符串分为两部分。（这里j从i-1下降到0会比从0上升到i-1更快。）
当dp[j]可以到达，且当前的哈希表中有(i-j)组成的字符串时，则dp[i]也可以到达。结束第二层循环。
继续搜索更长的字符串是否可以达到。
最后返回dp中的最后一个元素。

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 wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>();
        int n = s.length();
        int[] dp = new int[n+1];
        
        for(String word : wordDict){
            set.add(word);
        }
        dp[0] = 1;
        int temp = 0;
        for(int i = 1; i <= n; i++){
            for(int j = i - 1; j >= 0; j--){
                if(dp[j] == 1 && set.contains(s.substring(j, i))){
                    dp[i] = 1;
                    break;
                }
            }
        }
        return dp[n] == 1; 
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 312 words)

91. Decode Ways

A message containing letters from A-Z can be encoded into numbers using the following mapping:

‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, “11106” can be mapped into:

  • “AAJF” with the grouping (1 1 10 6)
  • “KJF” with the grouping (11 10 6)
    Note that the grouping (1 11 06) is invalid because “06” cannot be mapped into ‘F’ since “6” is different from “06”.

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

动态规划。转移方程的考虑比较麻烦。
当当前的字符不为0时，该为可以自己组成有效编码，因此dp[i] = dp[i-1]。
然后考虑上一位可以和当前位组成有效编码的情况，如果上一位和当前位的数字小于26，且上一位不等于0，则可以联合编码。
因此dp需要再加上前一位可以组成的编码数，即dp[i] += dp[i-2]。
当i等于1时，由于会越界因此我们手动给dp[i]++。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if(s.charAt(0) == '0') return 0;
        int[]dp = new int[n];
        dp[0] = 1;

        for(int i = 1 ; i < n; i++){
            if(s.charAt(i) != '0'){
                dp[i] = dp[i-1];
            }
            if(s.charAt(i-1) != '0' && (s.charAt(i-1) - '0') * 10 + (s.charAt(i) - '0') <= 26 ){
                if(i > 1) dp[i] += dp[i-2];
                else dp[i]++;
            }
        }
        return dp[n-1];
    }
}
300. Longest Increasing Subsequence
Posted Updated LeetCode / Medium / 复习4 minutes read (About 589 words)

300. Longest Increasing Subsequence

Question

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Solution

贪心算法

创建一个数组记录达到升序的长度时升序数列的最小末尾值。
如果想要增加数组的长度（即增加最大的升序数列长度），则新的数字必须要大于该数组最后一位的大小。
因此在这种情况下，该数组必然是单调递增的。

二分搜索

将第一个数字填入数组。
然后遍历数组，当新一项大于数组的最后一个值时，最大长度加一，并将其加入数组的尾部。
当新一项小于数组的最后一个值时，该数字需要与之前的数组组成新的升序数列。
我们可以替换掉之前数组中比该数字大的第一个数字，代表新组成的数组。（最长数组之间的数字无所谓，只记录最小的末尾值即可。）
我们可以用二分搜索查到该数字需要加入的index。然后替换掉数组中的数字。
单次二分搜索的时间复杂度为O($logn$)。总的时间复杂度为O($nlogn$)。

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 lengthOfLIS(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        int len = 1;
        ans.add(nums[0]);
    
        for(int i = 1; i < nums.length; i++){
            if(nums[i] > ans.get(ans.size()-1)){
                ans.add(nums[i]);
                len++;
            }
            else{
                int index = Collections.binarySearch(ans, nums[i]);
                if(index < 0){
                    ans.set(-(index+1), nums[i]);
                }
            }
        }
        return len;
    }
}

Solution 2

动态规划，创建一个数组dp[]用来记录最大长度，创建max记录最大值。
遍历，先将数组dp[]上的所有位置都填上1。
从0到i-1遍历j。当nums[i] > nums[j]时，更新dp[i]为dp[i]与dp[j]+1中的较大值。
当更新dp[i]时将其和max比较，如果比max大则更新max。
最后返回max值。时间复杂度为O($n_2$)

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 lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int max = 1;
        
        for(int i = 0; i < n; i++){
            dp[i] = 1;
            for(int j = i-1; j >= 0; j--){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                    if(max < dp[i]){
                        max = dp[i];
                        break;
                    }
                }
            }
        }
        return max;
    }
}
Posted Updated LeetCode / Medium / 复习6 minutes read (About 841 words)

399. Evaluate Division

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

这道题的核心是边上带权的并查集。
如何在find以及union时计算并更新权重是最重要的。
组合过后，根节点的权重依然为1，以其为标准更新其他节点的权重。

先通过一个哈希表建立字符串与id的映射关系，为每个字符串生成一个单独的id。

然后将一个equation里的两个字符串进行union操作。
并查集初始化时，所有权重为1。

在find时，执行路径压缩时需要用当前的权重weight[id]更新为其自身乘以其上一级的权重weight[origin]。
这里需要注意计算的顺序需要从根上的权重，以递归的形式计算到当前权重。
因此我们需要先单独保存parents[id]的位置。然后find(parents[id])，先计算出其上级的weight。
最后再将weight[id]更新为更新后的上一级的权重乘以自身权重。

1
2
3
int origin = parents[id];
parents[id] = find(parents[id]);
weight[id] *= weight[origin];

在union时，将两个集合中的一个的根指向另一个。
例如当结合a与b两个节点时，我们已经计算过了(a -> b)的权重关系，以及(d -> c)的权重关系。
我们将(b -> d)。这时我们可以通过values[i]得到(a -> d)的权重关系。因此我们可以据此得出以下公式：

weight[(b->c)] = weight[(d->c)] × values[(a->d)]/weight[(a->b)]

1
2
parents[p1] = parents[p2];
weight[p1] = weight[id2]*val/weight[id1];

最后，当所有节点都被合并后，我们可以遍历queries。
从哈希表获得对应字符串的id。
当有字符串未在哈希表中时，返回-1.0。
否则计算两个id对应的权重，并添加到答案中。

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
58
59
60
61
62
63
64
65
class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        double[] ret = new double[queries.size()];
        HashMap<String, Integer> map = new HashMap<>();
        UnionFind uf = new UnionFind(equations.size() * 2);
        int id = 0;
        for(int i = 0; i < equations.size(); i++){
            String var1 = equations.get(i).get(0);
            String var2 = equations.get(i).get(1);
            if( !map.containsKey( var1 ) ){
                map.put( var1, id );
                id++;
            }
            if( !map.containsKey( var2 ) ){
                map.put( var2, id );
                id++;
            }
            uf.union(map.get(var1), map.get(var2), values[i]);
        }
        for(int i = 0 ; i < queries.size(); i++){
            String var1 = queries.get(i).get(0);
            String var2 = queries.get(i).get(1);
            Integer id1 = map.get(var1);
            Integer id2 = map.get(var2);
            if(id1 == null || id2 == null) ret[i] = -1.0;
            else ret[i] = uf.isConnected(id1, id2);
        }
        return ret;
    }
    
    class UnionFind{
        int[] parents;
        double[] weight;
        public UnionFind(int n){
            parents = new int[n];
            weight = new double[n];
            for(int i = 0; i < parents.length; i++){
                parents[i] = i;
                weight[i] = 1.0;
            }
        }
        public int find(int id){
            if (id != parents[id]) {
                int origin = parents[id];
                parents[id] = find(parents[id]);
                weight[id] *= weight[origin];
            }
            return parents[id];
        }
        public boolean union(int id1, int id2, double val){
            int p1 = find(id1);
            int p2 = find(id2);
            if(p1 == p2) return false;
            parents[p1] = parents[p2];
            weight[p1] = weight[id2]*val/weight[id1];
            return true;
        }
        public double isConnected(int id1, int id2){
            int p1 = find(id1);
            int p2 = find(id2);
            if(p1 == p2) return weight[id1] / weight[id2];
            else return -1.0;
        }
    }
}
Follow

Recents

Archives

Links

×