Super Ugly Number

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.

Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.

Credits:
Special thanks to @peisi for adding this problem and creating all test cases.

public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] ret = new int[n];
        ret[0] = 1;

        int[] indexes  = new int[primes.length];
   
        for(int i = 1; i < n; i++){
            ret[i] = Integer.MAX_VALUE;
   
            for(int j = 0; j < primes.length; j++) {
                if (primes[j] * ret[indexes[j]] < ret[i]) {
                    ret[i] = primes[j] * ret[indexes[j]];
                }
            }
   
            for(int j = 0; j < indexes.length; j++){
                if(ret[i] == primes[j] * ret[indexes[j]]){
                    indexes[j]++;
                }
            }
        }
   
        return ret[n - 1];
    }
}

Burst Balloons

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note: 
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 167

    nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
   coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

Credits:
Special thanks to @peisi for adding this problem and creating all test cases.

public class Solution {
    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int[][] dp = new int[nums.length][nums.length];
        for (int len = 1; len <= nums.length; len++) {
            for (int start = 0; start <= nums.length - len; start++) {
                int end = start + len - 1;
                for (int i = start; i <= end; i++) {
                    int coins = nums[i] * getValue(nums, start - 1) * getValue(nums, end + 1);
                    coins += i != start ? dp[start][i - 1] : 0; // If not first one, we can add subrange on its left.
                    coins += i != end ? dp[i + 1][end] : 0; // If not last one, we can add subrange on its right
                    dp[start][end] = Math.max(dp[start][end], coins);
                }
            }
        }
        return dp[0][nums.length - 1];
    }

    private int getValue(int[] nums, int i) { // Deal with num[-1] and num[num.length]
        if (i < 0 || i >= nums.length) {
            return 1;
        }
        return nums[i];
    }
}

Sparse Matrix Multiplication

Given two sparse matrices A and B, return the result of AB.

You may assume that A's column number is equal to B's row number.

Example:

A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]

B = [
  [ 7, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 1 ]
]


     |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
                  | 0 0 1 |

public class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int m = A.length, n = A[0].length, nB = B[0].length;
        int[][] C = new int[m][nB];

        for(int i = 0; i < m; i++) {
            for(int k = 0; k < n; k++) {
                if (A[i][k] != 0) {
                    for (int j = 0; j < nB; j++) {
                        if (B[k][j] != 0) C[i][j] += A[i][k] * B[k][j];
                    }
                }
            }
        }
        return C;  
    }
}

Minimum Height Trees

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3

return [1]

Example 2:

Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5

return [3, 4]

Hint:

1. How many MHTs can a graph have at most?

Note:

(1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”

(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

Credits:
Special thanks to @peisi for adding this problem and creating all test cases.

public class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res = new ArrayList<>();
        if (n == 0) {
            return res;
        }
        if (n == 1) {
            res.add(0);
            return res;
        }
        List<Set<Integer>> adjacent = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjacent.add(new HashSet<Integer>());
        }
        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            adjacent.get(from).add(to);
            adjacent.get(to).add(from);
        }
        LinkedList<Integer> leaves = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (adjacent.get(i).size() == 1) {
                leaves.add(i);
            }
        }
        int numOfLeaves = n;
        while (numOfLeaves > 2) {
            numOfLeaves -= leaves.size();
            int count = leaves.size();
            while (count-- > 0) {
                int from = leaves.poll();
                int to = adjacent.get(from).iterator().next();
                adjacent.get(to).remove(from);
                if (adjacent.get(to).size() == 1) {
                    leaves.add(to);
                }
            }
        }
        return leaves;
    }
}

Best Time to Buy and Sell Stock with Cooldown

Say you have an array for which the i^th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

• You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
• After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

