10/29/2017 Sunday

 BLANK

1. OOD
2.

1.

380. Insert Delete GetRandom O(1)

This implementation is based on two hashmap, and indexVal can be implmented by arraylist.

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
class RandomizedSet {
    Map<Integer, Integer> valIndex;
    Map<Integer, Integer> indexVal;
    Random rand;
    /** Initialize your data structure here. */
    public RandomizedSet() {
        valIndex = new HashMap<Integer, Integer>();
        indexVal = new HashMap<Integer, Integer>();
        rand = new Random();
    }
 
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if(valIndex.containsKey(val)) return false;
        valIndex.put(val, valIndex.size());
        indexVal.put(indexVal.size(), val);
        return true;
    }
 
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(!valIndex.containsKey(val)) return false;
        int targetIndex = valIndex.get(val);
        int shiftVal = indexVal.get(indexVal.size()-1);
        indexVal.put(targetIndex, shiftVal); // Here you must first put and then delete!!!
        indexVal.remove(indexVal.size()-1);
        valIndex.put(shiftVal, targetIndex);
        valIndex.remove(val);
        return true;
    }
 
    /** Get a random element from the set. */
    public int getRandom() {
        return indexVal.get(rand.nextInt(indexVal.size()));
    }
}

10/28/2017 Saturday

 BLANK

1. Memeory-concern Problem
2.

1. Memeory-concern Problem

398. Random Pick Index

Random class

With the random helper

Init() O(1)
Pick() O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    private int[] arr;
    private Random rand;
    public Solution(int[] nums) {
        arr = nums;
        rand = new Random();
    }
 
    public int pick(int target) {
        int res = 0;
        int count = 0;
        for(int i = 0; i<arr.length; i++){
            if( arr[i] == target){
                res = rand.nextInt(++count)==0?i:res;
            }
        }
        return res;
    }
}

10/27/2017 Friday

BLANK

1. Graph

1. Graph

207. Course Schedule

BFS + Topological sort

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
public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList<Integer>[] graph = new ArrayList[numCourses]; 
        // Here is a tricky part
        // Generally, array does not allow generics 
        // however, we define type for reference rather than array object
        // it escapes such problem and supports auto unbox in the fowlling
        int[] degree = new int[numCourses];
        Queue<Integer> queue = new LinkedList<>();
        int count=0; // count the number of nodes with indegree =0
 
        for(int i=0;i<numCourses;i++)
            graph[i] = new ArrayList<Integer>();
 
        for(int i=0; i<prerequisites.length;i++){
            degree[prerequisites[i][1]]++;
            graph[prerequisites[i][0]].add(prerequisites[i][1]);
        }
        for(int i=0; i<degree.length;i++){
            if(degree[i] == 0){
                queue.add(i);
                count++;
            }
        }
 
        while(queue.size() != 0){
            int course = queue.poll();
            for(int i=0; i<graph[course].size();i++){
                int pointer = (int) graph[course].get(i);
                degree[pointer]--;
                if(degree[pointer] == 0){
                    queue.add(pointer);
                    count++;
                }
            }
        }
        return count == numCourses; 
    }
}

DFS

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
public class Solution {
    // adjacent list
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList[] graph = new ArrayList[numCourses];
        for(int i=0;i<numCourses;i++)
            graph[i] = new ArrayList();
 
        boolean[] visited = new boolean[numCourses];
        for(int i=0; i<prerequisites.length;i++){
            graph[prerequisites[i][1]].add(prerequisites[i][0]);
        }
 
        for(int i=0; i<numCourses; i++){
            if(!dfs(graph,visited,i))
                return false;
        }
        return true;
    }
 
    // DFS traverse all the path and check is there is loop
    private boolean dfs(ArrayList[] graph, boolean[] visited, int course){
        if(visited[course])
            return false;
        else
            visited[course] = true;;
 
        for(int i=0; i<graph[course].size();i++){
            if(!dfs(graph,visited,(int)graph[course].get(i)))
                return false;
        }
        visited[course] = false;
        return true;
    }
}

BFS

