@Yano 2015-12-30T03:24:58.000000Z 字数 7282 阅读 7399

# LeetCode之Binary Search题目汇总

LeetCode

LeetCode 题目汇总

# 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 2h 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.

n[s] < n[e]

0 1 2 4 5 6 7

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

4 5 6 7 0 1 2

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

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

6 7 0 1 2 4 5

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

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

    public int findMin(int[] nums) {        if (nums.length == 1) {            return nums;        }        if (nums.length == 2) {            return Math.min(nums, nums);        }        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;    }

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(xn).

    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;    }  • 私有
• 公开
• 删除