Python程式：查詢生成列表中特定元素的異或值

假設我們得到一個包含自然數的列表。現在，從該列表中移除所有二進位制表示中包含兩個連續1的數字，並生成另一個名為Z的列表。現在，我們得到另一個包含一些整數值的列表“input_list”。我們需要找出Z中指定元素的異或值，這些元素的索引在input_list中指定。

因此，如果輸入類似於input_list = [3, 4, 5]，則輸出將為9。

在Z的索引3、4和5處；值分別為4、5和8。所以，4 XOR 5 XOR 8 = 9。

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個函式zeck_num()。這將獲取k和f_list作為引數。
    • res := 0
    • 對於範圍從(f_list的大小 - 1)到-1的i，遞減1，執行以下操作：
      • 如果k >= f_list[i]，則
        • res := res + 2^i
        • k := k - f_list[i]
    • 返回res
  • MOD := 10^9 + 7
  • max_val := 10^18
  • f_list := 一個包含值1和2的新列表
  • 當f_list的最後一個元素 <= max_val時，執行以下操作：
    • 將f_list的最後一個元素 + f_list的倒數第二個元素插入到f_list的末尾
  • res := 0
  • 對於input_list中的每個索引，執行以下操作：
    • res := res XOR zeck_num(index, f_list)
  • 返回res mod MOD

示例

讓我們檢視以下實現以獲得更好的理解：

def zeck_num(k, f_list):
   res = 0
   for i in range(len(f_list)-1,-1,-1):
      if k >= f_list[i]:
         res += 2**i
         k -= f_list[i]
   return res

def solve(input_list):
   MOD = 10**9+7
   max_val = 10**18
   f_list = [1,2]
   while f_list[-1] <= max_val:
      f_list.append(f_list[-1] + f_list[-2])
   res = 0
   for index in input_list:
      res ^= zeck_num(index, f_list)
   return res % MOD

print(solve([3, 4, 5]))

輸入

[3, 4, 5]

輸出

9

更新於：2021年10月20日

125 次瀏覽

開啟您的職業生涯

透過完成課程獲得認證

開始學習
廣告