Credits:
Special thanks to @peisi for adding this problem and creating all test cases.

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int n = prices.length;
        int buy[] = new int[n];
        int sell[] = new int[n];
        buy[0] = -prices[0];
        sell[0] = 0;
        for (int i = 1; i < prices.length; i++) {
            buy[i] = Math.max(buy[i - 1], (i == 1 ? 0 : sell[i - 2]) - prices[i]);
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
        }
        return sell[n - 1];
    }
}

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int n = prices.length;
        int buy = -prices[0];
        int sell = 0;
        int prevSell = 0;
       
        for (int i = 1; i < prices.length; i++) {
            int tmpBuy = buy;
            buy = Math.max(buy, prevSell - prices[i]);
            prevSell = sell;
            sell = Math.max(sell, tmpBuy + prices[i]);
        }
        return sell;
    }
}

Additive Number

Additive number is a string whose digits can form additive sequence.
A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
For example:
"112358" is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.

1 + 99 = 100, 99 + 100 = 199

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.
Follow up:
How would you handle overflow for very large input integers?
Credits:
Special thanks to @jeantimex for adding this problem and creating all test cases


public class Solution {
    public boolean isAdditiveNumber(String num) {
        if (num == null || num.length() == 0) {
            return false;
        }
        return helper(num, 0, null, null);
    }
   
    private boolean helper(String num, int position, String pre2, String pre1) {
        if (pre2 != null && pre1 != null) {
            String sum = addTwoNumber(pre2, pre1);
            if (num.substring(position).startsWith(sum)) {
                if (num.length() == position + sum.length()) {
                    return true;
                } else if (num.length() > position + sum.length()) {
                    return helper(num, position + sum.length(), pre1, sum);
                }
            }
            return false;
        } else if (position < num.length()) {
            for (int i = position; i < num.length(); i++) {
                if (i != position && num.charAt(position) == '0') continue;
                if (pre2 == null) {
                    if (helper(num, i + 1, num.substring(position, i + 1), pre1)) return true;
                } else if (pre1 == null) {
                    if (helper(num, i + 1, pre2, num.substring(position, i + 1))) return true;
                }
            }
        }
        return false;
    }
   
    public String addTwoNumber(String str1, String str2) {
        StringBuilder sb = new StringBuilder();
        int p1 = str1.length() - 1;
        int p2 = str2.length() - 1;
        int carry = 0;
        while (p1 >= 0 || p2 >= 0 || carry != 0) {
            int val = carry;
            val += p1 >= 0 ? (str1.charAt(p1) - '0') : 0;
            val += p2 >= 0 ? (str2.charAt(p2) - '0') : 0;
            carry = val / 10;
            val %= 10;
            sb.append(val);
            p1--;
            p2--;
        }
        return sb.reverse().toString();
    }
}

Number of Islands II

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:

Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]].
Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

0 0 0
0 0 0
0 0 0

Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

1 0 0
0 0 0   Number of islands = 1
0 0 0

Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

1 1 0
0 0 0   Number of islands = 1
0 0 0

Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

1 1 0
0 0 1   Number of islands = 2
0 0 0

Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

1 1 0
0 0 1   Number of islands = 3
0 1 0

We return the result as an array: [1, 1, 2, 3]

Challenge:

Can you do it in time complexity O(k log mn), where k is the length of the positions?

public class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        int[] roots = new int[m*n];
        Arrays.fill(roots, -1);
   
        int[] xOffset ={0, 0, 1, -1};
        int[] yOffset = {1, -1, 0, 0};
        List<Integer> result = new ArrayList<Integer>();
        for(int[] position : positions){
            int pointID = position[0]*n + position[1];
            roots[pointID] = pointID;
            int count = result.isEmpty()? 1 : result.get(result.size()-1) + 1;
            for(int i = 0; i < 4; i++){
                int newX = xOffset[i] + position[0];
                int newY = yOffset[i] + position[1];
                if(newX >= 0 && newX < m && newY >= 0 && newY < n && roots[newX * n + newY] != -1){
                    int root1 = find(newX * n + newY, roots);
                    if(root1 != pointID) count--;
                    roots[root1] = pointID;
                }
            }
            result.add(count);
        }
        return result;
    }
   
    public int find(int target, int[] roots){
        if(roots[target] == target) return target;
        return find(roots[target], roots);
    }
}

