숫자 번호가 있다고 가정합니다. 0 ≤ i ≤ num 범위의 각 숫자 i에 대해 이진 대응 항목에서 1의 수를 계산하고 목록으로 반환해야 합니다. 따라서 숫자가 5이면 숫자는 [0, 1, 2, 3, 4, 5]이고 이 숫자에서 1의 개수는 [0, 1, 1, 2, 1, 2]이므로 7을 반환합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
res :=num + 1개의 0을 포함하는 배열
-
오프셋 :=0
-
범위 1에서 num + 1까지의 i에 대해
-
i 및 i − 1 =0이면 res[i] :=1이고 오프셋 :=0
-
그렇지 않으면 오프셋을 1 증가시키고 res[i] :=1 + res[offset]
-
-
res
요소의 합을 반환합니다.
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution: def countBits(self, num): result = [0] * (num+1) offset = 0 for i in range(1,num+1): if i & i-1 == 0: result[i] = 1 offset = 0 else: offset+=1 result[i] = 1 + result[offset] return sum(result) ob1 = Solution() print(ob1.countBits(5))
입력
5
출력
7