leetcode

from collections import defaultdict


class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        rows = defaultdict(int)
        cols = defaultdict(int)
        left = defaultdict(int)
        right = defaultdict(int)
        ans = []

        def put(output, i, j):
            rows[i] = 1
            cols[j] = 1
            left[i + j] = 1
            right[i - j] = 1
            output[i][j] = "Q"

        def clear(output, i, j):
            rows[i] = 0
            cols[j] = 0
            left[i + j] = 0
            right[i - j] = 0
            output[i][j] = "."

        def isValid(i, j):
            return (
                rows[i] == 0 and cols[j] == 0 and left[i + j] == 0 and right[i - j] == 0
            )

        def dfs(output, i):
            if i == n:
                ans.append(["".join(x) for x in output])
                return
            for j in range(n):
                if isValid(i, j):
                    put(output, i, j)
                    dfs(output, i + 1)
                    clear(output, i, j)

        output = [["." for _ in range(n)] for _ in range(n)]
        dfs(output, 0)
        return ans

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        visited = set()
        ans = []

        def dfs(curr):
            if len(curr) == len(nums):
                ans.append(curr)
                return
            used = set()
            for i, x in enumerate(nums):
                if i in visited:
                    continue
                if x in used:
                    continue
                used.add(x)
                visited.add(i)
                dfs(curr + [x])
                visited.remove(i)

        dfs([])
        return ans

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        M, N = len(matrix), len(matrix[0])

        def solve(lo, hi, target):
            if lo[0] >= hi[0] or lo[1] >= hi[1]:
                return False
            midx, midy = (lo[0] + hi[0]) // 2, (lo[1] + hi[1]) // 2
            if matrix[midx][midy] == target:
                return True
            if matrix[midx][midy] > target:
                return solve(lo, (midx, hi[1]), target) or solve(
                    lo, (hi[0], midy), target
                )
            return solve((lo[0], midy + 1), hi, target) or solve(
                (midx + 1, lo[1]), hi, target
            )

        return solve((0, 0), (M, N), target)

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        M, N = len(matrix), len(matrix[0])
        x, y = 0, N - 1
        while x < M and y >= 0:
            if matrix[x][y] == target:
                return True
            if matrix[x][y] > target:
                y -= 1
            else:
                x += 1
        return False

class Solution:
    def findMin(self, nums: List[int]) -> int:
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[lo] > nums[mid]:
                hi = mid
            elif nums[mid] > nums[hi]:
                lo = mid + 1
            else:
                hi = mid
        return nums[lo]

class Solution:
    def findMin(self, nums: List[int]) -> int:
        lo, hi = 0, len(nums)
        ans = 1 << 31
        while lo < hi:
            mid = (lo + hi) // 2
            ans = min(ans, nums[mid])
            if nums[lo] > nums[mid]:
                hi = mid
            elif nums[mid] > nums[hi - 1]:
                lo = mid + 1
            else:
                hi = mid
        return ans

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            if nums[lo] < nums[mid]:
                if target >= nums[lo] and target < nums[mid]:
                    hi = mid
                else:
                    lo = mid + 1
            else:
                if target > nums[mid] and target <= nums[hi - 1]:
                    lo = mid + 1
                else:
                    hi = mid
        return -1

class Solution:
    def mySqrt(self, x: int) -> int:
        lo = 1
        hi = x
        while lo <= hi:
            mid = (lo + hi) // 2
            if mid * mid <= x and (mid + 1) * (mid + 1) > x:
                return mid
            if mid * mid > x:
                hi = mid - 1
            else:
                lo = mid + 1
        return 0

