LeetCode之Binary Search题目汇总

LeetCode

我的博客：http://blog.csdn.net/yano_nankai
LeetCode题解：https://github.com/LjyYano/LeetCode

LeetCode 题目汇总

LeetCode之Array题目汇总
LeetCode之Hash Table题目汇总
LeetCode之Linked List题目汇总
LeetCode之Math题目汇总
LeetCode之String题目汇总
LeetCode之Binary Search题目汇总
LeetCode之Divide and Conquer题目汇总
LeetCode之Dynamic Programming题目汇总
LeetCode之Backtracing题目汇总
LeetCode之Stack题目汇总
LeetCode之Sort题目汇总
LeetCode之Bit Manipulation题目汇总
LeetCode之Tree题目汇总
LeetCode之Depth-first Search题目汇总
LeetCode之Breadth-first Search题目汇总
LeetCode之Graph题目汇总
LeetCode之Trie题目汇总
LeetCode之Design题目汇总

文章目录：

Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = 0;
        int rightHeight = 0;
        // 计算leftHeight
        TreeNode p = root;
        while (p != null) {
            p = p.left;
            leftHeight++;
        }
        // 计算rightHeight
        p = root;
        while (p != null) {
            p = p.right;
            rightHeight++;
        }
        // 如果相等，满足2^n-1
        if (leftHeight == rightHeight) {
            return (1 << leftHeight) - 1;
        }
        return 1 + countNodes(root.left) + countNodes(root.right);
    }

Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

    public int divide(int dividend, int divisor) {
        if (divisor == 0) {
            return Integer.MAX_VALUE;
        }
        int result = 0;
        if (dividend == Integer.MIN_VALUE) {
            result = 1;
            if (divisor == -1) {
                return Integer.MAX_VALUE;
            }
            dividend += Math.abs(divisor);
        }
        if (divisor == Integer.MIN_VALUE) {
            return result;
        }
        boolean isNeg = ((dividend ^ divisor) >>> 31 == 1) ? true : false;
        dividend = Math.abs(dividend);
        divisor = Math.abs(divisor);
        int c = 0;
        while (divisor <= (dividend >> 1)) {
            divisor <<= 1;
            c++;
        }
        while (c >= 0) {
            if (dividend >= divisor) {
                dividend -= divisor;
                result += 1 << c;
            }
            divisor >>= 1;
            c--;
        }
        System.out.println(result);
        return isNeg ? -result : result;
    }

Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

数列基本有序，使用二分查找。分为3种情况：

假设数列是n，s是起始下标，e是最后下标，m是中间元素下标。

n[s] < n[e]

0 1 2 4 5 6 7

这种情况，直接返回n[s]。因为数列是有序的，或者只是旋转过一次。如果n[s] < n[e]，则表明没有旋转。最小元素是n[s]。

n[m] > n[s] > n[e]

4 5 6 7 0 1 2

只需要满足n[m] > n[s]即可，因为第一种情况排除后，n[s]就一定会 > n[e]。

在本例中：

n[s] = 4
n[m] = 7
n[e] = 2

则最小值肯定在7之后，到2之间，即 [m+1, e]。

n[m] < n[e] < n[s]

6 7 0 1 2 4 5

n[m] < n[e]，在本例中：

n[s] = 6
n[m] = 1
n[e] = 5

则表明，从m到e，数组已经是上升的，所以最小值在[s, m]。

    public int findMin(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.min(nums[0], nums[1]);
        }
        int s = 0, e = nums.length - 1;
        int m = (s + e) / 2;
        if (nums[s] < nums[e]) {
            return nums[s];
        }
        if (nums[m] > nums[s]) {
            return findMin(Arrays.copyOfRange(nums, m + 1, e + 1));
        }
        return findMin(Arrays.copyOfRange(nums, s, m + 1));
    }

Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

click to show spoilers.

Note:

Your solution should be in logarithmic complexity.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

    public int findPeakElement(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] > nums[mid + 1]) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

    public int firstBadVersion(int n) {
        int low = 1, high = n;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (isBadVersion(mid)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

H-Index II

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

Hint:

1. Expected runtime complexity is in O(log n) and the input is sorted.

    public int hIndex(int[] citations) {
        int n = citations.length;
        int low = 0, high = n - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (citations[mid] == n - mid) {
                return n - mid;
            } else if (citations[mid] < n - mid) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return n - low;
    }

Pow(x, n)

Implement pow(x, n).

    public double myPow(double x, int n) {
        if (n < 0) {
            return 1 / pow(x, -n);
        } else {
            return pow(x, n);
        }
    }
    private double pow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        double v = pow(x, n / 2);
        if (n % 2 == 0) {
            return v * v;
        } else {
            return v * v * x;
        }
    }

Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

    public int[] searchRange(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] == target) {
                int s = m, e = m;
                while (s - 1 >= 0 && nums[s - 1] == target) {
                    s--;
                }
                while (e + 1 < nums.length && nums[e + 1] == target) {
                    e++;
                }
                return new int[] { s, e };
            } else if (nums[m] > target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return new int[] { -1, -1 };
    }

Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (nums[m] == target)
                return m;
            if (nums[l] < nums[m]) {
                if (target <= nums[m] && target >= nums[l])
                    r = m - 1;
                else
                    l = m + 1;
            } else if (nums[l] > nums[m]) {
                if (target >= nums[l] || target <= nums[m])
                    r = m - 1;
                else
                    l = m + 1;
            } else
                l++;
        }
        return -1;
    }

Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

    public boolean search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (nums[m] == target)
                return true;
            if (nums[l] < nums[m]) {
                if (target <= nums[m] && target >= nums[l])
                    r = m - 1;
                else
                    l = m + 1;
            } else if (nums[l] > nums[m]) {
                if (target >= nums[l] || target <= nums[m])
                    r = m - 1;
                else
                    l = m + 1;
            } else
                l++;
        }
        return false;
    }

Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        for (int i = 0; i < nums.length; i++) {
            if (target <= nums[i]) {
                return i;
            }
        }
        return nums.length;
    }

Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

    public int mySqrt(int x) {
        // 首先对负数和0进行处理
        if (x < 0) {
            return -1;
        } else if (x == 0) {
            return 0;
        }
        int start = 1;
        int end = x;
        while (start < end) {
            // 不能直接相加除以2，因为两个数相加可能溢出
            int m = start + (end - start) / 2;
            // 不能用m^2，(m+1)^2，因为可能溢出
            int m1 = x / m;
            int m2 = x / (m + 1);
            // m*2 == x
            if (m == m1) {
                return m;
            }
            // (m+1)^2 == x
            if (m + 1 == m2) {
                return m + 1;
            }
            // m*2 <= x && (m+1)^2 > x
            if (m < m1 && m + 1 > m2) {
                return m;
            }
            // m*2 > x
            if (m1 < m) {
                end = m;
            } else {
                // (m+1)^2 < x
                start = m + 1;
            }
        }
        return 1;
    }