361. Bomb Enemy

Version # 1 Optimized DP
Space O(m)  Time O(mn)

Look all the way to the right nearest wall/border and count the enemies on the way
Look all the way to the bottom nearest wall/border and  count the enemies on the way
This will be the current count of total enemies if current position is a empty '0'
We don't need to update any enemies count unless we step into a wall position
After we step over a wall, all the left and up enemies count will become zero, now we need to walk toward right and bottom again to recalculate the enemies again
The amortized time complexity is O(mn)

99.05 %
class Solution {
    public int maxKilledEnemies(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
// count of emenies [x, nearest wall/border on the right]
int horizontalCount = 0;
// verticalCount[y] [y, nearest wall/border under current y)
int max = 0;
int[] verticalCount = new int[cols];
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
// update when going to new line or see a wall
if (x == 0 || grid[y][x - 1] == 'W') {
horizontalCount = 0;
int j = x;
while (j < cols && grid[y][j] != 'W') {
if (grid[y][j] == 'E') {
horizontalCount++;
}
j++;
}
// System.out.println(x + " " + y + " -> " + horizontalCount);
}
if (y == 0 || grid[y - 1][x] == 'W') {
verticalCount[x] = 0;
int i = y;
verticalCount[x] = 0;
while (i < rows && grid[i][x] != 'W') {
if (grid[i][x] == 'E') {
verticalCount[x]++;
}
i++;
}
// System.out.println(x + " " + y + " -> vertical " + verticalCount[x]);
}
if (grid[y][x] == '0') {
max = Math.max(max, horizontalCount + verticalCount[x]);
}
}
}
return max;
}
}

685. Redundant Connection II[TODO]

721. Accounts Merge

Version # 2 DFS[TODO]
非常需要做一下，现在写不动了


二刷 08/2022

Version #1 Union Find

Time - Here N is the number of accounts and K is the maximum length of an account.

Time complexity: O(NKlogNK)

Space O(NK)

Runtime: 67 ms, faster than 40.75% of Java online submissions for Accounts Merge.

Memory Usage: 67.4 MB, less than 24.80% of Java online submissions for Accounts Merge.

class Solution {

    class UF {

        Set<String>[] emails;

        int[] id;

        String[] names;

        public UF(List<List<String>> accounts) {

            int n = accounts.size();

            emails = new Set[n];

            id = new int[n];

            names = new String[n];

            for (int i = 0; i < n; i++) {

                emails[i] = new HashSet<>();

                for (int j = 1; j < accounts.get(i).size(); j++) {

                    emails[i].add(accounts.get(i).get(j));

                }

                id[i] = i;

                names[i] = accounts.get(i).get(0);

            }

        }

        

        public int root(int i) {

            while (id[i] != i) {

                id[i] = id[id[i]];

                i = id[i];

            }

            return i;

        }

        

        public void union(int p, int q) {

            if (p == q) {

                return;

            }

            int rootP = root(p);

            int rootQ = root(q);

            if (rootP == rootQ) {

                return;

            }

            if (emails[rootP].size() < emails[rootQ].size()) {

                id[rootP] = rootQ;

                for (String email : emails[rootP]) {

                    emails[rootQ].add(email);

                }

            } else {

                id[rootQ] = rootP;

                for (String email : emails[rootQ]) {

                    emails[rootP].add(email);

                }

            }

        }

    }

    public List<List<String>> accountsMerge(List<List<String>> accounts) {

        UF uf = new UF(accounts);

        // key-email, value-one of the account index

        Map<String, Integer> map = new HashMap<>();

        for (int i = 0; i < accounts.size(); i++) {

            List<String> account = accounts.get(i);

            for (int j = 1; j < account.size(); j++) {

                String email = account.get(j);

                if (map.containsKey(email)) {

                    uf.union(i, map.get(email));

                }

                map.put(email, i);

            }

        }

        List<List<String>> result = new ArrayList<>();

        for (int i = 0; i < accounts.size(); i++) {

            if (uf.id[i] != i) {

                continue;

            }

            List<String> account = new ArrayList<>(uf.emails[i]);

            Collections.sort(account);

            account.add(0, uf.names[i]);

            result.add(account);

        }

        return result;

    }

}

一刷
Version #1 Union Find
精髓在于如何建图
一开始觉得既然每个email都有一个owner不如用owner作为parent，但实际上是不可行的，union find中所有的node都需要是同类型的data
因为就算当前这个owner name是parent，之后union完了还是会成为一个child
这里省略的weighted graph的步骤，因为感觉代码有些复杂
所以对于n个nodes 的amertized time complexity 是NlogN
本题的N是整个accounts list里面email的总数，也就是UF里面的node的总数
Time O(NlogN)
Space O(N)

77.17 %
class Solution {
    // key->node, value->id
    private Map<String, String> parent;
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        List<List<String>> result = new ArrayList<>();
        if (accounts == null || accounts.size() == 0) {
            return result;
        }
        // key->email, value->owner
        Map<String, String> owner = new HashMap<>();
        parent = new HashMap<>();
       
        for (List<String> account : accounts) {
            if (account.size() < 2) {
                continue;
            } 
            String firstEmail = account.get(1);
            owner.put(firstEmail, account.get(0));
            for (int i = 1; i < account.size(); i++) {
                String email = account.get(i);
                if(parent.containsKey(email)) {
                    union(firstEmail, root(email));
                } else {
                    parent.put(email, firstEmail);
                }
            }
        }
       
       
        // TODO
        Map<String, TreeSet<String>> parentToEmails = new HashMap<>();
        for (Map.Entry<String, String> entry : parent.entrySet()) {
            String root = root(entry.getKey());
            if (!parentToEmails.containsKey(root)) {
                parentToEmails.put(root, new TreeSet<>());
            }
            parentToEmails.get(root).add(entry.getKey());
        }
       
        for (Map.Entry<String, TreeSet<String>> entry : parentToEmails.entrySet()) {
            List<String> temp = new ArrayList<>(entry.getValue());
            temp.add(0, owner.get(entry.getKey()));
            result.add(temp);
        }
        return result;
    }
   
    private String root(String i) {
        while (parent.get(i) != i) {
            parent.put(i, parent.get(parent.get(i)));
            i = parent.get(i);
        }
        return i;
    }
   
    private void union(String p, String q) {
        String rootP = root(p);
        String rootQ = root(q);
        if (rootP.equals(rootQ)) {
            return;
        }
        parent.put(rootP, rootQ);
    }
}

684. Redundant Connection

