Binary Search

5月5号

1  174  Dungeon Game  动态规划 ，从后向前

    public int calculateMinimumHP(int[][] dungeon) {
        if (dungeon == null || dungeon.length == 0 || dungeon[0].length == 0) return 0;
        int m = dungeon.length, n = dungeon[0].length;
        int[][] np = new int[m][n];
        np[m - 1][n - 1] = Math.max(1, 1 - dungeon[m - 1][n - 1]);
        for (int i = n - 2; i >= 0; i--)
        {
            np[m - 1][i] = Math.max(1, np[m - 1][i + 1] - dungeon[m - 1][i]);
        }
        for (int i = m - 2; i >= 0; i--)
        {
            np[i][n - 1] = Math.max(1, np[i + 1][n - 1] - dungeon[i][n - 1]);
        }
        for (int i = m - 2; i >= 0; i--)
        {
            for (int j = n - 2; j >= 0; j--)
            {
                int down = Math.max(1, np[i + 1][j] - dungeon[i][j]);
                int right = Math.max(1, np[i][j + 1] - dungeon[i][j]);
                np[i][j] = Math.min(down, right);
            }
        }
        return np[0][0];
    }

2 Count Complete Tree Nodes     减半 操作

    int height(TreeNode root) {
        return root == null ? -1 : 1 + height(root.left);
    }
    public int countNodes(TreeNode root) {
        int h = height(root);
        return h < 0 ? 0 :
               height(root.right) == h-1 ? (1 << h) + countNodes(root.right)
                                         : (1 << h-1) + countNodes(root.left);
    }

 5 月 6 号

3 230 Kth Smallest Elemet in a BST   计算左子树节点个数  减半

    public int kthSmallest(TreeNode root, int k) {
        int cou = count(root.left);
        if (k <= cou){
            return kthSmallest(root.left, k);
        }
        else if (k > cou + 1)
        {
            return kthSmallest(root.right, k - cou - 1);
        }
        return root.val;
    }
    public int count(TreeNode root)
    {
        return root == null ? 0 : 1 + count(root.left) + count(root.right);
    }

4 240 Search a2D MatrixII   从右上开始

    public boolean searchMatrix(int[][] matrix, int target) {
                if(matrix == null || matrix.length < 1 || matrix[0].length <1) {
            return false;
        }
         int m = matrix.length, n = matrix[0].length;
         int i = 0, j = n - 1;
         while (i < m && j >= 0)
         {
             if (target == matrix[i][j]) return true;
             else if (target > matrix[i][j]) i++;
             else j--;
         }
         return false;
    }