性感100题

from itertools import permutations
return list(permutations(nums))

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

@cache
def dfs(i, j):
    if i == 0:
        return inf if j else 0
    if j < i * i:
        return dfs(i-1, j)
    return min(dfs(i-1, j), dfs(i, j-i*i) + 1)

@cache
def dfs(i):
    if i == 0:
        return 0
    cur_min = inf
    for n in range(1, isqrt(i)+1):
        cur_min = min(cur_min, dfs(i - n ** 2) + 1)
    return cur_min

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums=[[j, i] for i,j in enumerate(nums)]
        nums=sorted(nums)
        print(nums)
        ln=len(nums)
        l, r = 0, ln-1
        while l < r:
            if nums[l][0]+nums[r][0] > target:
                r -=1
            elif nums[l][0]+nums[r][0]<target:
                l+=1
            else:
                return [nums[l][1],nums[r][1]]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = []
        d = dict()
        ld = 0
        for i in strs: # 注意str sorted是对字符进行排序，还需要试用一下join
            si = "".join(sorted(i))
            if d.get(si, None) is None:
                d[si] = ld
                res.append([])
                res[ld].append(i)
                ld += 1
            else:
                nd = d[si]
                res[nd].append(i)
        return res

#相对来说最完美的
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
            
        num_set = set(nums)  # 转换为集合，去重
        max_length = 0
        
        for num in num_set:
            # 只有当 num-1 不存在时，才开始计算序列
            # 这确保了每个序列只被计算一次
            if num - 1 not in num_set:
                current_num = num
                current_length = 1
                
                # 向后查找连续序列
                while current_num + 1 in num_set:
                    current_num += 1
                    current_length += 1
                    
                max_length = max(max_length, current_length)
        
        return max_length
                    

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        d = set(nums)
        max_len = 0
        while d:
            # print(d)
            nc = d.pop()
            cur_len = 1
            # forward
            for i in range(1, 100_000):
                if nc + i not in d:
                    break
                else:
                    cur_len += 1
                    d.remove(nc+i)
            # backward
            for i in range(1, 100_000):
                if nc - i not in d:
                    break
                else:
                    cur_len += 1
                    d.remove(nc-i)
            max_len = max(max_len, cur_len)
        return max_len  
                    

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        left = right = 0
        while right < n:
            if nums[right] != 0:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
            right += 1

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

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        res = []
        len_n = len(nums)
        for mid in range(len_n-2):
            # 第一步去重
            if mid > 0 and nums[mid] == nums[mid-1]:
                continue
            l , r = mid + 1, len_n - 1
            mid_v = nums[mid]
            while l < r:
                if nums[l] + nums[r] >  - mid_v:
                    r -= 1
                elif nums[l] + nums[r] <  - mid_v:
                    l += 1
                else:
                    res.append([nums[l], mid_v, nums[r]])
                    # 跳过重复的左值
                    while l < r and nums[l] == nums[l+1]:
                        l += 1
                    # 跳过重复的右值
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    r -= 1
                    l += 1
        return res

class Solution:
    def trap(self, height: List[int]) -> int:
        ln = len(height)
        water = []
        c_max = height[0]
        res = 0
        for i in range(ln):
            if height[i] > c_max:
                c_max = height[i]
                water.append(0)
            elif height[i] == c_max:
                water.append(0)
            else:
                water.append(c_max-height[i])
        a_water = []
        height = height[::-1]
        c_max = height[0]
        for i in range(ln):
            if height[i] > c_max:
                c_max = height[i]
                a_water.append(0)
            elif height[i] == c_max:
                a_water.append(0)
            else:
                a_water.append(c_max-height[i])
        for i, j in zip(water, a_water[::-1]):
            res += min(i, j)
        return res
