LeetCode 솔루션 분류
[5/26] 191. Number of 1 Bits
본문
[LeetCode 시즌 3] 2022년 5월 26일 문제입니다.
https://leetcode.com/problems/number-of-1-bits/
191. Number of 1 Bits
Easy
3107813Add to ListShareWrite a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).
Note:
- Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
- In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3, the input represents the signed integer.
-3
.
Example 1:
Input: n = 00000000000000000000000000001011 Output: 3 Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.
Example 2:
Input: n = 00000000000000000000000010000000 Output: 1 Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.
Example 3:
Input: n = 11111111111111111111111111111101 Output: 31 Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.
Constraints:
- The input must be a binary string of length
32
.
Follow up: If this function is called many times, how would you optimize it?
태그
#LeetCode, #Box, #Facebook, #Amazon, #Cisco, #Google, #Qualcomm, #Microsoft, #Apple, #Yahoo, #Oracle, #Adobe, #Bloomberg, #Bit Manipulation
관련자료
-
링크
댓글 1
mingki님의 댓글
- 익명
- 작성일
C++
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Number of 1 Bits.
Memory Usage: 6.2 MB, less than 48.74% of C++ online submissions for Number of 1 Bits.
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Number of 1 Bits.
Memory Usage: 6.2 MB, less than 48.74% of C++ online submissions for Number of 1 Bits.
class Solution {
unordered_map<uint32_t, int> memo;
public:
int hammingWeight(uint32_t n) {
int cnt = 0;
if (memo.count(n)) {
return memo[n];
}
memo[n] = 0;
for (int i = 0; i < 32; ++i) memo[n] += (n >> i) & 1;
return memo[n];
}
};