Version # 2 Union Find
The only tricky part here is how to initialize the UF instance
Notice that -> a valid tree has vertex + 1 edges, since we have 1 redundant edge here, we have #vertices = #edges
This principle can also be used for the DFS version

 96.86 %
class Solution {
    class UF {
private int[] id;
private int[] size;
public UF(int N) {
id = new int[N];
size = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
size[i] = 1;
}
}

private int root(int i) {
while (id[i] != i) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}

public boolean union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if (rootP == rootQ) {
return false;
}
if (size[rootP] < size[rootQ]) {
id[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
id[rootQ] = rootP;
size[rootP] += size[rootQ];
}
return true;
}

}

public int[] findRedundantConnection(int[][] edges) {
if (edges == null || edges.length == 0 || edges[0] == null || edges[0].length == 0) {
return null;
}
int N =edges.length;
UF uf = new UF(N);
for (int[] edge : edges) {
if (!uf.union(edge[0] - 1, edge[1] - 1)) {
return edge;
}
}
return null;
}
}

Version #1 DFS

Time O(n^2) Space O()
[WHEN DONT WE NEED BACKTRACKING]
Notice that the backtracking part -> visited.remove(curr) is not necessary
If we do visited.remove(curr), means we are assuming that there's another situation that curr can be reached from another path that linking start node and curr node
-> which means there are two paths between start & curr
-> Since we guarantee that there's no cycle before, the curr will never be reached from another previous node, so this remove is not necessary

 9.09 %

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
if (edges == null || edges.length == 0 || edges[0] == null || edges[0].length == 0) {
return null;
}
Map<Integer, Set<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
// [u, v] -> u < v
int curr = edge[0];
int target = edge[1];
if (dfs(graph, curr, target, new HashSet<>())) {
return edge;
}
if (!graph.containsKey(curr)) {
graph.put(curr, new HashSet<>());
}
if (!graph.containsKey(target)) {
graph.put(target, new HashSet<>());
}
graph.get(curr).add(target);
graph.get(target).add(curr);
}
return null;
}
private boolean dfs(Map<Integer, Set<Integer>> graph, int curr, int target, Set<Integer> visited) {
if (curr == target) {
return true;
}
visited.add(curr);
Set<Integer> neighbors = graph.get(curr);
if (neighbors != null) {
for (Integer neighbor : neighbors) {
if (!visited.contains(neighbor) && dfs(graph, neighbor, target, visited)) {
return true;
}
}
}
// visited.remove(curr);
return false;
}
}

834. Sum of Distances in Tree

Reference to the solution
https://leetcode.com/problems/sum-of-distances-in-tree/solution/

二刷
96.91 %
class Solution {
    public int[] sumOfDistancesInTree(int N, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        int[] subCount = new int[N];
        int sum = dfs(0, graph, -1, subCount);
        int[] result = new int[N];
        result[0] = sum;
        dfs2(0, graph, N, -1, subCount, result);
        return result;
    }
   
    private void dfs2(int node, List<List<Integer>> graph, int N, int parent, int[] subCount, int[] result) {
        List<Integer> neighbors = graph.get(node);
        if (node != 0) {
            result[node] = result[parent] - subCount[node] + (N - subCount[node]);
        }
        for (int neighbor : neighbors) {
            if (neighbor == parent) {
                continue;
            }
            dfs2(neighbor, graph, N, node, subCount, result);
        }
    }
    // 1-2-3-0
   
    private int dfs(int node, List<List<Integer>> graph, int parent, int[] subCount) {
        List<Integer> neighbors = graph.get(node);
        int sum = 0;
        subCount[node] = 1;
        for (int neighbor : neighbors) {
            if (neighbor == parent) {
                continue;
            }
            sum += dfs(neighbor, graph, node, subCount) + subCount[neighbor];
            subCount[node] += subCount[neighbor];
        }
        return sum;
    }
}
一刷
Time O(n) Space O(n)

 97.62 %
class Solution {
    public int[] sumOfDistancesInTree(int N, int[][] edges) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < N; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
int[] subtreeSum = new int[N];
int[] subtreeCount = new int[N];
dfs(graph, subtreeSum, subtreeCount, 0, -1);
update(graph, subtreeSum, subtreeCount, 0, -1);
return subtreeSum;
}

private void dfs(List<List<Integer>> graph, int[] subtreeSum, int[] subtreeCount, int curr, int parent) {
List<Integer> neighbors = graph.get(curr);
subtreeCount[curr] = 1;
for (int neighbor : neighbors) {
if (neighbor != parent) {
dfs(graph, subtreeSum, subtreeCount, neighbor, curr);
subtreeSum[curr] += subtreeSum[neighbor] + subtreeCount[neighbor];
subtreeCount[curr] += subtreeCount[neighbor];
}
}
}

private void update(List<List<Integer>> graph, int[] subtreeSum, int[] subtreeCount, int curr, int parent) {
if (curr != 0) {
subtreeSum[curr] = subtreeSum[parent] - subtreeCount[curr] + graph.size() - subtreeCount[curr];
}
List<Integer> neighbors = graph.get(curr);
for (int neighbor : neighbors) {
if (neighbor != parent) {
update(graph, subtreeSum, subtreeCount, neighbor, curr);
}
}
}
}

97. Interleaving String

二刷 07/2022

Version #2 Optimized DP

Time O(MN)

Space O(N)

Runtime: 6 ms, faster than 52.14% of Java online submissions for Interleaving String.

Memory Usage: 41.8 MB, less than 81.71% of Java online submissions for Interleaving String.

class Solution {

    public boolean isInterleave(String s1, String s2, String s3) {

        if (s1.length() + s2.length() != s3.length()) {

            return false;

        }

        // dp[i][j] - if s1.substring(i) and s2.substring(j) can form s3.substring(i + j)

        boolean[] dp = new boolean[s2.length() + 1];

        for (int i = 0; i <= s1.length(); i++) {

            for (int j = 0; j <= s2.length(); j++) {

                if (i == 0 && j == 0) {

                    dp[0] = true;

                    continue;

                }

                char c = s3.charAt(i + j - 1);

                if (i == 0) {

                    dp[j] = c == s2.charAt(j - 1) && dp[j - 1];

                    continue;

                }

                if (j == 0) {

                    dp[0] = c == s1.charAt(i - 1) && dp[0];

                    continue;

                }

                dp[j] = (c == s1.charAt(i - 1) && dp[j]) || (c == s2.charAt(j - 1) && dp[j - 1]);

            }

        }

        return dp[s2.length()];

    }

}

一刷

