โปรแกรมค้นหา XOR สูงสุดสำหรับแต่ละแบบสอบถามใน Python

สมมติว่าเรามีอาร์เรย์ที่ได้รับการจัดเรียงไว้ล่วงหน้าเรียกว่า nums ขนาด n และยังมีค่าหนึ่ง b.We ต้องการดำเนินการค้นหาต่อไปนี้ n ครั้ง -

• ค้นหาค่าที่ไม่ใช่ค่าลบ k <2^m โดยที่ XOR ขององค์ประกอบทั้งหมดเป็น num และ k จะขยายให้ใหญ่สุด ดังนั้น k คือคำตอบของแบบสอบถาม ith

• ลบองค์ประกอบสุดท้ายออกจากจำนวนอาร์เรย์ปัจจุบัน

• เราต้องหาคำตอบของอาร์เรย์ โดยที่ answer[i] คือคำตอบของแบบสอบถาม ith

ดังนั้น หากอินพุตเท่ากับ nums =[0,1,1,3], m =2 เอาต์พุตจะเป็น [0,3,2,3] เพราะ

• nums =[0,1,1,3], k =0 ตั้งแต่ 0 XOR 1 XOR 1 XOR 3 XOR 0 =3.

• nums =[0,1,1], k =3 ตั้งแต่ 0 XOR 1 XOR 1 XOR 3 =3

• nums =[0,1], k =2 ตั้งแต่ 0 XOR 1 XOR 2 =3.

• nums =[0], k =3 เนื่องจาก 0 XOR 3 =3

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• x :=2^m - 1

• สำหรับฉันในช่วง 0 ถึงขนาดของ nums - 1 ทำ

  • nums[i] :=nums[i] XOR x

  • x :=nums[i]

• คืนค่าตัวเลขหลังจากการกลับรายการ

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(nums, m):
   x=2**m-1
   for i in range(len(nums)):
      nums[i]^= x
      x = nums[i]
   return(nums[::-1])

nums = [0,1,1,3]
m = 2
print(solve(nums, m))

อินพุต

[0,1,1,3], 2

ผลลัพธ์

[0, 3, 2, 3]