一、数据结构

2、链表题

2.1 力扣203

2.2 力扣206 反转链表

方法一、迭代1

  1. class Solution:
  2.     def reverseList(self, head: ListNode) -> ListNode:
  3.         dummy = ListNode()
  4.         dummy.next = head
  5.         while (head != None and head.next != None):
  6.             dnext = dummy.next
  7.             hnext = head.next
  9.             dummy.next, head.next, hnext.next = head.next, hnext.next, dummy.next
  10.         return dummy.next

方法二、迭代2
image.png

  1. def reverseList(self, head: ListNode) -> ListNode:
  2.     prev, curr = None, head
  3.     while curr is not None:
  4.         next = curr.next
  5.         curr.next = prev
  6.         prev = curr
  7.         curr = next
  8.     return prev

方法二、递归

  1. class Solution:
  2.     def reverseList(self, head: ListNode) -> ListNode:
  3.         if not head or not head.next:
  4.             return head
  5.         p = self.reverseList(head.next)
  6.         head.next.next = head
  7.         head.next = None
  8.         return p

3、队列

先进先出
创建队列

  1. # 创建的是双端队列
  2. from collections import *
  3. queue = deque()
  5. # 添加元素
  6. queue.append(1)
  7. queue.append(2)
  9. print(queue)
  11. # 获取即将出队的元素
  12. temp1 = queue[0]
  13. print(temp1)
  15. # 删除即将出队的元素返回删除的值
  16. temp2 = queue.popleft()
  17. print(temp2)
  19. # 判断队列是否为空
  20. len(queue) == 0
  22. # 遍历队列
  23. while len(queue) != 0:
  24.     temp = queue.popleft()
  25.     print(temp)

3.1 力扣 933 最近的请求次数

  1. class RecentCounter:
  3.     def __init__(self):
  4.         self.Q = deque()
  6.     def ping(self, t: int) -> int:
  7.         self.Q.append(t)
  8.         while (len(self.Q) > 0 and t - self.Q[0] > 3000):
  9.             self.Q.popleft()
  10.         return len(self.Q)

4、栈

  1. # 创建栈
  2. stack = []
  3. # 添加元素
  4. stack.append(1)
  5. stack.append(2)
  7. # 获取栈顶元素
  8. stack[-1]
  10. # 删除栈顶元素
  11. stack.pop()
  13. # 栈的大小 O(1)
  14. len(stack)
  16. # 栈是否为空 O(1)
  17. len(stack) == 0
  19. # 遍历栈 O(N)
  20. while len(stack) > 0:
  21.     temp = stack.pop()
  22.     print(temp)

4.1 力扣20 有效地括号

  1. class Solution:
  2.     def isValid(self, s: str) -> bool:
  3.         self.s = s
  4.         stack = []
  5.         if len(self.s) == 0:
  6.             return True
  7.         for k in self.s:
  8.             if k == '(' or k == '[' or k == '{':
  9.                 stack.append(k)
  10.             else:
  11.                 if len(stack) == 0:
  12.                     return False
  13.                 elif k == ')':
  14.                     if stack[-1] == '(':
  15.                         stack.pop()
  16.                     else:
  17.                         return False
  18.                 elif k == ']':
  19.                     if stack[-1] == '[':
  20.                         stack.pop()
  21.                     else:
  22.                         return False
  23.                 elif k == '}':
  24.                     if stack[-1] == '{':
  25.                         stack.pop()
  26.                     else:
  27.                         return False
  28.         if stack:
  29.             return False
  30.         else:
  31.             return True

4.2 力扣 496 下一个更大元素！

自己写出来的！！！

  1. class Solution:
  2.     def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
  3.         ans = []
  4.         for i in nums1:
  5.             l = nums2.index(i)
  6.             for k in nums2[l:]:
  7.                 if k > i :
  8.                     ans.append(k)
  9.                     break
  10.                 else:
  11.                     if k == nums2[-1]:
  12.                         ans.append(-1)
  13.         return ans

用栈的思想解题：

  1. class Solution:
  2.     def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
  3.         ans = []
  4.         temp = []
  6.         for l in nums1:
  7.             max1 = -1
  8.             isfound = True
  9.             while len(nums2) != 0 and isfound:
  10.                 top = nums2.pop()
  11.                 temp.append(top)
  12.                 if top > l:
  13.                     max1 = top
  14.                 else:
  15.                     if top == l:
  16.                         isfound = False
  17.             ans.append(max1)
  18.             while len(temp):
  19.                 nums2.append(temp.pop())
  20.         return ans

