LeetCode

刷题网站：

LeetCode大神_灵茶山艾府

LeetCode_Hot100

python常用数据结构：

"""
Python 常用数据结构（对应 C++ STL）及基本操作
================================================
C++              Python
-------------------------
vector           list
stack            list
queue            collections.deque
unordered_map    dict
unordered_set    set
"""
# ==========================================================
# 1. 数组 / 动态数组
# C++: vector
# Python: list
# ==========================================================
arr = [1, 2, 3]        # 创建数组
# 插入元素
arr.append(4)          # 尾部插入 O(1)
# 在指定位置插入
arr.insert(1, 10)      # index=1 插入 10  -> O(n)
# 删除尾部
arr.pop()              # 删除最后一个元素 O(1)
# 删除指定位置
arr.pop(1)             # 删除 index=1
# 修改元素
arr[0] = 100
# 查找元素
print(arr[1])
# 遍历数组
for x in arr:
    print(x)
# ==========================================================
# 2. 栈 (Stack)
# C++: stack
# Python: list
# ==========================================================
stack = []
# 入栈 push
stack.append(1)
stack.append(2)
stack.append(3)
# 查看栈顶
print(stack[-1])
stack.top()
# 出栈 pop
stack.pop()
# 判断是否为空
if not stack:
    print("stack empty")
# ==========================================================
# 3. 队列 (Queue)
# C++: queue
# Python: collections.deque
# ==========================================================
from collections import deque
q = deque()
# 入队
q.append(1)
q.append(2)
q.append(3)
# 出队
q.popleft()
# 查看队首
print(q[0])
# 查看队尾
print(q[-1])
# BFS常用
while q:
    node = q.popleft()
# ==========================================================
# 4. 哈希表 / 字典
# C++: unordered_map
# Python: dict
# ==========================================================
mp = {}
# 插入
mp["a"] = 1
mp["b"] = 2
# 修改
mp["a"] = 100
# 查询
print(mp["a"])
# 判断key存在
if "a" in mp:
    print("exist")
# 删除
del mp["a"]
# 遍历key
for k in mp:
    print(k)
# 遍历key-value
for k, v in mp.items():
    print(k, v)
# ==========================================================
# 5. 集合
# C++: unordered_set
# Python: set
# ==========================================================
s = set()
# 插入
s.add(1)
s.add(2)
s.add(3)
# 删除
s.remove(2)
# 删除（如果不存在不会报错）
s.discard(10)
# 查询
if 1 in s:
    print("exist")
# 遍历
for x in s:
    print(x)
# ==========================================================
# 6. 初始化技巧（刷题常用）
# ==========================================================
# 初始化数组
arr = [0] * 10
# 初始化二维数组
grid = [[0]*5 for _ in range(5)]
# 初始化dict
mp = {"a": 1, "b": 2}
# 初始化set
s = {1,2,3}
# 初始化队列
q = deque([1,2,3])
# ==========================================================
# 7. 常见复杂度总结
# ==========================================================
"""
list
----
append      O(1)
pop()       O(1)
insert      O(n)
访问        O(1)

stack
-----
push        O(1)
pop         O(1)

deque
-----
append      O(1)
popleft     O(1)

dict
----
insert      O(1)
find        O(1)
delete      O(1)

set
---
insert      O(1)
find        O(1)
delete      O(1)
"""

DAY 1

• 1.两数之和 O(n^2):

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i,num1 in enumerate(nums):
            if target-num1 in nums[i+1:]:
                j=nums[i+1:].index(target-num1)+1+i
                return [i,j]

哈希表O(n):

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        seen={}
        for i,num1 in enumerate(nums):
            num2=target-num1
            if num2 in seen :
                return [seen[num2],i]
            seen[num1]=i

O(nlogn):

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> s;  // key = num, value = index
        for(int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            if(s.find(complement) != s.end()) {
                return {s[complement], i};
            }
            s[nums[i]] = i;
        }
        return {};
    }
};

O(n):

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> s;
        for(int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            if(s.find(complement) != s.end()) {
                return {s[complement], i};
            }
            s[nums[i]] = i;
        }
        return {};
    }
};

