Re: leetcode Weekly Contest 408

[dont (dont)]

第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
```

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.48 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722140358.A.62F.html
→ sustainer123: 大神
→ r10521512: 瞎捧個啥 第三題沒寫出來 第四題吃error
對啊 我好廢QQ

→ DJYOMIYAHINA: 好強
推 oin1104: 大師
第4題看了一下hint
把四個邊加到union find寫起來更精簡
union完再看左右/上下/左下/右上 的root就好了

不過看討論
如果測資沒有限制圓心要在長方形內
會有圓外面相連再碰到兩邊的corner case 我寫法會過不了XD


第3題

因為1的個數要大於等於0的平方, 固定zeros 0~sqrt(N) 找substring

zeros>1用Queue紀錄 0的index, 做 sliding window

left    q[0]     right
1111111110
|--------|--------|

當queue的個數跟zeros相同且1的個數大於等於0的平方時

可延展的1的個數就是 [left, right]範圍內的substring個數
min(queue[0] - left + 1, ones - zeros ** 2 + 1)

```python
class Solution:
    def numberOfSubstrings(self, s: str) -> int:

        n = len(s)
        ans = 0

        # zeros = 0
        ones = 0
        for i in range(n):
            if s[i] == '1':
                ones += 1
                ans += ones
            else:
                ones = 0

        # zeros = 1 ~ sqrt(n)
        for zeros in range(1, isqrt(n) + 1):
            queue = deque()  # zero index
            left = ones = 0

            for right in range(n):
                if s[right] == '0':
                    queue.append(right)
                    while len(queue) > zeros:
                        ones -= (queue[0] - left)
                        left = queue.popleft() + 1
                else:
                    ones += 1

                if len(queue) == zeros and ones >= zeros ** 2:
                    ans += min(queue[0] - left + 1, ones - zeros ** 2 + 1)

        return ans
```
※ 編輯: dont (185.213.82.141 臺灣), 07/28/2024 20:06:00