2018-06-21

Q1: CommonElemPathSum
Q2: int[], max A[i] + A[j] + j - i, which j >= i
Q3: binary Tree split
Q4: k sub array
Q5: skyline
Q6: findIntegers
Q7: array hopper4
Q8: 01背包
Q9: chess cross
Q10: rounbround tourment

//public class RoundRobinTournament {
    //一个matrix上的D&C 通常都应该传递startX, startY 和size
    public void fill(int[][] input, int startX, int startY, int size) {
        //
        if (size == 1) {
            return;
        }
        int middle = size / 2;
        
        input[startX + middle][startY + middle] = input[startX][startY];
        input[startX + middle][startY] = input[startX][startY] + middle;
        input[startX][startY + middle] = input[startX + middle][startY];
        
        fill(input, startX, startY, middle);
        fill(input, startX, startY + middle, middle);
        fill(input, startX + middle, startY, middle);
        fill(input, startX + middle, startY + middle, middle);
        
    }
//
    public void findCover(int[][] input, int dr, int dc, int tr, int tc, int size, IntWarper t){
        if (size == 1) {
            return; 
        }
        t.i += 1;
        int m = t.i;
        System.out.println(t);  
        int s = size / 2;
         //处理带有特殊棋子的棋盘.tr、tc表示棋盘的入口即左上角的行列号，dr、dc表示特殊棋子的行列位置，size表示棋盘的行数或者列数  
        //左上角
        if (dr < tr + s && dc < tc + s) {
            findCover(input, dr, dc,tr, tc, s, t);
        } else {
            input[tr + s - 1][tc + s - 1] = m;
            //findCover(input, blackX, blackY,startX, startY, middle);
            findCover(input, tr + s - 1, tc + s - 1,tr, tc, s, t);
        }
        
        if (dr <= tr + s - 1 && dc >= tc + s) {
            findCover(input, dr, dc,tr,tc + s, s, t);
        } else {
            input[tr + s - 1][tc + s] = m;
            findCover(input, tr + s - 1, tc + s,tr,tc + s, s, t);
        }
        
        //左下角
        if (dr >= tr + s && dc <= tc + s - 1) {
            findCover(input, dr, dc,tr + s,tc, s, t);
        } else {
            input[tr + s][tc + s - 1] = m;
            findCover(input, tr + s, tc + s - 1,tr + s,tc, s, t);
            
        }
        
        //右上角
        
        //左下角
        if (dr >= tr + s && dc >= tc + s) {
            findCover(input, dr, dc,tr + s,tc + s, s, t);
        } else {
            input[tr + s][tc + s] = m;
            findCover(input, tr + s, tc + s,tr + s,tc + s, s, t);
        }
        int n = 4;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(input[i][j] + " ");
            }
            System.out.println(" ");
            
        }
        System.out.println(" asdfas");

    }

//
    public List<Integer> findMax(int[] weight, int[] val, int maxWeight) {
        int[][] dp = new int[weight.length + 1][maxWeight + 1];//搞疯了
        List<Integer> sol = new ArrayList<>();
        for (int i = 1; i <= weight.length; i++) {//dp[i] -> v[i - 1]
            for (int j = 1; j <= maxWeight; j++) {//i放这里了
                if (j < weight[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                
                } else {
                    int tmp = Math.max(dp[i - 1][j] , dp[i - 1][j - weight[i - 1]] + val[i - 1] );
                    dp[i][j] = tmp;
                }
            }
        }
        int weightRemain =  maxWeight;
        int curItem = weight.length;
        while(weightRemain > 0 ) {//必须单独写, 放里面有重复
            if (dp[curItem][weightRemain] != dp[curItem - 1][weightRemain]) {
                sol.add(weight[curItem - 1]);
                weightRemain -= weight[curItem - 1];//这两句顺序不可换
                curItem--;
            } else {
                curItem--;
            }
        }
        
        return sol;
    }

//
public int minCost(int[] stones) {
        int n = stones.length;
        int[][] dp = new int[n][n];
        // merge arr[i]..arr[j] into one pile, total cost = subarray sum
        int[] prefixSum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + stones[i - 1];
            ;
        }
        // arr[i] + .. arr[j] = prefixSum[ j + 1] - prefixSum[i]
        // dp[i][j] : first i elements into k pile, min cost Wrong
        // dp[i][j]: i to j elements into one pile, min cost
        // = dp[i][k] + dp[k + 1][j] | k : i + 1,...j - 2 Wrong
        // k: i.. ...j
        // 填表顺序出了问题呢
        // base: dp[i][i] = stones[i]
        //for (int i = 0; i < n; i++) {
        //  dp[i][i] = stones[i];
        //}

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                int temp = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    temp = Math.min(temp, dp[i][k] + dp[k + 1][j] + prefixSum[j + 1] - prefixSum[i]);
                }
                dp[i][j] = temp;
            }
        }
        return dp[0][n - 1];

    }
//
package others.question;