class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        N = len(nums)

        def ok(n):
            t = nums[::]
            for i in reversed(range(1, N)):
                if t[i] > n:
                    t[i - 1] += t[i] - n
            return t[0] <= n

        lo, hi = min(nums), max(nums)
        ans = 0
        while lo <= hi:
            mid = (lo + hi) // 2
            if ok(mid):
                ans = mid
                hi = mid - 1
            else:
                lo = mid + 1
        return ans

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        lo = 0
        hi = len(nums)
        N = len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if (mid == 0 or nums[mid] != nums[mid - 1]) and (
                mid == N - 1 or nums[mid] != nums[mid + 1]
            ):
                return nums[mid]
            pair = mid + 1 if mid % 2 == 0 else mid - 1
            if nums[mid] == nums[pair]:
                lo = mid + 1
            else:
                hi = mid

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False
        _dp = [{} for _ in range(len(nums))]
        _dp[0][0] = 1
        _dp[0][nums[0]] = 1
        for i in range(1, len(nums)):
            for k, v in _dp[i - 1].items():
                _dp[i][k + nums[i]] = 1
                _dp[i][k] = 1
        return total // 2 in _dp[-1]

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        _dp = [0 for _ in range(amount + 1)]
        MAX = 1 << 31

        def dp(i):
            if i < 0:
                return MAX
            return _dp[i]

        for i in range(1, amount + 1):
            tmp = MAX
            for c in coins:
                tmp = min(tmp, dp(i - c) + 1)
            _dp[i] = tmp

        if _dp[-1] == MAX:
            return -1
        return _dp[-1]

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        _dp = [0 for _ in range(amount + 1)]
        _dp[0] = 1

        def dp(i):
            if i < 0:
                return 0
            return _dp[i]

        for c in coins:
            for i in range(1, amount + 1):
                _dp[i] += dp(i - c)

        return _dp[-1]

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        _dp = [0 for _ in range(target + 1)]
        _dp[0] = 1

        def dp(i):
            if i < 0:
                return 0
            return _dp[i]

        for i in range(1, target + 1):
            for x in nums:
                _dp[i] += dp(i - x)
        return _dp[-1]

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        N = len(s)
        wordDict = set(wordDict)

        _dp = [False for _ in range(N)]

        def dp(i):
            if i == -1:
                return True
            return _dp[i]

        for i in range(N):
            for j in range(i + 1):
                x = s[j : i + 1]
                tmp = False
                if x in wordDict:
                    tmp |= dp(j - 1)
                if tmp:
                    _dp[i] = True
                    break
        return _dp[-1]

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        N = len(piles)
        # 5 3 4 5
        #   i j
        dp = [[0 for _ in range(N)] for _ in range(N)]
        for i in range(N):
            dp[i][i] = piles[i]
        for d in range(1, N):
            for i in range(N - d):
                dp[i][i + d] = max(
                    piles[i] - dp[i + 1][i + d], piles[i + d] - dp[i][i + d - 1]
                )
        return dp[0][-1] > 0

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        # 5 -3 5
        # 5 -3 5 5 -3 5
        def getMax(nums):
            ans = nums[0]
            dp = nums[:]
            for i in range(1, len(nums)):
                dp[i] = max(dp[i - 1] + nums[i], nums[i])
                ans = max(ans, dp[i])
            return ans

        def getMin(nums):
            ans = nums[0]
            dp = nums[:]
            for i in range(1, len(nums)):
                dp[i] = min(dp[i - 1] + nums[i], nums[i])
                ans = min(ans, dp[i])
            return ans

        a = getMax(nums)
        b = getMin(nums)
        if b == sum(nums):
            return a
        return max(a, sum(nums) - b)

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        _dp = [[0 for _ in range(query_row + 1)] for _ in range(query_row + 1)]
        _dp[0][0] = poured

        def get(i, j):
            if j < 0 or j > i:
                return 0
            return (_dp[i][j] - 1) / 2 if _dp[i][j] >= 1 else 0

        for i in range(1, query_row + 1):
            goon = False
            for j in range(i + 1):
                _dp[i][j] = get(i - 1, j - 1) + get(i - 1, j)
                if _dp[i][j] > 1:
                    goon = True
            if not goon:
                break
        return min(_dp[query_row][query_glass], 1)

class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        # 4 2 5 3
        N = len(nums)
        # subseq 中元素为偶数个
        _dpEven = [0 for _ in range(N)]
        # subseq 中元素为奇数个
        _dpOdd = [0 for _ in range(N)]

        _dpOdd[0] = nums[0]

        for i in range(1, N):
            _dpEven[i] = max(_dpEven[i - 1], _dpOdd[i - 1] - nums[i])
            _dpOdd[i] = max(_dpOdd[i - 1], _dpEven[i - 1] + nums[i])
        return max(_dpEven[-1], _dpOdd[-1])

