第1題 照題目
```python
class Solution:
def canAliceWin(self, nums: List[int]) -> bool:
single = double = 0
for num in nums:
if num > 9:
double += num
else:
single += num
return single != double
```
第2題 special是質數平方, 就建表計算
```python
class Solution:
def nonSpecialCount(self, l: int, r: int) -> int:
# special = prime square
primes = []
m = 1 + isqrt(r)
sieve = [0] * m
for i in range(2, m):
if sieve[i] == 0:
primes.append(i)
for j in range(i, m, i):
sieve[j] = i
special = 0
for prime in primes:
if l <= prime * prime <= r:
special += 1
return (r - l + 1) - special
```
第3題
應該是sliding window
但想了半小時寫不出來 放棄
第4題
可相連的圓做Union Find (兩圓中心距離 <= 兩圓半徑合)
如果圓碰到(0,0), (X,Y) 或 左+下/上+下/左+右/右+上的邊 就沒辦法走到(X, Y)
本來只想到四個邊都碰到的case, 吃error改掉後判斷寫很醜QQ
```python
class UnionFind:
def __init__(self, n):
self.size = n
self.rank = [1] * n
self.root = list(range(n))
def find(self, x):
if self.root[x] != x:
self.root[x] = self.find(self.root[x])
return self.root[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False
if self.rank[rx] >= self.rank[ry]:
self.rank[rx] += self.rank[ry]
self.root[ry] = rx
else:
self.rank[ry] += self.rank[rx]
self.root[rx] = ry
def get_groups(self):
groups = defaultdict(list)
for i in range(self.size):
groups[self.find(i)].append(i)
return groups.values()
class Solution:
def canReachCorner(self, X: int, Y: int, circles: List[List[int]]) ->
bool:
n = len(circles)
def get_mask(xi, yi, ri):
mask = 0
if xi + ri >= X:
mask |= (1 << 0)
if xi - ri <= 0:
mask |= (1 << 1)
if yi + ri >= Y:
mask |= (1 << 2)
if yi - ri <= 0:
mask |= (1 << 3)
return mask
reach = [0] * n
uf = UnionFind(n)
for i in range(n):
xi, yi, ri = circles[i]
reach[i] = get_mask(xi, yi, ri)
for xj, yj in (X, Y), (0, 0):
dist = (xi - xj) ** 2 + (yi - yj) ** 2
if ri ** 2 >= dist:
return False
for j in range(i+1, n):
xj, yj, rj = circles[j]
dist = (xi - xj) ** 2 + (yi - yj) ** 2
if (ri + rj) ** 2 >= dist:
uf.union(i, j)
for group in uf.get_groups():
mask = 0
for i in group:
mask |= reach[i]
if mask & 10 == 10 or mask & 5 == 5 or mask & 12 == 12 or
mask & 3 == 3 or mask == 15:
return False
return True
```