Posted Updated a minute read (About 198 words)

Portfolio

Click image to demonstrate in Fullscreen Mode.

Xander's Portfolio
Symbiotic Yard: Elderly Aprtments
Symbiotic Yard: Elderly Apartments
Symbiotic Yard: Community Center
Symbiotic Yard: Community Center
Light Cross: Arctic Hotel
Light Cross: Arctic Hotel
Compact City: High-Density Blocks
Compact City: High-Density Blocks
Creative Technology: Digital Design
Creative Technology: Digital Design
Work Experience

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;
    }
}
Icarus主题增加夜间模式
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
    }
}
Follow

Recents

Archives

Links

×