前往
大廳
主題

LeetCode - 2546. Apply Bitwise Operations to Make Strings Equal 解題心得

Not In My Back Yard | 2023-12-30 12:00:21 | 巴幣 0 | 人氣 58

題目連結:


題目意譯:
你被給定兩個索引值從 0 開始的二元字串 s 和 target,並且兩者長度相同。你可以對於 s 執行以下操作任意次數:
選擇兩個不同的索引值 i 和 j,其中 0 ≦ i, j < n;
同時將 s[i] 替換成 (s[i] OR s[j]) 以及將 s[j] 替換成 (s[i] XOR s[j])。

例如說,如果 s = "0110",你可以選擇 i = 0 且 j = 2,接著並同時將 s[0] 和 s[2] 分別替換成 (s[0] OR s[2] = 0 OR 1 = 1) 和 (s[0] XOR s[2] = 0 XOR 1 = 1),所以我們有 s = "1110"。

如果你可以讓 s 與 target 相等,則回傳真(True);反之,回傳假(False)。

限制:
n == s.length == target.length
2 ≦ n ≦ 10 ^ 5
s 和 target 只由數字 0 和 1 所組成。



範例測資:
範例 1:
輸入: s = "1010", target = "0110"
輸出: true
解釋: 我們可以做以下操作:
- 選擇 i = 2 切 j = 0。我們現在有 s = "0010"。
- 選擇 i = 2 切 j = 1。我們現在有 s = "0110"。
由於我們可以讓 s 與 target 相等,所以我們回傳真。

範例 2:
輸入: s = "11", target = "00"
輸出: false
解釋: 不論多少次操作都不可能使 s 與 target 相等。


解題思維:
觀察以下四種情況:
1. 當 s[i] == 0 、 s[j] == 0 時,兩數不變。
2. 當 s[i] == 0 、 s[j] == 1 時,s[i] 變成 1 、 s[j] 不變。
3. 當 s[i] == 1 、 s[j] == 0 時,s[i] 不變、 s[j] 變成 1。
4. 當 s[i] == 1 、 s[j] == 1 時,s[i] 不變、 s[j] 變成 0。

再加上我們可以 i 和 j 的角色交換,則可以得到以下五種可能的不同結果:
1. 兩數不變。
2. s[i] 變成 1 、 s[j] 不變。
3. s[i] 不變、 s[j] 變成 1。
4. s[i] 不變、 s[j] 變成 0。
5. s[i] 變成 0、 s[j] 不變。

所以我們可以看到題目定義的操作實際上是:
1. 挑兩個 0,不做任何變化。
2. 挑一個 0 、一個 1,並將那個 0 變成 1。
3. 挑兩個 1,並將其中一個 1 變成 0。

所以只要 s 中本來就有至少一個 1,則我們可以把 s 中任意若干個 0 變成 1;也可以把現在有的 1 消到只剩一個。也就是說我們「幾乎」可以操弄每一個位元是 0 或是 1。

因此可以看到我們只要統計 s 和 target 中各自有多少 1(令 Cs 為 s 的,而 Ct 為 target 的)便可以知道可不可以使兩者相等。方式如下:
如果 Ct == 0,則判斷 Cs 是否為 0。如果是則回傳真(因為兩字串本來就一樣,都全部由 0 組成);反之,則回傳假(因為此時 s 再努力也只能消到剩一個 1,不可能到達 0 個)。

如果 Ct != 0,則判斷 Cs 是否大於 0。如果是則回傳真(因為我們可以把 Cs 調整到等於 Ct 並將 s 中的 1 任意移動);反之,則回傳假(因為此時 s 中沒有 1 可以來使 Cs 增加)。




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

創作回應

更多創作