链表：

创建

  1. class Node:  # 结点类
  2.     def __init__(self, data):
  3.         self.data = data
  4.         self.next = None
  6. class SingleLinkList:  # 单链表类
  7.     def __init__(self):
  8.         self.head = None
  9.         self.tail = None
  11.     def append(self, x):  # 单链表尾部追加方法
  12.         if self.head is None:
  13.             self.head = self.tail = Node(x)
  14.         else:
  15.             self.tail.next = Node(x)
  16.             self.tail = self.tail.next
  18. test_link = SingleLinkList()
  19. for i in range(1, 8):
  20.     test_link.append(i)
  22. p = test_link.head
  23. while p is not None:
  24.     p = p.next

逆序

指针方法

  1. # -*- coding:utf-8 -*-
  2. class ListNode:
  3.     def __init__(self, x, next):
  4.         self.val = x
  5.         self.next = next
  7. class Solution:
  8.     # 返回ListNode
  9.     def ReverseList(self, pHead):
  10.         p1 = pHead
  11.         p2 = p1.next
  12.         pHead.next = None
  13.         while p2 is not None:
  14.             p3 = p2.next
  15.             p2.next = p1
  16.             p1 = p2
  17.             p2 = p3
  18.         return p1

数组中差值最少的两个数

  1. def subtract(lst):
  2.     """求输入中差值最小的两个数"""
  3.     lst.sort()                    # 排序，递增，确保下面迭代部分顺序
  4.     dd = float("inf")             # 初始一个无穷值
  5.     for i in range(len(lst) - 1):
  6.         x, y = lst[i], lst[i + 1]
  7.         if x == y:
  8.             continue
  9.         d = abs(x - y)
  10.         if d < dd:                # 条件是最少，所以dd值除无穷大，确保第一次肯定执行
  11.             xx, yy, dd = x, y, d  # 第一次执行时dd这个无穷大的值会变成(x - y)的绝对值d，相当于给dd这个条件值赋一个初始值
  12.     return xx, yy

lru_cache(Least Recently Used 缓存算法)

  1. from functools import lru_cache
  2. @lru_cache(maxsize=30)  # maxsize参数告诉lru_cache缓存最近多少个返回值
  3. def fib(n):
  4.     if n < 2:
  5.         return n
  6.     return fib(n-1) + fib(n-2)
  7. print([fib(n) for n in range(10)])
  8. fib.cache_clear()   # 清空缓存
  1. class Solution:
  2.     def LRU(self, operators, k):
  3.         # write code here
  4.         d1 = OrderedDict()
  5.         res = []
  6.         for li in operators:
  7.             if len(li) == 2:
  8.                 # get
  9.                 v = d1.get(li[1], -1)    # 取li(key)映射的val，取不到默认-1
  10.                 res.append(v)            # 主输出
  11.                 if v != -1:
  12.                     d1.move_to_end(li[1], last=False)    # 排序移到最后
  13.             else:
  14.                 if len(d1) < k:
  15.                     # set
  16.                     d1[li[1]] = li[2]
  17.                     d1.move_to_end(li[1], last=False)
  18.                 else:
  19.                     # delete
  20.                     d1.popitem(last=True)
  21.                     # set
  22.                     d1[li[1]] = li[2]
  23.                     d1.move_to_end(li[1], last=False)
  24.         return res

栈

匹配括号

  1. def isvalid(s: str) -> bool:
  2.     stack = []  # 设置一个列表，把该列表当做栈来使用即可。
  3.     dic = {')': '(', '}': '{', ']': '['}  # 使用字典存储括号,并且右括号为key,左括号为value
  4.     v = dic.values()
  5.     for char in s:
  6.         if char in v:  # 左括号就入栈
  7.             stack.append(char)
  8.         elif char in dic:  # 有右括号的话就进行比较，
  9.             if stack==[] or dic[char]!=stack.pop():
  10.                 return False
  11.         else:
  12.             return False  # 不再字典中的输入直接输出错误
  13.     return stack==[]

每日温度

  1. def dailyTemperatures(temperatures: iter):
  2.     stack = list()
  3.     out = [0] * len(temperatures)
  4.     for i, per_temp in enumerate(temperatures):
  5.         while len(stack):
  6.             _ = stack.pop()
  7.             if per_temp > _[1]:
  8.                 index = _[0]
  9.                 out[index] = i - index
  10.             else:
  11.                 stack.append(_)
  12.                 break
  13.         stack.append((i, per_temp))
  14.     return out

双向队列

滑动窗口最大值

  1. def dequeue(nums: iter, k):
  2.     """保持一个最大为K的dequeue(简称dq)
  3.     1、保证最左为dq中的最大值
  4.     2、以栈形式比较大小
  5.         2.1、每当有新的最大值时，栈比较出掉对比当前小的值
  6.         2.2、当len(dq) > k，以队列方式出掉值
  7.     """
  8.     dq = deque()
  9.     ans = []
  10.     for i in range(len(nums)):
  11.         # 只要当前遍历的元素的值比队尾大，让队尾出队列，
  12.         # 最终队列中的最小元素是大于当前元素的
  13.         while dq and dq[-1] < nums[i]:
  14.             dq.pop()
  15.         # 当前遍历的元素入队列， 此时队列中的元素一定是有序的，队列头部最大
  16.         dq.append(nums[i])
  17.         if i >= k - 1:  # 超过k个才开始真正运算ans
  18.             # 如果窗口即将失效（下一次循环要失效）的值与当前对列头部的值相同，那么将对头的值出队列，
  19.             # 注意只pop一次，可能两个4，相邻同时是最大值，
  20.             ans.append(dq[0])
  21.             # 从队列中删除即将失效的数据
  22.             if nums[i + 1 - k] == dq[0]:
  23.                 dq.popleft()
  24.     return ans

指针

合并两个有序数组

  1. """arr1长度n,arr2长度m"""
  2. # 方法1 暴力破解 直接合并后，(快速排序)时间复杂度O((m+n)log(m+n))，空间复杂度O(log(m+n))
  4. # 方法2 双指针