# 还有一个极端版本
class Solution:
    def trap(self, height: List[int]) -> int:
        return 0 if len(set(height)) == 1 else sum([min(max(height[:i+1]), max(height[i:])) - height[i] for i in range(len(height))]) 

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0:
            return 0
        l, r = 0, 0
        hasht = set()
        ls = len(s)
        ml = 1
        while r < ls:
            if s[r] not in hasht:
                hasht.add(s[r])
                r += 1
            else:
                ml = max(ml , r - l)
                hasht -= set(s[l])
                l += 1
        return max(ml, r-l)

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        sp = "".join(sorted(p))
        lsp, ls = len(sp), len(s)
        res = []
        for i in range(ls - lsp + 1):
            if "".join(sorted(s[i:i+lsp])) == sp:
                res.append(i)
        return res

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ans = []
        cnt = Counter(p)  # 统计 p 的每种字母的出现次数
        left = 0
        for right, c in enumerate(s):
            cnt[c] -= 1  # 右端点字母进入窗口
            while cnt[c] < 0:  # 字母 c 太多了
                cnt[s[left]] += 1  # 左端点字母离开窗口
                left += 1
            if right - left + 1 == len(p):  # s' 和 p 的每种字母的出现次数都相同
                ans.append(left)  # s' 左端点下标加入答案
        return ans

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        ln = len(nums)
        sum_n = [0] + [sum(nums[:i]) for i in range(1, ln+1)]
        lsum_n = len(sum_n)
        res = 0
        for i in range(lsum_n-1):
            for j in range(i+1, lsum_n):
                if sum_n[j] - sum_n[i] == k:
                    res += 1
        return res

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        ln = len(nums)
        sum_n = [0] * (len(nums) + 1)
        for i, x in enumerate(nums):
            sum_n[i + 1] = sum_n[i] + x
        res_d = defaultdict(int)
        ans = 0
        for i in sum_n:
            ans += res_d[i - k]
            res_d[i] += 1
        return ans

for i in sum_n:
    ans += res_d[i - k]
    res_d[i] += 1

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if len(nums) <= 1 or k == 1:
            return nums
        r = k
        res = []
        cmax = max(nums[:r])
        while r < len(nums):
            res.append(cmax)
            if nums[r] > cmax:
                cmax = nums[r]
            r += 1
            if nums[r-k-1] == cmax:
                cmax = max(nums[r-k:r])
        res.append(cmax)
        return res

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans = []
        q = deque()  # 双端队列
        for i, x in enumerate(nums):
            # 1. 入
            while q and nums[q[-1]] <= x:
                q.pop()  # 维护 q 的单调性
            q.append(i)  # 入队
            # 2. 出
            if i - q[0] >= k:  # 队首已经离开窗口了
                q.popleft()
            # 3. 记录答案
            if i >= k - 1:
                # 由于队首到队尾单调递减，所以窗口最大值就是队首
                ans.append(nums[q[0]])
        return ans
## 双端队列

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        # 注意 Python 默认的优先队列是小根堆
        q = [(-nums[i], i) for i in range(k)]
        heapq.heapify(q)

        ans = [-q[0][0]]
        for i in range(k, n):
            heapq.heappush(q, (-nums[i], i))
            while q[0][1] <= i - k:
                heapq.heappop(q)
            ans.append(-q[0][0])
        
        return ans
## 最大堆

class Counter():
    ...
    def __le__(self, other):
        'True if all counts in self are a subset of those in other.'
        if not isinstance(other, Counter):
            return NotImplemented
        return all(self[e] <= other[e] for c in (self, other) for e in c)

