class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1

        l, r = 0, len(nums) - 1

        while l <= r:
            mid = (r - l)//2 + l

            if nums[mid] < target:
                l = mid + 1
            elif nums[mid] > target:
                r = mid - 1
            else:
                return mid
        
        return -1

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:

        if not nums:
            return [-1, -1]

        def binSearch(nums, t, flag):
            l, r = 0, len(nums) - 1
            while l <= r:
                mid = (l + r) // 2
                if nums[mid] > t:
                    r = mid - 1
                elif nums[mid] < t:
                    l = mid + 1
                else:
                    if flag == "L":
                        r = mid - 1
                    else:
                        l = mid + 1

            if flag == 'L' and r + 1 < len(nums) and nums[r + 1] == t:
                return r + 1
            if flag == 'R' and l - 1 >= 0 and nums[l - 1] == t:
                return l - 1
            return -1

        return [binSearch(nums=nums, t=target, flag='L'), binSearch(nums=nums, t=target, flag='R')]

from typing import List

class Solution:
    def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
        """
        Do not return anything, modify A in-place instead.
        """
        pa, pb = m - 1, n - 1
        tail = m + n - 1
        
        while pa >= 0 or pb >= 0:
            if pa == -1:
                A[tail] = B[pb]
                pb -= 1
            elif pb == -1:
                A[tail] = A[pa]
                pa -= 1
            elif A[pa] > B[pb]:
                A[tail] = A[pa]
                pa -= 1
            else:
                A[tail] = B[pb]
                pb -= 1
            tail -= 1

        return A[:]  # 如果需要返回数组副本，则添加这一行

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()
        
        # 枚举 a
        for first in range(n):
            # 需要和上一次枚举的数不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # c 对应的指针初始指向数组的最右端
            third = n - 1
            target = -nums[first]
            # 枚举 b
            for second in range(first + 1, n):
                # 需要和上一次枚举的数不相同
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                # 需要保证 b 的指针在 c 的指针的左侧
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                # 如果指针重合，随着 b 后续的增加
                # 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if second == third:
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        
        return ans

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        area = 0
        while l < r:
            area = max(area, min(height[l], height[r]) * (r-l))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return area

class Solution:
    def decodeString(self, s: str) -> str:
        stack, res, multi = [], "", 0
        for c in s:
            if c == '[':
                stack.append([multi, res])
                res, multi = "", 0
            elif c == ']':
                cur_multi, last_res = stack.pop()
                res = last_res + cur_multi * res
            elif '0' <= c <= '9':
                multi = multi * 10 + int(c)            
            else:
                res += c
        return res

from heapq import heapify, heappush, heappop 
# python中的heap是小根堆:  heapify(hp) , heappop(hp), heappush(hp, v) 
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums)
        if k == 0 or k > n:
            return []
        
        hp = nums[:k]

        heapify(hp)

        for i in range(k, n):
            v = nums[i]
            if v > hp[0]:
                heappop(hp)
                heappush(hp, v)

        return hp[0]

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = {}
        dp[1] = 1
        dp[2] = 2
        for i in range(3,n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

# 定义链表节点类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        if head is None:
            return []
        else:
            return self.reversePrint(head.next) + [head.val]

# 示例用法
# 创建链表 1 -> 3 -> 2
head = ListNode(1)
head.next = ListNode(3)
head.next.next = ListNode(2)

# 创建 Solution 对象并调用 reversePrint 方法
solution = Solution()
result = solution.reversePrint(head)

# 打印结果
print(result)  # 输出 [2, 3, 1]

# 输入: 1->2->3->4->5->NULL
# 输出: 5->4->3->2->1->NULL

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


class Solution(object):
    def reverseList(self, head) -> ListNode:
        if not head or not head.next:
            return head
        
        pre, cur = head, head.next
        pre.next = None

        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp

        return pre

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        
        if l1.val < l2.val:
            p = ListNode(l1.val)
            p.next = self.mergeTwoLists(l1.next, l2)
        else:
            p = ListNode(l2.val)
            p.next = self.mergeTwoLists(l1, l2.next)
        
        return p
        

# 创建一个环：将链表的尾节点指向头节点，形成一个环。
# 找到断开点：从头节点开始，走 𝑛 − 𝑘 % 𝑛 步，然后在这个点断开环。
# 形成新的链表：新的链表从断开点开始，前半部分接在断开点后面

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

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or not head.next or k == 0:
            return head
        
        # 计算链表长度，并找到尾节点
        length = 1
        tail = head
        while tail.next:
            tail = tail.next
            length += 1
        
        # 将尾节点连接到头节点，形成环
        tail.next = head
        
        # 找到新的尾节点位置 (length - k % length - 1)
        new_tail_pos = length - k % length - 1
        new_tail = head
        for _ in range(new_tail_pos):
            new_tail = new_tail.next
        
        # 新的头节点是新的尾节点的下一个节点
        new_head = new_tail.next
        
        # 断开环
        new_tail.next = None
        
        return new_head

# 示例用法
# 创建链表 1 -> 2 -> 3 -> 4 -> 5 -> 6
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
head.next.next.next.next.next = ListNode(6)

# 创建 Solution 对象并调用 rotateRight 方法
solution = Solution()
k = 3
new_head = solution.rotateRight(head, k)

# 打印结果
current = new_head
while current:
    print(current.val, end=" -> " if current.next else " -> NULL")
    current = current.next

from collections import deque
class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        q = deque()
        q.append((0,0))
        s = set()
        s.add((0,0))
        while q:
            x, y = q.popleft()
            for (i, j) in [(x+1, y), (x, y+1)]:
                if valid(i, j, k, s, m, n):
                    q.append((i, j))
                    s.add((i, j))
        return len(s)

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def maxHigh(root):
            if root == None:
                return 0
            return max(maxHigh(root.left), maxHigh(root.right)) + 1

        if root == None:
            return True
        return abs(maxHigh(root.left) - maxHigh(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)