— 190-191-170-172-java + Python

The article directories

• • • • 190. Reverse binary bits
      • 172. Zero after factorial
      • 191. The number of bits 1
      • 170. Sum of two numbers III – Data structure design
      • 69. Square root of x

190. Reverse binary bits

Inverts the binary bits of the given 32-bit unsigned integer.

The sample1: input, output: 00000010100101000001111010011100, 00111001011110000010100101000000: Input binary string of 00000010100101000001111010011100 indicates an unsigned integer43261596, so return964176192The binary representation of 00111001011110000010100101000000.Copy the code

The sample2Input:11111111111111111111111111111101Output:10111111111111111111111111111111Explanation: Input binary string11111111111111111111111111111101Represents an unsigned integer4294967293, so return3221225471Its binary representation is10111111111111111111111111111111 。
Copy the code

Tip: Note that in some languages, such as Java, there are no unsigned integer types. In this case, both input and output will be specified as signed integer types, and should not affect your implementation, because the internal binary representation of an integer is the same whether it is signed or unsigned. In Java, the compiler uses binary complement notation to represent signed integers. Therefore, in example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.

The problem requires reversing the binary representation of a given integer and finally returning the integer with the reversed binary representation. So, the first thing you need to do is convert between binary and decimal, and bin() in Python can easily convert decimal to binary, while binary to decimal only needs to use int(). In addition, bin() is denoted as obxxxxx, so the 0b needs to be removed, and when converted to decimal, the inverted binary is converted by adding 0b at the beginning.

class Solution:
    def reverseBits(self, n: int) - >int:
        if n == 0: return 0

        number = list(bin(n).replace('0b'.' '))
        Make up to 32 bits
        if len(number) < 33:
            t = ['0' for i in range(33 - len(number) - 1)]
            number = t + number

        return int('0b' + "".join(number[::-1]), 2)
Copy the code

172. Zero after factorial

Input:3Output:0Explanation:3! = 6, there are no zeros in the mantissa.Copy the code

Input:5Output:1Explanation:5! = 120In the mantissa1A zero.Copy the code

class Solution:
  def trailingZeroes(self, n: int) - >int:
    count = 0
    while n > 0:
        count += n // 5
        n = n // 5
    
    return count
Copy the code

191. The number of bits 1

Write a function that takes an unsigned integer and returns the number of digits of ‘1’ in its binary expression (also known as hamming weight).

Example 1:

Input: 00000000000000000000000000001011 output:3Explanation: the input binary string in 00000000000000000000000000001011, a total of three'1'.Copy the code

Example 2:

Input: 00000000000000000000000010000000 output:1Explanation: the input binary string in 00000000000000000000000010000000, a total of one'1'.Copy the code

Example 3:

Input:11111111111111111111111111111101Output:31Explanation: Input binary string11111111111111111111111111111101, there are31Bit is'1'.Copy the code

Tip:

• Note that in some languages, such as Java, there are no unsigned integer types. In this case, both input and output will be specified as signed integer types, and should not affect your implementation, because the internal binary representation of an integer is the same whether it is signed or unsigned.
• In Java, the compiler uses binary complement notation to represent signed integers. Therefore, in example 3 above, the input represents the signed integer -3.

We did the last one, and we didn’t have anything new to do with this problem, except count the number of ones in binary.

class Solution:
    def hammingWeight(self, n: int) - >int:
        if n == 0: return 0

        count = 0
        str = bin(n).replace('0b'.' ')
  
        for i in range(len(str)) :if str[i] == '1':
                count +=1 
            
        return count
Copy the code

170. Sum of two numbers III – Data structure design

add(1); add(3); add(5);
find(4) -> true
find(7) -> false
Copy the code

add(3); add(1); add(2);
find(3) -> true
find(6) -> false
Copy the code

class TwoSum:

    def __init__(self) :
        """ Initialize your data structure here. """
        self.s = list(a)def add(self, number: int) - >None:
        """ Add the number to an internal data structure.. "" "
        self.s.append(number)

    def find(self, value: int) - >bool:
        """ Find if there exists any pair of numbers which sum is equal to the value. """
        self.s.sort() 
        if len(self.s) < 2:
            return False
       
        left = 0
        right = len(self.s) - 1
        while left < right:
            # print(self.s[left], self.s[right])
            if self.s[left] + self.s[right] < value:
                left += 1
            elif self.s[left] + self.s[right] == value:
                return True
            else:
                right -= 1

        return False
Copy the code

69. Square root of x

Implement the int SQRT (int x) function. Calculates and returns the square root of x, where x is a non-negative integer. Since the return type is an integer, only the integer part of the result is retained, and the fractional part is omitted.

Example 1:

Input:4Output:2
Copy the code

Example 2:

Input:8Output:2
Copy the code

Description: The square root of 8 is 2.82842… Because the return type is an integer, the decimal part will be omitted.

The calculation of x \ SQRT {x} x is converted to the calculation of other mathematical formulas, as shown below: X = 1/2 x = 1/2 ln ⁡ x (e) = e 1 2 ln ⁡ x \ SQRT {x} = x ^ = 1/2} {\ left (e ^ {\ ln x} \ right) ^ ^ 1/2} {= e {\ frac {1} {2}} \ ln x x =x1/2=(elnx)1/2=e21lnx

class Solution:

    def mySqrt(self, x: int) - >int:
        if x == 0: 
        	return 0
        ans = int(math.exp(0.5 * math.log(x)))
        return ans + 1 if (ans + 1) * *2 <= x else ans
Copy the code

Of course, the idea is to use Newton’s method of numerical computation, but I don’t care if it’s a little complicated.