Version # 2 Optimized DP
Time O(mn) Space O(n)
73.41 %
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
// dp[i][j] -> s1[0, p1), s2[0, p2) can form s3[0, p1 + p2)
if (s1 == null || s2 == null || s3 == null || s1.length() + s2.length() != s3.length()) {
return false;
}
int p1 = 0;
int p2 = 0;
boolean[] dp = new boolean[s2.length() + 1];
dp[0] = true;
// p1 = 0;
for (p2 = 1; p2 <= s2.length(); p2++) {
dp[p2] = dp[p2 - 1] && s2.charAt(p2 - 1) == s3.charAt(p2 - 1);
}
for (p1 = 1; p1 <= s1.length(); p1++) {
dp[0] = dp[0] && s1.charAt(p1 - 1) == s3.charAt(p1 - 1);
for (p2 = 1; p2 <= s2.length(); p2++) {
dp[p2] = dp[p2 - 1] && s2.charAt(p2 - 1) == s3.charAt(p1 + p2 - 1)
                    || dp[p2] && s1.charAt(p1 - 1) == s3.charAt(p1 + p2 - 1);
}
}
return dp[s2.length()];
}
}


Version #1 Naive DP
Time O(mn)
Space O(mn)

54.98 %

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
// dp[i][j] -> s1[0, p1), s2[0, p2) can form s3[0, p1 + p2)
        if (s1 == null && s2 == null) {
            return s3 == null;
        }
        if (s1 == null || s1.length() == 0) {
            return s2.equals(s3);
        }
        if (s2 == null || s2.length() == 0) {
            return s1.equals(s3);
        }
if (s1.length() + s2.length() != s3.length()) {
return false;
}
int p1 = 0;
int p2 = 0;
boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
for (p1 = 0; p1 <= s1.length(); p1++) {
            dp[p1][0] = p1 == 0 ? true : dp[p1 - 1][0] && s1.charAt(p1 - 1) == s3.charAt(p1 - 1);
for (p2 = 1; p2 <= s2.length(); p2++) {
// start with p2
if (p1 + p2 - 1 >= s3.length()) {
return false;
}
if (p1 == 0) {
dp[p1][p2] = dp[p1][p2 - 1] && s2.charAt(p2 - 1) == s3.charAt(p1 + p2 - 1);
} else {
dp[p1][p2] = (dp[p1][p2 - 1] && s2.charAt(p2 - 1) == s3.charAt(p1 + p2 - 1))
|| (dp[p1 - 1][p2] && s1.charAt(p1 - 1) == s3.charAt(p1 + p2 - 1));
}
}
}
return dp[s1.length()][s2.length()];
}
}

514. Freedom Trail

Naive DP 
Can be optimized by iterating from key.length() - 1 to 0
这样可以省略i == 0的初始化和最后的stream

n -> ring.length(), m -> key.length()
Time O(mnn)
Space O(mn)

Without lambda
72.89 %

With lambda
21.61 %
class Solution {
    public int findRotateSteps(String ring, String key) {
        // ring = "godding", key = "gd"
        if (ring == null || key == null) {
            return 0;
        }
        // dp[i] -> min steps to take to dial key -> [0, i)
        // dp[i - 1][j] -> j positions have ring.charAt(j) == key.charAt(i - 1)
        // for all j -> min dp[i - 1][j] + j to all chars ring.charAt(k) == key.charAt(i)
        int[][] dp = new int[key.length()][ring.length()];
        int n = ring.length();
        for (int i = 0; i < key.length(); i++) {
            for (int j = 0; j < n; j++) { // find the position of key.charAt(i) on the ring
                int min = Integer.MAX_VALUE;
                if (ring.charAt(j) == key.charAt(i)) {
                    if (i == 0) {
                        // pos == 0
                        dp[i][j] = Math.min(j, n - j);
                        continue;
                    }
                    for (int pos = 0; pos < n; pos++) {
                        if (dp[i - 1][pos] != -1) {
                            int diff = Math.abs(pos - j);
                            min = Math.min(min, dp[i - 1][pos] + Math.min(diff, n - diff));
                        }
                    }
                    dp[i][j] = min;
                } else {
                    dp[i][j] = -1;
                }
            }
        }
        return key.length() + IntStream.of(dp[key.length() - 1]).filter(num -> num != -1).min().getAsInt();
    }
}

312. Burst Balloons

47.79 %
class Solution {
    public int maxCoins(int[] nums) {
        // dp[i][j] -> maxCoins to burst from i to j
        // i <= k <= j, k is the last ballon to burst
        // dp[i][j] = dp[i, k - 1] + nums[k] + dp[k + 1, j]
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int[][] dp = new int[len][len];
        for (int j = 0; j < len; j++) {
            for (int i = j; i >= 0; i--) {
                if (i == j) {
                    dp[i][j] = nums[i] * (i - 1 >= 0 ? nums[i - 1] : 1)
                                       * (j + 1 < len ? nums[j + 1] : 1);
                } else {
                    int max = 0;
                    for (int k = i; k <= j; k++) {
                        int left = k - 1 < i ? 0 : dp[i][k - 1];
                        int right = k + 1 > j ? 0 : dp[k + 1][j];
                        max = Math.max(max, left + right + nums[k]
                                       * (i - 1 >= 0 ? nums[i - 1] : 1)
                                       * (j + 1 < len ? nums[j + 1] : 1));
                    }
                    dp[i][j] = max;
                }
            }
        }
        return dp[0][len - 1];
    }
}

309. Best Time to Buy and Sell Stock with Cooldown

二刷 07/2022

Version #1 DP with 1 loop

一开始写了一个双重循环的dp也可以过但是比较慢 beats 5%

Time O(N^2)

Space O(N)

class Solution {

    public int maxProfit(int[] prices) {

        int[] dp = new int[prices.length + 1];

        for (int i = 1; i <= prices.length; i++) {

            // if we don't do anything

            dp[i] = dp[i - 1];

            for (int j = i - 1; j > 0; j--) {

                dp[i] = Math.max(dp[i], prices[i - 1] - prices[j - 1] + (j - 2 >= 0 ? dp[j - 2] : 0));

            }

            // System.out.printf("dp[%d]=%d\n", i, dp[i]);

        }

        return dp[prices.length];

    }

}

然后看了一下其实是求当前不操作和当前卖的最大值

只需要维护一个 max{dp[i - 3] - prices[i - 1]}就可以了

还有就是prevMax初始化不可以是0因为会是负数

空间还可以优化成O(1)

Time O(N)

Space O(N)

Runtime: 1 ms, faster than 93.44% of Java online submissions for Best Time to Buy and Sell Stock with Cooldown.

Memory Usage: 42.2 MB, less than 51.71% of Java online submissions for Best Time to Buy and Sell Stock with Cooldown.