5、哈希表

key:value

  1. # 创建哈希表
  2. hashtable = ['']*4
  4. mappling = {}
  6. # 添加元素
  7. hashtable[1] = 'hanmeimei'
  8. hashtable[2] = 'lihua'
  10. mappling[1] = 'hanmeimei'
  11. mappling[2] = 'lihua'
  13. # 修改元素
  14. hashtable[1] = 'bishi'
  16. mappling[1] = 'bishi'
  18. # 删除元素
  19. hashtable[1] = ''
  21. mappling.pop(1)
  22. del mappling[1]
  24. # 获取元素
  25. hashtable[3]
  27. mappling[3]
  29. # 检查key是否存在
  30. 数组创建的只能遍历一遍
  32. 3 in mappling # 返回True False
  34. # 哈希表的长度
  35. len(mappling)
  36. # 哈希表是否还有元素
  37. len(mappling) == 0

5.1 217. 存在重复元素

太简单

  1. class Solution:
  2.     def containsDuplicate(self, nums: List[int]) -> bool:
  3.         len1 = len(nums)
  4.         len2 = len(set(nums))
  5.         if len1 == len2:
  6.             return False
  7.         else:
  8.             return True

5.2 389. 找不同

方法一

  1. class Solution:
  2.     def findTheDifference(self, s: str, t: str) -> str:
  3.         list1 = []
  4.         for i in t:
  5.             list1.append(i)
  6.         for l in s:
  7.             list1.remove(l)
  8.         return list1[0]

方法二

  1. class Solution:
  2.     def findTheDifference(self, s: str, t: str) -> str:
  3.         list1 = [0]*26
  4.         if len(s) == 0:
  5.             return t
  6.         for i in s:
  7.             temp = ord(i) - 97
  8.             list1[temp] -= 1
  9.         for l in t:
  10.             temp = ord(l) - 97
  11.             list1[temp] += 1
  12.         return chr(list1.index(1)+97)

6、集合

  1. # 创建集合
  2. s =set()
  4. # 添加元素 O(1)
  5. s.add(1)
  6. s.add(2)
  8. # 搜索元素 O(1)
  9. 2 in s
  11. # 删除元素 O(1)
  12. s.remove(2)
  14. # 长度
  15. len(s)

6.1 705. 设计哈希集合

  1. class MyHashSet:
  4.     def __init__(self):
  5.         self.myHashSet = [False, ] * 1000001
  7.     def add(self, key: int) -> None:
  8.         self.myHashSet[key] = True
  11.     def remove(self, key: int) -> None:
  12.         self.myHashSet[key] = False
  14.     def contains(self, key: int) -> bool:
  15.         return self.myHashSet[key]

7、树 tree

image.png
前序：根 左 右
中序：左 根 右
后序：左 右 根
image.png
用Python创建最小堆
没有直接办法创建最大堆，方法就是把所有元素转换为负数

  1. import heapq
  3. class Test:
  4.     def test(self):
  5.         # Create minheap
  6.         minheap = []
  7.         heapq.heapify(minheap)
  9.         # Add element
  10.         heapq.heappush(minheap, 10)
  11.         heapq.heappush(minheap, 8)
  12.         heapq.heappush(minheap, 9)
  13.         heapq.heappush(minheap, 2)
  14.         heapq.heappush(minheap, 1)
  15.         heapq.heappush(minheap, 11)
  17.         # [1, 2, 9, 10, 8, 11]
  18.         print(minheap)
  20.         # peek
  21.         # 1
  22.         print(minheap[0])
  24.         # Delete
  25.         heapq.heappop(minheap)
  27.         # size
  28.         len(minheap)
  30.         # Iteration
  31.         while len(minheap) != 0:
  32.             print(heapq.heappop(minheap))