class Solution:
    def findTheCity(
        self, n: int, edges: List[List[int]], distanceThreshold: int
    ) -> int:
        dist = [[1 << 31 for _ in range(n)] for _ in range(n)]
        for x, y, d in edges:
            dist[x][y] = d
            dist[y][x] = d
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if i == j:
                        continue
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

        count = [len(list(filter(lambda x: x <= distanceThreshold, x))) for x in dist]
        target = min(count)
        for i in reversed(range(n)):
            if count[i] == target:
                return i

from collections import deque


class Solution:
    def findCheapestPrice(
        self, n: int, flights: List[List[int]], src: int, dst: int, k: int
    ) -> int:
        q = deque()
        q.append((src, 0))
        q.append(None)
        stops = 0
        ans = 0
        shortest = {}
        conn = {}
        for f, t, p in flights:
            if f not in conn:
                conn[f] = []
            conn[f].append([t, p])
        while q:
            top = q.popleft()
            if top is None:
                if q:
                    q.append(None)
                stops += 1
                if stops == k + 2:
                    break
                continue
            shortest[top[0]] = min(shortest.get(top[0], 1 << 31), top[1])
            for t, p in conn.get(top[0], []):
                if t not in shortest or shortest[t] > p + top[1]:
                    q.append((t, top[1] + p))
        if dst in shortest:
            return shortest[dst]
        return -1

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        dep = [[] for _ in range(numCourses)]
        order = [0 for _ in range(numCourses)]
        for a, b in prerequisites:
            dep[b].append(a)
            order[a] += 1
        q = deque()
        count = 0
        for i in range(numCourses):
            if order[i] == 0:
                count += 1
                q.append(i)
        while q:
            top = q.popleft()
            for x in dep[top]:
                order[x] -= 1
                if order[x] == 0:
                    count += 1
                    q.append(x)
        return count == numCourses

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        M, N = len(board), len(board[0])

        visited = {}

        def dfs(x, y):
            if x < 0 or y < 0 or x >= M or y >= N:
                return
            if board[x][y] != "O":
                return
            if (x, y) in visited:
                return
            visited[(x, y)] = 1
            board[x][y] = "Y"
            dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]
            for xx, yy in dir:
                dfs(x + xx, y + yy)

        for x in [0, M - 1]:
            for y in range(N):
                dfs(x, y)
        for y in [0, N - 1]:
            for x in range(M):
                dfs(x, y)

        for x in range(M):
            for y in range(N):
                if board[x][y] == "O":
                    board[x][y] = "X"
        for x in range(M):
            for y in range(N):
                if board[x][y] == "Y":
                    board[x][y] = "O"

from collections import deque


class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        # 000
        # 010
        # 111
        q = deque()
        M, N = len(mat), len(mat[0])
        ans = [[-1 for _ in range(N)] for _ in range(M)]
        visited = set()
        for i in range(M):
            for j in range(N):
                if mat[i][j] == 0:
                    ans[i][j] = 0
                    q.append((i, j))
                    visited.add((i, j))

        q.append(None)
        distance = 1
        while q:
            top = q.popleft()
            if top is None:
                if q:
                    q.append(None)
                distance += 1
                continue
            for d in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                x, y = top[0] + d[0], top[1] + d[1]
                if x < 0 or x >= M or y < 0 or y >= N:
                    continue
                if (x, y) in visited:
                    continue
                ans[x][y] = distance
                visited.add((x, y))
                q.append((x, y))
        return ans

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        m = {}
        for i, v in enumerate(nums):
            if target - v in m:
                return [m[target - v], i]
            m[v] = i
        return None

class Solution:
    def kSmallestPairs(self, nums1, nums2, k):
        q = [(nums1[0] + nums2[0], [0, 0])]
        visited = {}
        A, B = len(nums1), len(nums2)
        ans = []
        while k > 0:
            a, b = heappop(q)[1]
            if (a, b) in visited:
                continue
            k -= 1
            visited[(a, b)] = 1
            ans.append([nums1[a], nums2[b]])
            if a + 1 < A:
                heappush(q, (nums1[a + 1] + nums2[b], [a + 1, b]))
            if b + 1 < B:
                heappush(q, (nums1[a] + nums2[b + 1], [a, b + 1]))
        return ans

