สมมติว่าเรามีตัวเลข สำหรับแต่ละตัวเลข i ในช่วง 0 ≤ i ≤ num เราต้องคำนวณจำนวน 1 ในตัวคู่ไบนารีของพวกมันและส่งคืนเป็นรายการ ดังนั้นถ้าตัวเลขคือ 5 แล้วตัวเลขก็คือ [0, 1, 2, 3, 4, 5] และเลข 1 ในตัวเลขเหล่านี้คือ [0, 1, 1, 2, 1, 2] ก็จะได้ กลับ 7.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
res :=อาร์เรย์ที่เก็บ num + 1 จำนวน 0s
-
ออฟเซ็ต :=0
-
สำหรับฉันอยู่ในช่วง 1 ถึง num + 1
-
ถ้า i และ i − 1 =0 แล้ว res[i] :=1 และ offset :=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
