ETH官方钱包

前往
大廳
主題

LeetCode - 2429. Minimize XOR 解題心得

Not In My Back Yard | 2023-08-23 12:00:01 | 巴幣 0 | 人氣 163

題目連結:


題目意譯:
給定兩正整數 num1 和 num2,請找到正整數 x 使得:
x 與 num2 在有著相同數量的設置位元(Set Bits),且
x 與 num1 XOR 之值為可能的最小值。

注意到該 XOR 之操作為按位元(Bitwise) XOR。

回傳該整數 x。測資之生成滿足 x 之值唯一。

一個整數的設置位元之數量為其於二進位制中 1 的個數。

限制:
1 ≦ num1, num2 ≦ 10 ^ 9



範例測資:
範例 1:
輸入: num1 = 3, num2 = 5
輸出: 3
解釋:
num1 和 num2 的二進位表示法分別為 0011 和 0101。
整數 3 與 num2 有著相同的設置位元,而 3 XOR 3 = 0 是最小值。

範例 2:
輸入: num1 = 1, num2 = 12
輸出: 3
解釋:
num1 和 num2 的二進位表示法分別為 0001 和 1100。
整數 3 與 num2 有著相同的設置位元,而 3 XOR 1 = 2 是最小值。


解題思維:
首先先數一下 num2 有多少個設置位元,假設有 C2 個。同樣地,算一下 num1 有幾個設置位元,假設有 C1 個。

如果 C1 = C2,則事情非常地簡單——x 之值即為 num1,因為 XOR 之後的結果為 0,必定是最小值;

如果 C1 < C2,則 num1 中是 1 的位元,對應到 x 之中也是 1(XOR 後才能消掉)。而剩下的 C2 - C1 的位元應選盡可能靠右的(也就是在二進位中代表的數字越小者),當然不能選到已經是 1 的位元。而這個造出來的數值即為 x(為了篇幅短一點,證明省略;但真的想證的話,只要用反證法假設我們的選擇不是最佳,然後發現這個假設是錯的即可);

如果 C1 > C2,則選出 num1 中盡可能靠左的 C2 個設置位元,它們對應於 x 中也將是設置位元,這樣子的 x 之值也是所求(一樣這邊省略證明,但證明精神如上所述)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作