LeetCode(111) -- 221, 223, 227

P221. Maximal Square (Medium)

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Solution

方法一：暴力

public class Solution {
    public int maximalSquare(char[][] matrix) {
        int rows = matrix.length;
        int cols = rows > 0 ? matrix[0].length : 0;
        int maxsqlen = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    int sqlen = 1;
                    boolean flag = true;
                    while (sqlen + i < rows && sqlen + j < cols && flag) {
                        for (int k = j; k <= sqlen + j; k++) {
                            if (matrix[i + sqlen][k] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        for (int k = i; k <= sqlen + i; k++) {
                            if (matrix[k][j + sqlen] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        if (flag) {
                            sqlen++;
                        }
                    }
                    if (sqlen > maxsqlen) {
                        maxsqlen = sqlen;
                    }
                }
            }
        }
        return maxsqlen * maxsqlen;
    }
}

方法二：dp

class Solution {
    public int maximalSquare(char[][] matrix) {
        int rows = matrix.length;
        int cols = rows > 0 ? matrix[0].length : 0;
        int[][] dp = new int[rows + 1][cols + 1];
        int maxsqlen = 0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                    maxsqlen = Math.max(maxsqlen, dp[i][j]);
                }
            }
        }
        return maxsqlen * maxsqlen;
    }
}

方法三：优化dp

class Solution {
    public int maximalSquare(char[][] matrix) {
        int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
        int[] dp = new int[cols + 1];
        int maxsqlen = 0, prev = 0;
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                int temp = dp[j];
                if (matrix[i - 1][j - 1] == '1') {
                    dp[j] = Math.min(Math.min(dp[j - 1], prev), dp[j]) + 1;
                    maxsqlen = Math.max(maxsqlen, dp[j]);
                } else {
                    dp[j] = 0;
                }
                prev = temp;
            }
        }
        return maxsqlen * maxsqlen;
    }
}

P223. Rectangle Area (Medium)

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

My Solution

class Solution {
    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int area = (C - A) * (D - B) + (G - E) * (H - F);
        if (A < G && E < C && F < D && B < H) {
            area -= (Math.min(C, G) - Math.max(A, E)) * (Math.min(D, H) - Math.max(B, F));
        }
        return  area;
    }
}

100%

The Best Solution

class Solution {
    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int total = (D - B) * (C - A) + (G - E) * (H - F);
        int left = Math.max(A, E);
        int right = Math.min(C, G);
        int top = Math.min(D, H);
        int bottom = Math.max(B, F);
        if (right > left && top > bottom)
            return total - (right - left) * (top - bottom);
        return total;
    }
}

P227. Basic Calculator II (Medium)

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

My Solution

class Solution {
    Stack<Integer> integers = new Stack<>();
    Stack<Character> operators = new Stack<>();
    public int calculate(String s) {
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ') {
                continue;
            }
            if (Character.isDigit(s.charAt(i))) {
                int j = i;
                while (j < s.length() && Character.isDigit(s.charAt(j))) {
                    j++;
                }
                integers.push(Integer.parseInt(s.substring(i, j)));
                i = j - 1;
                if (!operators.isEmpty()) {
                    Character topOp = operators.peek();
                    if (topOp == '*' || topOp == '/') {
                        eval();
                    }
                }
            } else {
                if ((s.charAt(i) == '+' || s.charAt(i) == '-') && !operators.isEmpty()) {
                    eval();
                }
                operators.push(s.charAt(i));
            }
        }
        if (!operators.isEmpty()) {
            eval();
        }
        return integers.pop();
    }

    private void eval() {
        Integer second = integers.pop();
        Integer first = integers.pop();
        Character op = operators.pop();
        if (op == '+') {
            integers.push(first + second);
        } else if (op == '-') {
            integers.push(first - second);
        } else if (op == '*') {
            integers.push(first * second);
        } else if (op == '/') {
            integers.push(first / second);
        }
    }
}

20%

The Best Solution

class Solution {
    public int calculate(String s) {
        
        int digit = 0;
        char operator = '+';
        int[] temp = new int[s.length()];
        int index = 0;
        
        for (int i = 0; i < s.length(); i++) {
            
            char x = s.charAt(i);
            
            if (x == ' ' && i < s.length() - 1) {
                continue;
            }
            
            if (x >= '0' && x <= '9') {
                digit = digit * 10 + (x - '0');
                if (i < s.length() - 1) {
                    continue;
                }
            }
            
            switch(operator) {
                case '+': temp[index++] = digit; break;
                case '-': temp[index++] = -digit; break;
                case '*': temp[index - 1] *= digit; break;
                case '/': temp[index - 1] /= digit; break;
            }
            
            operator = x;
            digit = 0;
        }
        
        int result = 0;
        
        for(int i = 0; i < temp.length; i++) {
            result += temp[i];
        } 
        
        return result;
    }
}