7.1 前中后序遍历方法

  3. root = [1, 'null', 2, 3]
  5. # 前序遍历 根 左 右
  6. def preordertraversal(root):
  7.     stack, res = [], []
  8.     while root or stack:
  9.         while root:
  10.             res.append(root.val)
  11.             stack.append(root)
  12.             root = root.left
  14.         cur = stack.pop()
  15.         root = cur.right
  16.     return res
  19. # 中序遍历 左 根 右
  20. def inordertraversal(root):
  21.     stack, res = [], []
  22.     while root or stack:
  23.         while root:
  24.             stack.append(root)
  25.             root = root.left
  27.         root = stack.pop()
  28.         res.append(root.val)
  29.         root = root.right
  30.     return res
  32. # 后续遍历 左 右 根
  33. def postordertraversal(root):
  34.     stack, res = [], []
  35.     while root or stack:
  36.         while root:
  37.             res.append(root.val)
  38.             stack.append(root)
  39.             root = root.right
  41.         cur = stack.pop()
  42.         root = cur.left
  43.     res.reverse()   # 把 根 右 左 反转为 左 右 根
  44.     return res

7.2 692. 前K个高频单词

  1. class Solution:
  2.     def topKFrequent(self, words: List[str], k: int) -> List[str]:
  3.         dic = collections.Counter(words)
  4.         heap, ans = [], []
  5.         for i in dic:
  6.             heapq.heappush(heap, (-dic[i], i))
  7.         for _ in range(k):
  8.             ans.append(heapq.heappop(heap)[1])
  9.         return ans

8、图

  • 无向图
  • 有向图
  • 权重图

备注 2021年4月20日的副本.jpg

二、算法

1、双指针 Two Pointers

  • 普通双指针：两个指针往同一方向移动
  • 对撞双指针：两个指针面对面移动
  • 快慢双指针：慢指针 + 快指针

    1.1 141. 环形链表

    1. class Solution:
    2.   def hasCycle(self, head: Optional[ListNode]) -> bool:
    3.       index1 = head
    4.       index2 = head
    5.       if head == None:
    6.           return False
    7.       while index2 != None and index2.next != None:
    8.           index1 = index1.next
    9.           index2 = index2.next.next
    10.           if index1 == index2:
    11.               return True
    12.               break
    13.       return False

    1.2 881. 救生艇

    1. class Solution:
    2.   def numRescueBoats(self, people: List[int], limit: int) -> int:
    3.       if people == None:
    4.           return 0
    5.       people.sort()
    6.       res = 0
    7.       i = 0
    8.       j = len(people) - 1
    9.       while (i <= j):
    10.           if (people[i] + people[j] <= limit):
    11.               i += 1
    12.           j -= 1            
    13.           res += 1
    14.       return res

    2、 二分法查找

    2.1 704. 二分查找

    1. class Solution:
    2.   def search(self, nums: List[int], target: int) -> int:
    3.       if target not in nums:
    4.           return -1
    5.       else:
    6.           r = 0
    7.           l = len(nums) - 1
    8.           while r <= l:
    9.               mid = (l - r) // 2 + r
    10.               if nums[mid] < target:
    11.                   r = mid + 1   
    12.               elif nums[mid] > target:
    13.                   l = mid - 1
    14.               else:
    15.                   return mid

    2.2 35. 搜索插入位置

    1. class Solution:
    2.   def searchInsert(self, nums: List[int], target: int) -> int:
    3.       l = 0
    4.       r = len(nums) - 1
    5.       while l <= r:
    6.           mid = (r - l) // 2 + l
    7.           if nums[mid] < target:
    8.               l = mid + 1
    9.           elif nums[mid] > target:
    10.               r = mid - 1
    11.           else:
    12.               return mid
    13.       return l

    2.3 162. 寻找峰值

    方法一
    1. class Solution:
    2.   def findPeakElement(self, nums: List[int]) -> int:
    3.       if len(nums) < 2:
    4.           return 0
    5.       elif len(nums) == 2:
    6.           if nums[0] > nums[1]:
    7.               return 0
    8.           else:
    9.               return 1
    10.       l = 0
    11.       m = l + 1
    12.       r = l + 2
    13.       while (r < len(nums)):
    14.           if nums[l] < nums[m] > nums[r]:
    15.               return m
    16.           elif nums[l] > nums[m]:
    17.               return l
    18.           elif nums[r] > nums[m] and len(nums) == r + 1:
    19.               return r
    20.           else:
    21.               l += 1
    22.               m = l + 1
    23.               r = l + 2
    方法二
    1. class Solution:
    2.   def findPeakElement(self, nums: List[int]) -> int:
    3.       l = 0
    4.       r = len(nums) - 1
    5.       while l < r:
    6.           mid = (r - l) // 2 + l
    7.           if nums[mid] > nums[mid+1]:
    8.               r = mid
    9.           else:
    10.               l = mid + 1
    11.       return l

    2.4 74. 搜索二维矩阵

    遍历法
    1. class Solution:
    2.   def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    3.       k = 0
    4.       li = []
    5.       for i in matrix:
    6.           for l in i:
    7.               li.append(l)
    8.       l = 0
    9.       r = l + 1
    10.       while r < len(li):
    11.           if li[r] >= li[l]:
    12.               l += 1
    13.               r = l + 1
    14.           else:
    15.               return False
    16.       if l == len(li)-1 and target in li:
    17.           return True
    18.       else:
    19.           return False
    image.png ```python class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    1.   if len(matrix) == 0 or matrix == None:
    2.       return False
    3.   row = len(matrix)
    4.   col = len(matrix[0])
  1.     l = 0
  2.     r = row * col - 1
  3.     while l <= r:
  4.         m = (r - l) // 2 + l
  5.         element = matrix[m // col][m % col]
  6.         if element == target:
  7.             return True
  8.         elif element > target:
  9.             r = m - 1
  10.         else:
  11.             l = m + 1
  12.     return False
  1. <a name="L3v4Z"></a>
  2. ## 3、滑动窗口 Sliding Window
  3. 目的：减少while循环
  4. <a name="HZSQs"></a>
  5. ### ![image.png](https://cdn.nlark.com/yuque/0/2022/png/22488566/1643120889411-cc36b0c1-701a-45d8-a3cb-749dfd791e9a.png#clientId=ua3e90cbb-27cc-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=1522&id=ue6b2ebd7&margin=%5Bobject%20Object%5D&name=image.png&originHeight=1522&originWidth=2288&originalType=binary&ratio=1&rotation=0&showTitle=false&size=1165528&status=done&style=none&taskId=u46654fd9-aeb0-4aa1-a506-f5028d1fccb&title=&width=2288)3.1 [209. 长度最小的子数组](https://leetcode-cn.com/problems/minimum-size-subarray-sum/)
  6. ```python
  7. class Solution:
  8.     def minSubArrayLen(self, target: int, nums: List[int]) -> int:
  9.         if len(nums) == 0:
  10.             return 0
  11.         r = 0
  12.         l = 0
  13.         res = len(nums) + 1
  14.         total = 0
  15.         while l < len(nums):
  16.             total += nums[l]
  17.             l += 1
  18.             while total >= target:
  19.                 res = min(res, l - r)
  20.                 total -= nums[r]
  21.                 r += 1
  22.         if res == len(nums) + 1:
  23.             return 0
  24.         else:
  25.             return res