class MedianFinder:

    def __init__(self):
        self.lq = []  # maxheap
        self.rq = []  # minheap

    def addNum(self, num: int) -> None:
        if len(self.lq) == len(self.rq):
            heappush(self.lq, -heappushpop(self.rq, num))
        else:
            heappush(self.rq, -heappushpop(self.lq, -num))

    def findMedian(self) -> float:
        if len(self.lq) == len(self.rq):
            return (-self.lq[0] + self.rq[0]) / 2
        else:
            return -self.lq[0]

class Solution:
    def insert(self, intervals, newInterval):
        intervals.sort(key=lambda x: x[0])
        ans = []
        lo, hi = newInterval
        i = 0
        while i < len(intervals) and intervals[i][1] < lo:
            ans.append(intervals[i])
            i += 1
        while i < len(intervals) and intervals[i][0] <= hi:
            lo, hi = min(lo, intervals[i][0]), max(hi, intervals[i][1])
            i += 1
        ans.append([lo, hi])
        while i < len(intervals):
            ans.append(intervals[i])
            i += 1
        return ans

class Node:
    def __init__(self, k=0, v=0):
        self.prev = self
        self.next = self
        self.val = v
        self.key = k

    def insert(self, b):
        # a b c
        a = self
        c = self.next
        a.next, b.next = b, c
        c.prev, b.prev = b, a

    def delete(self):
        # a b c
        a = self.prev
        c = self.next
        a.next, c.prev = c, a


