1711. 大餐计数

1711. 大餐计数

from typing import List
from collections import Counter
import math


class Solution:
    def countPairs(self, deliciousness: List[int]) -> int:
        min_deliciousness = min(deliciousness)
        if min_deliciousness <= 0:
            min_deliciousness = 0.5
        max_deliciousness = max(deliciousness)
        count = Counter(deliciousness)
        ans = 0
        wait_list = [2 ** i for i in
                     range(int(math.log(min_deliciousness * 2, 2)), int(math.log(max_deliciousness * 2, 2)) + 1)]
        used = set()
        for k, v in count.items():
            for i in range(len(wait_list)):
                if wait_list[i] - k in count:
                    if wait_list[i] - k == k and v > 1:
                        ans += (1 + v - 1) * (v - 1) // 2
                        ans = ans % (10 ** 9 + 7)
                    elif wait_list[i] - k == k:
                        pass
                    else:
                        if wait_list[i] - k not in used:
                            ans += v * count[wait_list[i] - k]
                            ans = ans % (10 ** 9 + 7)
            used.add(k)
        return ans % (10 ** 9 + 7)

1702. 修改后的最大二进制字符串

1702. 修改后的最大二进制字符串

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        left = 0
        binary = list(binary)
        while left < len(binary) and binary[left] == '1':
            left += 1
        right = left + 1
        while right < len(binary):
            if binary[right] == '1':
                right += 1
                continue
            if right - left == 1:
                binary[left] = '1'
            else:
                binary[left] = '1'
                binary[right] = '1'
                binary[left + 1] = '0'
            left += 1
            right += 1
        return ''.join(binary)

133. 克隆图

133. 克隆图

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []


from typing import Optional


class Solution:
    def __init__(self):
        self.created = {}
        self.used = set()

    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if node is None:
            return None
        val = node.val
        self.dfs(node)
        return self.created[val]

    def dfs(self, node: Optional['Node']):
        if node.val in self.used:
            return
        if node.val not in self.created:
            new_node = Node(node.val)
            self.created[node.val] = new_node
        else:
            new_node = self.created[node.val]

        self.used.add(node.val)
        for i in range(len(node.neighbors)):
            if node.neighbors[i].val in self.created:
                new_node.neighbors.append(self.created[node.neighbors[i].val])
            else:
                tmp_node = Node(node.neighbors[i].val)
                self.created[tmp_node.val] = tmp_node
                new_node.neighbors.append(tmp_node)
            self.dfs(node.neighbors[i])

1991. 找到数组的中间位置

1991. 找到数组的中间位置

class Solution:
    def findMiddleIndex(self, nums: List[int]) -> int:
        right = sum(nums)
        left = 0
        for i in range(len(nums)):
            right -= nums[i]
            if left == right:
                return i
            left += nums[i]
        return -1

994. 腐烂的橘子

994. 腐烂的橘子

class Solution:
    def __init__(self):
        self.time = 0

    def orangesRotting(self, grid: List[List[int]]) -> int:
        rotting_oranges = set()
        normal_oranges = set()
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == 2:
                    rotting_oranges.add((i, j))
                if grid[i][j] == 1:
                    normal_oranges.add((i, j))
        if not normal_oranges:
            return 0
        while rotting_oranges:
            rotting_oranges_bak = set(rotting_oranges)
            for (x, y) in rotting_oranges_bak:
                if x - 1 >= 0 and grid[x - 1][y] == 1:
                    grid[x - 1][y] = 2
                    rotting_oranges.add((x - 1, y))
                if x + 1 < len(grid) and grid[x + 1][y] == 1:
                    grid[x + 1][y] = 2
                    rotting_oranges.add((x + 1, y))
                if y - 1 >= 0 and grid[x][y - 1] == 1:
                    grid[x][y - 1] = 2
                    rotting_oranges.add((x, y - 1))
                if y + 1 < len(grid[x]) and grid[x][y + 1] == 1:
                    grid[x][y + 1] = 2
                    rotting_oranges.add((x, y + 1))
            rotting_oranges = rotting_oranges - rotting_oranges_bak
            normal_oranges = normal_oranges - rotting_oranges
            self.time += 1
        return self.time - 1 if not normal_oranges else -1