2024.5.23力扣刷题记录（未完）

本文主要是介绍2024.5.23力扣刷题记录（未完），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、每日一题-2831. 找出最长等值子数组

1.分组 + 滑动窗口

2.一次遍历

二、1441. 用栈操作构建数组

模拟

三、844. 比较含退格的字符串

1.栈 + 模拟

2.重构字符串

3.快慢指针

四、378. 有序矩阵中第 K 小的元素

1.堆排序

（未完待续）

五、23. 合并 K 个升序链表

1.归并排序-递归

（未完待续）

一、每日一题-2831. 找出最长等值子数组

1.分组 + 滑动窗口

来自灵神题解（. - 力扣（LeetCode））。

class Solution:def longestEqualSubarray(self, nums: List[int], k: int) -> int:# 分组 + 滑动窗口group = defaultdict(list)for i, x in enumerate(nums):# group[x].append(i)group[x].append(i - len(group[x]))ans = 0for g in group.values():if len(g) <= ans:continueleft = 0for right, v in enumerate(g):# left <= right < n# left < n# if v - g[left] - right + left > k:if v - g[left] > k:left += 1ans = max(ans, right - left + 1)return ans

2.一次遍历

来自官方题解（. - 力扣（LeetCode））。

class Solution:def longestEqualSubarray(self, nums: List[int], k: int) -> int:# 一次遍历# 寻找区间众数ans = 0cnt = collections.defaultdict(int)left = 0for right, x in enumerate(nums):cnt[x] += 1if right - left + 1 - cnt[nums[left]] > k:cnt[nums[left]] -= 1left += 1# 以右端点更新，包含了左右等和左右不等的情况# 而以左端点更新达不到这样的效果# 可以看成左端点是变化的，而右端点没变ans = max(ans, cnt[nums[right]])return ans

二、1441. 用栈操作构建数组

模拟

class Solution:def buildArray(self, target: List[int], n: int) -> List[str]:# 模拟# 遇见不一样的就push + popif target[-1] > n:return []ans = []num = 1for x in target:while num < x:ans.extend(["Push", "Pop"])num += 1ans.append("Push")num += 1return ans

三、844. 比较含退格的字符串

1.栈 + 模拟

class Solution:def backspaceCompare(self, s: str, t: str) -> bool:# 栈 + 模拟n1, n2 = len(s), len(t)st1, st2 = [0] * n1, [0] * n2top1, top2 = 0, 0for c in s:if c == '#':top1 = max(0, top1 - 1)else:st1[top1] = ctop1 += 1for c in t:if c == '#':top2 = max(0, top2 - 1)else:st2[top2] = ctop2 += 1if top1 != top2:return Falsefor i in range(top1):if st1[i] != st2[i]:return Falsereturn True

2.重构字符串

来自官方题解（. - 力扣（LeetCode））。但是有点慢。

class Solution:def backspaceCompare(self, s: str, t: str) -> bool:# 重构字符串def bulid(s: str) -> str:st = []for c in s:if c != '#':st.append(c)elif st:st.pop()return "".join(st)return bulid(s) == bulid(t)

3.快慢指针

来自题解（. - 力扣（LeetCode））。很妙！

class Solution:def backspaceCompare(self, s: str, t: str) -> bool:# 快慢指针# 优化速度和存储空间# 从后向前遍历i, j = len(s) - 1, len(t) - 1skipS, skipT = 0, 0while i >= 0 or j >= 0:# 外循环，判断对应位置是否相等while i >= 0:# 内循环，跳过特殊情况if s[i] == '#':skipS += 1i -= 1elif skipS > 0:skipS -= 1i -= 1else:breakwhile j >= 0:if t[j] == '#':skipT += 1j -= 1elif skipT > 0:skipT -= 1j -= 1else:break# 判断if i >= 0 and j >= 0:if s[i] != t[j]:return Falseelif i >= 0 or j >= 0:return Falsei -= 1j -= 1return True

四、378. 有序矩阵中第 K 小的元素

1.堆排序

class Solution:def kthSmallest(self, matrix: List[List[int]], k: int) -> int:# 堆排序# 时复O(n*n)（或O(n*n + klogn)）, 空复O(n*n)q = [x for row in matrix for x in row]heapq.heapify(q)for _ in range(k - 1):heapq.heappop(q)return q[0]

（未完待续）

五、23. 合并 K 个升序链表

1.归并排序-递归

# 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]:# 归并排序-递归n = len(lists)if n == 0:return Noneif n == 1:# 边界条件return lists[0]left = self.mergeKLists(lists[:n // 2])     # 递归right = self.mergeKLists(lists[n // 2:])head = ListNode()   # 返回链表lose = ListNode()   # 指向链表头，方便返回lose.next = headwhile left and right:if left.val > right.val:head.next = rightright = right.nextelse:head.next = leftleft = left.next# 挪动指针head = head.next# 剩下部分if left:head.next = leftelse:head.next = right# lose -> head -> 表return lose.next.next