面试题 17.07. 婴儿名字

面试题 17.07. 婴儿名字

并查集

from typing import List
import re
from collections import defaultdict


class UnionFindSet:
    def __init__(self):
        self.parent = {}

    def find(self, x):
        if x not in self.parent:
            self.parent[x] = x
            return x
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def merge(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if root_x < root_y:
            self.parent[root_y] = root_x
        else:
            self.parent[root_x] = root_y


class Solution:
    def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:
        uf = UnionFindSet()
        for item in synonyms:
            x = item[1:-1].split(',')
            uf.merge(x[0], x[1])
        ans = defaultdict(int)
        for item in names:
            r = item.split('(')
            name = r[0]
            count = int(r[1][:-1])
            ans[uf.find(name)] += count
        return_list = []
        for k, v in ans.items():
            return_list.append(f"{k}({v})")
        return return_list

LCR 073. 爱吃香蕉的狒狒

LCR 073. 爱吃香蕉的狒狒

二分法

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        right = max(piles)
        left = 1
        while left < right:
            speed = (right - left) // 2 + left  # 中点
            if sum([(speed + p - 1) // speed for p in piles]) <= h:
                right = speed
            else:
                left = speed + 1
        return left

LCR 059. 数据流中的第 K 大元素

LCR 059. 数据流中的第 K 大元素

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        self.k_nums = sorted(nums, reverse=True)[:k]

    def add(self, val: int) -> int:
        if len(self.k_nums) < self.k:
            self.k_nums.append(val)
            self.k_nums.sort(reverse=True)
        elif self.k_nums[-1] < val:
            self.k_nums.pop()
            self.k_nums.append(val)
            self.k_nums.sort(reverse=True)
        return self.k_nums[-1]

2296. 设计一个文本编辑器

2296. 设计一个文本编辑器

双链表或者对顶栈

class Node:
    def __init__(self, val, prev_node=None, next_node=None):
        self.val = val
        self.prev_node = prev_node
        self.next_node = next_node


class TextEditor:
    def __init__(self):
        self.cursor = Node(None)
        self.cursor.prev_node = None
        self.cursor.next_node = Node(None)
        self.cursor.next_node.prev_node = self.cursor

    def addText(self, text: str) -> None:
        for c in text:
            node = Node(c, self.cursor, self.cursor.next_node)
            self.cursor.next_node.prev_node = node
            self.cursor.next_node = node
            self.cursor = node

    def deleteText(self, k: int) -> int:
        delete_num = 0
        for i in range(k):
            if self.cursor.val is None:
                break
            self.cursor.next_node.prev_node = self.cursor.prev_node
            self.cursor.prev_node.next_node = self.cursor.next_node
            self.cursor = self.cursor.prev_node
            delete_num += 1
        # print(delete_num)
        return delete_num

    def cursorLeft(self, k: int) -> str:
        for i in range(k):
            if self.cursor.val is None:
                break
            self.cursor = self.cursor.prev_node
        tmp_cursor = self.cursor
        join_list = []
        for i in range(10):
            if tmp_cursor.val is None:
                break
            join_list.append(tmp_cursor.val)
            tmp_cursor = tmp_cursor.prev_node
        join_list.reverse()
        return "".join(join_list)

    def cursorRight(self, k: int) -> str:
        for i in range(k):
            if self.cursor.next_node.val is None:
                break
            self.cursor = self.cursor.next_node
        tmp_cursor = self.cursor
        join_list = []
        for i in range(10):
            if tmp_cursor.val is None:
                break
            join_list.append(tmp_cursor.val)
            tmp_cursor = tmp_cursor.prev_node
        join_list.reverse()
        return "".join(join_list)