class Solution {
    //一旦出现两个连着的1,之后就可以直接return了
    public int findIntegers(int num) {
        int[] fib = new int[32];
    fib[0] = 1;
    fib[1] = 2;
    for (int i = 2; i < 32; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    int bitIdx = 31;
    int result = 0;
    boolean hasOne = false;
    
    if (num == 1) {
        return 2;
    }
    while (bitIdx >= 0) {
        if ((num & (1 << bitIdx)) != 0) {//not == 1
          System.out.println(bitIdx);
            result += fib[bitIdx];
            if (hasOne) {
                return result;
            }
            hasOne = true;
        } else {
            hasOne = false; 
        }
        bitIdx--;
        //System.out.println(bitIdx);
    }
    return result + 1;       
}

//
public class SkyLine {

    public int getArea(Rectangle[] input) {

        List<Wall> walls = new ArrayList<>();
        getWalls(input, walls);
        PriorityQueue<Rectangle> maxHeight = new PriorityQueue<>(new Comparator<Rectangle>() {
            @Override
            public int compare(Rectangle o1, Rectangle o2) {
                return o2.height.compareTo(o1.height);
            }
        });
        maxHeight.add(input[walls.get(0).id]);
        return calArea(walls, input, maxHeight);
    }

    private int calArea(List<Wall> walls, Rectangle[] input, PriorityQueue<Rectangle> maxHeight) {
        int result = 0;
        for (int i = 0; i < walls.size() - 1; i++) {
            Wall cur = walls.get(i);
            Wall next = walls.get(i + 1);
            int diff = next.x - cur.x;
            int curHeight = maxHeight.peek().height;
            if (cur.isLeft && !next.isLeft) {
                maxHeight.remove(input[next.id]);
                result += diff * curHeight;
            }
            if (cur.isLeft && next.isLeft) {
                maxHeight.add(input[next.id]);
                result += diff * curHeight;
            }
            if (!cur.isLeft && !next.isLeft) {
                maxHeight.remove(input[cur.id]);
                result += diff * curHeight;
            }
            if (!cur.isLeft && next.isLeft) {
                maxHeight.remove(input[cur.id]);
                maxHeight.add(input[next.id]);
            }
        }
        return result;

    }

    private void getWalls(Rectangle[] input, List<Wall> walls) {
        int id = 0;
        for (Rectangle r : input) {
            walls.add(new Wall(r.left, id, true));
            walls.add(new Wall(r.right, id, false));
            ++id;
        }
        sort(walls);
    }

    public static void main(String[] args) {
        Rectangle[] data = { new Rectangle(0, 2, 2), new Rectangle(1, 3, 3), new Rectangle(-1, 4, 1), };
        SkyLine test = new SkyLine();
        System.out.println(test.getArea(data));
    }
}
class Rectangle {
    Integer left;
    Integer right;
    Integer height;

    Rectangle(int left, int right, int height) {
        this.left = left;
        this.right = right;
        this.height = height;
    }
}


class Wall implements Comparable<Wall> {
    int x;
    int id;
    boolean isLeft;

    public Wall(int x, int id, boolean isLeft) {
        this.x = x;
        this.id = id;
        this.isLeft = isLeft;
    }

    @Override
    public int compareTo(Wall e) {
        return compare(x, e.x);
    }
}

//

public class KsubArray {
    public int findMax(int[] input, int k) {
        if (input == null || input.length < k || k <= 0) {
            return Integer.MIN_VALUE;
        }
        int[][] dp = calMaxK(input, k);
        return dp[input.length][k];
    }

    private int[][] calMaxK(int[] input, int k) {
        int n = input.length;
        int[][] subMax = getSubMax(input);
        int[][] dp = new int[n + 1][k + 1];
        for (int j = 1; j <= k; j++) {
            for (int i = j; i <= n; i++) {
                int max = Integer.MIN_VALUE;
                for (int m = j - 1; m < i; m++) {
                    max = Math.max(dp[m][j - 1] + subMax[m + 1][i], max);
                }
                dp[i][j] = max;
            }
        }
        return dp;
    }

    private int[][] getSubMax(int[] input) {
        int n = input.length;
        int[][] subMax = new int[n + 1][n + 1];
        for (int i = 0; i < n; i++) {
            int curMax = input[i];
            for (int j = i + 1; j < n; j++) {
                curMax = Math.max(curMax + input[j], input[j]);
                subMax[i + 1][j + 1] = curMax;
            }
        }
        return subMax;
    }
}

//Q
//Q;
public class CommonElemPathSum {
    public Node maxPathSum(Node n1, Node n2){ 
         return calPathSum(n1, n2);
        }
    private Node calPathSum(Node n1, Node n2) {
        Node dummy = new Node(0);
        Node result = dummy;
        Node startN1 = n1;
        Node startN2 = n2;
    
        int sum1 = 0;
        int sum2 = 0;
        while ( n1 != null && n2 != null) {
            if (n1.val < n2.val) {
                sum1 +=n1.val;
                n1 = n1.next;
            } else if (n1.val > n2.val) {
                sum2 +=n2.val;
                n2 = n2.next;
            } else {
                result.next = sum1 > sum2 ? startN1 : startN2;
                while(result.next.val != n1.val) {
                    result = result.next;
                }
                sum1 = sum2 = n1.val;
                startN1 = n1;
                startN2 = n2;
                n1 = n1.next;
                n2 = n2.next;
            }
        }
        
        if (n1 == null) {
            sum2 = addRemaining(n2, sum2);  
        } else {
            sum1 = addRemaining(n1, sum1);  
        }
        result.next = sum1 > sum2 ? startN1 : startN2;
        return dummy.next;
        
    }
    
    private int addRemaining( Node n, int sum) {
        while(n != null) {
            sum += n.val;
            n = n.next;
        }
        return sum;
    }

//Q:
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;
    }

//Q
public int cal(int[] arr) {
  int maxI = A[0];
int result = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
    int curJ = A[j] + j;
    maxI = Math.max(maxI, A[i] - i);
    result = Math.max(curJ + maxI);
  }
  return result;
}