class Solution {

    public int maxProfit(int[] prices) {

        if (prices.length < 2) {

            return 0;

        }

        int prevMax = -prices[0];

        int max = 0;

        int[] dp = new int[prices.length];

        // prevprev prev curr

        for (int i = 1; i < prices.length; i++) {

            prevMax = Math.max(prevMax, (i >= 3 ? dp[i - 3] : 0) - prices[i - 1]);

            dp[i] = Math.max(dp[i - 1], prices[i] + prevMax);

        }

        return dp[prices.length - 1];

    }

}

Version #2 Optimized DP
模糊地懂了，这个方法的定义和下面naive的定义稍微有些区别

prevBuy 包含的内容是 buy之前的最大profit和花掉buy的price之后得到的profit最大 -> 相当于负的minCost
当我想要当前sell的时候，我可以比较 prevSell(当前不卖) 和当前卖谁大，就是找到最后一次买入，和Price求差
buy和sell分别代表了， 以sell操作和buy操作结尾的一系列sequence

44.32 %
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int len = prices.length;
        // buy[i]/sell[i] -> Max profit we can get to buy/sell on day i
        // buy[i] = Math.max(buy[i - 1] -> do nothing on day i, sell[i - 2])
        // sell[i] = Math.max(sell[i - 1] ->  do nothing, buy[j] + prices[i])
        // buy[j] -> for any j < i, max buy[j]
        int prevBuy = Integer.MIN_VALUE, currBuy = 0;
        int prevPrevSell = 0, prevSell =0, currSell = 0;
        for (int i = 0; i < len; i++) {
            currBuy = Math.max(prevBuy, prevPrevSell - prices[i]);
            currSell = Math.max(prevSell, prevBuy + prices[i]);
            prevPrevSell = prevSell;
            prevSell = currSell;
            prevBuy = currBuy;
        }
        return currSell;
    }
}




Version #1 Naive TLE DP
class Solution {
    public int maxProfit(int[] prices) {
        // dp[ii][k] -> k transactions on day ii
        //                                       sell on i, by on j, max profit of 2 days before j
        // dp[ii][k] = Math.max(dp[ii - 1][k], prices[i] - prices[j] +  dp[j - 2][k - 1])
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int len = prices.length;
        int[][] dp = new int[len][len / 3 + 2];
        Arrays.fill(dp[0], 0);
        Arrays.fill(dp[1], Math.max(0, prices[1] - prices[0]));
        dp[1][0] = 0;
        int max = dp[1][1];
        for (int k = 1; k < dp[0].length; k++) {
            for (int ii = 2; ii < len; ii++) {
                int minCost = prices[0];
                for (int jj = ii - 1; jj >= 0; jj--) {
                    minCost = Math.min(minCost, prices[jj] - (jj - 2 >= 0 ? dp[jj -2][k - 1] : 0));
                }
                dp[ii][k] = Math.max(dp[ii - 1][k], prices[ii] - minCost);
            }
            max = Math.max(max, dp[len - 1][k]);
        }
        return max;
    }
}