Range Sum Query 2D - Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

Note:

1. You may assume that the matrix does not change.
2. There are many calls to sumRegion function.
3. You may assume that row1 ≤ row2 and col1 ≤ col2.

public class NumMatrix {
    int dp[][];
   
    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        dp = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
    }
}


// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix = new NumMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);

Range Sum Query - Immutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:

1. You may assume that the array does not change.
2. There are many calls to sumRange function.

public class NumArray {
   
    int[] sums;

    public NumArray(int[] nums) {
        this.sums = new int[nums.length + 1];
        sums[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            sums[i + 1] = nums[i] + sums[i];    
        }
    }

    public int sumRange(int i, int j) {
        return sums[j + 1] - sums[i];
    }
}


// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);

Smallest Rectangle Enclosing Black Pixels

An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location (x, y) of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.

For example, given the following image:

[
  "0010",
  "0110",
  "0100"
]

and x = 0, y = 2,

Return 6.

public class Solution {
    public int minArea(char[][] image, int x, int y) {
        int left = getLeftRightMost(image, y, true);
        int right = getLeftRightMost(image, y, false);
        int up = getUpBottomMost(image, x, true);
        int bottom = getUpBottomMost(image, x, false);
        return (right - left + 1) * (-up + bottom + 1);
    }
   
    private int getUpBottomMost(char[][] image, int x, boolean up) {
        int height = image.length;
        int width = image[0].length;
        int start = up ? 0 : x;
        int end = up ? x : height - 1;
        int res = 0;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            boolean black = false;
            for (int i = 0; i < width; i++) {
                if (image[mid][i] == '1') {
                    black = true;
                    break;
                }
            }
            if (!black) {
                if (up) start = mid + 1;
                else {
                    end = mid - 1;
                }
            } else {
                res = mid;
                if (up) end = mid - 1;
                else {
                    start = mid + 1;      
                }
            }
        }
        return res;
    }
   
    private int getLeftRightMost(char[][] image, int y, boolean left) {
        int height = image.length;
        int width = image[0].length;
        int start = left ? 0 : y;
        int end = left ? y : width - 1;
        int res = 0;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            boolean black = false;
            for (int i = 0; i < height; i++) {
                if (image[i][mid] == '1') {
                    black = true;
                    break;
                }
            }
            if (!black) {
                if (left) start = mid + 1;
                else end = mid - 1;
            } else {
                res = mid;
                if (left) end = mid - 1;
                else {
                    start = mid + 1;      
                }
            }
        }
        return res;
    }
}

Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:

"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

Credits:
Special thanks to @hpplayer for adding this problem and creating all test cases.

public class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new LinkedList<>();
        if (s == null) {
            return res;
        }
        //Remove proceeding ")".
        int i = 0;
        while (i < s.length() && s.charAt(i) != '(') i++;
        s = s.substring(0, i).replace(")", "") + ((i == s.length())?"" : s.substring(i));

        //Remove trailing "("
        int j = s.length() - 1;
        while (j >= 0 && s.charAt(j) != ')') j--;
        s = s.substring(0, j+1) + ((j == s.length()-1)? "" : s.substring(j+1).replace("(", ""));

        HashSet<String> visited = new HashSet<>();
        visited.add(s);
        LinkedList<String> queue = new LinkedList<>();
        queue.add(s);
        boolean isValid = false;
        while (!queue.isEmpty() && !isValid) {
            int count = queue.size();
            while (count-- > 0) {
                String str = queue.poll();
                if (isValid(str)) {
                    res.add(str);
                    isValid = true;
                } else {
                    for (int position = 0; position < str.length(); position++) {
                        if (str.charAt(position) != '(' && str.charAt(position) != ')') continue;
                        String nextStr = str.substring(0, position) + str.substring(position + 1);
                        if (visited.add(nextStr)) {
                            queue.add(nextStr);
                        }
                    }
                }
            }
        }
        return res;
    }
 
    private boolean isValid(String str) {
        int left = 0;
        for (char c : str.toCharArray()) {
            if (c == '(') {
                left++;
            } else if (c == ')') {
                left--;
                if (left < 0) return false;
            }
        }
        return left == 0;
    }
}

