break algorithm---multi-interface

---

---

python语言实现

---

341.flatten-nested-list-iterator
600.non-negative-integers-without-consecutive-ones
707.design-linked-list
1603.design-parking-system
1656.design-an-ordered-stream
1670.design-front-middle-back-queue
1797.design-authentication-manager
1845.seat-reservation-manager
1912.design-movie-rental-system

---

---

341.flatten-nested-list-iterator

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """


class NestedInteger:
   def isInteger(self) -> bool:
       """ @return True if this NestedInteger holds a single integer, rather than a nested list. """

   def getInteger(self) -> int:
       """ @return the single integer that this NestedInteger holds, if it holds a single integer Return None if this NestedInteger holds a nested list """

   # def getList(self) -> [NestedInteger]:
   def getList(self):
       """ @return the nested list that this NestedInteger holds, if it holds a nested list Return None if this NestedInteger holds a single integer """

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):

        def gen(nl):
            for ni in nl:
                if ni.isInteger():
                    yield ni.getInteger()
                else:
                    yield from gen(ni.getList())

        self.it = gen(nestedList)
        try:
            self.store = next(self.it)
        except StopIteration:
            self.store = None

    def next(self) -> int:
        ret = self.store
        try:
            self.store = next(self.it)
        except StopIteration:
            self.store = None
        return ret

    def hasNext(self) -> bool:
        return self.store is not None


# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

---

---

---

---

707.design-linked-list

class ListNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None


class MyLinkedList:
    def __init__(self):
        self.size = 0
        self.head = ListNode(0)  # sentinel node as pseudo-head

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1

        curr = self.head
        for _ in range(index + 1):
            curr = curr.next
        return curr.val

    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size:
            return

        if index < 0:
            index = 0

        self.size += 1
        # find predecessor of the node to be added
        pred = self.head
        for _ in range(index):
            pred = pred.next

        # node to be added
        to_add = ListNode(val)
        # insertion itself
        to_add.next = pred.next
        pred.next = to_add

    def deleteAtIndex(self, index: int) -> None:
        """ Delete the index-th node in the linked list, if the index is valid. """
        # if the index is invalid, do nothing
        if index < 0 or index >= self.size:
            return

        self.size -= 1
        # find predecessor of the node to be deleted
        pred = self.head
        for _ in range(index):
            pred = pred.next

        # delete pred.next
        pred.next = pred.next.next

    def print(self) -> None:
        p = self.head
        while p.next:
            p = p.next
            print(p.val)


# Your MyLinkedList object will be instantiated and called as such:
linkedList = MyLinkedList()

linkedList.addAtHead(1)
linkedList.print()
print('---')


linkedList.addAtTail(3)
linkedList.print()
print('---')


linkedList.addAtIndex(1, 2)  # 链表变为1-> 2-> 3
linkedList.print()
print('---')


linkedList.get(1)  # 返回2
linkedList.print()
print('---')

linkedList.deleteAtIndex(1)  # 现在链表是1-> 3
linkedList.print()
print('---')

linkedList.get(1)  # 返回3
linkedList.print()
print('---')

---

---

1603.design-parking-system

class ParkingSystem:

    def __init__(self, big: int, medium: int, small: int):
        self.big = big
        self.medium = medium
        self.small = small

    def addCar(self, carType: int) -> bool:
        if carType == 1 and self.big > 0:
            self.big -= 1
            return True
        if carType == 2 and self.medium > 0:
            self.medium -= 1
            return True
        if carType == 3 and self.small > 0:
            self.small -= 1
            return True
        return False


# Your ParkingSystem object will be instantiated and called as such:
obj = ParkingSystem(1, 1, 0)

# 返回 true ，因为有 1 个空的大车位
print(obj.addCar(1))

# 返回 true ，因为有 1 个空的中车位
print(obj.addCar(2))

# 返回 false ，因为没有空的小车位
print(obj.addCar(3))

# 返回 false ，因为没有空的大车位，唯一一个大车位已经被占据了
print(obj.addCar(1))

---

---

1656.design-an-ordered-stream

from typing import List


class OrderedStream:

    def __init__(self, n: int):
        self.n = n
        self.ptr = 1
        self.stream = {
    }

    def insert(self, idKey: int, value: str) -> List[str]:
        if idKey < 0 or idKey > self.n:
            return []

        self.stream.setdefault(idKey, value)
        res = []
        if self.stream.get(self.ptr):
            while idKey < self.n + 1:
                if self.stream.get(idKey):
                    res.append(self.stream.get(idKey))
                    idKey += 1
                    self.ptr = idKey
                else:
                    break
        # print(res)
        return res


# Your OrderedStream object will be instantiated and called as such:
obj = OrderedStream(5)

# 插入 (3, "ccccc")，返回 []
obj.insert(3, "ccccc")

# 插入 (1, "aaaaa")，返回 ["aaaaa"]
obj.insert(1, "aaaaa")

# 插入 (2, "bbbbb")，返回 ["bbbbb", "ccccc"]
obj.insert(2, "bbbbb")

# 插入 (5, "eeeee")，返回 []
obj.insert(5, "eeeee")

# 插入 (4, "ddddd")，返回 ["ddddd", "eeeee"]
obj.insert(4, "ddddd")

---

---

1670.design-front-middle-back-queue

class FrontMiddleBackQueue:

    def __init__(self):
        self.list = []

    def pushFront(self, val: int) -> None:
        self.list.insert(0, val)

    def pushMiddle(self, val: int) -> None:
        self.list.insert(len(self.list) // 2, val)

    def pushBack(self, val: int) -> None:
        self.list.append(val)

    def popFront(self) -> int:
        # self.list.try_pop(0)
        return self.try_pop(0)

    def popMiddle(self) -> int:
        return self.try_pop((len(self.list) - 1) // 2)

    def popBack(self) -> int:
        return self.try_pop(-1)

    def try_pop(self, index):
        try:
            return self.list.pop(index)
        except:
            return -1

    def print(self):
        print(self.list)


# Your FrontMiddleBackQueue object will be instantiated and called as such:
q = FrontMiddleBackQueue()

# [1]
q.pushFront(1)
q.print()
print('---')

# [1, 2]
q.pushBack(2)
q.print()
print('---')

# [1, 3, 2]
q.pushMiddle(3)
q.print()
print('---')

# [1, 4, 3, 2]
q.pushMiddle(4)
q.print()
print('---')

# return 1 -> [4, 3, 2]
q.popFront()
q.print()
print('---')

# return 3 -> [4, 2]
q.popMiddle()
q.print()
print('---')

# return 4 -> [2]
q.popMiddle()
q.print()
print('---')

# return 2 -> []
q.popBack()
q.print()
print('---')

# return -1 -> [] (The queue is empty)
q.popFront()
q.print()
print('---')

---

---

1797.design-authentication-manager

class AuthenticationManager:

    def __init__(self, timeToLive: int):
        self.timeToLive = timeToLive
        self.tokenId = dict()

    def generate(self, tokenId: str, currentTime: int) -> None:
        self.tokenId.setdefault(tokenId, currentTime)

    def renew(self, tokenId: str, currentTime: int) -> None:
        if self.tokenId.get(tokenId) and currentTime < self.timeToLive + self.tokenId.get(tokenId):
            self.tokenId[tokenId] = currentTime
        else:
            return

    def countUnexpiredTokens(self, currentTime: int) -> int:
        res = 0
        times = self.tokenId.values()
        for time in times:
            if time + self.timeToLive > currentTime:
                res += 1
        return res


# 构造 AuthenticationManager ，设置 timeToLive = 5 秒。
authenticationManager = AuthenticationManager(5)
# 时刻 1 时，没有验证码的 tokenId 为 "aaa" ，没有验证码被更新。
print(authenticationManager.renew("aaa", 1))
# 时刻 2 时，生成一个 tokenId 为 "aaa" 的新验证码。
print(authenticationManager.generate("aaa", 2))
# 时刻 6 时，只有 tokenId 为 "aaa" 的验证码未过期，所以返回 1 。
print(authenticationManager.countUnexpiredTokens(6))
# 时刻 7 时，生成一个 tokenId 为 "bbb" 的新验证码。
print(authenticationManager.generate("bbb", 7))
# tokenId 为 "aaa" 的验证码在时刻 7 过期，且 8 >= 7 ，所以时刻 8 的renew 操作被忽略，没有验证码被更新。
print(authenticationManager.renew("aaa", 8))
# tokenId 为 "bbb" 的验证码在时刻 10 没有过期，所以 renew 操作会执行，该 token 将在时刻 15 过期。
print(authenticationManager.renew("bbb", 10))
# tokenId 为 "bbb" 的验证码在时刻 15 过期，tokenId 为 "aaa" 的验证码在时刻 7 过期，所有验证码均已过期，所以返回 0 。
print(authenticationManager.countUnexpiredTokens(15))

---

---

1845.seat-reservation-manager

---

---

1912.design-movie-rental-system

from collections import defaultdict
from typing import List
import sortedcontainers


class MovieRentingSystem:

    def __init__(self, n: int, entries: List[List[int]]):
        self.t_price = dict()
        self.t_valid = defaultdict(sortedcontainers.SortedList)
        self.t_rent = sortedcontainers.SortedList()

        for shop, movie, price in entries:
            self.t_price[(shop, movie)] = price
            self.t_valid[movie].add((price, shop))

    def search(self, movie: int) -> List[int]:
        t_valid_ = self.t_valid

        if movie not in t_valid_:
            return []

        return [shop for (price, shop) in t_valid_[movie][:5]]

    def rent(self, shop: int, movie: int) -> None:
        price = self.t_price[(shop, movie)]
        self.t_valid[movie].discard((price, shop))
        self.t_rent.add((price, shop, movie))

    def drop(self, shop: int, movie: int) -> None:
        price = self.t_price[(shop, movie)]
        self.t_valid[movie].add((price, shop))
        self.t_rent.discard((price, shop, movie))

    def report(self) -> List[List[int]]:
        return [[shop, movie] for price, shop, movie in self.t_rent[:5]]


movieRentingSystem = MovieRentingSystem(3, [[0, 1, 5], [0, 2, 6], [0, 3, 7], [1, 1, 4], [1, 2, 7], [2, 1, 5]])
# 返回 [1, 0, 2] ，商店 1，0 和 2 有未借出的 ID 为 1 的电影。商店 1 最便宜，商店 0 和 2 价格相同，所以按商店编号排序。
movieRentingSystem.search(1)
# 从商店 0 借出电影 1 。现在商店 0 未借出电影编号为 [2,3] 。
movieRentingSystem.rent(0, 1)
print('---')
# 从商店 1 借出电影 2 。现在商店 1 未借出的电影编号为 [1] 。
movieRentingSystem.rent(1, 2)
print('---')
# 返回 [[0, 1], [1, 2]] 。商店 0 借出的电影 1 最便宜，然后是商店 1 借出的电影 2 。
movieRentingSystem.report()
# 在商店 1 返还电影 2 。现在商店 1 未借出的电影编号为 [1,2] 。
movieRentingSystem.drop(1, 2)
print('---')
# # 返回 [0, 1] 。商店 0 和 1 有未借出的 ID 为 2 的电影。商店 0 最便宜，然后是商店 1 。
# movieRentingSystem.search(2)