※ 引述《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
赶快趁断线之前发