Re: [閒聊] 每日leetcode

[Meaverzt (單推凜寶)]

題目：

有兩個陣列nums1跟nums2裡面有很多數字

我們要去做一個nums3裡面是nums1跟nums2中所有xor後可能的值

最後回傳nums3每一項xor後的值

思路：

因為一個數字只要被xor兩次就會變0

所以去算每個數字被xor幾次

只要是奇數就去跟答案xor

Code:

class Solution {
public:
    int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> dict;
        auto a = nums1.size(), b = nums2.size();
        for (auto i : nums2) {
            dict[i] += a;
        }
        for (auto i : nums1) {
            dict[i] += b;
        }
        int ans = 0;
        for (auto& [key, value] : dict) {
            if (value % 2 == 1) {
                ans ^= key;
            }
        }
        return ans;
    }
};

雖然是O(n)了結果跑起來一坨

思路二：

nums1 nums2裡面每個數字兩兩xor的情況下

nums2裡面的數字會被xor len(nums1)次

同理nums1裡面的數字會被xor len(nums2)次

所以只要把同一個陣列都先xor起來

再去看陣列長度是不是奇數就好了

Code:

class Solution {
public:
    int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
        int a = 0, b = 0;
        for (int num : nums1)
            a ^= num;
        for (int num : nums2)
            b ^= num;
        return (nums1.size() % 2 ? b : 0) ^ (nums2.size() % 2 ? a : 0);
    }
};

bit操作的題目真的好煩
--
https://i.imgur.com/GaH3jI8.jpeg


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.237.23.221 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1737010389.A.0D8.html