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
 */

One thought to “10/08/2017 Sunday! :(”

Leave a Reply

Your email address will not be published. Required fields are marked *