[106,373,495,46,359,919,906,440,783,583,784,73,238,701,972,308,165,774,990,675,737,990,713,157,211,880,961,132,980,136,285,239,628,221,948,939,28,541,414,180,171,640,297,873,59,814,832,611,868,633,101,67,396,264,445,548,257,656,624,71,607,67,836,14,373,205,434,203,661,793,45,623,140,67,177,885,155,764,363,269,599,32,228,111,102,565,918,592,604,244,982,533,781,604,115,429,33,894,778,885,145,888,577,275,644,824,277,302,182,94,479,563,52,771,544,794,964,827,744,366,548,761,477,434,999,86,1000,5,99,311,346,609,778,937,372,793,754,191,592,860,748,297,610,386,146,220,7,113,657,438,482,700,158,884,877,964,777,139,809,489,383,92,581,970,899,947,864,443,490,825,674,906,402,270,416,611,949,476,775,899,837,796,227,232,226,11,266,889,215,6,182,430,5,706,994,128,359,841,439,263,491,689,638,485,763,695,135,800,763,54,569,387,112,316,193,675,546,531,954,571,208,282,557,892,469,875,765,592,374,276,892,843,625,180,249,292,477,882,837,112,46,667,187,93,418,790,903,12,978,510,647,446,597,958,678,897,420,907,256,170,669,920,711,635,995,259,994,634,583,175,380,435,942,739,921,132,455,986,567,464,301,10,579,84,745,717,588,414,375,319,770,310,510,521,88,445,59,460,120,765,480,441,169,374,180,947,179,346,490,417,149,140,577,624,427,238,341,686,623,228,672,859,372,938,567,141,133,671,255,997,272,591,115,340,692,531,235,123,677,980,31,774,135,194,956,723,779,375,546,59,695,616,416,362,38,145,782,184,418,806,444,177,360,485,941,998,85,840,740,545,49,570,17,824,845,749,177,727,238,656,787,425,473,323,683,578,442,436,444,595,367,44,467,93,507,949,598,579,471,1,347,982,232,878,217,845,777,284,527,529,100,482,456,814,457,251,494,419,922,139,706,384,954,365,680,70,810,764,820,992,622,29,697,294,553,655,63,934,827,157,680,812,729,486,403,151,988,926,460,193,294,423,774,715,906,957,598,929,339,119,686,88,228,803,806,743,430,315,224,712,724,69,606,411,271,700,520,179,916,490,652,319,69,245,827,185,200,911,363,335,50,353,551,737,15,429,966,766,307,829,379,184,779,239,254,904,262,719,321,380,253,564,348,878,570,470,313,752,563,164,301,239,856,491,154,795,640,199,940,420,201,254,400,865,886,819,424,292,257,572,112,590,984,421,639,705,707,779,660,4,817,265,465,737,56,564,797,178,552,988,621,98,665,379,607,300,439,269,196,94,860,540,830,756,294,806,321,930,623,206,440,730,829,566,420,488,49,438,447,294,548,804,514,45,383,431,373,424,11,377,868,559,316,831,464,211,710,803,680,665,39,523,951,219,293,909,838,708,663,627,220,100,565,269,982,236,185,194,697,556,767,541,360,103,497,271,919,19,206,73,393,50,421,466,970,329,105,618,17,687,578,260,759,366,334,686,613,616,893,351,847,861,452,454,454,88,135,357,194,220,504,36,916,246,718,172,395,292,613,533,662,983,701,877,842,445,263,529,679,526,31,385,918,898,584,846,474,648,67,331,890,174,766,274,476,414,701,835,537,531,578,7,479,906,93,667,735,435,899,49,953,854,843,326,322,13,865,791,828,686,760,957,655,601,406,185,738,788,519,874,630,440,839,511,149,715,566,988,0,354,498,81,193,335,196,157,515,590,768,366,287,386,502,143,547,659,616,822,479,813,497,222,285,6,453,363,906,388,733,804,624,963,634,319,817,674,754,378,999,373,793,419,246,274,960,1,130,186,576,382,204,227,607,435,299,790,603,196,236,955,654,812,214,297,926,721,977,568,339,913,297,621,783,242,257,483,325,998,164,586,782,597,210,522,369,676,339,626,650,634,477,793,85,12,695,655,53,287,730,0,689,225,805,593,430,610,963,172,148,740,579,16,523,570,802,627,220,664,945,788,500,90,410,916,481,454,538,622,161,373,523,757,446,855,958,390,333,927,253,814,442,77,325,14,655,502,200,791,58,714,951,370,557,261,859,199,46,775,249,369,233,321,733,310,503,539,618,839,272,315,999,229,390,359,528,334,878,342,977,869,704,564,506,867,77,248,674,557,258,710,126,617,531,969,289,578,947,103,581,599,918,686,143,253,56,393,58,144,211,806,285,635,203,194,884,687,653,856,688,623,568,394,749,302,534,631,894,167,111,227,296,41,854,81,147,656,319,748,530,457,340,223,896,77,166,974,659,36,338,177,496,483,690,569,504,211,554,758,732,660,61,62,669,273,0,616,899,789,380,386,357,403,251,926,636,419,148,820,774,485,497,370,907,973,255,277,341,466,254,333,219,819,521,974,213,590,981,697,927,904,717,726,574,94,625,991,378,249,388,786,355,69,318,357,467,695,825,585,940,323,993,549,485,564,833,530,398,789,608,59,541,915,81,681,544,460,318,954,764,879,708,258,276,259,505,649,529,824,914,660,490,666,676,618,339,712,981,802,239,605,270,29,491,41,243,361,644,327,472,460,725,864,129,142,610,782,935,929,63,865,287,316,740,212,152,567,620,591,394,805,586,177,918,516,911,944,427,128,778,930,965,27,633,534,567,575,247,691,571,775,456,622,219,698,772,305,27,810,690,555,222,877,985,493,202,84,180,133,129,539,151,275,234,999,676,629,715,839,6,789,663,467,435,275,580,296,8,73,849,456,681,794,954,543,602,615,4,131,593,778,175,587,670,88,648,79,703,99,457,261,722,357,966,724,523,612,610,376,575,174,2,53,637,478,850,250,238,344,381,543,686,761,582,598,804,12,128,928,133,998,188,598,590,507,898,402,771,703,912,744,317,300,852,631,767,157,278,520,452,721,560,112,206,69,317,498,942,942,963,347,61,186,390,128,946,462,230,551,956,195,960,143,225,654,255,370,778,770,487,192,479,180,505,509,508,717,976,826,346,521,472,148,965,965,971,421,402,233,76,543,533,815,281,986,638,936,139,754,728,779,551,425,17,546,516,862,963,648,127,510,453,311,759,654,550,755,654,567,129,34,927,900,421,961,923,117,766,71,132,680,917,460,609,874,179,336,496,287,61,846,228,871,590,858,404,646,449,770,724,245,634,900,496,157,864,407,632,998,596,451,482,921,102,624,148,346,282,624,150,523,598,492,267,54,889,872,979,38,1,282,513,877,798,994,400,254,435,487,707,459,575,275,297,165,104,468,80,820,571,215,869,381,107,209,762,455,415,810,137,674,304,692,639,304,534,348,938,575,432,471,74,631,291,405,622,352,58,549,832,655,458,688,468,827,447,946,181,908,585,53,905,733,363,210,536,960,577,815,462,193,31,731,8,538,695,936,795,139,782,357,52,492,610,512,544,323,276,649,940,54,749,723,544,365,500,441,284,17,660,748,871,701,591,356,64,34,422,713,978,96,218,756,833,177,832,61,91,764,510,188,415,622,473,549,944,716,998,528,61,829,953,280,284,706,323,981,405,91,887,568,874,725,236,933,41,895,940,375,468,314,667,694,609,631,621,655,640,835,513,461,854,419,455,860,912,572,769,963,213,818,158,840,699,414,969,430,59,855,997,997,884,349,723,837,488,430,671,743,943,310,399,884,423,486,587,491,106,716,0,768,704,483,663,827,587,915,904,742,976,6,455,221,849,920,548,156,35,101,270,684,123,549,649,977,711,965,492,525,130,744,697,910,699,301,285,696,313,117,122,777,163,789,924,543,446,60,214,102,97,45,670,960,23,522,680,178,757,792,633,244,327,129,188,357,733,419,496,774,408,90,615,663,321,526,946,990,273,135,373,719,870,810,798,826,64,971,156,233,587,253,712,384,964,173,511,116,291,639,450,947,623,656,548,605,498,709,143,895,739,663,160,442,820,802,380,413,356,742,744,764,421,355,499,614,678,336,850,1000,463,794,388,478,188,576,822,164,209,465,901,116,729,891,952,611,15,798,731,711,6,459,587,278,996,220,642,563,363,271,16,379,959,332,315,414,659,602,786,571,78,450,544,393,404,953,480,215,771,419,8,738,36,191,138,204,146,923,413,908,998,46,928,678,425,584,372,689,245,721,177,833,44,784,121,164,16,714,680,974,685,340,810,101,301,791,716,697,768,33,901,994,417,353,248,559,807,64,450,724,896,889,880,818,89,495,848,915,450,409,958,413,149,743,782,64,687,196,737,769,311,429,598,585,690,919,331,94,211,633,888,856,844,870,931,934,66,407,121,902,417,522,423,821,196,625,855,830,673,463,181,857,775,374,490,971,751,835,823,770,79,916,80,829,810,856,674,524,352,251,548,899,363,465,0,989,322,51,86,740,542,920,310,365,677,287,688,373,225,774,331,430,482,630,46,567,236,370,502,347,191,137,646,218,634,399,278,423,540,26,612,700,43,508,176,268,525,267,676,257,651,88,349,556,6,463,29,410,753,224,693,535,747,40,854,155,376,192,434,12,342,98,718,639,951,205,923,354,564,988,960,676,965,29,104,898,535,915,868,768,269,294,944,523,145,895,382,53,935,671,518,338,623,524,204,146,900,161,258,739,417,119,825,336,182,123,749,355,188,109,740,945,826,921,123,65,69,682,461,259,661,247,523,796,153,142,851,411,536,190,478,417,296,113,158,263,754,532,368,748,42,890,129,643,717,564,525,5,348,204,383,427,696,861,684,902,591,609,467,837,104,565,168,828,916,645,232,153,794,384,642,753,550,176,142,132,141,192,635,14,634,329,403,790,460,29,512,443,15,74,114,456,487,303,13,822,429,136,113,637,283,542,519,411,564,220,346,907,389,780,479,480,179,385,285,445,393,508,885,697,168,542,357,553,149,710,126,508,271,845,689,231,217,984,848,905,87,168,1000,169,336,672,595,501,411,81,707,708,634,150,722,379,77,762,737,585,419,428,37,869,509,222,335,192,980,209,883,864,215,497,992,155,408,652,927,990,708,439,857,934,838,69,140,713,573,939,338,628,685,412,147,530,643,471,545,58,111,132,665,572,38,176,460,555,997,61,602,471,901,620,830,577,436,495,685,619,600,549,270,77,512,249,697,466,864,336,981,901,573,702,694,937,299,565,436,613,187,377,364,473,405,384,280,658,561,85,987,302,856,107,191,486,464,165,514,948,227,310,133,799,363,481,289,153,990,445,246,454,729,887,980,546,730,528,817,521,437,376,238,965,511,995,432,227,883,550,904,818,556,295,413,786,861,248,113,660,982,445,292,562,722,433,621,783,375,53,236,856,275,898,532,915,804,362,545,373,397,740,453,726,983,665,715,379,176,408,3,911,573,883,195,254,469,758,844,355,409,562,307,752,274,105,227,635,121,335,338,46,993,243,567,765,589,806,405,558,25,246,526,490,306,295,112,847,792,759,881,500,398,791,266,33,372,546,217,286,898,596,955,720,70,9,458,698,367,936,134,95,887,300,975,72,235,77,870,943,511,883,923,619,812,904,990,643,871,346,588,807,957,681,581,195,82,448,146,807,559,21,412,950,536,681,541,856,631,378,258,736,116,580,20,606,748,537,343,681,22,711,628,536,395,422,874,135,519,294,876,185,583,392,253,220,80,341,203,970,825,762,558,942,797,651,290,8,414,375,913,167,977,94,706,970,286,278,349,909,422,887,921,492,467,550,538,555,841,446,199,312,816,562,296,609,39,393,240,763,222,828,802,944,714,325,334,936,995,950,487,433,195,370,498,926,109,543,885,463,687,171,703,985,292,123,314,174,183,588,487,857,63,736,126,156,172,367,313,672,494,56,202,470,821,735,72,812,282,570,756,633,82,52,920,300,199,927,534,214,354,764,84,419,462,5,246,787,305,788,852,58,698,241,184,904,533,333,857,215,531,81,862,567,56,773,741,169,982,965,302,724,145,342,731,184,914,977,933,727,918,420,438,491,300,104,107,730,506,214,214,968,351,66,844,965,758,845,503,495,503,208,281,622,905,49,751,660,268,420,360,354,971,441,565,513,711,283,695,109,432,127,399,177,640,67,77,364,327,943,1000,979,278,526,222,929,120,753,580,743,456,241,148,339,599,919,11,473,101,365,789,465,819,778,134,278,89,598,801,904,681,695,599,43,897,763,193,257,719,410,610,58,72,912,598,793,347,640,725,855,390,754,785,70,449,24,962,843,735,729,893,797,512,390,57,474,336,855,970,389,722,735,464,28,894,664,645,96,357,255,117,795,479,151,790,432,748,780,940,255,204,607,999,989,48,139,945,783,736,826,640,597,171,423,457,972,424,419,140,706,333,648,557,155,707,547,337,66,338,818,829,972,13,500,310,961,668,991,407,386,893,589,308,129,739,689,452,361,822,418,606,961,981,385,132,7,938,102,942,534,154,133,921,51,257,205,281,771,215,508,816,466,744,85,141,163,418,894,386,779,142,137,825,556,764,647,414,792,605,945,36,427,173,907,356,893,875,449,621,181,963,801,14,502,234,495,437,86,635,846,182,182,540,340,648,772,195,93,539,716,573,431,342,989,156,745,436,709,22,532,100,504,0,985,838,461,725,555,219,710,568,914,736,791,507,615,442,494,977,546,519,389,614,78,172,991,255,154,243,495,876,267,948,657,692,46,107,864,168,785,965,740,16,878,713,79,517,68,208,621,13,362,99,379,109,823,960,645,440,944,342,710,267,656,646,639,453,155,867,456,606,328,444,136,89,104,650,36,240,320,31,352,522,520,260,510,981,591,655,668,23,544,320,541,707,133,708,809,972,196,59,383,642,153,993,837,98,300,751,564,399,848,325,903,534,662,201,690,300,404,115,104,600,236,752,651,640,244,254,40,549,304,86,600,755,59,662,106,290,368,725,138,705,28,550,955,277,959,346,721,759,569,420,424,59,989,438,867,725,544,178,575,137,21,536,72,617,194,421,226,378,483,880,688,791,930,97,831,113,711,445,308,813,967,120,769,329,718,899,364,638,308,644,25,138,88,732,922,721,850,835,367,831,292,651,966,268,628,925,205,824,429,917,534,323,887,3,302,134,904,300,678,929,491,229,671,817,442,678,879,373,664,990,53,395,738,570,497,113,322,557,341,641,331,932,830,433,590,738,780,50,446,504,743,311,980,88,224,732,316,664,742,69,146,801,334,41,198,629,690,869,598,612,662,385,637,769,984,316,741,980,2,794,814,730,297,503,734,836,604,674,376,692,277,727,455,975,703,115,25,552,404,460,543,738,86,488,356,929,668,835,222,413,172,221,1000,30,888,350,514,908,870,323,991,201,738,335,189,437,604,316,514,575,531,514,318,43,592,594,9,773,609,952,708,868,291,962,572,772,291,214,992,238,275,36,882,631,376,150,838,376,862,996,258,545,331,907,958,925,503,1,745,559,147,617,487,185,623,287,658,340,84,835,563,168,845,401,395,928,277,136,890,276,45,806,121,264,416,417,596,208,106,738,352,995,746,731,72,258,112,885,445,165,74,847,633,343,721,237,20,91,575,410,765,274,233,738,893,999,283,104,414,981,448,761,47,48,725,459,265,318,564,353,260,896,874,563,492,710,336,952,80,195,326,311,716,167,561,556,234,680,631,112,573,248,422,130,219,134,75,722,188,221,238,193,689,63,787,657,956,214,895,657,169,349,575,577,869,64,325,187,471,535,572,39,872,966,22,232,427,501,855,239,487,263,335,645,461,973,447,923,922,788,286,610,55,708,827,250,355,481,379,322,926,796,815,2,952,268,257,61,795,364,999,535,494,664,619,711,228,411,587,292,345,671,640,231,384,859,88,640,838,904,27,235,605,766,887,23,438,816,764,91,12,324,709,411,659,405,927,769,505,259,383,714,333,652,648,663,604,596,231,114,320,955,689,626,495,758,96,848,43,189,848,656,114,475,349,148,995,467,94,519,141,125,598,738,822,701,194,46,936,332,370,764,944,711,889,568,508,186,981,48,400,69,182,698,25,526,808,272,963,451,335,883,718,199,185,437,81,987,4,274,482,263,509,584,767,141,53,365,14,657,712,837,161,378,525,313,685,183,869,202,382,339,351,686,15,667,636,756,553,848,57,740,862,962,838,410,722,409,589,891,370,520,790,880,276,478,26,459,671,728,301,296,75,194,173,116,938,933,977,812,863,868,286,973,984,265,631,456,436,683,28,126,319,285,62,247,88,60,824,710,26,602,897,765,998,610,138,773,555,153,114,932,21,111,171,282,246,909,419,647,781,166,966,200,521,188,808,295,685,1000,890,353,301,983,862,527,974,241,705,437,523,213,704,421,225,428,310,255,719,243,962,757,27,476,181,138,95,309,122,500,846,627,371,470,759,255,373,520,748,856,459,71,431,782,307,524,644,130,120,56,406,387,435,201,7,392,922,503,578,331,827,954,21,351,869,65,300,697,908,505,315,198,744,892,510,307,985,129,634,773,343,640,702,748,973,594,271,151,254,513,339,843,425,153,19,309,489,333,944,442,904,447,239,487,6,230,988,656,716,488,779,362,738,663,516,432,964,142,823,353,175,797,645,613,553,26,41,946,47,479,181,964,901,251,843,715,211,366,335,16,103,547,171,276,29,165,993,424,274,334,754,982,63,963,904,150,342,301,238,152,314,892,498,958,192,806,208,681,703,970,688,5,809,705,182,230,658,531,793,303,475,825,924,538,488,100,655,524,569,655,430,808,820,402,852,760,691,751,779,868,247,688,545,780,350,400,550,307,577,803,527,302,916,984,829,257,172,392,41,233,241,587,159,176,904,926,540,324,918,177,817,585,722,89,987,476,637,210,980,905,911,547,762,490,197,718,774,982,484,781,675,152,144,412,255,800,480,901,892,309,382,873,469,662,375,499,646,436,410,866,440,708,613,842,663,604,555,133,77,458,66,660,504,635,896,621,126,995,506,7,283,11,610,11,727,667,101,589,309,240,508,368,830,805,4,259,936,39,510,645,772,993,530,932,393,19,82,915,994,853,683,183,797,61,292,942,434,846,265,316,991,751,579,182,162,454,5,194,97,451,906,177,761,988,314,425,5,63,127,565,427,774,66,195,627,731,750,586,874,599,878,759,807]