• 2.两数相加(基于链表的倒序存储) 思路分别计算两个数的大小，然后相加，最后用链表存储：
  点击展开

  # Definition for singly-linked list.
  # class ListNode:
  #     def __init__(self, val=0, next=None):
  #         self.val = val
  #         self.next = next
  class Solution:
      def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
          length1 = 0
          num1 = 0
          while l1:
              num1 += l1.val * (10 ** length1)
              length1 += 1
              l1 = l1.next
          length2 = 0
          num2 = 0
          while l2:
              num2 += l2.val * (10 ** length2)
              length2 += 1
              l2 = l2.next
          num3 = num1 + num2
          result = ListNode(0)
          cur = result
          if num3 == 0:
              return ListNode(0)
          while num3 >= 1:
              cur.next = ListNode(num3 % 10)
              cur = cur.next
              num3 //= 10  
          return result.next
  

  上述存在的问题在于，直接两数相加会存在溢出风险，可以采用逐位相加的思路：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        cur = dummy
        carry = 0
        while l1 or l2 or carry:
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0
            s = v1 + v2 + carry
            cur.next = ListNode(s % 10)
            carry = s // 10
            cur = cur.next
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
        return dummy.next

• 链表的快速建立和初始化：

nums = [1,2,3,4]
dummy = ListNode(0)
cur = dummy
for n in nums:
    cur.next = ListNode(n)
    cur = cur.next
head = dummy.next

• 链表的遍历：

cur = head
while cur:
    print(cur.val)
    cur = cur.next

• 3.相交链表(哈希/双指针/链表) 双重while循环O(m*n)超时：

  点击展开

  # 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]:
          headB_head = headB
          while headA:
              while headB:
                  if headA != headB:
                      headB = headB.next
                  else:
                      return headB
              headA = headA.next
              headB = headB_head
          return None
  

  可以采用哈希，提高检索效率O(m+n)：
  点击展开

  class Solution:
      def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
          setA = set()
          while headA:
              setA.add(headA)
              headA = headA.next
          while headB:
              if headB in setA:
                  return headB
              headB = headB.next
          return None
  

  也可以采用双指针O(m+n)，关键弄懂指针怎么移动的——a+c+b=b+c+a
  点击展开

  # 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]:
          PA=headA
          PB=headB
          while PA!=PB:
              if PA:
                  PA=PA.next
              else:
                  PA=headB
              if PB:
                  PB=PB.next
              else:
                  PB=headA
          return PA
  

• 4.反转链表(递归/链表) 递归写法：

  点击展开

  # Definition for singly-linked list.
  # class ListNode:
  #     def __init__(self, val=0, next=None):
  #         self.val = val
  #         self.next = next
  class Solution:
      def digui(self, cur: Optional[ListNode], pre: Optional[ListNode]) -> Optional[ListNode]:
          # 递归终止：cur为空，返回新的头节点
          if not cur:
              return pre
          # 保存下一节点
          nxt = cur.next
          # 反转指针
          cur.next = pre
          # 递归处理下一个节点
          return self.digui(nxt, cur)
      def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
          return self.digui(head, None)
  

  迭代写法：
  点击展开

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

• 5.回文链表(双指针/链表) 双指针O(n)：

  点击展开

  # Definition for singly-linked list.
  # class ListNode:
  #     def __init__(self, val=0, next=None):
  #         self.val = val
  #         self.next = next
  class Solution:
      def isPalindrome(self, head: Optional[ListNode]) -> bool:
          cur = head
          arr = []
          # 将链表存入数组
          while cur:
              arr.append(cur.val)
              cur = cur.next
          left = 0
          right = len(arr) - 1
          # 双指针判断回文
          while left < right:
              if arr[left] != arr[right]:
                  return False
              left += 1
              right -= 1
          return True
  

DAY 2 (滑动窗口专题——定长滑动窗口)

定长滑动窗口模板

for right in range(len(nums)):
    # 1 进入窗口
    add(nums[right])
    # 2 窗口超过k
    if right >= k:
        remove(nums[right-k])
    # 3 窗口大小=k时更新答案
    if right >= k-1:
        update()

