Re: [閒聊] 每日leetcode

[JerryChungYC (JerryChung)]

https://leetcode.com/problems/maximum-xor-for-each-query

1829. Maximum XOR for Each Query

字太多 不說了

就給一個 nums

先計算所有的 xor

然後配上一個 k 使得結果為小於 2^maximumBit 的最大值

排掉最後一個 num 後循環繼續做

思路：
反著做 最後再 reverse()

在研究 XOR 的時候 發現一篇文章 a, b 進行三次 XOR 就能把 a, b 互換

a, b = 5, 11
a = a ^ b (14, 11)
b = a ^ b (14,  5)
a = a ^ b (11,  5)

首先跟 0 xor 後再跟 2^maximumBit-1 xor 就能得到 k

將 k 加入 list 後再跟 2^maximumBit-1 做一次 xor 就能恢復到原本的進度

重複循環就好

Python Code:

class Solution:
    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
        ans = []
        maximized = 2 ** maximumBit - 1
        k = 0
        for num in nums:
            k ^= num
            k ^= maximized
            ans.append(k)
            k ^= maximized
        ans.reverse()
        return ans

原本以為那個做三次對這題沒幫助 結果剛才突然開竅 還不錯 睡覺去 晚安

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.45.20.205 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1731104831.A.285.html
→ JerryChungYC: JS用這寫法會TLE 什麼爛東西
→ JerryChungYC: 不能用 unshift(k) 要 push(k) 最後再 reverse()

class Solution:
    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
        ans = []
        maximized = 2 ** maximumBit - 1
        for num in nums:
            maximized ^= num
            ans.append(maximized)
        ans.reverse()
        return ans

原來只要一次就好 啊這
※ 編輯: JerryChungYC (114.45.20.205 臺灣), 11/09/2024 06:47:09