desperado1288

//classical way, same as maximal rectangle
public int maximalSquare(char[][] matrix){
  if(matrix == null || matrix.length == 0)  return 0;
  int m = matrix.length, n = matrix[0].length;
  int[] dp = new int[n+1];
  int max = 0;
  for(int i = 0; i < m; i++){
    for(int j = 0; j < n; j++){
      if(matrix[i][j] == '1'){
        dp[j]++;

desperado1288

public boolean exist(char[][] board, String word){
  if(word.length() == 0){
    return true;
  }
  else if(board == null || board.length == 0){
    return false;
  }
  int m = board.length, n = board[0].length;
  for(int i = 0; i < m; i++){
    for(int j = 0; j < n; j++){

desperado1288

public List<List<Integer>> pathSum(TreeNode root, int sum){
  List<List<Integer>> list = new ArrayList<>();
  pathSumHelper(list, new ArrayList<>(), root, 0, sum);
  return list;
}
private void pathSumHelper(List<List<Integer>> list, List<Integer> templist, TreeNode cur, int sum, int target){
  if(cur == null) return;
  templist.add(cur.val);
  sum += cur.val;
  if(cur.left == null && cur.right == null && sum == target){

desperado1288

//recursive
public boolean isSymmetric(TreeNode root){
  if(root == null)  return true;
  return isSymmetricHelper(root.left, root.right);
}
private boolean isSymmetricHelper(TreeNode left, TreeNode right){
  if(left == null && right == null){
    return true;
  }
  else if(left == null || right == null){

desperado1288

//standard simplied knapsack problem II(infinitely many of each item):
//17ms-20ms
public int coinChange(int[] coins, int amount){
    int[] dp = new int[amount+1];
    Arrays.fill(dp, amount+1);//Since the given memory heap cannot hold array length of Integer.MAX_VALUE, so amount << MAX_VALUE.
    dp[0] = 0;
    for(int coin: coins){
        for(int i = coin; i <= amount; i++) dp[i] = Math.min(dp[i], dp[i-coin] + 1);
    }
    return dp[amount] > amount ? -1 : dp[amount];

desperado1288

//Ugly Number I:
public boolean isUgly(int num){
    while(num > 1){
        if(num % 2 == 0)    num /= 2;
        else if(num % 3 == 0)   num /= 3;
        else if(num % 5 == 0)   num /= 5;
        else    return false;
    }
    return num == 1;
}

desperado1288

//HashMap
public int maxSubArrayLen(int[] nums, int k){
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(k, -1);
    int sum = 0, maxlen = 0;
    for(int i = 0; i < nums.length; i++){
        sum += nums[i];
        maxlen = Math.max(maxlen, i - map.getOrDefault(sum, i));
        map.putIfAbsent(sum + k, i);
    }

desperado1288

//Power of Two:
public boolean isPowerOfTwo(int n){
    return n > 0 && (n & n - 1) == 0;
}

//Power of Three:
//Sol1:
private static final int maxPow3 = (int)Math.pow(3, (int)(Math.log(0x7fffffff)/Math.log(3)));//which is 1162261467
public boolean isPowerOfThree(int n){
    return n > 0 && maxPow3 % n == 0;

desperado1288

//Merge-Sort, count smaller numbers in the right part when doing merge
//10-14ms
public List<Integer> countSmaller(int[] nums){
    int n = nums.length;
    int[] indices = new int[n], result = new int[n];
    for(int i = 0; i < n; i++)  indices[i] = i;
    mergeSort(nums, 0, n, indices, result);
    List<Integer> list = new ArrayList<>();
    for(int i: result)  list.add(i);
    return list;

desperado1288

//HashMap Solution
public int[][] multiply(int[][] A, int[][] B){
    int m = A.length, n = A[0].length, n1 = B[0].length;
    Set<Integer>[] notZero = new HashSet[n];
    int[][] C = new int[m][n1];
    for(int i = 0; i < n; i++){
        notZero[i] = new HashSet<>();
        for(int j = 0; j < n1; j++){
            if(B[i][j] != 0)    notZero[i].add(j);
        }