1583. 统计不开心的朋友

1583. 统计不开心的朋友

模拟

class Solution:
    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:
        pair_index = {}
        for x in range(len(pairs)):
            for j in range(len(pairs[x])):
                pair_index[pairs[x][j]] = x
        unhappy = set()
        for x in range(n):
            if x in unhappy:
                continue
            pair = pairs[pair_index[x]]
            y = pair[0] if pair[0] != x else pair[1]
            for j in range(len(preferences[x])):
                u = preferences[x][j]
                if u == y:
                    break
                pair = pairs[pair_index[u]]
                v = pair[0] if pair[0] != u else pair[1]
                for k in range(len(preferences[u])):
                    if preferences[u][k] == x:
                        unhappy.add(x)
                        break
                    if preferences[u][k] == v:
                        break
        return len(unhappy)

1399. 统计最大组的数目

1399. 统计最大组的数目

from collections import defaultdict

class Solution:
    def countLargestGroup(self, n: int) -> int:
        d = defaultdict(int)
        max_cnt = 0
        for i in range(1, n + 1):
            x = sum(map(int, str(i)))
            d[x] += 1
            if d[x] > max_cnt:
                max_cnt = d[x]
        return sum(1 for value in d.values() if value == max_cnt)

1162. 地图分析

1162. 地图分析

class Solution:
    def __init__(self):
        self.next = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        self.calc_now = []
        self.calc_next = []

    def maxDistance(self, grid: List[List[int]]) -> int:
        dis = 0
        has_zero = False
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == 1:
                    self.calc_now.append((i, j))
                if grid[i][j] == 0:
                    has_zero = True
        if not self.calc_now or not has_zero:
            return -1
        while self.calc_now:
            dis += 1
            for i in range(len(self.calc_now)):
                self.set_dis(grid, self.calc_now[i][0], self.calc_now[i][1], dis)
            self.calc_now = self.calc_next[:]
            self.calc_next.clear()

        return dis - 1

    def set_dis(self, grid, i, j, dis):
        for k in range(len(self.next)):
            x = i + self.next[k][0]
            y = j + self.next[k][1]
            if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[x]):
                continue
            if grid[x][y] != 0:
                continue
            grid[x][y] = dis + 1
            self.calc_next.append((x, y))

1592. 重新排列单词间的空格

1592. 重新排列单词间的空格

class Solution:
    def reorderSpaces(self, text: str) -> str:
        space_num = text.count(' ')
        if space_num == 0:
            return text
        words = [word for word in text.split(' ') if word != '']
        if len(words) == 1:
            return words[0] + ' ' * space_num
        ans = []
        for i in range(len(words)):
            ans.append(words[i])
            if i != len(words) - 1:
                ans.append(' ' * (space_num // (len(words) - 1)))
        ans.append(" " * (space_num % (len(words) - 1)))
        return ''.join(ans)

427. 建立四叉树

427. 建立四叉树

class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        x = self.build(grid, 0, 0, len(grid), len(grid))
        return x

    def build(self, grid, x0, y0, x1, y1):
        res, val = self.check(grid, x0, y0, x1, y1)
        if res:
            node = Node(val, True, None, None, None, None)
            return node
        else:
            node = Node(val, False, None, None, None, None)
        area = {
            "topLeft": [x0, y0, (x0 + x1) // 2, (y0 + y1) // 2],
            "bottomRight": [(x0 + x1) // 2, (y0 + y1) // 2, x1, y1],
            "topRight": [x0, (y0 + y1) // 2, (x0 + x1) // 2, y1],
            "bottomLeft": [(x0 + x1) // 2, y0, x1, (y0 + y1) // 2],
        }
        for k, v in area.items():
            child_node = self.build(grid, *v)
            node.__setattr__(k, child_node)
        return node

    def check(self, grid, x0, y0, x1, y1):
        val = grid[x0][y0]
        for i in range(x0, x1):
            for j in range(y0, y1):
                if grid[i][j] != val:
                    return False, None
        return True, val

2166. 设计位集

2166. 设计位集

import array


class Bitset:
    def __init__(self, size: int):
        self.array = array.array('i', [0 for i in range(size // 8 + int(bool(size % 8)))])
        self.size = size
        self.cnt = 0
        self.reverse = False

    def fix(self, idx: int) -> None:
        array_idx = idx // 8
        bit_idx = idx % 8
        if (self.array[array_idx] >> bit_idx) & 0b1 == 0b1 and not self.reverse:
            return
        if (self.array[array_idx] >> bit_idx) & 0b1 == 0b0 and self.reverse:
            return
        self.cnt += 1
        self.array[array_idx] ^= (1 << bit_idx)

    def unfix(self, idx: int) -> None:
        array_idx = idx // 8
        bit_idx = idx % 8
        if (self.array[array_idx] >> bit_idx) & 0b1 == 0b1 and self.reverse:
            return
        if (self.array[array_idx] >> bit_idx) & 0b1 == 0b0 and not self.reverse:
            return
        self.cnt -= 1
        self.array[array_idx] ^= (1 << bit_idx)

    def flip(self) -> None:
        self.reverse = not self.reverse
        self.cnt = self.size - self.cnt

    def all(self) -> bool:
        return self.cnt == self.size

    def one(self) -> bool:
        return self.cnt >= 1

    def count(self) -> int:
        return self.cnt

    def toString(self) -> str:
        ans = []
        for i in range(len(self.array)):
            if not self.reverse:
                ans.append(bin(self.array[i])[:1:-1].ljust(8, '0'))
            else:
                ans.append(bin((2 ** 8 - 1) ^ self.array[i])[:1:-1].ljust(8, '0'))
        ans[-1] = ans[-1][:self.size % 8 if self.size % 8 != 0 else 8]
        return "".join(ans)