This version is slow for it uses adjacency matrix instead of adjacency 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
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[][] matrix = new int[numCourses][numCourses]; // i -> j
        int[] indegree = new int[numCourses];
 
        for (int i=0; i<prerequisites.length; i++) {
            int ready = prerequisites[i][0];
            int pre = prerequisites[i][1];
            if (matrix[pre][ready] == 0)
                indegree[ready]++; //duplicate case
            matrix[pre][ready] = 1;
        }
 
        int count = 0;
        Queue<Integer> queue = new LinkedList();
        for (int i=0; i<indegree.length; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }
        while (!queue.isEmpty()) {
            int course = queue.poll();
            count++;
            for (int i=0; i<numCourses; i++) {
                if (matrix[course][i] != 0) {
                    if (--indegree[i] == 0)
                        queue.offer(i);
                }
            }
        }
        return count == numCourses;
    }
}

Union-find

fatal error: although accepted, but cannot handle course which has more than one prerequisites!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
        if(numCourses<2) return true;
        int[] pre = new int[numCourses];
        Arrays.fill(pre, -1);
        for(int[] p : prerequisites){
            int tmp = p[1];
            while(tmp>=0){                
                tmp=pre[tmp];
                if(tmp==p[0])
                    return false;
            }
            pre[p[0]]=p[1];
        }
        return true;
    }
}

10/26/2017 Thursday

 BLANK

1. DP
2. Tree
3. Java8 Stream File Reading

1. DP

322. Coin Change

Brute force

This solution is TLE. It takes backtrack to traverse all possibkle solution.
Time complexity of worst case is O(S^n), where S is the amount, n is the length of coins[]
Space complexity: recursion depth is n => O(n)

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 int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        return helper(coins, amount, coins.length -1);
 
    }
 
    public int helper(int[] coins, int amount, int pos){
        if(amount == 0) return 0;
        if(pos <0 || amount <0) return -1;
        int num = amount / coins[pos];
        int min = Integer.MAX_VALUE;
        for(int i = num; i>=0; i--){
            int temp =  helper(coins, amount - coins[pos] * i, pos-1);
            if(temp == -1) continue;
            else {
                min = Math.min(min, temp +i);
            }
        }
        return min != Integer.MAX_VALUE?min:-1; 
    }
}

Bottom-up DP

Time complexity: O(S*n)
Space complexity: O(S)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        int[] table = new int[amount+1];
        Arrays.fill(table, -1);
        table[0] = 0;
        for(int i =1; i<=amount; i++){
            for(int coin : coins){
                if(i -coin >= 0 && table[i- coin] > -1){
                    if(table[i] == -1) table[i] = Integer.MAX_VALUE;
                    table[i] = Math.min(table[i], table[i-coin]+1);
                }
            }
        }
        return table[amount];  
    }
}

Top-bottom Memoziation

Time complexity: O(S*n)
Space complexity: O(S)

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 int coinChange(int[] coins, int amount) {
        if(amount < 1) return 0;
        int[] table = new int[amount+1];
        return coinChange(coins , amount, table);
    }
 
    public int coinChange(int[] coins, int amount, int[] table){
        if(amount < 0) return -1;
        if(amount ==0) return 0;
        if(table[amount] != 0 ) return table[amount];
        int min = Integer.MAX_VALUE;
        for(int coin : coins){
            int num = coinChange(coins, amount - coin, table);
            if(num != -1){
                min = Math.min(min, num +1);
            }
        }
        table[amount] = min == Integer.MAX_VALUE?-1:min;
        return table[amount];
    }
}

Pruned backtrack

Unbalanced testcases lead to high speed. You shouldn’t expect this one. Just for record.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution{
    int min = Integer.MAX_VALUE;
 
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;       
        Arrays.sort(coins);      
        dfs(coins, amount, coins.length-1, 0);    
        if (min == Integer.MAX_VALUE) return -1;   
        return min;
    }
 
    private void dfs(int[] coins, int remain, int index, int count){
        if (index < 0) return;
        if (count + remain / coins[index] >= min) return;
        if (remain == coins[index]){
            min = Math.min(min, count + 1);
            return;
        }else if (remain > coins[index]){
            dfs(coins, remain - coins[index], index, count + 1);
        }
        dfs(coins, remain, index -1, count);
    }
}

2. Tree

105. Construct Binary Tree from Preorder and Inorder Traversal

Recussion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return construct(preorder, inorder, 0, inorder.length-1, 0);
    }
 
    public TreeNode construct(int[] pre, int[] in, int start, int end, int pos){
        if(start > end) return null;
        if(start == end) return new TreeNode(in[start]);
        int index = find(in, pre[pos]);
        TreeNode root = new TreeNode(pre[pos]);
        root.left = construct(pre, in, start, index-1,pos+1);
        root.right = construct(pre, in, index +1, end, pos+index-start+1);
        return root;
    }
 
    public int find(int[] in, int target){
        for(int i =0; i<in.length; i++){
            if(in[i] == target){
                return i;
            }
        }
        return -1;
    }
}