class LRUCache:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.m = {}  # map int to node
        self.head = Node()
        self.tail = Node()
        self.head.next, self.head.prev = self.tail, self.tail
        self.tail.next, self.tail.prev = self.head, self.head

    def get(self, key: int) -> int:
        if key not in self.m:
            return -1
        node = self.m[key]
        node.delete()
        self.head.insert(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.m:
            node = self.m[key]
            node.val = value
            node.delete()
            self.head.insert(node)
            return
        if len(self.m) == self.cap:
            evict = self.tail.prev
            self.m.pop(evict.key)
            evict.delete()
        node = Node(key, value)
        self.m[key] = node
        self.head.insert(node)

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head:
            return head

        prev, curr = head, head
        N = 0
        while curr:
            prev, curr = curr, curr.next
            N += 1
        k %= N
        prev.next = head

        prev = head
        for _ in range(N - k):
            prev, head = head, head.next
        prev.next = None
        return head

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        N = len(nums)
        _dp = [1 for _ in range(N)]
        ans = 1
        for i in range(N):
            for j in range(i):
                if nums[i] > nums[j]:
                    _dp[i] = max(_dp[i], _dp[j] + 1)
            ans = max(ans, _dp[i])
        return ans

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        def bisect_left(nums, target):
            lo, hi = 0, len(nums)
            while lo < hi:
                mid = (lo + hi) // 2
                if target <= nums[mid]:
                    hi = mid
                else:
                    lo = mid + 1
            return lo

        lis = []
        for x in nums:
            if not lis or x > lis[-1]:
                lis.append(x)
            else:
                idx = bisect_left(lis, x)
                lis[idx] = x
        return len(lis)

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        ans = 1
        _dp = {}
        for x in s:
            t = 1
            for y, l in _dp.items():
                if abs(ord(x) - ord(y)) <= k:
                    t = max(t, l + 1)
            _dp[x] = t
            ans = max(ans, t)
        return ans

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        dp = [0, 0]
        for x in s:
            if x == "0":
                dp[0] += 1
            else:
                dp[1] = max(dp[0], dp[1]) + 1
        return len(s) - max(dp)

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """

        def transpose(matrix):
            N = len(matrix)
            for i in range(N):
                # NOTE: inplace transpose 时注意 j 的范围
                for j in range(i, N):
                    matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

        def reverse(matrix):
            N = len(matrix)
            for i in range(N // 2):
                matrix[i], matrix[N - 1 - i] = matrix[N - 1 - i], matrix[i]

        reverse(matrix)
        transpose(matrix)

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        N = len(temperatures)
        ans = [0 for _ in range(N)]
        for i in range(N):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                t = stack.pop()
                ans[t] = i - t
            stack.append(i)
        return ans

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        # 3 1 2 4
        N = len(arr)

        left = [0 for _ in range(N)]
        stack = []
        for i in range(N):
            while stack and arr[i] <= arr[stack[-1]]:
                stack.pop()
            left[i] = stack[-1] if stack else -1
            stack.append(i)

        right = [0 for _ in range(N)]
        stack = []
        for i in reversed(range(N)):
            while stack and arr[i] < arr[stack[-1]]:
                stack.pop()
            right[i] = stack[-1] if stack else N
            stack.append(i)

        ans = 0
        for i in range(N):
            ans += arr[i] * (i - left[i]) * (right[i] - i)
        return ans % (10**9 + 7)

class Solution:
    def find132pattern(self, nums: List[int]) -> bool:
        stack = []
        third = -1 << 31
        for i in reversed(range(len(nums))):
            if nums[i] < third:
                return True
            while stack and nums[i] > stack[-1]:
                third = stack.pop()
            stack.append(nums[i])
        return False

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        N = len(days)

        @cache
        def solve(start):
            if start >= N:
                return 0

            A = costs[0] + solve(start + 1)

            idx = bisect_left(days, days[start] + 7)
            B = costs[1] + solve(idx)

            idx = bisect_left(days, days[start] + 30)
            C = costs[2] + solve(idx)

            return min(A, B, C)

        return solve(0)

from collections import Counter
from collections import defaultdict


class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        c = Counter(words)
        width = len(words[0])

        def solve(s):
            x = []
            for i in range(0, len(s), width):
                x.append(s[i : i + width])
            N = len(x)
            ans = []
            lo = 0
            window = len(words)
            m = defaultdict(int)
            for hi in range(N):
                m[x[hi]] += 1
                if hi - lo + 1 == window:
                    if all([m[x] == c[x] for x in c.keys()]):
                        ans.append(lo * width)
                    m[x[lo]] -= 1
                    lo += 1
            return ans

        ans = []
        for i in range(width):
            ans.extend([x + i for x in solve(s[i:])])
        return ans

from collections import defaultdict


class Solution:
    def test(self, counter, k):
        x = list(counter.values())
        return sum(x) - max(x) == k + 1

    def characterReplacement(self, s: str, k: int) -> int:
        counter = defaultdict(int)
        lo = 0
        ans = 0
        for hi in range(len(s)):
            x = s[hi]
            counter[x] += 1
            while self.test(counter, k):
                counter[s[lo]] -= 1
                lo += 1
            ans = max(ans, hi - lo + 1)
        ans = max(ans, hi - lo + 1)
        return ans

from collections import defaultdict
from collections import Counter


class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        maxChar = len(Counter(s))
        ans = 0
        for i in range(1, maxChar + 1):
            uniqueCounter = defaultdict(int)
            lo = 0
            for hi in range(len(s)):
                uniqueCounter[s[hi]] += 1
                while len(uniqueCounter) > i:
                    uniqueCounter[s[lo]] -= 1
                    if uniqueCounter[s[lo]] == 0:
                        uniqueCounter.pop(s[lo])
                    lo += 1
                if all([x >= k for x in uniqueCounter.values()]):
                    ans = max(ans, hi - lo + 1)
            if all([x >= k for x in uniqueCounter.values()]):
                ans = max(ans, hi - lo + 1)
        return ans

class Solution:
    def longestNiceSubarray(self, nums: List[int]) -> int:
        lo = 0
        used = 0
        ans = 0
        for hi in range(len(nums)):
            while used & nums[hi] != 0:
                used ^= nums[lo]
                lo += 1
            used |= nums[hi]
            ans = max(ans, hi - lo + 1)
        return ans

from collections import defaultdict


class Solution:
    def countCompleteSubarrays(self, nums: List[int]) -> int:
        b = set(nums)
        a = defaultdict(int)
        lo = 0
        ans = 0
        for hi in range(len(nums)):
            a[nums[hi]] += 1
            while set(a.keys()) == b:
                ans += len(nums) - hi
                a[nums[lo]] -= 1
                if a[nums[lo]] == 0:
                    a.pop(nums[lo])
                lo += 1
        return ans

def solve(tokens):
    ans = 0
    sign = 1
    for x in tokens:
        if x == "+":
            sign = 1
        elif x == "-":
            sign = -1
        else:
            ans += int(x) * sign
    return ans

class Solution:
    def calculate(self, s: str) -> int:
        def getTokens(s):
            ans = []
            i = 0
            digit = ""
            while i < len(s):
                if s[i] == " ":
                    i += 1
                    continue
                if s[i].isdigit():
                    while i < len(s) and s[i].isdigit():
                        digit += s[i]
                        i += 1
                    ans.append(digit)
                    digit = ""
                elif s[i] in "+-*/":
                    ans.append(s[i])
                    i += 1
                else:
                    balance = 0
                    tmp = ""
                    while True:
                        if s[i] == "(":
                            balance += 1
                        elif s[i] == ")":
                            balance -= 1
                        tmp += s[i]
                        i += 1
                        if balance == 0:
                            ans.append(getTokens(tmp[1:-1]))
                            break
            return ans

        def solve(tokens):
            sign = 1
            times = 0
            divid = 0
            stack = []
            for x in tokens:
                if x == "+":
                    sign = 1
                elif x == "-":
                    sign = -1
                elif x == "*":
                    times = 1
                elif x == "-":
                    divid = 1
                else:
                    if isinstance(x, list):
                        stack.append(solve(x) * sign)
                    elif x.isdigit():
                        stack.append(int(x) * sign)
                    if times == 1:
                        stack.append(stack.pop() * stack.pop())
                        times = 0
                    if divid == 1:
                        b, a = stack.pop(), stack.pop()
                        stack.append(a / b)
                        divid = 0
            return sum(stack)

        return solve(getTokens(s))


if __name__ == "__main__":
    S = Solution()
    print(S.calculate("1+2*2*(1+1*2)+3+(-1)*(-1-1)*(-2)"))

class BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        self.stack = []
        curr = root
        while curr:
            self.stack.append(curr)
            curr = curr.left

    def next(self) -> int:
        top = self.stack.pop()
        curr = top.right
        while curr:
            self.stack.append(curr)
            curr = curr.left
        return top.val

    def hasNext(self) -> bool:
        return len(self.stack) != 0

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def same(a, b):
            if not a and not b:
                return True
            if not a or not b:
                return False
            return a.val == b.val and same(a.left, b.right) and same(a.right, b.left)

        return same(root.left, root.right)

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def check(root):
            MIN, MAX = root.val, root.val
            if root.left:
                ans, x, y = check(root.left)
                if not ans:
                    return False, 0, 0
                if root.val <= y:
                    return False, 0, 0
                MIN = min(MIN, x)
                MAX = max(MAX, y)
            if root.right:
                ans, x, y = check(root.right)
                if not ans:
                    return False, 0, 0
                if root.val >= x:
                    return False, 0, 0
                MIN = min(MIN, x)
                MAX = max(MAX, y)
            return True, MIN, MAX

        if not root:
            return True
        ans, _, _ = check(root)
        return ans

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        ans = []

        def inorder(root):
            if not root:
                return
            inorder(root.left)
            ans.append(root.val)
            inorder(root.right)

        def isSorted(nums):
            if len(nums) <= 1:
                return True
            for i in range(1, len(nums)):
                if nums[i] <= nums[i - 1]:
                    return False
            return True

        inorder(root)
        return isSorted(ans)

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            n = -n
            x = 1 / x
            ans = 1
        while n > 1:
            if n % 2 == 1:
                ans *= x
                n -= 1
            else:
                x *= x
                n /= 2
        return ans * x

class Solution:
    def romanToInt(self, s: str) -> int:
        m = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
        ans = 0
        MAX = 1
        for x in s[::-1]:
            v = m[x]
            if v >= MAX:
                ans += v
                MAX = v
            else:
                ans -= v
        return ans

class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        total = 0
        ans = 0
        for i, v in enumerate(nums):
            total += v
            ans = max(ans, math.ceil(total / (i + 1)))
        return ans

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        M, N = len(grid), len(grid[0])
        x, y = 0, N - 1
        ans = 0
        while x < M and y >= 0:
            if grid[x][y] >= 0:
                x += 1
            else:
                ans += M - x
                y -= 1
        return ans

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        ans = [0 for _ in range(len(nums))]

        def mergeSort(nums):
            # 5 2 6 1
            # 2 5 | 1 6
            if len(nums) <= 1:
                return nums
            mid = len(nums) // 2
            a = mergeSort(nums[:mid])
            b = mergeSort(nums[mid:])

            hi = 0
            for lo in range(len(a)):
                while hi < len(b) and a[lo][1] > b[hi][1]:
                    hi += 1
                ans[a[lo][0]] += hi

            ret = []
            ai, bi = 0, 0
            while ai < len(a) or bi < len(b):
                x = a[ai][1] if ai < len(a) else 1 << 31
                y = b[bi][1] if bi < len(b) else 1 << 31
                if x <= y:
                    ret.append(a[ai])
                    ai += 1
                else:
                    ret.append(b[bi])
                    bi += 1
            return ret

        mergeSort([(i, a) for i, a in enumerate(nums)])
        return ans

class Node:
    def __init__(self):
        self.children = {}
        self.word = None


class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        def addWord(root, word):
            for w in word:
                if w not in root.children:
                    root.children[w] = Node()
                root = root.children[w]
            root.word = word

        trie = Node()
        for word in words:
            addWord(trie, word)

        ans = set()
        visited = set()
        M, N = len(board), len(board[0])

        def dfs(x, y, root):
            if x < 0 or x >= M or y < 0 or y >= N:
                return
            if board[x][y] not in root.children:
                return
            if (x, y) in visited:
                return
            visited.add((x, y))
            root = root.children[board[x][y]]
            if root.word:
                ans.add(root.word)
            for xx, yy in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                dfs(x + xx, y + yy, root)
            visited.remove((x, y))

        for x in range(M):
            for y in range(N):
                dfs(x, y, trie)

        return list(ans)

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        houses.sort()
        heaters.sort()
        # 1 2 3 4
        # 1     4
        hidx = 0
        ans = 0
        for h in houses:
            while hidx != len(heaters) - 1 and abs(h - heaters[hidx]) >= abs(
                h - heaters[hidx + 1]
            ):
                hidx += 1
            ans = max(ans, abs(h - heaters[hidx]))
        return ans

class Solution:
    def removeDuplicates(self, nums):
        lo = 2
        for x in nums[2:]:
            # nums[lo - 1] != x 代表 lo 设为 x 后 lo-1 和 lo 不重复
            #
            # nums[lo - 2] != x 代表 lo 设为 x 后 lo-1 和 lo 重复, 但 lo-2,
            # lo-1, lo 不重复
            #
            # 实际上 nums[lo - 1] != x or nums[lo - 2] != x 可以简化为 nums[lo -
            # 2] != x
            #
            # 因为 nums 是非递减序列, lo-1!=x <=> lo-1!=x and lo-2!=x, 所以
            #
            # lo-1 !=x or lo-2!=x
            # <=> (lo-1!=x and lo-2!=x) or (lo-1==x and lo-2!=x)
            # <=> lo-2!=x and 1
            # <=> lo-2!=x
            if nums[lo - 1] != x or nums[lo - 2] != x:
                nums[lo] = x
                lo += 1
        return lo


if __name__ == "__main__":
    S = Solution()
    nums = [0, 0, 1, 1, 1, 1, 2, 3, 3]
    assert nums[: S.removeDuplicates(nums)] == [0, 0, 1, 1, 2, 3, 3]

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        power = 4
        k = 10
        mul = power ** (k - 1)

        ans = set()
        hashes = set()
        currHash = 0
        lo = 0

        value = {"A": 1, "T": 2, "C": 3, "G": 4}
        for hi in range(len(s)):
            currHash = currHash * power + value[s[hi]]
            if hi - lo + 1 == k:
                if currHash in hashes:
                    ans.add(s[lo : hi + 1])
                hashes.add(currHash)
                currHash -= value[s[lo]] * mul
                lo += 1
        return list(ans)