Giả sử chúng ta có hai số nguyên N và K; chúng ta phải tìm N giá trị duy nhất có bit khôn ngoan OR giống như K. Nếu không có kết quả như vậy, thì trả về -1
Vì vậy, nếu đầu vào là N =4 và K =6, thì đầu ra sẽ là [6,0,1,2].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
TỐI ĐA:=32
-
đã thăm:=danh sách có kích thước MAX và điền sai
-
res:=một danh sách mới
-
Định nghĩa một hàm add (). Điều này sẽ mất số
-
điểm:=0
-
giá trị:=0
-
đối với tôi trong phạm vi từ 0 đến MAX, hãy thực hiện
-
nếu lượt truy cập [i] khác 0 thì
-
chuyển sang lần lặp tiếp theo
-
-
nếu không,
-
nếu num VÀ 1 khác 0 thì
-
value:=value + (2 ^ i)
-
-
num:=num / 2 (chỉ lấy phần nguyên)
-
-
-
chèn giá trị vào cuối res
-
Từ phương thức chính, thực hiện như sau -
-
pow2:=một mảng lũy thừa của 2 từ 2 ^ 0 đến 2 ^ 31
-
chèn k vào cuối res
-
cnt_k:=số bit tính bằng k
-
nếu pow2 [cnt_k]
-
trả về -1
-
-
đếm:=0
-
đối với tôi trong phạm vi 0 đến pow2 [cnt_k] - 1, thực hiện
-
thêm (i)
-
count:=count + 1
-
nếu số đếm giống n, thì
-
đi ra từ vòng lặp
-
-
-
trả lại res
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơ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))
Đầu vào
4, 6
Đầu ra
[6, 0, 1, 2]