265. Paint House II

dp[h][c] -> the min cost to paint house h with color c
Naive的思路是在iterate 当前house的k 个color的同时， 再 iterate 前一个house的k个color, 在前一个不等于当前色的cost中找min
但是这里要求O(nk) instead of O(nkk), 所以观察了一下发现对于prev只需要一个min1 和一个min2
具体代码还可以简化，譬如引入prevMin1 和prevMin2 -> 可以避免做两次for (int c = 0; c < COLOR; c++)

还看到有Override costs array的做到Space O(1), 但是我感觉改变input并不好

一刷
69.77 %
class Solution {
    public int minCostII(int[][] costs) {
        // dp[h][c] -> the min cost to paint house h with color c
        if (costs == null || costs.length == 0 || costs[0] == null || costs[0].length == 0) {
            return 0;
        }
        int HOUSE = costs.length;
        int COLOR = costs[0].length;
        int[][] dp = new int[HOUSE][COLOR];
        int min1 = -1;
        int min2 = -1;
        for (int i = 0; i < COLOR; i++) {
            //  min1   min2
            if (min1 == -1 || costs[0][i] <= costs[0][min1]) {
                min2 = min1;
                min1 = i;
            } else if (min2 == -1 || costs[0][i] < costs[0][min2]) {
                min2 = i;
            }
            dp[0][i] = costs[0][i];
            // System.out.println("min1 -> " + min1 + "min2 -> " + min2);
        }
        for (int h = 1; h < HOUSE; h++) {
            for (int c = 0; c < COLOR; c++) {
                if (c == min1) {
                    dp[h][c] = dp[h - 1][min2] + costs[h][c];
                } else {
                    dp[h][c] = dp[h - 1][min1] + costs[h][c];
                }
                // System.out.println(dp[h][c]);
            }
            min1 = -1;
            min2 = -1;
            for (int c = 0; c < COLOR; c++) {
                if (min1 == -1 || dp[h][c] <= dp[h][min1]) {
                    min2 = min1;
                    min1 = c;
                } else if (min2 == -1 || dp[h][c] < dp[h][min2]) {
                    min2 = c;
                }
            }
        }
        return dp[costs.length - 1][min1];
    }
}

