338.Counting-Bits
338. Counting Bits
้ข็ฎๅฐๅ
https://leetcode.com/problems/counting-bits/
้ข็ฎๆ่ฟฐ
ไปฃ็
Approach #1 DP + Most Significant Bit
ๆ นๆฎ้ข็ฎ็่ฆๆฑ๏ผๆถ้ดๅ็ฉบ้ดๅคๆๅบฆ๏ผๆๆพๆฏ่ฆๅจๆ่งๅ็ๆนๆณ
ๅพๅบๆจๅฐๅ
ฌๅผ๏ผf(n)
= ไธๅคงไบf(n)
็ๆๅคง็2็ๆฌกๆน +f(k)
๏ผkไธๅฎๆฏๅจๅ้ขๅบ็ฐ็๏ผ็จๆฐ็ป่ฎฐๅฝ๏ผ็ดๆฅๆฅ่ฏข
๏ผๆณจๆ2็ๆฌกๆน้ฝๆฏไธไธช1๏ผ่ไธๆฏๆ้ซไฝ๏ผ
f(5) = 1 + f(1)
f(6) = 1 + f(2)
็ดๅฐ
f(8) = 1
Approach #2 DP + Least Significant Bit
Approach #3 Pop Count
x & (x - 1)็ไฝ็จๆฏๅฐไบ่ฟๅถ่กจ็คบไธญๅณ่พน็ฌฌไธไธช1็ฝฎ0
Last updated