Press "Enter" to skip to content

Posts published in “Bit”

花花酱 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)

 

花花酱 LeetCode 693. Binary Number with Alternating Bits

Problem:

Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

Example 1:

Example 2:

Example 3:

Example 4:

 

Idea:

Bit operation

Solution

C++