設 a 為答案最大值
設 b,c 為 list 的兩數字
1 2 3 4 ... k
a x x x x ... x
b x x x x ... x
c x x x x ... x
每次 a 由左至右算第 k 位 bit 時，都先假設為 1
如果能找到一組(b,c)，使得:
prefix(a,k) & prefix(b',k) = prefix(a,k) & prefix(c,k)
則 a 的第 k bit 必存在有 1 的解，否則該 bit 為 0
註: 紅色等式如果改成:
prefix(b,k) ^ prefix(a,k) = prefix(c,k)
感覺比較好理解！
※ 引述《benchen0812 (あBen)》之銘言：
: 第一次發文
: 如果有那裡不妥當請告知
: 最近在LEETCODE刷提 遇到一題求 list 裡面任意兩數字XOR最大值
: 題目連結在這邊
: https://goo.gl/HPH4Sm
: 這題最快的解答是
: class Solution:
: def findMaximumXOR(self, nums):
: """
: :type nums: List[int]
: :rtype: int
: """
: ans = 0
: for bit in range(31, -1, -1) :
: ans = (ans << 1) + 1
: pre = set()
: for n in nums :
: p = (n >> bit) & ans
: if p in pre : #1
: break #2
: pre.add(ans - p) #3
: else : #4
: ans -= 1
: return ans
: 我的問題在我標#1-4的地方
: 我不太明白這邊的if else statement 怎麼運作的(特別是#4)
: 一開始我以為是當if p not in pre:
: 就會直接跳到#4
: 但是好像不太對
: 請問有人可以跟我說明一下嗎?
: 非常感謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.252.242.204
※ 文章網址: https://www.ptt.cc/bbs/Python/M.1530163416.A.927.html