=================

Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Credits:

Special thanks to @pbrother for adding this problem and creating all test cases.

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;

        for(int x : nums) {
            int i = binarySearch(dp, 0, len - 1, x);
            if(i < 0) i = -(i + 1);
            dp[i] = x;
            if(i == len) len++;
        }

        return len;
    }
   
    private int binarySearch(int[] dp, int start, int end, int element) {
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (dp[mid] == element) {
                return mid;
            } else if (dp[mid] > element) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -(start + 1);
    }
}

zigzag print

1. zigzag print一个matrix，input: [ [1, 2, 3], [4, 5, 6] ] 

output: [ [1], [2, 4], [3, 5], [6] ]

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

public class Solution {

public void zigzagPrint(List<List<Integer>> input) {

int index = 0;

boolean print = true;

while (print) {

print = false;

int tmpIndex = index;

for (List<Integer> list : input) {

if (tmpIndex < list.size()) {

print = true;

System.out.print(list.get(tmpIndex));

}

if (tmpIndex == 0) break;

tmpIndex--;

}

if (print)

System.out.println();

index++;

}

}

public static void main(String args[]) {

Solution solution = new Solution();

List<List<Integer>> input = new ArrayList<>();

input.add(Arrays.asList(1, 2, 3));

input.add(Arrays.asList(4, 5, 6));

solution.zigzagPrint(input);

}

}

Max Value using +, * and ()

第二轮是一个abc或者中国人，口语屌炸。问了我第二个intern proj。 开始想出Bigint，我说已经在电面做过了。 然后他就另外出了一个找最大值的题。给一个数组[1,1,2,1]，然后用+ * （）三个操作求出这个数组的最大值，这个题返回6。 很简单，DP解决。我开始写了个用res[i][j] 表示的solution，然后写完代码，测了几个用例，都过了。然后他问如果数组里面有负数和0咋办呢。 我说维护两个表max[i][j] 和 min[i][j]。然后他很满意。我说其实还有复杂度更低的方法，可以用一位数组做。他说不用了，这个方法已经够好了，不要求写那么复杂。 然后面完还有10分钟，他问我有什么问题没有，我一听慌了，连时间都没有用完是不是不好，我就问他这个是不是没面好的征兆。他说不是不是，因为我已经很快给出solution，而且代码也没有问题，还给出了follow up的思路，就够了，说有时候时间没用完也是面的好的表现。 我听完心里放松了一些，然后和他唠了唠team之间的工作什么的，只是为了把时间耗完

public class Solution {

public int getMax(int[] nums) {

int n = nums.length;

int maxResult[][] = new int[n][n];

for (int len = 1; len <= n; len++) {

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

int end = start + len - 1;

if (end >= n) {

continue;

}

if (start == end) {

maxResult[start][end] = nums[start];

continue;

}

for (int mid = start; mid < end; mid++) {

maxResult[start][end] = Math.max(maxResult[start][end],

Math.max(maxResult[start][mid] + maxResult[mid + 1][end],

maxResult[start][mid] * maxResult[mid + 1][end]));

}

}

}

return maxResult[0][n - 1];

}

public static void main(String args[]) {

Solution solution = new Solution();

System.out.println(solution.getMax(new int[] { 1, 1, 2, 1 }));

}

}

getWeight recurseive structure