3.2 1456. 定长子串中元音的最大数目

  1. class Solution:
  2.     def maxVowels(self, s: str, k: int) -> int:
  3.         if len(s) == 0 or len(s) < k:
  4.             return 0
  5.         res = count = 0
  6.         yuan = ['a', 'e', 'i', 'o', 'u']
  7.         for i in range(0, k):
  8.             if s[i] in yuan:
  9.                 count += 1
  10.         res = max(res, count)
  12.         for i in range(k, len(s)):
  13.             if s[i - k] in yuan:
  14.                 count -= 1
  15.             if s[i] in yuan:
  16.                 count += 1
  17.             res = max(res, count)
  18.         return res

4、递归

递归四要素

  • 接受的参数
  • 返回值
  • 终止的条件
  • 递归的拆解：如何递归下一层
    1. def reasion():
    2.   if n == 0:
    3.       return 0
    4.   m = reasion(n-1)
    5.   return m

    4.1 509. 斐波那契数

    1. class Solution:
    2.   def fib(self, n: int) -> int:
    3.       if n < 2:
    4.           return 0 if n == 0 else 1
    5.       m = self.fib(n - 1) + self.fib(n - 2)
    6.       return m

    4.2 206.反转链表

    1. # Definition for singly-linked list.
    2. # class ListNode:
    3. #     def __init__(self, val=0, next=None):
    4. #         self.val = val
    5. #         self.next = next
    6. class Solution:
    7.   def reverseList(self, head: ListNode) -> ListNode:
    8.       if not head or not head.next:
    9.           return head
    10.       p = self.reverseList(head.next)
    11.       head.next.next = head
    12.       head.next = None
    13.       return p

    5、分治法

    image.pngimage.png