[TOC]

Two Numbers by

29. The two numbers divide by medium

Title description:

Given two integers, dividend and divisor. Dividing two numbers requires no multiplication, division, and mod operators.

Returns the quotient of dividend divided by divisor.

Input: Dividend = 10, Divisor = 3 Output: 3 Input: Dividend = 7, Divisor = -3 Output: -2Copy the code

Description:

  • Both dividend and divisor are 32-bit signed integers.
  • The divisor is not 0.
  • Assume that our environment can store only 32-bit signed integers with values in the range of [−231, 231 − 1]. In this case, 231 − 1 is returned if the division result overflows.

Answer:

Use bitwise operations instead of multiplication and division + binary search.

Division: dividend/divisor = quotient… remainder

Similarly, division can be understood as adding the number of divisor numbers and then adding the remainder to equal the dividend, for example: 10/3 = 3 * 2 + 3 * 1 + 1, the quotient = 2 + 1 = 3, and the last number that is not multiplied is the remainder, the remainder = 1

Displacement: move one bit to the left, equivalent to multiplying by 2; If we move one to the right, that’s the same thing as dividing by 2.

Take 10/3 for example: the first one matches the condition: I = 1; T >> 1 = 10/2 ^ 1 = 5 > 3; Result = result + 1 << 1 = 0 + 1 * 2 ^ 1 = 2; T = t-3 << 1 = 10-3 * 2 = 4; The second one satisfies the condition: I = 0; T >> 0 = 4/2 ^ 0 = 4 > 3; result = result + 1 << 0 = 2 + 1 * 2 ^ 0 = 3; T = 4-3 << 0 = 4-3 * 2 ^ 0 = 1;Copy the code

In the example above, t is the remainder and result is the quotient we want

Code:

public int divide(int dividend, int divisor) {
    if (divisor == 0) {
        return 0;
    }
    if (dividend == Integer.MIN_VALUE && divisor == -1) {
        return Integer.MAX_VALUE;
    }
    // The absolute value is used to indicate whether two symbols are inconsistent
    boolean negative = (dividend ^ divisor) < 0;
    long t = Math.abs((long) dividend);
    long d = Math.abs((long) divisor);
    int result = 0;
    for (int i = 31; i >= 0; i--) {
        // Find a large enough number 2 ^ I * divisor
        if ((t >> i) >= d) {
            // That's plus 2 to the I
            result += 1 << i;
            // The dividend minus 2 ^ I divisort -= d << i; }}return negative ? - result : result;
}
Copy the code

Pow(x, n)

50. Pow(x, n) medium

Title description:

Implement POW (x, n), that is, compute x to the NTH power function.

Input: 2.00000, 10 Output: 1024.00000 Input: 2.10000, 3 Output: 9.26100 Input: 2.00000, -2 output: 0.25000 Description: 2-2 = 1/22 = 1/4 = 0.25 Description: -100.0 < x < 100.0 2. N is a 32-bit signed integer in the range of −231, 231 − 1.Copy the code

Answer:

1, the first thought must be n times to multiply, violence unravelling.

2. Halve n by half each time.

Each time you calculate, multiply the base to double it.

When n becomes odd, you multiply x less than once.

Finally determine the symbol of the power number, greater than zero return res, if not take the reciprocal.

Code:

public double myPow(double x, int n) {
    double res = 1.0;
    for (inti = n; i ! =0; i/=2) {
        if (i % 2! =0){
            res *= x;
        }
         x *= x;
    }
    return n < 0= =true ? 1/ res : res;
}
Copy the code

Find the minimum value in the rotation sort array

153. Find minimum value in rotation sort array medium

Title description:

Suppose the array sorted in ascending order is rotated at some previously unknown point.

For example, the array [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2].

Please find the smallest element.

You can assume that there are no duplicate elements in the array.

Input: [3,4,5,1,2] output: 1 input: [4,5,6,7,0, 2] output: 0Copy the code

Answer:

Using half search, each time through the loop, compare the median to the number in the left and right subscripts.

Keep decreasing the left and right subscripts to find the number of faults.

Code:

public int findMin(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int l = 0, r = nums.length - 1;
    // If the length is 1, or the array is already ordered, return the first number
    if (l == r || nums[l] < nums[r]) {
        return nums[0];
    }
    // Use the left - and right-most indices of the array each time
    while (l < r) {
        // Half the subscript
        int mid = (l + r) / 2;
        if (mid == l) {
            // There are only two numbers left
            return Math.min(nums[l], nums[r]);
        }
        if (nums[mid] > nums[l]) {
            // The median subscript corresponds to a larger number than the left subscript
            if (nums[mid] < nums[r]) {
                // It is smaller than the right subscript, indicating that the fault occurs between the left subscript and middle subscript
                r = mid - 1;
            } else {
                // If not, the fault occurs between (middle subscripts and right subscripts)
                l = mid + 1; }}else {
            // Determine the fault directly between [left subscript and middle coordinate]r = mid; }}return nums[l];
}
Copy the code

Looking for peak

162. Look for medium peaks

Description:

Peak elements are those whose values are greater than their left and right neighbors.

Given an input array nums where nums[I] ≠ nums[I +1], find the peak element and return its index.

The array may contain multiple peaks, in which case you simply return the location of any one of the peaks.

You can assume that NUMs [-1] = nums[n] = -∞.

Input: nums = [1,2,3,1] output: 2 explanation: 3 is the peak element, and your function should return its index 2. Input: nums = [1,2,1,3,5,6,4] Or return index 5 with a peak element of 6.Copy the code

Answer:

Because in the description of the problem, it’s clear

No nums[I]! = nums[i + 1]

Nums [I] > nums[I +1] = nums[I +1]

3. If there are multiple peak values, return any one of them

So all you have to do is find a binary solution

Code:

public int findPeakElement(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[mid + 1]) {
            right = mid;
        } else {
            left = mid + 1; }}return left;
}
Copy the code

The first incorrect version

Title description:

You are a product manager, currently leading a team to develop a new product. Unfortunately, the latest version of your product did not pass the quality test. Since each version is based on the previous version, all versions after the incorrect version are incorrect.

Suppose you have n versions [1, 2… n] and you want to find the first incorrect version that causes all subsequent versions to fail.

You can tell if version failed in unit tests by calling the bool isBadVersion(version) interface. Implement a function to find the first incorrect version. You should minimize the number of calls to the API.

Given n = 5, and version = 4 is the first incorrect version. Call isBadVersion (3) - >falseCall isBadVersion (5) - >trueCall isBadVersion (4) - >trueSo, 4 is the first incorrect version.Copy the code

Answer:

Mid = left + (right-left) / 2; mid = left + (right-left) / 2

Code:

/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); * /

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1; }}returnleft; }}Copy the code