forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhajunyoo.py
More file actions
34 lines (30 loc) ยท 889 Bytes
/
hajunyoo.py
File metadata and controls
34 lines (30 loc) ยท 889 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution1:
# time complexity: O(n)
# space complexity: O(1)
def countBits(self, n: int) -> List[int]:
list = [i for i in range(n + 1)]
result = [bin(num).count('1') for num in list]
return result
class Solution2:
# time complexity: O(n * logn)
# space complexity: O(1)
def countBits(self, n: int) -> List[int]:
def count(num):
cnt = 0
while num:
cnt += num % 2
num //= 2
return cnt
res = [count(i) for i in range(n+1)]
return res
class Solution3:
# time complexity: O(n)
# space complexity: O(1)
def countBits(self, n: int) -> List[int]:
res = [0] * (n + 1)
msb = 1
for i in range(1, n + 1):
if i == msb * 2:
msb *= 2
res[i] = res[i - msb] + 1
return res