cnt_s = Counter()
cnt_t = Counter(t)
...
if cnt_s < cnt_t:
    ...

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        ans_left, ans_right = -1, len(s)
        cnt_s = Counter()  # s 子串字母的出现次数
        cnt_t = Counter(t)  # t 中字母的出现次数

        left = 0
        for right, c in enumerate(s):  # 移动子串右端点
            cnt_s[c] += 1  # 右端点字母移入子串
            while cnt_s >= cnt_t:  # 涵盖
                if right - left < ans_right - ans_left:  # 找到更短的子串
                    ans_left, ans_right = left, right  # 记录此时的左右端点
                cnt_s[s[left]] -= 1  # 左端点字母移出子串
                left += 1
        return "" if ans_left < 0 else s[ans_left: ans_right + 1]

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        c_max = -inf
        ln = len(nums)
        res = [-inf for i in range(ln+1)]
        for i in range(1, ln+1):
            res[i] = max(res[i-1]+nums[i-1], nums[i-1])
            c_max = max(res[i], c_max)
        # print(res)
        return c_max

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        ci = intervals.pop(0)
        res = []
        while intervals:
            new = intervals.pop(0)
            if new[0] <= ci[1]:
                if new[1] > ci[1]:
                    ci[1] = new[1]
            else:
                res.append(ci)
                ci = new
        res.append(ci)
        return res

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        nums[:] = nums[-k % n:] + nums[:-k % n]

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n
        nums[:n-k] = nums[:n-k][::-1]
        nums[n-k:] = nums[n-k:][::-1]
        nums[:] = nums[::-1]

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        pre = [1] * n
        post = [1] * n
        for i in range(1, n):
            pre[i] = nums[i-1] * pre[i-1]
        for i in range(n-2, -1, -1):
            post[i] = post[i+1] * nums[i+1]
        return [p*s for p,s in zip(pre, post)] 

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        suf = [1] * n
        for i in range(n - 2, -1, -1):
            suf[i] = suf[i + 1] * nums[i + 1]

        pre = 1
        for i, x in enumerate(nums):
            # 此时 pre 为 nums[0] 到 nums[i-1] 的乘积，直接乘到 suf[i] 中
            suf[i] *= pre
            pre *= x

        return suf

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        maxn = max(nums) + 1
        space_min = inf
        not1 = 1
        for i in nums:
            if i <= 0 :
                continue
            elif i == not1:
                not1 += 1 # 已经很接近了
            else :
                if (i - 1) < space_min and (i - 1) != not1:
                    space_min = i - 1
                else:
                    maxn = i + 1
        return min(space_min, maxn, not1)
                  

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        l_row, l_col = len(matrix), len(matrix[0])
        sign_row, sign_col = None, None
        for i in range(l_row):
            for j in range(l_col):
                if sign_row is None and matrix[i][j] == 0:
                    sign_row, sign_col = i, j
                    matrix[sign_row][sign_col] = None
        if sign_row is None:
            return
        for i in range(l_row):
            if i == sign_row:
                continue
            if 0 in matrix[i]:
                matrix[i][sign_col] = None
        for i in range(l_col):
            if i == sign_col:
                continue
            for j in range(l_row):
                if matrix[j][i] == 0:
                    matrix[sign_row][i] = None
                    break
        print(matrix)
        for i in range(l_row):
            if matrix[i][sign_col] is None:
                for j in range(l_col):
                    if matrix[i][j] is None:
                        continue
                    else:
                        matrix[i][j] = 0
        for i in range(l_col):
            if matrix[sign_row][i] is None:
                for j in range(l_row):
                    if matrix[j][i] is None:
                        continue
                    else:
                        matrix[j][i] = 0
        for i in range(l_row):
            for j in range(l_col):
                if matrix[i][j] is None:
                    matrix[i][j] = 0

                

        

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:
            return []
        m, n = len(matrix), len(matrix[0])
        res = []
        
        def spiral_layer(sx, sy, rows, cols):
            if rows <= 0 or cols <= 0:
                return
            # 上：从左到右
            for i in range(sx, sx + cols):
                res.append(matrix[sy][i])
            # 右：从上到下（至少两行）
            if rows > 1:
                for j in range(sy + 1, sy + rows):
                    res.append(matrix[j][sx + cols - 1])
                # 下：从右到左（至少两列）
                if cols > 1:
                    for i in range(sx + cols - 2, sx - 1, -1):
                        res.append(matrix[sy + rows - 1][i])
                    # 左：从下到上（至少三行）
                    if rows > 2:
                        for j in range(sy + rows - 2, sy, -1):
                            res.append(matrix[j][sx])
            # 递归处理内层
            spiral_layer(sx + 1, sy + 1, rows - 2, cols - 2)
        
        spiral_layer(0, 0, m, n)
        return res

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None: 
        n = len(matrix)
        mr = int(n//2)
        for r in range(mr):
            for c in range(n):
                matrix[r][c], matrix[n-r-1][c] =  matrix[n-r-1][c], matrix[r][c]
        for i in range(n):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        return matrix

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        l_row, l_cow = len(matrix), len(matrix[0])
        for i in range(l_row):
            for j in range(l_cow):
                if matrix[i][j] == target:
                    return True
        return False

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

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

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        len_a, len_b = 0, 0
        cur_node = headA
        while cur_node:
            len_a += 1
            cur_node = cur_node.next
        cur_node = headB
        while cur_node:
            len_b += 1
            cur_node = cur_node.next
        longer = headA if len_a > len_b else headB
        shorter = headB if len_a > len_b else headA
        for i in range(abs(len_a-len_b)):
            longer = longer.next
        while longer or shorter:
            if id(longer) == id(shorter):
                return longer
            longer = longer.next
            shorter = shorter.next
        return None

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        curr = head
        prev = None
        while curr != None:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        return prev

class Solution:
    # 876. 链表的中间结点
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    # 206. 反转链表
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur = None, head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        mid = self.middleNode(head)
        head2 = self.reverseList(mid)
        while head2:
            if head.val != head2.val:  # 不是回文链表
                return False
            head = head.next
            head2 = head2.next
        return True

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head  # 乌龟和兔子同时从起点出发
        while fast and fast.next:
            slow = slow.next  # 乌龟走一步
            fast = fast.next.next  # 兔子走两步
            if fast is slow:  # 兔子追上乌龟（套圈），说明有环
                return True
        return False  # 访问到了链表末尾，无环

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast is slow:
                while slow is not head:
                    slow = slow.next
                    head = head.next
                return slow
        return None

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode()  # 用哨兵节点简化代码逻辑
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1  # 把 list1 加到新链表中
                list1 = list1.next
            else:  # 注：相等的情况加哪个节点都是可以的
                cur.next = list2  # 把 list2 加到新链表中
                list2 = list2.next
            cur = cur.next
        cur.next = list1 or list2  # 拼接剩余链表
        return dummy.next

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        l1v, l2v = "", ""
        while l1:
            l1v += str(l1.val)
            l1 = l1.next
        while l2:
            l2v += str(l2.val)
            l2 = l2.next
        
        dummy = ListNode(None)
        curr = dummy
        for i in str(eval(l1v[::-1] + "+" + l2v[::-1]))[::-1]:
            newn = ListNode(int(i))
            curr.next = newn
            curr = curr.next
        curr.next = None
        return dummy.next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # 由于可能会删除链表头部，用哨兵节点简化代码
        left = right = dummy = ListNode(next=head)
        for _ in range(n):
            right = right.next  # 右指针先向右走 n 步
        while right.next:
            left = left.next
            right = right.next  # 左右指针一起走
        left.next = left.next.next  # 左指针的下一个节点就是倒数第 n 个节点
        return dummy.next
### 另一种好写的：
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        ll = 0
        while head:
            ll += 1
            head = head.next
        head = dummy
        for i in range(ll-n):
            head = head.next
        head.next = head.next.next
        return dummy.next

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        node0 = dummy = ListNode(next=head)  # 用哨兵节点简化代码逻辑
        node1 = head
        while node1 and node1.next:  # 至少有两个节点
            node2 = node1.next
            node3 = node2.next

            node0.next = node2  # 0 -> 2
            node2.next = node1  # 2 -> 1
            node1.next = node3  # 1 -> 3

            node0 = node1  # 下一轮交换，0 是 1
            node1 = node3  # 下一轮交换，1 是 3
        return dummy.next  # 返回新链表的头节点

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        n = 0
        cur = head
        while cur:
            n += 1
            cur = cur.next

        p0 = dummy = ListNode(next=head)
        pre = None
        cur = head

        while n >= k:
            n -= k
            for _ in range(k):
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur = nxt

            nxt = p0.next
            nxt.next = cur
            p0.next = pre
            p0 = nxt
        return dummy.next

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return
    	cur = head
        dic = {}
        while cur:
            dic[cur] = Node(cur.val)
            cur = cur.next
        cur = head
        while cur:
            dic[cur].next = dic.get(cur.next)
            dic[cur].random = dic.get(cur.random)
           	cur = cur.next
        return dic[head]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head: return
        dic = []
        cur = head
        while cur:
            dic.append(cur)
            cur = cur.next
        dic = sorted(dic, key=lambda x: x.val)
        for i in range(len(dic)-1):
            dic[i].next = dic[i+1]
        dic[-1].next = None
        return dic[0]
        

class Solution:
    # 876. 链表的中间结点（快慢指针）
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            pre = slow  # 记录 slow 的前一个节点
            slow = slow.next
            fast = fast.next.next
        pre.next = None  # 断开 slow 的前一个节点和 slow 的连接
        return slow

    # 21. 合并两个有序链表（双指针）
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode()  # 用哨兵节点简化代码逻辑
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1  # 把 list1 加到新链表中
                list1 = list1.next
            else:  # 注：相等的情况加哪个节点都是可以的
                cur.next = list2  # 把 list2 加到新链表中
                list2 = list2.next
            cur = cur.next
        cur.next = list1 if list1 else list2  # 拼接剩余链表
        return dummy.next

    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 如果链表为空或者只有一个节点，无需排序
        if head is None or head.next is None:
            return head
        # 找到中间节点 head2，并断开 head2 与其前一个节点的连接
        # 比如 head=[4,2,1,3]，那么 middleNode 调用结束后 head=[4,2] head2=[1,3]
        head2 = self.middleNode(head)
        # 分治
        head = self.sortList(head)
        head2 = self.sortList(head2)
        # 合并
        return self.mergeTwoLists(head, head2)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        res = []
        for i in lists:
            cur = i
            while cur:
                res.append(cur)
                cur = cur.next
        res = sorted(res, key=lambda x:x.val)
        for i in range(len(res)-1):
            res[i].next = res[i+1]
        if len(res) == 0:
            return 
        res[-1].next = None
        return res[0]
        

class Node:
    # 提高访问属性的速度，并节省内存
    __slots__ = 'prev', 'next', 'key', 'value'

    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.dummy = Node()  # 哨兵节点
        self.dummy.prev = self.dummy
        self.dummy.next = self.dummy
        self.key_to_node = {}

    # 获取 key 对应的节点，同时把该节点移到链表头部
    def get_node(self, key: int) -> Optional[Node]:
        if key not in self.key_to_node:  # 没有这本书
            return None
        node = self.key_to_node[key]  # 有这本书
        self.remove(node)  # 把这本书抽出来
        self.push_front(node)  # 放到最上面
        return node

    def get(self, key: int) -> int:
        node = self.get_node(key)  # get_node 会把对应节点移到链表头部
        return node.value if node else -1

    def put(self, key: int, value: int) -> None:
        node = self.get_node(key)  # get_node 会把对应节点移到链表头部
        if node:  # 有这本书
            node.value = value  # 更新 value
            return
        self.key_to_node[key] = node = Node(key, value)  # 新书
        self.push_front(node)  # 放到最上面
        if len(self.key_to_node) > self.capacity:  # 书太多了
            back_node = self.dummy.prev
            del self.key_to_node[back_node.key]
            self.remove(back_node)  # 去掉最后一本书

    # 删除一个节点（抽出一本书）
    def remove(self, x: Node) -> None:
        x.prev.next = x.next
        x.next.prev = x.prev

    # 在链表头添加一个节点（把一本书放到最上面）
    def push_front(self, x: Node) -> None:
        x.prev = self.dummy
        x.next = self.dummy.next
        x.prev.next = x
        x.next.prev = x