※ 引述《fxfxxxfxx (愛麗絲)》之銘言：
: Biweekly Contest 88
1.給一個字串 問有沒有辦法刪掉一個字母後讓其他字母出現次數相等
字母的出現次數有幾種狀況:
只有一種字母: 直接回傳true
只有兩種字母: 檢查是不是 [1, n] 或 [n-1, n]
兩種字母以上: 檢查是不是 [1, n, n, n ...] 或 [n, n, n, ... , n+1]
counter 之後 sort 就好
class Solution:
def equalFrequency(self, word: str) -> bool:
c = Counter(word)
num = sorted([c[k] for k in c.keys()])
n = len(num)
if n == 1:
return True
elif n == 2:
return num[1] - num[0] == 1 or num[0] == 1
else:
return (num[0] == num[-2] and num[-1] == num[0]+1) or (num[0] ==
1 and num[1] == num[-1])
2.要你寫能算 longest prefix 的資料結構 支援 upload(n) -> 插入數字n
longest() -> 回傳最大的 prefix 也就是 [1, 2, 3 ... , n] 都已經upload
這題不太確定 感覺是用 disjoint set 插入n時 root[n-1] = n
查最大時看root[0]的觸手能摸到誰
class LUPrefix:
def __init__(self, n: int):
self.root = list(range(n+1))
def upload(self, video: int) -> None:
if video <= len(self.root):
self.root[video-1] = video
def longest(self) -> int:
def find(n):
if self.root[n] == n:
return n
self.root[n] = find(self.root[n])
return self.root[n]
return find(0)
3.給兩個陣列 nums1 nums2 要你先算出nums3 = 他們裡面元素兩兩配對的XOR
之後再算 nums3裡全部元素的XOR
只要知道 a XOR a = 0, a XOR 0 = a 就好
所以就看 nums1 和 nums2 的長度 例如是 [1,2] 和 [3,4,5] 好了
最後會是 (1^3)^(1^4)^(1^5)^(2^3)^(2^4)^(2^5) = 1^2
觀察得知 如果len(nums1)是偶數 就會讓nums2每個元素都出現偶數次 最後就會是0
如果是奇數 就會出現2n+1次 那其實也就XOR一次nums2就好
class Solution:
def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
res = 0
n1, n2 = len(nums1), len(nums2)
if n1%2 == 0 and n2%2 == 0:
return 0
if n1%2:
for n in nums2:
res ^= n
if n2%2:
for n in nums1:
res ^= n
return res
4.給你兩個list nums1 nums2 問你滿足條件的 i, j 組合有多少
0 <= i < j <= n - 1 and
nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff
這裡可以移項
nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff
先算出 nums3[i] = nums1[i] - nums2[i] 的話就是
找所有的i, j 讓 nums3[i] <= nums3[j] + diff
很直覺的兩層for-loop iterate i,j 會TLE
觀察發現要求j大於i 那有沒有辦法 iterate j 就好? 然後一次檢查滿足要求的i的總數
可以藉由維護一個 sorted list 然後二分搜做到
用bisect搜尋 n+diff 能插在 sorted list 的第幾個位置 就代表前面的全部比他小
算完再插入 n 到 sorted list 裡
只是 bisect 的 insort 好像是 O(n)
隨便啦管他的 反正能過
class Solution:
def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) ->
int:
n = len(nums1)
nums = [nums1[i] - nums2[i] for i in range(n)]
currnums = [nums[0]]
res = 0
for i in range(1, n):
res += bisect.bisect(currnums, nums[i]+diff)
bisect.insort(currnums, nums[i])
return res
趕快趁斷線之前發