• 1456. 定长子串中元音的最大数目
• 643. 子数组最大平均数 I
• 1343. 大小为 K 且平均值大于等于阈值的子数组数目
• 2090. 半径为 k 的子数组平均值
• 2379. 得到 K 个黑块的最少涂色次数
• 2841. 几乎唯一子数组的最大和(结合哈希表)
  点击展开

  from collections import defaultdict
  class Solution(object):
      def maxSum(self, nums, m, k):
          """
          :type nums: List[int]
          :type m: int
          :type k: int
          :rtype: int
          题意：
          找到长度为 k 的子数组，使得其中不同元素个数 >= m，
          并返回该子数组的最大和。
          """
          # 记录窗口中每个元素出现的次数
          freq = defaultdict(int)
          # 当前窗口的元素和
          window_sum = 0
          # 记录满足条件的最大和
          max_sum = 0
          for i in range(len(nums)):
              # 1. 右边界进入窗口
              freq[nums[i]] += 1
              window_sum += nums[i]
              # 2. 如果窗口超过 k，需要移除左边元素
              if i >= k:
                  left_value = nums[i - k]
                  window_sum -= left_value
                  freq[left_value] -= 1
                  # 如果该元素数量变为0，删除该key
                  # 保证 len(freq) 表示窗口中的 distinct 数量
                  if freq[left_value] == 0:
                      del freq[left_value]
              # 3. 当窗口大小达到 k 时，判断是否满足 distinct >= m
              if i >= k - 1 and len(freq) >= m:
                  max_sum = max(max_sum, window_sum)
          return max_sum
  

  2461. 长度为 K 子数组中的最大和 1423. 可获得的最大点数 3679. 使库存平衡的最少丢弃次数(结合贪心)
  点击展开

  from collections import defaultdict
  from typing import List
  class Solution:
      def minArrivalsToDiscard(self, arrivals: List[int], w: int, m: int) -> int:
          """
          arrivals : 到达的事件序列
          w        : 滑动窗口大小
          m        : 每个值在窗口内最多允许出现的次数
          目标：
          在任何长度为 w 的窗口中，每个值最多出现 m 次。
          如果超过 m 次，就需要丢弃当前到达的元素。
          返回最少需要丢弃的数量。
          """
          # 记录当前窗口中每个值的出现次数
          freq = defaultdict(int)
          # 标记某个位置是否被丢弃
          discarded = [0] * len(arrivals)
          # 最少丢弃次数
          discard_count = 0
          for i in range(len(arrivals)):
              # 1. 当前元素进入窗口
              value = arrivals[i]
              freq[value] += 1
              # 2. 如果窗口超过 w，需要移除 i-w 位置的元素
              if i >= w:
                  left_index = i - w
                  # 只有当该元素没有被丢弃时，才需要减少频率
                  if discarded[left_index] != 1:
                      freq[arrivals[left_index]] -= 1
              # 3. 如果当前元素出现次数超过 m，需要丢弃
              if freq[value] > m:
                  # 回退刚刚加入的频率
                  freq[value] -= 1
                  # 标记当前位置为丢弃
                  discarded[i] = 1
                  # 丢弃计数 +1
                  discard_count += 1
  
          return discard_count
  

  1052. 爱生气的书店老板

DAY 3 (滑动窗口专题——不定长滑动窗口)

不定长滑动窗口模板

for right:
    add()
    while invalid:
        remove()
    update()

• 3. 无重复字符的最长子串
  点击展开

  from collections import defaultdict
  class Solution(object):
      def lengthOfLongestSubstring(self, s):
          window = defaultdict(int)
          left = 0
          res = 0
          for right in range(len(s)):
              c = s[right]
              window[c] += 1
              while window[c] > 1:
                  d = s[left]
                  window[d] -= 1
                  left += 1
              res = max(res, right - left + 1)
          return res
  

• 3090. 每个字符最多出现两次的最长子字符串
• 1493. 删掉一个元素以后全为 1 的最长子数组
• 3634. 使数组平衡的最少移除数目
• 1208. 尽可能使字符串相等
• 904. 水果成篮
• 1695. 删除子数组的最大得分
• 2958. 最多 K 个重复元素的最长子数组
• 2024. 考试的最大困扰度
• 1004. 最大连续1的个数 III