191. Number of bits 1, power of 231. 2, 190. Reverse binary, 371. Sum of two integers

136. A number that appears only once

Given an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once.

Description:

Your algorithm should have linear time complexity. Can you do it without using extra space?

Example 1:

Input: [2,2,1] output: 1Copy the code

Example 2:

Input: [4,1,2, 2] Output: 4Copy the code

Solution 1: violence

  • For each number, look through the array to see if there are any identical elements
  • The complexity of the
    • Time: O (n ^ 2)
    • Space: the O (1)
public int singleNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            boolean flag = true;
            for (int j = 0; j < nums.length; j++) {
                if(nums[i] == nums[j] && i ! = j) { flag =false;
                    continue; }}if (flag) return nums[i];
        }

        return nums[0];
    }
Copy the code

Solution 2: Space for time (Set)

  • A double loop is used to determine whether there are duplicate elements. Can we reduce the time complexity by introducing a container? Yes, that’s a good place to use Set. Add all elements to the set in turn and determine if any are duplicated. What about the non-repeating elements? The sum of all elements and uniqueSum of all non-repeating elements =2* uniquesum-sum.
  • Complexity:
    • Time: O(n), just go through it once
    • Space: O(n), to introduce a set to hold all data
public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int sum = 0, uniqueSum = 0; 
        for (int i = 0; i < nums.length; i++) {
            // set.add (), returns Boolean (Whether the current element was added successfully (does not exist))
            if (set.add(nums[i])) uniqueSum += nums[i];
            sum += nums[i];
        }
        // All numbers except one appear twice
        // So the unique number = 2 * occurs once the sum of digits - currently all digits sum
        return 2 * uniqueSum - sum;
    }
Copy the code

Solution 3: Bit operation (xOR)

  • Any number or itself equals 0
  • The complexity of the
    • Time: O (n)
    • Space: the O (1)
// Time: O (n), Space: O (1)
public int singleNumber(int[] nums) {
        int res = 0;
    	// 1.a ^ a = 0
        // 2. Commutative law =====> The result of all xOR numbers is unique
        for (int i = 0; i < nums.length; i++) res ^= nums[i];
        return res;
    }
Copy the code

268. Missing numbers (¹)

Given a field containing 0, 1, 2… , the sequence of n numbers in n, find 0.. The number in n that does not appear in the sequence.

Example 1:

Input: [3,0,1] output: 2Copy the code

Example 2:

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

Note: Your algorithm should have linear time complexity. Can you just do it using extra constant space?

Solution 1: Violence

  • Nums [I] = nums[I]
  • The complexity of the
    • Time: O (n)
    • Space: O (1)
public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) 
            if(nums[i] ! = i)return i;
        return nums.length;
    }
Copy the code

Solution 2: Bit operation (xOR)

  • If nums[I] is equal to I, then (^) is equal to 0 + commutative
  • The complexity of the
    • Time: O (n)
    • Space: O (1)
 public int missingNumber(int[] nums) {
        // Note: this must be initialized to len, because I will not equal len when iterating through the array
        int res = nums.length;
        for (int i = 0; i < nums.length; i++) res = res ^ i ^ nums[i];
        return res;
    }
Copy the code

461. Hamming distance ¹

The Hamming distance between two integers refers to the number of different positions of the two numbers corresponding to the binary bits.

Given two integers x and y, calculate the Hamming distance between them.

Note: 0 ≤ x, y < 231.

Example:

Input: x = 1, y = 4 Output: 2 Explanation: 1 (0 0 0 1) 4 (0 1 0 0 0) ↑ arrows indicate the different locations of the corresponding binary bits.Copy the code

Solution 1: Bit operation (xOR)

  • 11=0, 00=0, 10=1. So how many 1’s you get for x to the y, how many different bits you get
  • The complexity of the
    • Time: O (n), n is related to the binary number of x and y
    • Space: O (1)
class Solution {
    public int hammingDistance(int x, int y) {
    	// if x^y has the same bit, the corresponding position of num is 0. So now we count the number of ones
        int num = x ^ y; 
        int count = 0;
        while (num > 0) {
            if ((num & 1) = =1) count++;
            num >>= 1;
        }
        returncount; }}Copy the code

Optimization: Java provides a bitCount method that counts the number of 1s in binary

class Solution {
    public int hammingDistance(int x, int y) {
        returnInteger.bitCount(x ^ y); }}Copy the code

50. The Pow (x, n) squared

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

Example 1:

Input: 2.00000, 10 output: 1024.00000Copy the code

Example 2:

Input: 2.10000, 3 Output: 9.26100Copy the code

Example 3:

Input: 2.00000, -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25Copy the code

Description:

  • 100.0 <x < 100.0
  • nIs a 32-bit signed integer that ranges from −231 to 231 − 1.

Solution 1: Violent method (timeout)

  • Loop, multiply by x each time
    • Note: If n < 0, processing needs to be done
  • Complexity:
    • Time: O (n)
    • Space: O (1)
public double myPow(double x, int n) {
        double res = 1;
    	// Convert to long because int[-2147483648,2147483647] and 2147483648 is outside the int range
        long N = Math.abs((long)n);
        for (int i = 0; i < N; i++) 
            res *= x;
        return n > 0 ? res : 1 / res;
}
Copy the code
public double myPow(double x, int n) {
        double pow = 1;
        for (int i = 0; i < Math.abs(n); i++) {
            pow = n >= 0 ? pow * x : pow / x;
        }
        return pow;
}
Copy the code

Solution two: bit operation

  • For example, x ^ 11 =?
    1. 11 = 1011, or 8,421 yards
    2. X ^ 11 = x^8 * x^2 * x^1 Lambda is equal to the square of the previous digit
  • Complexity:
    • Time: O(logn), because >> is equal to /2 dichotomy
    • Space: the O (1)
public double myPow(double x, int n) {
        double res = 1;
        // Note: Long is converted because int[-2147483648,2147483647] and 2147483648 is outside the int range
        long N = Math.abs((long)n);
        while(N ! =0) {
            // Get the lowest mod with 0001
            if ((N & 1) = =1) 
                // Multiply the weights
                res *= x;
            // Move right to get the next digit
            N >>= 1;   
            // square to get the weight of the next digit
            x *= x;
        }
        return n > 0 ? res : 1 / res;
    }
Copy the code