Recussion

非常巧妙的方法,利用了全局变量不断迭代进入子树,形成了先左后右的规则。速度很快,但是逻辑比较复杂,并不是十分推荐。
Very brilliant method with global vairibles to buld subtree recurssively. It is fast but trick and not recommended, if in interview.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 
    int preIdx = 0, inIdx = 0;
 
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, inorder, Integer.MAX_VALUE);    
    }
 
    private TreeNode buildTree(int[] pre, int[] in, int rootValue) {
        if (inIdx == in.length || in[inIdx] == rootValue) {
            return null;
        }
        TreeNode node = new TreeNode(pre[preIdx]);
        preIdx++;
        node.left = buildTree(pre, in, node.val);
        inIdx++;
        node.right = buildTree(pre, in, rootValue);
        return node;
    }
}

3. Java8 Stream File

Refer

10/24/2017 Tuesday

I did a lot of stuff this weekend and failed use ngrok to make up intranet tunnel for my Raspberry. It seems there is IO time out here, perhaps hardware problem here? If everyone knows the solution, tell me, please!

Today, I have to restart my schedule, which covers oj, system reviewing and bash programming.
Bash Programmig
Here is an example

1
 join -t , t1.csv t2.csv | tr ',' ' '| awk '{if($4=="2")printf $1 " ""%.2f\n", $2/2}'

10/14/2017 Saturday

Readings:

Manacher Algorithm Rabin–Karp algorithm Boyer–Moore string search algorithm

All the above methods are about substring search, code can be got here!

1. Math
2. Array

1. Math

367. Valid Perfect Square

O(sqrt(n))

1 = 1;
4 = 1 + 3;
9 = 1 + 3 + 5;
….

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public boolean isPerfectSquare(int num) {
         int i = 1;
         while (num > 0) {
             num -= i;
             i += 2;
         }
         return num == 0;
     }
}

O(log(n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public boolean isPerfectSquare(int num) {
        int low = 1, high = num;
        while (low <= high) {
            long mid = (low + high) >>> 1;
            if (mid * mid == num) {
                return true;
            } else if (mid * mid < num) {
                low = (int) mid + 1;
            } else {
                high = (int) mid - 1;
            }
        }
        return false;
    }
}

Newton Method

O(log(n))

1
2
3
4
5
6
7
8
9
public class Solution {
    public boolean isPerfectSquare(int num) {
        long x = num;
        while (x * x > num) {
            x = (x + num / x) >> 1;
        }
        return x * x == num;
    }
}

Reach the point

Given two pairs, (a,b) , (c,d), a,b,c,d >0,in each iteration, we can take one operation,(a,a+b) or (a_b, a), check if (c,d) can be reached.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class reach{
	public static void main(String[] args) {
		int[] a1 =new int[]{1,2};
		int[] b1 = new int[]{2,0};
		System.out.println(solution(a1,b1));
	}
 
	public static  boolean solution(int[] a, int[] b){
		if(a[0] > b[0] || a[1] > b[1]){
			return false;
		}else if(a[0] == b[0] && a[1] == b[1]){
			return true;
		}else{
			return solution(new int[]{a[0], a[1] +a[0]}, b) || 
			solution(new int[]{a[0] + a[1], a[1]}, b);
		}
	}
}

2. Array

Given two string, check is one is the rotation of the other one.

O(n^2) but most elegant one

Good talk!

1
2
3
boolean isRotation(String s1,String s2) {
    return (s1.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1);
}

For array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class isrotate{
	public static void main(String[] args) {
		int[] a1 = new int[]{2,3,4,3,1};
		int[] a2 = new int[]{1,2,3,4,5};
		System.out.println(solution(a1, a2));
	}
 
	public static boolean solution(int[] a1, int[] a2){
		if(a1.length != a2.length) return false;
		for(int i =0; i< a1.length; i++){
			int index = i;
			boolean flag = true;
			for(int j =0; j<a1.length; j++){
				if(a2[i++%a2.length] != a1[j]){
					flag = false;
					break;
				}
			}
			if(flag) return true;
			i = index;
		}
		return false;
	}
}

438. Find All Anagrams in a String

Sliding window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        if (s == null || s.length() == 0 || p == null || p.length() == 0) return list;
        int[] hash = new int[256]; 
        for (char c : p.toCharArray()) {
            hash[c]++;
        }
        int left = 0, right = 0, count = p.length();
        while (right < s.length()) {
            if (hash[s.charAt(right++)]-- >= 1) count--; 
            if (count == 0) list.add(left);
            if (right - left == p.length() && hash[s.charAt(left++)]++ >= 0) count++;
        }
        return list;
    }
}