1 given [1, [2,3], [[4]]], return sum. 计算sum的方法是每向下一个level权重+1， 例子的sum = 1 * 1 + (2 + 3) * 2 + 4 * 3。follow up：每向下一个level 权重 - 1， sum = 3 * 1 +（2 + 3）* 2 + 4 * 1 

import java.util.ArrayList;
import java.util.List;

public class Solution {

public static class Node {

}

public static class ValNode extends Node {
int val;
public ValNode(int v) {
this.val = v;
}
}

public static class ListNode extends Node {
List<Node> nodes;
public ListNode() {
nodes = new ArrayList<Node>();
}

public void addNode(Node node) {
this.nodes.add(node);
}
}

public static int getWeightIncrease(Node node, int weight) {
int res = 0;
if (node instanceof ValNode) {
res += weight * ((ValNode) node).val;
} else {
ListNode list = (ListNode) node;
for (Node child : list.nodes) {
res += getWeightIncrease(child, weight + 1);
}
}
return res;
}

public static void main(String args[]) {
ListNode all = new ListNode();
Node node1 = new ValNode(1);
ListNode node2 = new ListNode();
node2.addNode(new ValNode(2));
node2.addNode(new ValNode(3));

ListNode node3 = new ListNode();
ListNode sub = new ListNode();
node3.addNode(sub);
sub.addNode(new ValNode(4));

all.addNode(node1);
all.addNode(node2);
all.addNode(node3);

System.out.println(getWeightIncrease(all, 0));
}
}

print path from leftup to rightdown

M*N的地图上0表示可以走，1表示不能走，求从左上角到右下角的最短路径
很显然的BFS，也很快把基本的写出来了，然而我BFS每一步存了路径，大哥说这样内存消耗太大，怎么improve，然后在提示下想到每个node存一个路径上从哪来的信息，最后反过来打印。
然而悲剧就此来了，因为存的坐标信息是（x,y)，python的tuple是immutable的，存[x,y]的list初始化成M*N又有问题。然后想着建个class用coordinates表示x,y，然后一直有bug，到结束了都没有run出来，面完多看了眼就发现初始化coordinate的class应该初始化M*N个而不是直接复制（那样都是引用，导致最后改一个都改了）。因为这种问题跪了真是不甘心

import java.util.LinkedList;

public class Solution {

public String findPath(int[][] board) {
int m = board.length;
int n = board[0].length;
LinkedList<int[]> queue = new LinkedList<int[]>();
queue.add(new int[] { 0, 0 });
boolean find = false;
while (!queue.isEmpty()) {
int count = queue.size();
while (count-- > 0) {
int[] point = queue.poll();
int x = point[0];
int y = point[1];
if (x == m - 1 && y == n - 1) {
find = true;
break;
}
if (x > 0 && board[x - 1][y] == 0) {
board[x - 1][y] = 2;// up
queue.add(new int[] { x - 1, y });
}
if (x < m - 1 && board[x + 1][y] == 0) {
board[x + 1][y] = 3;// down
queue.add(new int[] { x + 1, y });
}
if (y > 0 && board[x][y - 1] == 0) {
board[x][y - 1] = 4;// left
queue.add(new int[] { x, y - 1 });
}
if (y < n - 1 && board[x][y + 1] == 0) {
board[x][y + 1] = 5;
queue.add(new int[] { x, y + 1 });
}
}
if (find) break;
}
if (!find) return "No Path";
String res = "";
int x = m - 1;
int y = n - 1;
while (x != 0 || y != 0) {
int dir = board[x][y];
if (dir == 2) {
res = "up ->" + res;
x++;
} else if (dir == 3) {
res = "down ->" + res;
x--;
} else if (dir == 4) {
res = "left ->" + res;
y++;
} else if (dir == 5) {
res = "right ->" + res;
y--;
}
}
return res;
}

public static void main(String args[]) {
Solution s = new Solution();
int[][] board = {{0, 1, 1, 1, 0}, {0, 1, 0, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 0, 1, 0}};
System.out.println(s.findPath(board));
}
}