2018-06-13

Q1:root to target 距离
Q2:检查graph是tree
Q3:count 2 sum 没有重复元素
Q4: count 2 sum, 重复元素只记录1次
Q5:count 2 sum,重复元素记录重数
Q6: leetcode, set matrix to 0
Q7:BST split
Q8: max product
Q9:max sub Array
Q10:加法实现乘除减

\\Q1
public int calDis(Node root, Node target) {
  return helper(root, target);
}

private int helper(Node cur, Node target) {
  if (cur == null) {
    return -1;
  }
  if (cur == target) {
    return 0;
  }
  int left = helper(cur.left, target);
  int right = helper(cur.right, target);
  if (left != -1 || right != -1) {
    return left != -1 ? left + 1 : right + 1;
  }
  return -1;
}

//Q2
public boolean isTree(int n, List<List<Integer>> egdes) {
  if (edges == null || edges.size() != n - 1) {
    return false;
  }
  Map<Integer, Integer> used = new HashMap<>();//val, freq
  for (List<Integer> edge: edges) {
    for (int v : edge) {
        int freq = used.getOrDefault(v, 0);
        used.put(v, freq + 1);
    }
  }
  return used.size() == n;
} 
//Q3
/*case 1 no dup in input*/
int i = 0;
int j = arr.length - 1;
int count = 0;
while (i < j) {
  int sum = arr[i] + arr[j];
  if (sum == target) {
    count++;
    i++; //没有dup时, 有没有j-- 都可以, 下一层自动handle
    j--;
  } else if (sum < target) {
    i++; 
  } else {
    j--;
  }
}

//Q4

int i = 0;
int j = arr.length - 1;
int count = 0;
while (i < j) {
  int sum = arr[i] + arr[j];
  if (sum == target) {
    count++;
    while (i + 1 < j && arr[i + 1] == arr[i]) {
      i++;
    }
    i++; //why 有这一个?
    /*上面的*/
  } else if (sum < target) {
    i++; 
  } else {
    j--;
  }
}
//Q5

int i = 0;
int j = arr.length - 1;
int count = 0;
while (i < j) {
  int sum = arr[i] + arr[j];
  if (sum == target) {
    int countI = 0;
    int countJ = 0;
    while (i + 1 < j && arr[i + 1] == arr[i]) {
      i++;
      countI++;
    }
     while (j - 1 > i && arr[j - 1] == arr[j]) {
      j--;
      countJ++;
    }
    i++;
    j--;
    count += (countI + 1) * (countJ + 1);

  } else if (sum < target) {
    i++; 
  } else {
    j--;
  }
}
//Q6
        public void setZeroes(int[][] matrix) {
            boolean hasZeroFirstRow = false;
            boolean hasZeroFirstCol = false;
            int m = matrix.length;
            int n = matrix[0].length;

            for (int i = 0; i < n; i++) {
                if (matrix[0][i] == 0) {
                    hasZeroFirstRow = true;
                    break;
                }
            }
            for (int i = 0; i < m; i++) {
                if (matrix[i][0] == 0) {
                    hasZeroFirstCol = true;
                    break;
                }
            }

            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    if (matrix[i][j] == 0) {
                        matrix[0][j] = 0;
                        matrix[i][0] = 0;
                    }
                }
            }

            for (int i = 0; i < n; i++) {
                if (matrix[0][i] == 0) {
                    for (int j = 1; j < m; j++) {
                        matrix[j][i] = 0;
                    }
                }
            }

            for (int i = 0; i < m; i++) {
                if (matrix[i][0] == 0) {
                    for (int j = 1; j < n; j++) {
                        matrix[i][j] = 0;
                    }
                }
            }
            if (hasZeroFirstRow) {
                for (int j = 0; j < n; j++) {
                    matrix[0][j] = 0;
                }
            }
            if (hasZeroFirstCol) {
                for (int j = 0; j < m; j++) {
                    matrix[j][0] = 0;
                }
            }


        }
//Q7
public class BSTSplit {
    public TreeNode[]split(TreeNode root, int target) {

        if (root == null) {
            return null;
        }
       return helper(root, new TreeNode[]{null, null}, target);

    }

    private TreeNode[] helper(TreeNode cur, TreeNode[] result, int target){
        if (cur == null) {
            return new TreeNode[]{null, null};
        }

        if (cur.val > target) {

            cur.left = helper(cur.left, result, target)[1];

            cur.right = helper(cur.right, result, target)[1];
            result[1] = cur;
        } else {
            cur.left = helper(cur.left, result, target)[0];
            cur.right = helper(cur.right, result,target)[0];
            result[0] = cur;
        }
        return result;
    }
//Q8
public int findMax(int[] a){
        if (a == null || a.length == 0) {
            return -1;
        }
        int n = a.length;
        int[] dp = new int[n];
        int prefixProduct = 1;
        int result = -1;
        for (int i = 0; i < n; i++) {
            if (prefixProduct > 1) {
                dp[i] = prefixProduct * a[i];
            } else {
                dp[i] = a[i];
            }
            result = Math.max(dp[i], result);
        }
        return result;
    }
//Q9
public int maxProduct(int[] nums) {
            int n = nums.length;
            int maxPre = 1, minPre = 1;
            int result = Integer.MIN_VALUE;
            for (int i = 0; i < n; i++) {
                int temMax = Math.max(Math.max(maxPre * nums[i], nums[i]), minPre * nums[i]);
                minPre = Math.min(Math.min(minPre * nums[i], nums[i]), maxPre * nums[i]);

                maxPre = temMax;
                result = Math.max(maxPre, result);
            }
            return result;
        }
//Q10
  public int minus(int a, int b) {
        return add(a, ~b + 1);
    }

    public int multiple(int a, int b) {
        int result = 0;
        while ( b > 0) {
            result = add(result, a);
            b--;
        }
        return result;
    }

    public int divide(int a, int b) {
        int result = 0;

        while (a > 0) {
            a = minus(a, b);
            result++;
        }
        return result -1;
    }