10/08/2017 Sunday! :(

 BLANK

1. Arrays
2. String专题,复杂的算数解析系列

1. Arrays

18. 4Sum

This is vary basic problem set and can be imported to other problems. Generally, we keep a numbers and convet it into 3sum and keep another one and convert into 2 sum.

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
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int len = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        for(int i = 0 ; i < nums.length - 3 ; i++){
            if(nums[i] + nums[i+1] + nums[i+2] +nums[i+3] > target) 
                break; // prune
            if(nums[i] + nums[len -3] + nums[len-2] + nums[len-1] < target) 
                continue; //prune
            if(i != 0 && nums[i] == nums[i-1]) 
                continue; //delete duplicates
 
            /* here is the 3 sum solution */
 
            for(int j = i+1 ; j < nums.length - 2; j++){
                if(nums[i] + nums[j] + nums[j+1] + nums[j+2]  > target) 
                    break; // because of the order, prune 
                if(nums[i] + nums[j] + nums[len-2] + nums[len-1] < target) 
                    continue; // quickly get the largest value and compare , prune
                if(j != i+1 && nums[j] == nums[j-1]) 
                    continue;  //delete duplicates
                // j!= i+1 is very important in deciding we can use duplicates
 
                /* here is the like - 2 sum solution */
                int sum = target - nums[i] - nums[j];
                int lo = j + 1; 
                int hi = nums.length - 1; // for o(n) walk through
                if(nums[i] + nums[j] + nums[lo] + nums[lo+1] > target) break;
                while(lo < hi){
                    if(nums[lo] + nums[hi] == sum){
                        ret.add(Arrays.asList(nums[i] , nums[j] , nums[lo] , nums[hi]));
                        lo++;
                        hi--;
                        while(lo < hi && nums[lo] == nums[lo-1]) lo++; //delete duplicates
                        while(lo < hi && nums[hi] == nums[hi+1]) hi--; //delete duplicates
                    }else if(nums[lo] + nums[hi] < sum){
                        lo++;
                    }else{
                        hi--;
                    }
                }
            }
        }
        return ret;
    }
}

454. 4Sum II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
 
        Map<Integer, Integer> map = new HashMap<>();
        for(int i =0; i<A.length; i++){
            for(int j =0; j<B.length; j++){
                map.put(A[i] + B[j], map.getOrDefault(A[i] + B[j], 0)+1);
            }
        }
        int count = 0;
        for(int i =0; i<C.length; i++){
            for(int j =0; j<D.length; j++){
                if(map.containsKey(-C[i] - D[j])){
                    count += map.get(-C[i] - D[j]);
                }
            }
        }
        return count;
 
    }
}

695. Max Area of Island

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
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int area = dfs(grid, i, j, m, n, 0);
                    max = Math.max(area, max);
                }
            }
        }
        return max;
    }
 
    int dfs(int[][] grid, int i, int j, int m, int n, int area) {
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {
            return area;
        }
        grid[i][j] = 0;
        area++;
        area = dfs(grid, i + 1, j, m, n, area);
        area = dfs(grid, i, j + 1, m, n, area);
        area = dfs(grid, i - 1, j, m, n, area);
        area = dfs(grid, i, j - 1, m, n, area);
        return area;
    }
}

542. 01 Matrix

BFS

This solution is slow but the idea is great. Firstly, we flag all ZERO points. And then we have comoute ONE points.
Then, from the ZERO points, we walk through the matrix and renew the length of ONE points by step of 1. We add all renew points to queue and do such operation in loop.

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
public class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
 
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    queue.offer(new int[] {i, j});
                }
                else {
                    matrix[i][j] = Integer.MAX_VALUE;
                }
            }
        }
 
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                int r = cell[0] + d[0];
                int c = cell[1] + d[1];
                if (r < 0 || r >= m || c < 0 || c >= n || 
                    matrix[r][c] <= matrix[cell[0]][cell[1]] + 1) continue;
                queue.add(new int[] {r, c}); 
                // once renewed, we have to add the point to queue
                // But every point can be added to queue at most once.
                // So the complexity of time and space are both o(n^2)
                matrix[r][c] = matrix[cell[0]][cell[1]] + 1;
            }
        }
 
        return matrix;
    }
}

