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 }));

}

}