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 / Easya minute read (About 148 words)

905. Sort Array By Parity

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.

Return any array that satisfies this condition.

双指针，右侧指针之后存放奇数项。
当左侧指针的元素为奇数时，交换left和right上的元素。然后将右侧指针左移。
当左侧指针的元素为偶数时，左侧指针左移。

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
class Solution {
    int[] arr;
    public int[] sortArrayByParity(int[] nums) {
        arr = nums;
        int left = 0;
        int right = nums.length-1;
        
        while(left < right){
            if(nums[left] % 2 == 1){
                swap(left, right);
                right--;
            }
            else{
                left++;
            }
        }
        return arr;
    }
    
    private void swap(int left, int right){
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
}
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;
    }
}
Follow

Recents

Archives

Links

×