DFS

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
class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        if(matrix.length==0) return matrix;
 
        for(int i = 0; i<matrix.length; i++)
            for(int j = 0; j<matrix[0].length; j++)
                if(matrix[i][j]==1&&!hasNeiberZero(i, j,matrix)) 
                    matrix[i][j] = Integer.MAX_VALUE;
        // mark all points which is not ajacent tp 0
 
        for(int i = 0; i<matrix.length; i++)
            for(int j = 0; j<matrix[0].length; j++)
                if(matrix[i][j]==1) //dfs all ONE point but the distance is 1(adjacent to ZERO)
                    dfs(matrix, i, j, -1);
 
        return matrix;
    }
 
    // renew from short distance to long, if not shorted, prune this branch
    private void dfs(int[][] matrix, int x, int y, int val){
        if(x<0||y<0||y>=matrix[0].length||x>=matrix.length||matrix[x][y]<=val)
            return;
 
        if(val>0) matrix[x][y] = val;
 
        dfs(matrix, x+1, y, matrix[x][y]+1);
        dfs(matrix, x-1, y, matrix[x][y]+1);
        dfs(matrix, x, y+1, matrix[x][y]+1);
        dfs(matrix, x, y-1, matrix[x][y]+1);
 
    }
    private boolean hasNeiberZero(int x, int y, int[][] matrix){
        if(x>0&&matrix[x-1][y]==0) return true;
        if(x<matrix.length-1&&matrix[x+1][y]==0) return true;
        if(y>0&&matrix[x][y-1]==0) return true;
        if(y<matrix[0].length-1&&matrix[x][y+1]==0) return true;
 
        return false;
    }
}

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
29
30
31
32
33
34
35
class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return matrix;
        }
        int[][] dis = new int[matrix.length][matrix[0].length];
        int range = matrix.length * matrix[0].length;
 
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    dis[i][j] = 0;
                } else {
                    int upCell = (i > 0) ? dis[i - 1][j] : range;
                    int leftCell = (j > 0) ? dis[i][j - 1] : range;
                    dis[i][j] = Math.min(upCell, leftCell) + 1;
                }
            }
        }
 
        for (int i = matrix.length - 1; i >= 0; i--) {
            for (int j = matrix[0].length - 1; j >= 0; j--) {
                if (matrix[i][j] == 0) {
                    dis[i][j] = 0;
                } else {
                    int downCell = (i < matrix.length - 1) ? dis[i + 1][j] : range;
                    int rightCell = (j < matrix[0].length - 1) ? dis[i][j + 1] : range;
                    dis[i][j] = Math.min(Math.min(downCell, rightCell) + 1, dis[i][j]);
                }
            }
        }
 
        return dis;
    }
}

2. String专题,复杂的算数解析系列

640. Solve the Equation

Basic Method

Based on regex of split, split with signal and use Integer.parseInt() can handle the + or –

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
class Solution {
    public String solveEquation(String equation) {
        String left = equation.split("=")[0];
        String right = equation.split("=")[1];
        int[] res1 = evaluate(left);
        int[] res2 = evaluate(right);
        res1[0] -= res2[0];
        res2[1] -= res1[1];
        if (res1[0] == 0 && res2[1] == 0) return "Infinite solutions";
        if (res1[0]==0) return "No solution";
        return "x=" + res2[1]/res1[0];
 
    }
    public int[] evaluate(String s) {
        int[] res = new int[2];
 
        String[] tokens = s.split("(?=[+-])");
        for (String token: tokens) {
            if (token.equals("x") || token.equals("+x")) {
                res[0]++;
            } else if (token.equals("-x")) {
                res[0]--;
            } else if (token.contains("x")) {
                res[0] += Integer.parseInt(token.substring(0, token.length()-1));
            } else {
                res[1] += Integer.parseInt(token);
            }
        }
        return res;
    }
}

Pointes

