在 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 次查看

开启您的 职业生涯

通过完成课程获得认证

开始
广告