在 Python 中查詢 N 個不同的數字，其按位或等於 K

假設我們有兩個整數 N 和 K；我們必須找到 N 個唯一的值，其按位或等於 K。如果沒有這樣的結果，則返回 -1

因此，如果輸入類似於 N = 4 和 K = 6，則輸出將為 [6,0,1,2]。

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

  • MAX := 32

  • visited := 一個大小為 MAX 的列表，並填充為 False

  • res := 一個新列表

  • 定義一個函式 add()。這將接收 num

  • point := 0

  • value := 0

  • 對於 i 從 0 到 MAX，執行以下操作：

    • 如果 visited[i] 不為零，則

      • 轉到下一次迭代

    • 否則，

      • 如果 num AND 1 不為零，則

        • value := value +(2^i)

      • num := num/2（僅取整數部分）

  • 在 res 的末尾插入 value

  • 從主方法中，執行以下操作：

  • pow2 := 從 2^0 到 2^31 的 2 的冪陣列

  • 在 res 的末尾插入 k

  • cnt_k := k 中位的數量

  • 如果 pow2[cnt_k] < n，則

    • 返回 -1

  • count := 0

  • 對於 i 從 0 到 pow2[cnt_k] - 1，執行以下操作：

    • add(i)

    • count := count + 1

    • 如果 count 等於 n，則

      • 退出迴圈

  • 返回 res

示例

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

 即時演示

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]

更新於： 2020年8月25日

109 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始
廣告

© . All rights reserved.