Although this solution is quicker with pointer manipulation, this is not recomoonded!

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
66
67
68
69
70
71
72
class Solution {
    public String solveEquation(String e) {
        if(e == null || e.length() == 0){
            return "No solution";
        }
        String[] arr = e.split("=");
        String left = arr[0];
        String right = arr[1];
        int lx = getNumX(left);
        int li = getInteger(left);
        int rx = getNumX(right);
        int ri = getInteger(right);       
        if(lx == rx && li == ri){
            return "Infinite solutions";
        }
        if(lx == rx){
            return "No solution";
        }
        return "x" + "=" + ((ri-li)/(lx-rx));
    }
 
    public int getNumX(String s){
        int sum = 0;
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(ch == 'x'){
                int num = 1;
                int j = i - 1;
                while(j >= 0 && Character.isDigit(s.charAt(j))){
                    j--;
                }
                if(j + 1 == i){
                    num = 1;
                }else{
                    num = Integer.parseInt(s.substring(j+1,i));
                }
                if(j >= 0){
                    if(s.charAt(j) == '-'){
                        num = -num;
                    }
                }
                sum += num;
            }
        }
        return sum;
    }
 
    public int getInteger(String s){
        int sum = 0;
        for(int i = 0; i < s.length(); i++){
            int num = 1;
            char ch = s.charAt(i);
            if(Character.isDigit(ch)){
                int j = i + 1;
                while(j < s.length() && Character.isDigit(s.charAt(j))){
                    j++;
                }
                num = Integer.parseInt(s.substring(i, j));
                if(j < s.length() && s.charAt(j) == 'x'){
                    num = 0;
                    continue;
                }
                if(i > 0 && s.charAt(i-1) == '-'){
                    num = -num;
                }
                sum += num;
                i = j;
            }
        }
        return sum;
    }   
}

Regex of split

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
/**
  *[ab, defg]
  *[ab, cdefg]
  *[a, bc, d, ef, g]
  *[abc, defg]
  *[a, b, cd, e, f, g]
  *[ab, defg]
**/
import java.io.*;
import java.util.*;
 
class myCode
{
    public static void main (String[] args) throws java.lang.Exception
    {
        String s1 = "abcdefg";
        String[] a = s1.split("(?:c)");
        print(a);
        String[] b = s1.split("(?=c)");
        print(b);      
        String[] c = s1.split("(?![cf])");
        print(c);           
        String[] d = s1.split("(?<=c)");
        print(d);  
        String[] e = s1.split("(?<!c)");
        print(e); 
        String[] f = s1.split("(?>c)");
        print(f);         
    }
 
    public static void print(String[] s){
        System.out.println(Arrays.toString(s));
        // #1
        //Arrays.asList(strArray).stream().forEach(s -> System.out.println(s));
 
        // #2
        // Stream.of(strArray).forEach(System.out::println);
 
        // #3
        // Arrays.stream(strArray).forEach(System.out::println);
    }
}
 
 
/* 
(?<name>X)    X, as a named-capturing group
(?:X)    X, as a non-capturing group
(?idmsuxU-idmsuxU)     Nothing, but turns match flags i d m s u x U on - off
(?idmsux-idmsux:X)      X, as a non-capturing group with the given flags i d m s u x on - off
(?=X)    X, via zero-width positive lookahead
(?!X)    X, via zero-width negative lookahead
(?<=X)    X, via zero-width positive lookbehind
(?<!X)    X, via zero-width negative lookbehind
(?>X)    X, as an independent, non-capturing group
 */

10/07/2017 Saturday

 680. Valid Palindrome II 653

1. Array
2. Tree
3. OO Design
4. Appendex

1. Array + DP

673. Number of Longest Increasing Subsequence

O(n^2) slotutio but kindo of revised

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length, res = 0, max_len = 0;
        int[] len =  new int[n], cnt = new int[n];
        for(int i = 0; i<n; i++){
            len[i] = cnt[i] = 1;
            for(int j = 0; j <i ; j++){
                if(nums[i] > nums[j]){
                    if(len[i] == len[j] + 1)cnt[i] += cnt[j];
                    if(len[i] < len[j] + 1){
                        len[i] = len[j] + 1;
                        cnt[i] = cnt[j];
                    }
                }
            }
            if(max_len == len[i])res += cnt[i];
            if(max_len < len[i]){
                max_len = len[i];
                res = cnt[i];
            }
        }
        return res;
    }
}

2. Tree

