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