สมมติว่าเรามีจำนวนเต็มบวก N เราต้องหาระยะทางที่ยาวที่สุดระหว่าง 2 ตัวที่ติดกัน 1 ในการแทนค่าไบนารีของ N หากไม่มี 1 สองตัวติดต่อกัน ให้คืนค่า 0
ดังนั้น ถ้าอินพุตเท่ากับ 22 เอาต์พุตจะเป็น 2 เนื่องจาก 22 ในระบบไบนารีเท่ากับ 10110 มีสามตัวในการแทนค่าไบนารีของ 22 และ 1 คู่ติดต่อกันสองคู่ คู่ที่ 1 ติดต่อกันมีระยะทาง 2 จากนั้นคู่ที่ 2 ติดต่อกันมีระยะทาง 1 คำตอบจะมีระยะทางมากที่สุดในสองระยะทางนี้ ซึ่งก็คือ 2
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- K :=ทำรายการบิตของการแทนค่าไบนารีของ N
- สูงสุด :=0, C :=0, S :=0
- ตั้งค่าสถานะ :=เท็จ
- สำหรับฉันในช่วง 0 ถึงขนาด K ทำ
- ถ้า K[i] คือ '1' และ C คือ 0 และแฟล็กเป็นเท็จ ดังนั้น
- C:=ฉัน
- ตั้งค่าสถานะ :=จริง
- มิฉะนั้นเมื่อ K[i] เป็น '1' และแฟล็ก จากนั้น
- S:=ฉัน
- ถ้า Max
- สูงสุด :=|S-C|
- C:=ส
- ถ้า K[i] คือ '1' และ C คือ 0 และแฟล็กเป็นเท็จ ดังนั้น
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution:
def binaryGap(self, N):
B = bin(N).replace('0b','')
K = str(B)
K = list(K)
Max = 0
C = 0
S =0
Flag =False
for i in range(len(K)):
if K[i] is '1' and C is 0 and Flag is False:
C=i
Flag = True
elif K[i] is '1' and Flag:
S=i
if Max<abs(S-C):
Max = abs(S-C)
C=S
return Max
ob = Solution()
print(ob.binaryGap(22)) อินพุต
22
ผลลัพธ์
2
