Press "Enter" to skip to content

Posts published in “Bit”

花花酱 LeetCode 762. Prime Number of Set Bits in Binary Representation

题目大意:求给定范围内,数的二进制形式中1的个数为素数个的数字的个数。

Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.

(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)

Example 1:

Example 2:

Note:

  1. L, R will be integers L <= R in the range [1, 10^6].
  2. R - L will be at most 10000.

Solution 1: Brute Force

C++

 

 

Java

Python2

Python2

 

花花酱 307. Range Sum Query – Mutable

题目大意:给你一个数组,让你求一个范围之内所有元素的和,数组元素可以更改。

Problem:

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Note:

  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.

Idea:

Fenwick Tree

Solution:

C++

Time complexity:

init O(nlogn)

query: O(logn)

update: O(logn)

C++

Java

Python3

Solution 2: Segment Tree

C++

花花酱 LeetCode 476. Number Complement

题目大意:给你一个正整数,输出和它互补的数(翻转所有的bits)。

Problem:

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:

  1. The given integer is guaranteed to fit within the range of a 32-bit signed integer.
  2. You could assume no leading zero bit in the integer’s binary representation.

Example 1:

Example 2:

Idea:

Bit



Solution:

C++

 

花花酱 LeetCode 477. Total Hamming Distance

Problem:

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:

Note:

  1. Elements of the given array are in the range of to 10^9
  2. Length of the array will not exceed 10^4.

题目大意:给你一堆数,让你求所有数对的HammingDistance的总和。

Idea:

  1. Brute force, compute HammingDistance for all pairs. O(n^2) TLE
  2. Count how many ones on i-th bit, assuming k. Distance += k * (n – k). O(n)

Solution:

C++ / O(n)

 

花花酱 LeetCode 169. Majority Element

题目大意:给你一个数组,其中一个数出现超过n/2次,问你出现次数最多的那个数是什么?

Problem:

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Ideas:


Solution 1:

Hash table O(n) / O(n)

 

Solution 2:

BST O(nlogk) / O(n)

 

Solution 3:

Randomization O(n) / O(1)

 

Solution 4:

Bit voting O(n) / O(1)

 

Solution 5:

Moore Voting O(n) / O(1)

 

Solution 6:

Full sorting O(nlogn) / O(1)

 

Solution 7:

Partial sorting O(n) / O(1)

 

Solution 8:

Divide and conquer O(nlogn) / O(logn)

Divide and conquer O(nlogn) / O(logn)