255. Verify Preorder Sequence in Binary Search Tree

[6, 1, 0, 3, 2, 5, 8]

             6
            / \
          1   8
         / \
       0   3
           /  \
         2    5

If we walk all the way down to the left, it will be a decreasing sequence
If we see a number greater that its previous number, means we start a right branch
We move up to find the last node that is smaller than curr and attach it to the right

78.36 %
class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null) {
            return false;
        }
        int min = Integer.MIN_VALUE;
        Deque<Integer> deque = new ArrayDeque<>();
        for (int num : preorder) {
            if (num < min) {
                return false;
            }
            while (!deque.isEmpty() && num > deque.peekFirst()) {
                min = deque.removeFirst();
            }
            deque.addFirst(num);
        }
        return true;
    }
}

145. Binary Tree Postorder Traversal

Version #2  Stack Double Push [TODO]

Version #1 Stack -> push right-root reversely

1.1 Create an empty stack2.1 Do following while root is not NULL    a) Push root's right child and then root to stack.    b) Set root as root's left child.2.2 Pop an item from stack and set it as root.    a) If the popped item has a right child and the right child        is at top of stack, then remove the right child from stack,       push the root back and set root as root's right child.    b) Else print root's data and set root as NULL.2.3 Repeat steps 2.1 and 2.2 while stack is not empty.