637. Average of Levels in Binary Tree

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<Double> list = new LinkedList<>();
        if(root == null) return list;
        queue.offer(root);
        while(!queue.isEmpty()){
            int len = queue.size(); //Store the length and can be used to level track
            double sum = 0.0;
            for(int i =0; i<len; i++){
                TreeNode node = queue.poll();
                sum += node.val;
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            list.add(sum / len);  
        }
        return list;
    }
}

572. Subtree of Another Tree

One DFS

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
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        return dfs(s, t, false);
    }
 
    public boolean dfs(TreeNode s, TreeNode t, boolean b) {
        if (s == null) {
            if (t == null) {
                return true;
            } else {
                return false;
            } 
        } else {
            if (t == null) {
                return false;
            } else if (b && s.val != t.val) {
                return false;
            }
        }
 
        if (s.val == t.val) {
            boolean left = dfs(s.left, t.left, true);
            boolean right = dfs(s.right, t.right, true);
            if (left && right) {
                return true;
            }
        }
 
        return dfs(s.left, t, false) || dfs(s.right, t, false);
    }
}

Two DFS(my own answer)

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 isSubtree(TreeNode s, TreeNode t) {
        if(check(s, t)){
            return true;
        }else if(s != null){
            return isSubtree(s.left, t) || isSubtree(s.right, t);
        }
        return false;
    }
 
    public boolean check(TreeNode s, TreeNode t){
        if( s == null && t == null){
            return true;
        }
        if(s == null || t == null) return false;
        if(s.val == t.val){
            return check(s.left, t.left) && check(s.right, t.right);
        }else{
            return false;
        }
    }
}

O(n) solution: preorder and string match

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 *Stack, cannot use queue, We have to use FILO method of stack,
 *always keep current route first
 **/
public boolean isSubtree(TreeNode s, TreeNode t) {
    return serialize(s).contains(serialize(t)); // Java uses a naive contains algorithm so to ensure linear time, 
                                                // replace with KMP algorithm
}
 
public String serialize(TreeNode root) {
    StringBuilder res = new StringBuilder();
    serialize(root, res);
    return res.toString();
}
 
private void serialize(TreeNode cur, StringBuilder res) {
    if (cur == null) {res.append(",#"); return;}
    res.append("," + cur.val);
    serialize(cur.left, res);
    serialize(cur.right, res);
}

3. OO

341. Flatten Nested List Iterator

Iterator implementation with stack

Constructor: O(n)
next: O(1)
hasNext: Amortized O(1)

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
public class NestedIterator implements Iterator<Integer> {
    Stack<NestedInteger> stack = new Stack<>();
    public NestedIterator(List<NestedInteger> nestedList) {
        for(int i = nestedList.size() - 1; i >= 0; i--) {
            stack.push(nestedList.get(i));
        }
    }
 
    @Override
    public Integer next() {
        return stack.pop().getInteger();
    }
 
    @Override
    public boolean hasNext() {
        while(!stack.isEmpty()) {
            NestedInteger curr = stack.peek();
            if(curr.isInteger()) {
                return true;
            }
            stack.pop();
            for(int i = curr.getList().size() - 1; i >= 0; i--) {
                stack.push(curr.getList().get(i));
            }
        }
        return false;
    }
}

Iterator implementation with iterator and list

Constructor: O(n)
next: O(1)
hasNext: O(1)

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
public class NestedIterator implements Iterator<Integer> {
    // Solution 1: travel(stack, recursion)
 
    // List<Integer> list;
    // Iterator<Integer> itr; // 注意:Iterator<!!!!>
 
    Iterator<Integer> itr;
    List<Integer> list;
    public NestedIterator(List<NestedInteger> nestedList) {
        list = new ArrayList<>();
        flat(nestedList);
        itr = list.iterator();
    }
 
    public void flat(List<NestedInteger> nestedList) {
        for(NestedInteger item: nestedList) {
            if(item.isInteger())  list.add(item.getInteger());
            else  flat(item.getList());
        }
    }
 
    @Override
    public Integer next() {
        return itr.next();
    }
 
    @Override
    public boolean hasNext() {
        return itr.hasNext();
    }
}

4. Appendex

67. Add Binary

Good Write-up

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() -1, carry = 0;
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if (j >= 0) sum += b.charAt(j--) - '0';
            if (i >= 0) sum += a.charAt(i--) - '0';
            sb.append(sum % 2);
            carry = sum / 2;
        }
        if (carry != 0) sb.append(carry);
        return sb.reverse().toString();
    }
}

