Re: [閒聊] 每日leetcode

[yam276 (三角初華的事件視界)]

※ 引述《Meaverzt (單推凜寶)》之銘言：
: 題目：
: 有兩個陣列nums1跟nums2裡面有很多數字
: 我們要去做一個nums3裡面是nums1跟nums2中所有xor後可能的值
: 最後回傳nums3每一項xor後的值
: 思路：
: 因為一個數字只要被xor兩次就會變0
: 所以去算每個數字被xor幾次
: 只要是奇數就去跟答案xor

這題是數學問題

暴力解是

for &n1 in &nums1 {
    for &n2 in &nums2 {
        result ^= (n1 ^ n2);
    }
}

但這效率很爛 所以不太可能直接用這個


考慮到結果num3等於所有n1 ^ n2的xor

也就是num3實際上是

(nums1[i] ^ nums2[0]) ^ (nums1[i] ^ nums2[1]) ^ ... ^ (nums1[i] ^ nums2[n-1])

的結果


所以因為大家都是xor

根據分配律

可以改寫成

nums1[i] ^ nums1[i] ^ ... ^ nums1[i] ^ nums2[0] ^ nums2[1] ^ ... ^ nums2[n-1]


然後總之

計算 nums1 的 XOR 和 xor1

計算 nums2 的 XOR 和 xor2

如果 nums2 的長度是奇數 則結果包含 xor1

如果 nums1 的長度是奇數 則結果包含 xor2


Code:

impl Solution {
    pub fn xor_all_nums(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let xor1: i32 = nums1.iter().fold(0, |acc, &x| acc ^ x);
        let xor2: i32 = nums2.iter().fold(0, |acc, &x| acc ^ x);

        let m = nums1.len();
        let n = nums2.len();

        let mut result = 0;
        if n % 2 == 1 {
            result ^= xor1;
        }
        if m % 2 == 1 {
            result ^= xor2;
        }
        result
    }
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.172 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1737020649.A.EA8.html
※ 編輯: yam276 (60.248.143.172 臺灣), 01/16/2025 17:45:51
→ sustainer123: 為啥奇偶數有差?
→ sustainer123: 我就看不懂這個
推 oin1104: 偶數次xor就會把自己消掉吧
→ yam276: 偶數次的xor=0
推 sustainer123: 好 那我懂了