The tricky part is we can't determine if the current node is fully checked or not
We can only add it to result if both its left and right children are fully checked -> that's why we might have a double push method
So here we firstly push right and then push curr -> and then fully check curr.left
When we come back to curr node, there are 2 situations 1.It comes back from its left child 2.It comes back from its right child
Now if we check stack.peek() == curr.right we know that it is from the left child
    So! We should step into its right subtree to check, right?
    How? Somehow we want to come back after the right subtree check is fully done.
    So we firstly pop right out -> stack.pop()
    And then we push our curr back
    and then we go to curr.right
If stack.peek() != curr.right -> This is the second time we visit curr!
    now we need to add curr.val to result
    Important part is! Remember to SET CURR  = NULL -> so in the next round it will pop from stack

69.78 %
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
Deque<TreeNode> deque = new ArrayDeque<>();
TreeNode curr = root;
while (curr != null || !deque.isEmpty()) {
while (curr != null) {
if (curr.right != null) {
deque.addFirst(curr.right);
}
deque.addFirst(curr);
curr = curr.left;
}
curr = deque.removeFirst();
// curr.right can be null
if (!deque.isEmpty() && curr.right == deque.peekFirst()) {
deque.removeFirst();
deque.addFirst(curr);
curr = curr.right;
} else {
result.add(curr.val); // curr.right has been visited
curr = null;
}
}
return result;
    }
}

Spring Cloud

https://cloud.spring.io/spring-cloud-static/spring-cloud.html


-> Config Server
Bootstrap properties are added with high precedence, so they cannot be overridden by local configuration, by default.

application.yml -> main application context
bootstrap.yml -> locating external configuration

You can disable the bootstrap process completely by setting spring.cloud.bootstrap.enabled=false (e.g. in System properties).

spring.cloud.config.enabled = false -> in child application?

Application Context Hierarchies

It is a feature of Spring that child contexts inherit property sources and profiles from their parent


bootstrap -> high priority from Bootstrap context -> properties from the Spring Cloud Config Server
applicationConfig [classpath:bootstrap.yml] -> configure the child context when its parent is set
                                        -> have lower precedence than the application.yml

do not contain any data from bootstrap.yml, which has very low precedence, but can be used to set defaults.

-> Also inside of config server
Child context can override properties in parent
properties from a child context override those in the parent, by name and also by property source name (if the child has a property source with the same name as the parent, the one from the parent is not included in the child)

Overriding the Values of Remote Properties

spring.cloud.config.allowOverride=true

Customizing the Bootstrap Property Sources

Adding additional beans to bootstrap context(via spring.factories) e.g. from different server/ db

@Configuration
public class CustomPropertySourceLocator implements PropertySourceLocator {

    @Override
    public PropertySource<?> locate(Environment environment) {
        return new MapPropertySource("customProperty",
                Collections.<String, Object>singletonMap("property.from.sample.custom.source", "worked as intended"));
    }

}

@Valid Spring Validation

Hibernate Validation

http://docs.jboss.org/hibernate/validator/4.1/reference/en-US/html/validator-gettingstarted.html#validator-gettingstarted

Consistent Hashing[TODO]

https://www.educative.io/collection/page/5668639101419520/5649050225344512/5709068098338816

TinyURL

Seconds per day -> 24 * 3600 -> 10^5

base64 encoded -> each base64 character encodes 6 bits value

Using base64 encoding, a 6 letter long key would result in 64^6 = ~68.7 billion possible strings
Using base64 encoding, an 8 letter long key would result in 64^8 = ~281 trillion possible strings

URL-Encoded [TODO]

Modern day server -> 256 GB memory

88. Merge Sorted Array

二刷 06/2022

Version #2 Merge from the largest numbers

Time O(M + N)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Sorted Array.

Memory Usage: 41.9 MB, less than 96.28% of Java online submissions for Merge Sorted Array.

class Solution {

    public void merge(int[] nums1, int m, int[] nums2, int n) {

        int p = m + n - 1;

        int p1 = m - 1;

        int p2 = n - 1;

        while (p1 >= 0 && p2 >= 0) {

            if (nums1[p1] > nums2[p2]) {

                nums1[p--] = nums1[p1--];

            } else {

                nums1[p--] = nums2[p2--];

            }

        }

        // Already in place, can be skipped

        // while (p1 >= 0) {

        //     nums1[p--] = nums1[p1--];

        // }

        while (p2 >= 0) {

            nums1[p--] = nums2[p2--];

        }

    }

}

Version #1 Move nums1 elements to the end of the array and merge from small elements - not optimal

此处写了一个bug，就是如果nums1是从小到大move，那么当nums2比nums1短的时候，就是发生nums1自己overwrite自己的情况

e.g.

[1,2,4,5,6,0]

5
[3]
1

所以此处nums1要从end开始move

当然看了答案发现可以从end开始merge，是更优的解法

Time O(M + N)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Sorted Array.

Memory Usage: 43 MB, less than 36.08% of Java online submissions for Merge Sorted Array.

class Solution {

    public void merge(int[] nums1, int m, int[] nums2, int n) {

        if (n == 0) {

            return;

        }

        int p1 = n;

        for (int i = m - 1; i >= 0; i--) {

            nums1[i + n] = nums1[i];

        }

        int p = 0;

        p1 = n;

        int p2 = 0;

      

        while (p1 < m + n && p2 < n) {

            if (nums1[p1] < nums2[p2]) {

                nums1[p++] = nums1[p1++];

            } else {

                nums1[p++] = nums2[p2++];

            }

        }

        while (p1 < m + n) {

            nums1[p++] = nums1[p1++];

        }

        while (p2 < n) {

            // System.out.printf("p=%d, p2=%d, n=%d", p, p2, n);

            nums1[p++] = nums2[p2++];

        }

        

    }

}

一刷

为了不污染nums1的数据 -> 从大到小merge
一个 bug
如果nums1里面的数都merge完毕了-> p1 = -1 -> nums2还没有merge完
则需要继续向里面merge
此时就一个一个的把nums2里面的数放到nums1里面
所以判断是 p1 >= 0 或 nums1[p1] > nums2[p2]
99.99 %
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p = m + n - 1;
        int p1 = m - 1;
        int p2 = n - 1;
        while (p2 >= 0) {
            if (p1 >= 0 && nums1[p1] > nums2[p2]) {
                nums1[p] = nums1[p1];
                p1--;
            } else {
                nums1[p] = nums2[p2];
                p2--;
            }
            p--;
        }
    }
}