10/06/2017 Friday!!!

 BLANK

1.
2.

1. Array

334. Increasing Triplet Subsequence

Naive Solution

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
class Solution {
    public boolean increasingTriplet(int[] nums) {
        int minPrev = Integer.MAX_VALUE;
        int minStart  = Integer.MAX_VALUE;
        int min = Integer.MIN_VALUE;
        int length = 0;
 
        for(int i =0; i<nums.length; i++){
            if(length >= 3 ) return true;
            if(nums[i] > minPrev) return true;
            minStart = Math.min(minStart, nums[i]);
            if(min > nums[i]){
                if(length == 2){
                    minPrev = min;
                    min = nums[i];
                    length = 1;
                }else{
                    min = nums[i];
                    length = 1;    
                } 
            }else if(min < nums[i]){
                length ++;
                min = nums[i];
            }
            if(nums[i] > minStart){
                minPrev = Math.min(minPrev, nums[i]);
            }
        }
        return length >= 3;
    }
}

Elegant one

1
2
3
4
5
6
7
8
9
10
   public boolean increasingTriplet(int[] nums) {
        // start with two largest values, as soon as we find a number bigger than both, while both have been updated, return true.
        int small = Integer.MAX_VALUE, big = Integer.MAX_VALUE;
        for (int n : nums) {
            if (n <= small) { small = n; } // update small if n is smaller than both
            else if (n <= big) { big = n; } // update big only if greater than small but smaller than big
            else return true; // return if you find a number bigger than both
        }
        return false;
    }

public class Solution {

321. Create Maximum Number

Naive Solution

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
    public String removeDuplicateLetters(String s) {
        if (s == null || s.length() <= 1) return s;
 
        Map<Character, Integer> lastPosMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            lastPosMap.put(s.charAt(i), i);
        }
 
        char[] result = new char[lastPosMap.size()];
        int begin = 0, end = findMinLastPos(lastPosMap);
 
        for (int i = 0; i < result.length; i++) {
            char minChar = 'z' + 1;
            for (int k = begin; k <= end; k++) {
                if (lastPosMap.containsKey(s.charAt(k)) && s.charAt(k) < minChar) {
                    minChar = s.charAt(k);
                    begin = k+1;
                }
            }
 
            result[i] = minChar;
            if (i == result.length-1) break;
 
            lastPosMap.remove(minChar);
            if (s.charAt(end) == minChar) end = findMinLastPos(lastPosMap);
        }
 
        return new String(result);
    }
 
    private int findMinLastPos(Map<Character, Integer> lastPosMap) {
        if (lastPosMap == null || lastPosMap.isEmpty()) return -1;
        int minLastPos = Integer.MAX_VALUE;
        for (int lastPos : lastPosMap.values()) {
             minLastPos = Math.min(minLastPos, lastPos);
        }
        return minLastPos;
    }
 
}

10/05/2017 Thursday

 BLANK

1.
2.

1. DP

312. Burst Balloons

Memoization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int DP(int i, int j, int[] nums, int[][] dp) {
        if (dp[i][j] > 0) return dp[i][j];
        for (int x = i; x <= j; x++) {
            dp[i][j] = Math.max(dp[i][j], DP(i, x - 1, nums, dp) + nums[i - 1] * nums[x] * nums[j + 1] + DP(x + 1, j, nums, dp));
        }
        return dp[i][j];
    }
 
    public int maxCoins(int[] iNums) {
        int n = iNums.length;
        int[] nums = new int[n + 2];
        for (int i = 0; i < n; i++) nums[i + 1] = iNums[i];
        nums[0] = nums[n + 1] = 1;
        int[][] dp = new int[n + 2][n + 2];
        return DP(1, n, nums, dp);
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int maxCoins(int[] iNums) {
        int n = iNums.length;
        int[] nums = new int[n + 2];
        for (int i = 0; i < n; i++) nums[i + 1] = iNums[i];
        nums[0] = nums[n + 1] = 1;
        int[][] dp = new int[n + 2][n + 2];
        for (int k = 1; k <= n; k++) { //k is the length of each subset 
            for (int i = 1; i <= n - k + 1; i++) { // i is the start of k length subset
                int j = i + k - 1;// j is the end of k length subset
                for (int x = i; x <= j; x++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][x - 1] + nums[i - 1] * nums[x] * nums[j + 1] + dp[x + 1][j]);
                }
            }
        }
        return dp[1][n];
    }
}