三个月算法进阶--day88

class Solution:
    def majorityElement(self, nums):
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        return candidate

class Solution(object):
	def reverseList(self, head):
		"""
		:type head: ListNode
		:rtype: ListNode
		"""
		if not head or not head.next:
			return head
		cur = self.reverseList(head.next)
		head.next.next = head
		head.next = None
		return cur

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        prev = None
        ptr = head
        while ptr:
            temp = ptr.next
            ptr.next = prev
            prev = ptr
            ptr = temp
        return prev

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        import heapq
        nums = [-num for num in nums]
        heapq.heapify(nums)
        for _ in range(k):
            res = heapq.heappop(nums)
        return -res

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        from queue import PriorityQueue as PQ
        pq = PQ()
        for i, t in enumerate(nums):
            if i < k:
                pq.put(t)
                continue
            pq.put(t)
            pq.get()
        return pq.get()

def heap_adjust(L, start, end):
    temp = L[start]
 
    i = start
    j = 2 * i
    while j <= end:
        if j < end and L[j] < L[j + 1]:
            j += 1
        if temp < L[j]:
            L[i] = L[j]
            i = j
            j = 2 * i
        else:
            break
    L[i] = temp

L = collections.deque([50, 15, 7, 80, 2])
L.appendleft(0)
L_length = len(L) - 1
first_sort_count = L_length // 2
for i in range(first_sort_count):
    heap_adjust(L, first_sort_count - i, L_length)

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        def inorder(root: TreeNode) -> List[int]:
            if root:
                yield from inorder(root.left)
                yield root.val
                yield from inorder(root.right)
        for n, val in enumerate(inorder(root)):
            if n == k - 1:
                return val

class Solution:
    def KthSmallest(self, root: TreeNode, k: int) -> int:
        stack = []
        
        while True:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if not k:
                return root.val
            root = root.right

def isPowerOfTwo(self, n):
    return n != 0 and n & (-n) == n

def isPowerOfTwo(self, n):
    return n != 0 and not n & (n - 1)

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q: 
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right: 
            return root
        if left:
            return left
        else:
            return right

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        self.preorder = preorder
        self.tmp = {inorder[i]: i for i in range(len(inorder)) }
        return self.recur(0, 0, len(inorder) - 1)
    
    def recur(self, preroot, left, right):
        if left > right:
            return
        index = self.tmp[self.preorder[preroot]]
        root = TreeNode(self.preorder[preroot])
        root.left = self.recur(preroot + 1, left, index - 1)
        root.right = self.recur(preroot + index - left + 1, index + 1, right)
        return root

INT_MAX = 2 ** 31 - 1
INT_MIN = -2 ** 31

class Automaton:
    def __init__(self):
        self.state = 'start'
        self.sign = 1
        self.ans = 0
        self.table = {
            'start': ['start', 'signed', 'in_number', 'end'],
            'signed': ['end', 'end', 'in_number', 'end'],
            'in_number': ['end', 'end', 'in_number', 'end'],
            'end': ['end', 'end', 'end', 'end'],
        }
        
    def get_col(self, c):
        if c.isspace():
            return 0
        if c == '+' or c == '-':
            return 1
        if c.isdigit():
            return 2
        return 3

    def get(self, c):
        self.state = self.table[self.state][self.get_col(c)]
        if self.state == 'in_number':
            self.ans = self.ans * 10 + int(c)
            self.ans = min(self.ans, INT_MAX) if self.sign == 1 else min(self.ans, -INT_MIN)
        elif self.state == 'signed':
            self.sign = 1 if c == '+' else -1

class Solution:
    def myAtoi(self, str: str) -> int:
        automaton = Automaton()
        for c in str:
            automaton.get(c)
        return automaton.sign * automaton.ans

class Solution:
    def fib(self, n: int) -> int:
        a, b = 1, 1
        for _ in range(n):
            a, b = b, a + b
        return a

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        left, right = 0, len(numbers) - 1
        while left < right:
            pivot = left + (right - left) // 2
            if numbers[pivot] < numbers[right]:
                right = pivot
            elif numbers[pivot] > numbers[right]:
                left = pivot + 1
            else:
                right -= 1
        return numbers[left]

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(m, n, k):
            if m >= len(board) or m < 0 or n < 0 or n >= len(board[0]) or board[m][n] != word[k]:
                return False
            if k == len(word) -1:
                return True
            tmp, board[m][n] = board[m][n], "#"
            res = dfs(m+1, n, k+1) or dfs(m, n+1, k+1) or dfs(m-1, n, k+1) or dfs(m, n-1, k+1)
            board[m][n] = tmp
            return res
        
        for i in range(len(board)):
            for t in range(len(board[0])):
                if dfs(i, t, 0):
                    return True
        return False