음수가 아닌 정수 num이 있다고 가정합니다. 0 ≤ i ≤ num 범위의 각 숫자 i에 대해 이진 대응 항목에서 1의 수를 계산하고 목록으로 반환해야 합니다. 따라서 숫자가 5이면 숫자는 [0, 1, 2, 3, 4, 5]이고 이 숫자에서 1의 개수는 [0, 1, 1, 2, 1, 2]
입니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- res :=num + 1개의 0을 포함하는 배열
- 오프셋:=0
- 1에서 num + 1까지의 i에 대해
- i와 i – 1 =0이면 res[i] :=1이고 offset :=0입니다.
- 그렇지 않으면 오프셋을 1만큼 증가시키고 res[i] :=1 + res[offset]
- 반환 결과
예제(파이썬)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
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 result ob1 = Solution() print(ob1.countBits(6))
입력
6
출력
[0, 1, 1, 2, 1, 2, 2]