สมมติว่าเรามีจำนวนเต็มสองจำนวน N และ K; เราต้องหาค่าที่ไม่ซ้ำ N ค่าซึ่งมี OR แบบ bit-wise เท่ากับ K หากไม่มีผลลัพธ์ดังกล่าว ให้คืนค่า -1
ดังนั้น หากอินพุตเป็น N =4 และ K =6 เอาต์พุตจะเป็น [6,0,1,2]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สูงสุด :=32
-
เข้าชมแล้ว :=รายการขนาด MAX และกรอกเป็นเท็จ
-
res :=รายการใหม่
-
กำหนดฟังก์ชัน add() นี่จะใช้เวลา num
-
จุด :=0
-
ค่า :=0
-
สำหรับผมอยู่ในช่วง 0 ถึง MAX ทำ
-
ถ้า visit[i] ไม่เป็นศูนย์ แล้ว
-
ไปทำซ้ำต่อไป
-
-
มิฉะนั้น
-
ถ้า num AND 1 ไม่ใช่ศูนย์ ดังนั้น
-
ค่า :=ค่า +(2^i)
-
-
num :=num/2 (ใช้เฉพาะส่วนจำนวนเต็ม)
-
-
-
ใส่ค่าที่ท้าย res
-
จากวิธีหลัก ให้ทำดังนี้ −
-
pow2 :=อาร์เรย์ของกำลัง 2 จาก 2^0 ถึง 2^31
-
ใส่ k ต่อท้าย res
-
cnt_k :=จำนวนบิตในหน่วย k
-
ถ้า pow2[cnt_k]
-
กลับ -1
-
-
นับ :=0
-
สำหรับฉันอยู่ในช่วง 0 ถึง pow2[cnt_k] - 1 ทำ
-
เพิ่ม(i)
-
นับ :=นับ + 1
-
ถ้านับเท่ากับ n แล้ว
-
ออกจากวง
-
-
-
ผลตอบแทน
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
MAX = 32 visited = [False for i in range(MAX)] res = [] def set_bit_count(n): if (n == 0): return 0 else: return (n & 1) + set_bit_count(n >> 1) def add(num): point = 0 value = 0 for i in range(MAX): if (visited[i]): continue else: if (num & 1): value += (1 << i) num = num//2 res.append(value) def solve(n, k): pow2 = [2**i for i in range(MAX)] res.append(k) cnt_k = set_bit_count(k) if (pow2[cnt_k] < n): return -1 count = 0 for i in range(pow2[cnt_k] - 1): add(i) count += 1 if (count == n): break return res n = 4 k = 6 print(solve(n, k))
อินพุต
4, 6
ผลลัพธ์
[6, 0, 1, 2]
