数据结构与算法笔记：概念与leetcode练习题

1、数组Array

时间复杂度

数组访问：O(1)

数组搜索：O(N)

数组插入：O(N)

数组删除：O(N)

特点

适合读，不适合写

数组常用操作

# 1、创建数组
a = []
# 2、尾部添加元素
a.append(1)
a.append(2)
a.append(3)
# 3、在中间位置添加元素
a.insert(2, 88)
# 4、访问元素
temp = a[2]
print(temp)
# 5、更新元素
a[2] = 88
# 6、删除元素
a.remove(88)  # O(N)
a.pop(1)  # O(N)
a.pop()  # O(1)
# 7、获取数组长度
size = len(a)
print(size)
# 8、遍历数组
for i in a:print(i)
for index, element in enumerate(a):print("索引是：", index, "值是：", element)
for i in range(0, len(a)):print(a[i])
# 9、查找某个元素
index = a.index(2)
print(index)
# 10、排序
# 从小到大排序
a = [3, 1, 2]
a.sort()
# 从大到小排序
a.sort(reverse=True)

相应练习题

LeetCode485：最大连续1的数

需要一个count计算1出现次数，另外一个result比较哪个连续次数更大

class Solution:def findMaxConsecutiveOnes(self, nums: List[int]) -> int:if nums is None or len(nums)==0:return Nonecount = 0result = 0for num in nums:if num==1:count += 1else:result = max(count,result)count = 0return max(count,result)

LeetCode283：移动零

遍历列表，当值不为0时，把该值移动到当前索引位置，索引+1；然后把剩下的值都赋为1


class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""index = 0for num in nums:if num != 0:nums[index] = numindex = index +1for i in range(index,len(nums)):nums[i] = 0# 双指针
class Solution:def moveZeroes(self, nums):""":type nums: List[int]:rtype: None Do not return anything, modify nums in-place instead."""left = 0 # 第一个指针，leftfor right in range(len(nums)):  # 第二个指针，right，在for循环中实现移动# 核心的交换步骤：如果当前right不为0，则交换到左侧，把非0数往左侧移动就对了if nums[right]: nums[left], nums[right] = nums[right], nums[left]left += 1 # 交换后也移动left

LeetCode27：移除元素

快慢指针，快指针往前走，遇到非val值，就把值赋给慢指针，然后慢指针也走一步，这样前面的数都不为val，返回慢指针的值即非val值个数

class Solution:def removeElement(self, nums: List[int], val: int) -> int:if nums is None or len(nums)==0:return Noneslow,fast = 0,0while fast < len(nums):if nums[fast] != val:nums[slow]=nums[fast]slow = slow+1fast = fast+1return slow

2、链表Linked List

链表：在不连续的空间中存储，每个节点包含一个next指针和元素，指针指向下一个节点

时间复杂度

链表访问：O(N)

链表搜索：O(N)

链表插入：O(1)

链表删除：O(1)

特点

写快读满慢，适合读少写多的场景

链表常用操作

from collections import deque
# 1、创建链表
linkedlist = deque()
# 2、添加元素
linkedlist.append(1)
linkedlist.append(2)
linkedlist.append(3)
print(linkedlist)
linkedlist.insert(2,99)
# 3、访问元素
element = linkedlist[2]
print(element)
# 4、查找元素
index = linkedlist.index(99)
print(index)
# 5、更新元素
linkedlist[2] = 88
# 6、删除元素O(N)
del linkedlist[2]
linkedlist.remove(88)
# 7、链表的长度
length = len(linkedlist)

相应练习题

LeetCode203：移除链表元素

class Solution:def removeElements(self, head: ListNode, val: int) -> ListNode:dummy_head = ListNode(next=head) #添加一个虚拟节点cur = dummy_headwhile(cur.next!=None):if(cur.next.val == val):cur.next = cur.next.next #删除cur.next节点else:cur = cur.nextreturn dummy_head.next

LeetCode206：反转链表

class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:cur,pre = head,Nonewhile cur is not None:# 因为cur连接pre后，就直接断开与后面连接了，所以要先存储起来temp = cur.nextcur.next = prepre = curcur = tempreturn pre

3、队列queue

队列：先入先出，等同于排队

单端队列：只有一个口可以入，另外一个口出

双端队列：两个口都可以入和出

时间复杂度

链表访问：O(N)

链表搜索：O(N)

链表插入：O(1)

链表删除：O(1)

常用操作

# 1、创建队列
from collections import deque
queue = deque()
# 2、添加元素
queue.append(1)
queue.append(2)
queue.append(3)
# 3、获取即将出队的元素O(1)
e = queue[0]
print(e)
# 4、删除即将出队的元素O(1)
d = queue.popleft()
print(d)
# 5、判断队列是否为空
len(queue) == 0
# 6、遍历队列（边删除边遍历队列的操作）
while len(queue) != 0:temp = queue.popleft()print(temp)

LeetCode933：最近的请求次数

class RecentCounter:def __init__(self):self.q = deque()def ping(self, t: int) -> int:self.q.append(t)while (len(self.q)>0 and t-self.q[0]>3000):self.q.popleft()return len(self.q)

4、栈Stack

栈：先进后出，例如浏览器返回功能和WPS撤回

时间复杂度

栈访问：O(1) 栈顶元素

栈搜索：O(N)

栈插入：O(1)

栈删除：O(1)

常用操作

# 1、创建栈
stack = []
# 2、增加元素
stack.append(1)
stack.append(2)
stack.append(3)
# 3、获取栈顶元素
temp = stack[-1]
print(temp)
# 4、删除栈顶元素
stack.pop()
# 5、栈的大小
len(stack)
# 6、栈是否为空
len(stack) == 0
# 7、栈的遍历
while len(stack) > 0:print(stack.pop())

相应练习题

LeetCode20：有效的括号

class Solution:def isValid(self, s: str) -> bool:stack = []if len(s) == 0:return Truefor c in s:if c in ["(","{","["]:stack.append(c)else:if len(stack) == 0:return Falseelse:temp = stack.pop()if c == ")":if temp != "(":return Falseelif c == "}":if temp != "{":return Falseelif c == "]":if temp != "[":return Falseelse:return Falsereturn True if len(stack)==0 else False

LeetCode496：下一个更大元素 I

思路：使用暴力解法或者单调栈解决（用于解决下一个更大元素和上一个更小元素等问题）

暴力解法

class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:# 结果列表result = []# 遍历nums1中的每个元素for num in nums1:found_greater = Falseindex = nums2.index(num)  # 查找num在nums2中的索引# 从num的位置开始向后搜索for j in range(index + 1, len(nums2)):if nums2[j] > num:result.append(nums2[j])  # 找到了更大的数，加入结果列表found_greater = Truebreakif not found_greater:result.append(-1)  # 没有找到更大的数，加入-1return result

单调栈解法：

5、哈希表HashTable

哈希表在python中相当于Python的字典，键值对，有key和value

哈希冲突：两个不同的key通过同一个哈希函数得到相同的内存地址

时间复杂度

哈希表访问：不存在

哈希表搜索：O(1) 碰撞：O(K) 碰撞元素的个数

哈希表插入：O(1)

哈希表删除：O(1)

常用操作

# 1、创建哈希表（数组或者字典）
HashMap = ['']*4
map = {}
# 2、添加元素  O(1)
HashMap[1] = "lihua"
HashMap[2] = "xiaoming"
HashMap[3] = "nsn"
map[1] = "lihua"
map[2] = "xiaoming"
map[3] = "nsn"
# 3、修改元素  O(1)
HashMap[1] = "zhangsan"
map[1] = "zhangsan"
# 4、删除元素  O(1)
HashMap[1] = ""
map.pop(1)
# 5、获取元素  O(1)
value = HashMap[1]
value1 = map[1]
# 6、检查key是否存在
var = 3 in map
# 7、哈希表的长度或判断是否有元素
len(map)
len(map) == 0

相应练习题

LeetCode217：存在重复元素

class Solution:def containsDuplicate(self, nums: List[int]) -> bool:map = {}for i in range(len(nums)):if nums[i] in map:return Trueelse:map[nums[i]]=ielse:return False

LeetCode389：找不同

方法一：位运算，可以计算s和t中每个字符出现次数的异或结果，这样相同的字符会相互抵消，最后剩下的就是那个唯一的字符，但是考虑到题目中提到的字符范围只是小写字母，我们可以简化为直接计算ASCII值的和。

class Solution:def findTheDifference(self, s: str, t: str) -> str:# 计算字符串s中所有字符的ASCII值之和# ord可以将字母转化为ASCII值sum_s = sum(ord(char) for char in s)# 计算字符串t中所有字符的ASCII值之和sum_t = sum(ord(char) for char in t)# 相减得到多出来的字符的ASCII值diff = sum_t - sum_s# 返回ASCII值对应的字符# chr可以将ASCII值转化为字母return chr(diff)

方法二：哈希表

class Solution:def findTheDifference(self, s: str, t: str) -> str:# 初始化两个字典来记录字符出现次数count_s = {}count_t = {}# 遍历字符串s，记录字符出现次数for char in s:if char in count_s:count_s[char] += 1else:count_s[char] = 1# 遍历字符串t，记录字符出现次数for char in t:if char in count_t:count_t[char] += 1else:count_t[char] = 1# 查找多出来的字符for char in count_t:if count_t[char] > (count_s[char] if char in count_s else 0):return char

LeetCode496：下一个更大的元素I

思路：栈+哈希表

class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:res = []stack = []map = {}for num in nums2:while len(stack)!=0 and num > stack[-1]:temp = stack.pop()map[temp] = numstack.append(num)while len(stack)!=0:map[stack.pop()]=-1for num in nums1:res.append(map[num])return res

6、哈希集合Set

无序、不重复，主要作用：检查某一个元素是否存在；重复元素

哈希集合搜索：O(1) 哈希冲突：O(K)

哈希集合插入：O(1) 哈希冲突：O(K)

哈希集合删除：O(1) 哈希冲突：O(K)

常用操作

# 1、创建集合
s = set()
# 2、添加元素
s.add(1)
s.add(2)
s.add(3)
s.add(4)
# 3、搜索元素
2 in s
# 4、删除元素
s.remove(2)
# 5、长度
len(s)

LeetCode217：存在重复元素，哈希集合元素是唯一的，可以先将数组转化为哈希集合，然后再判断长度是否相同

class Solution:def containsDuplicate(self, nums: List[int]) -> bool:s = set(nums)if len(s)==len(nums):return Falseelse:return True

LeetCode705：设计哈希集合

思路：创建一个10**6+1大小的bool集合，添加元素，就将对应键改为True，删除改为False

class MyHashSet:def __init__(self):self.hashset = [False]*1000001def add(self, key: int) -> None:self.hashset[key]=Truedef remove(self, key: int) -> None:self.hashset[key]=Falsedef contains(self, key: int) -> bool:return self.hashset[key]

7、树Tree

根节点：最开始的节点

叶子节点：没有孩子的节点

树的高度：从底下往上计算，210

树的深度：从上往下计算，012

树的层：从上往下，123

树的类型

普通二叉树：每个节点最多两个孩子

满二叉树：除了叶子节点，每个节点都有左右两个孩子，且所有叶子节点在同一层上

完全二叉树：从树的根节点从上到下，从左到右，依次填满节点形成的二叉树

遍历方式

前序遍历：根节点-左节点-右节点

中序遍历：左节点-根节点-右节点

后序遍历：左节点-右节点-根节点

相应练习题

LeetCode144：二叉树前序遍历

递归法

迭代法

# 前序遍历-迭代-LC144_二叉树的前序遍历
class Solution:def preorderTraversal(self, root: TreeNode) -> List[int]:# 根结点为空则返回空列表if not root:return []stack = [root]result = []while stack:node = stack.pop()# 中结点先处理result.append(node.val)# 右孩子先入栈if node.right:stack.append(node.right)# 左孩子后入栈if node.left:stack.append(node.left)return result

LeetCode94：二叉树中序遍历

递归法

迭代法

# 中序遍历-迭代-LC94_二叉树的中序遍历
class Solution:def inorderTraversal(self, root: TreeNode) -> List[int]:if not root:return []stack = []  # 不能提前将root结点加入stack中result = []cur = rootwhile cur or stack:# 先迭代访问最底层的左子树结点if cur:     stack.append(cur)cur = cur.left		# 到达最左结点后处理栈顶结点    else:		cur = stack.pop()result.append(cur.val)# 取栈顶元素右结点cur = cur.right	return result

LeetCode145：二叉树后序遍历

递归法

迭代法

# 后序遍历-迭代-LC145_二叉树的后序遍历
class Solution:def postorderTraversal(self, root: TreeNode) -> List[int]:if not root:return []stack = [root]result = []while stack:node = stack.pop()# 中结点先处理result.append(node.val)# 左孩子先入栈if node.left:stack.append(node.left)# 右孩子后入栈if node.right:stack.append(node.right)# 将最终的数组翻转return result[::-1]

8、堆Heap

堆：

完全二叉树

每个节点>=or<=孩子节点

如果每个节点都大于等于堆节点，最大堆，否则就是最小堆

时间复杂度

堆搜索：O(1)

堆插入：O(logN)

堆删除：O(logN)

常用操作

# 1、创建堆
import heapq
class Test:def test(self):minheap = []heapq.heapify(minheap)
# 2、添加元素heapq.heappush(minheap,10);heapq.heappush(minheap,8);heapq.heappush(minheap,9);heapq.heappush(minheap,2);heapq.heappush(minheap,1);heapq.heappush(minheap,11);print(minheap)
# 3、删除元素heapq.heappop(minheap)
# 4、获取堆顶元素print(minheap[0])
# 5、堆的长度len(minheap)
# 6、堆的遍历while len(minheap)!=0:print(heapq.heappop(minheap))

相应练习题

LeetCode215：数组中第K个最大的元素

最大堆

import heapqclass Solution:def findKthLargest(self, nums: List[int], k: int) -> int:# 转换为最大堆的方式：取每个数的相反数max_heap = [-num for num in nums]# 建立最大堆heapq.heapify(max_heap)# 从堆中弹出 k-1 次最大值for _ in range(k - 1):heapq.heappop(max_heap)# 堆顶元素就是第 k 大的元素return -heapq.heappop(max_heap)

堆排序

class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:return heapq.nlargest(k, nums)[k-1]

LeetCode692：前K个高频单词

哈希表+堆

import heapq
from collections import Counterclass Solution:def topKFrequent(self, words: List[str], k: int) -> List[str]:# 使用 Counter 来统计每个单词出现的次数word_count = Counter(words)# 使用最小堆来维护前 k 个出现次数最多的单词# 为了让堆顶保持出现次数最少的单词，我们将出现次数乘以 -1# 同时，为了保证字典序，我们先比较负出现次数，再比较单词本身的字典序heap = [(-freq, word) for word, freq in word_count.items()]heapq.heapify(heap)# 保持堆的大小不超过 kwhile len(heap) > k:heapq.heappop(heap)# 从堆中提取前 k 个单词# 注意，这里提取的是出现次数最少的单词，因此需要翻转结果result = [heapq.heappop(heap)[1] for _ in range(len(heap))]result.reverse()  # 因为我们是从堆里一个个 pop 出来，所以需要反转一下return result

优先队列排序

class Solution:def topKFrequent(self, words: List[str], k: int) -> List[str]:c = collections.Counter(words)return heapq.nsmallest(k, c, lambda s: (-c[s], s))

9、图Graph

顶点、邻居顶点

有向图：入度：多少边指向该顶点；出度：多少边从这个点为起点指向别的顶点

无向图：无指向

权重图：求最短路径用

10、双指针

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

双指针技术的应用场景

数组和字符串中的滑动窗口：
- 滑动窗口最大值/最小值：在固定大小的窗口内找到最大值或最小值。
- 子数组/子串问题：寻找满足一定条件的最长或最短子数组/子串。
数组和链表中的合并与排序：
- 合并有序数组/链表：合并两个或多个已排序的数组或链表。
- 排序算法：某些排序算法（如归并排序）也可以使用双指针思想。
数组和字符串中的匹配问题：
- 回文检测：检查字符串或数组是否为回文。
- 字符匹配：检查字符串中的模式匹配。
数组中的查找问题：
- 两数之和：给定一个数组和目标值，找到数组中两个数的和等于目标值。
- 三数之和：给定一个数组和目标值，找到数组中三个数的和等于目标值。
链表中的快慢指针：
- 链表中间节点：找到链表的中间节点。
- 环检测：检测链表中是否存在环。

LeetCode141：环形链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def hasCycle(self, head: Optional[ListNode]) -> bool:slow = headfast = headwhile fast is not None and fast.next is not None:# 满指针走一步，快指针走两步slow = slow.nextfast = fast.next.next# 如果快慢指针相遇，说明存在环if slow == fast:return Truereturn False

LeetCode881：救生艇

class Solution:def numRescueBoats(self, people: List[int], limit: int) -> int:if people is None or len(people)==0:return 0# 创建对撞指针p1 = 0p2 = len(people)-1res = 0people.sort()while p1<=p2:# 如果头和尾相加小于限制，则头指针+1，表示可以坐一艘船if people[p1]+people[p2]<=limit:p1+=1# 如果超重，则尾指针-1，表示尾部单独坐一艘船p2-=1res+=1return res

11、二分查找

使用二分法的前提是数组已经排序好，时间复杂度O(logN)

二分查找法的应用场景

二分查找是一种在有序数组中查找特定元素的高效算法。它的工作原理是通过将查找区间分为两部分，并根据中间元素与目标值的关系来决定搜索哪一半，从而每次迭代都能将搜索空间减少一半。这种方法适用于解决那些可以通过缩小搜索范围来逐步逼近答案的问题。

以下是几种常见的LeetCode题目类型，这些题目可以通过二分查找来解决：

1. 查找特定元素：
- 给定一个排序数组，查找一个特定值。例如，LeetCode题目 #34 "在排序数组中查找元素的第一个和最后一个位置"。

2. 查找特定条件下的最小/最大值：
- 在给定条件下查找符合条件的最小或最大索引。例如，LeetCode题目 #162 "寻找峰值元素"。

3. 确定某个条件的边界：
- 寻找元素首次出现或最后一次出现的位置。如上述提到的LeetCode题目 #34。

4. 旋转排序数组中的查找：
- 如果一个排序数组被旋转过，可以使用修改后的二分查找来定位元素。如LeetCode题目 #33 "搜索旋转排序数组" 和 #81 "搜索旋转排序数组 II"。

5. 确定可行解的范围：
- 当问题要求确定一个数值解，而这个解又依赖于某种条件时，可以使用二分查找来确定解的范围。例如，LeetCode题目 #69 "x 的平方根”。

6. 查找旋转排序数组中的最小值：
- 在旋转过的排序数组中查找最小值。如LeetCode题目 #153 "寻找旋转排序数组中的最小值"。

7. 复杂条件下的优化问题：
- 有时候，二分查找也可以用来优化一些问题，例如在LeetCode题目 #410 "分割排序数组的最大值" 中，可以使用二分查找来寻找最优分割方案。

LeetCode704：二分查找

class Solution:def search(self, nums: List[int], target: int) -> int:if nums is None or len(nums)==0:return -1l=0r=len(nums)-1while l<=r:mid=(l+r)//2s = nums[mid]if s>target:r=mid-1elif s==target:return midelse:l=mid+1return -1

LeetCode162：寻找峰值

class Solution:def findPeakElement(self, nums: List[int]) -> int:# 开区间[0,n-2],(-1,n-1)l,r=-1,len(nums)-1while l+1<r:mid=(l+r)//2if nums[mid]>nums[mid+1]:r=midelse:l=midreturn r

12、滑动窗口

一种方法可以用来减少while循环，用来解决数组中定长问题，例如一个数组中找三个数组成最大和，如果用常规暴力法，需要三层循环，但是用滑动窗口，只需要移动包含三个数的窗口即可

滑动窗口的应用场景

滑动窗口技术是一种用于处理数组或字符串问题的有效方法，特别适用于需要在连续子数组或子串中寻找满足特定条件的问题。滑动窗口的核心思想是通过移动两个指针（通常称为左右指针）来创建一个“窗口”，这个窗口会覆盖数组或字符串的一部分，随着窗口的移动，你可以动态地调整窗口内的数据，以达到解决问题的目的。

关键词：

满足XX条件（计算结果、出现次数，同时包含）
最长/最短
子串、子数组、子序列
例如：长度最小的子数组

使用思路：寻找最长

——核心：左右双指针（L、R在起始点），R向右逐位滑动循环

——每次滑动过程中：

如果：窗内元素满足条件，R向右扩大窗口，并更新最优结果

如果：窗内元素不满足条件，L向右收缩窗口

R到达结尾

使用思路：寻找最短

——核心：左右双指针（L、R在起始点），R向右逐位滑动循环

——每次滑动过程中：

如果：窗内元素满足条件，L向右收缩窗口，并更新最优结果

如果：窗内元素不满足条件，R向右收缩窗口

R到达结尾

伪代码模板

# 最长模板
# 初始化left、right、result、bestResult
while (右指针未到达末尾):窗口扩大，加入right对应元素，更新当前resultwhile (result不满足要求):窗口缩小，移除left对应元素，left右移# 更新最优结果bestResultright = right+1
return bestResult# 最短模板
# 初始化left、right、result、bestResult
while (右指针未到达末尾):窗口扩大，加入right对应元素，更新当前resultwhile (result满足要求):# 更新最优结果bestResult窗口缩小，移除left对应元素，left右移right = right+1
return bestResult

滑动窗口方法的优点在于它可以有效地减少不必要的计算，避免了对每个子数组/子串都重新计算一遍。通过维护一个当前窗口的状态，并根据窗口的变化动态调整状态，滑动窗口可以在线性时间内解决问题，这比穷举法（即检查所有可能的子数组/子串）要高效得多。

使用滑动窗口时，关键是要正确设置初始状态，并确定何时扩大窗口，何时收缩窗口，以及如何更新窗口的状态，以便能够快速地找到满足条件的答案。

应用实例

LeetCode209:长度最小的子数组

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:l,r,curSum,minLegth=0,0,0,0while (r<len(nums)):curSum=curSum+nums[r]while (curSum>=target):if (r-l+1<minLegth or minLegth==0):minLegth=r-l+1curSum=curSum-nums[l]l=l+1r=r+1return minLegth

LeetCode713：乘积小于k的子数组

class Solution:def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:# l，r指针# 如果[l,r]区间满足条件，则[l+1,r],[l+2,r]...[r,r]都满足条件# 因此如果找到对应区间，就有r-l+1个子数组满足乘积小于K# 因为元素乘积要小于K，数组元素是正整数，因此1和0都不可能存在if k<=1:return 0ans=0result=1l=0for r,x in enumerate(nums):# x=nums[r]result=result*xwhile result>=k:result=result/nums[l]l=l+1ans=ans+r-l+1return ans

13、递归

相应练习题

LeetCode509：斐波那契数列

class Solution:def fib(self, n: int) -> int:if n==0:return 0if n==1:return 1m = self.fib(n-1)+self.fib(n-2)return m

LeetCode208：反转链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:if not head or not head.next:return headp=self.reverseList(head.next)head.next.next=headhead.next=Nonereturn p

14、贪心算法

15、动态规划

16、回溯

HOT100

链表

虚拟头节点dummy使用场景：当你需要创造一条新链表的时候，可以使用虚拟头结点简化边界情况的处理。

断开链表节点：如果我们需要把原链表的节点接到新链表上，而不是 new 新节点来组成新链表的话，那么断开节点和原链表之间的链接可能是必要的。那其实我们可以养成一个好习惯，但凡遇到这种情况，就把原链表的节点断开，这样就不会出错了。

LeetCode160：相交链表

哈希集合记录一个表的节点，然后再遍历另外一个表，看看有没有相同的节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:h = set()p,q=headA,headBwhile p:h.add(p)p=p.nextwhile q:if q in h:return qq =q.nextreturn None

LeetCode21：合并两个有序链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:p1=list1p2=list2dummy=ListNode(-1)p=dummywhile p1 is not None and p2 is not None:if p1.val>p2.val:p.next=p2p2=p2.nextelse:p.next=p1p1=p1.nextp=p.next# 如果l1，l2还有元素，需要拼接起来if p1 is not None:p.next=p1if p2 is not None:p.next=p2return dummy.next

LeetCode86：分隔链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:# 需要两个链表，一个用来存储小于x的节点，另外一个存储大于等于x的节点dummy1=ListNode(-1)dummy2=ListNode(-2)p1=dummy1p2=dummy2p=headwhile p:if p.val<x:p1.next=pp1=p1.nextelse:p2.next=pp2=p2.next# 这里不能让p指针直接动，要断开连接，否则会形成环temp=p.nextp.next=Nonep=tempp1.next=dummy2.nextreturn dummy1.next

LeetCode19：删除链表的倒数第n个数

方法一：暴力破解，循环遍历链表获得长度，再遍历获得倒数第n个数

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:dummy = ListNode(-1)dummy.next=head# 计算链表长度cur,sum=head,0while cur != None:sum+=1cur=cur.next# 遍历链表，找到倒数第n个节点的前一个数cur = dummyfor _ in range(sum-n):cur=cur.next# 删除节点，并重新连接cur.next=cur.next.nextreturn dummy.next

方法二：快慢指针，让p1指针先走k步，然后p1，p2指针走n-k步，这样p2指针就指向了n-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 find(self,head:ListNode,k:int) -> ListNode:p1=headfor _ in range(k):p1=p1.nextp2=headwhile p1!=None:p2=p2.nextp1=p1.next# p2指向n-k+1个节点，即倒数第k个节点return p2def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:dummy = ListNode(-1)dummy.next=headx=self.find(dummy,n+1)x.next=x.next.nextreturn dummy.next

LeetCode141：环形链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def hasCycle(self, head: Optional[ListNode]) -> bool:slow = headfast = headwhile fast is not None and fast.next is not None:# 满指针走一步，快指针走两步slow = slow.nextfast = fast.next.next# 如果快慢指针相遇，说明存在环if slow == fast:return Truereturn False

LeetCode142：环形链表II

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:s,f=head,headwhile f and f.next:s=s.nextf=f.next.nextif s==f:breakif f is None or f.next is None:return Nones=headwhile s!=f:s=s.nextf=f.nextreturn s

哈希

LeetCode1：两数之和

    # 方法一：哈希表def twoSum(self, nums: List[int], target: int) -> List[int]:h = dict()for i,num in enumerate(nums):if target-num in h:return [h[target-num],i]h[nums[i]]=ireturn []# 方法二：暴力解法def twoSum(self, nums: List[int], target: int) -> List[int]:n=len(nums)for i in range(n):for j in range(i+1,n):if nums[i]+nums[j]==target:return[i,j]

LeetCode49：字母异位词分组

思路：异位词排序好后都是一样的，所以可以创建一个哈希表，键是排序好的字符，值是一个列表，存储的是所有排序后是键的词。

class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:table={}for s in strs:sort="".join(sorted(s))if sort not in table:table[sort]=[s]else:table[sort].append(s)return list(table.values())

LeetCode128：最长连续序列

方法一：直接排序，然后再遍历整个数组，找到最长序列，时间复杂度是O(nlog(n))

class Solution:def longestConsecutive(self, nums: List[int]) -> int:s=nums.sort()c=1m=1if not nums:return 0for i in range(1,len(nums)):if nums[i]==nums[i-1]+1:c+=1elif nums[i]!=nums[i-1]:m=max(c,m)c=1return max(c,m)

方法二：哈希表，先判断数是不是连续子序列第一个数，不是就跳过，是的话就向上计算，直到找到最大子序列长度。

class Solution:def longestConsecutive(self, nums: List[int]) -> int:# 将数组转换为哈希集合，方便查找是否存在某个元素set_nums=set(nums)res=0for num in set_nums:if num-1 in set_nums:# num不是连续子序列第一个，跳过continue# num是连续子序列的第一个，开始向上计算连续子序列cur_num=numcur_len=1while cur_num+1 in set_nums:cur_num+=1cur_len+=1# 更新最长连续序列长度res = max(res,cur_len)return res

双指针

LeetCode283：移动零

class Solution:# 方法一：把非零数全部移到前面，后面的数再全部赋值为0def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""index = 0for num in nums:if num != 0:nums[index]=numindex=index+1for i in range(index,len(nums)):nums[i]=0class Solution:# 方法二：双指针解法def moveZeroes(self, nums):left = 0 # 第一个指针，leftfor right in range(len(nums)):  # 第二个指针，right，在for循环中实现移动# 核心的交换步骤：如果当前right不为0，则交换到左侧，把非0数往左侧移动就对了if nums[right]: nums[left], nums[right] = nums[right], nums[left]left += 1 # 交换后也移动left

LeetCode11：盛最多水的容器

class Solution:def maxArea(self, height: List[int]) -> int:left, right = 0, len(height) - 1res = 0# 双指针不断收缩while left < right:w = right-lefth = min(height[left],height[right])res = max(res, w*h)# 双指针技巧，移动较低的一边if height[left] < height[right]:left += 1else:right -= 1return res

LeetCode15：三数之和

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:nums.sort()res = []n=len(nums)for i in range(n-2):x=nums[i]if i>0 and x==nums[i-1]:continuel=i+1r=n-1while l<r:s=x+nums[l]+nums[r]if s<0:l+=1elif s>0:r-=1else:res.append([x,nums[l],nums[r]])l+=1while l<r and nums[l]==nums[l-1]:l+=1r-=1while l<r and nums[r]==nums[r+1]:r-=1return res

二分查找

LeetCode35：搜索插入位置

# lower_bound 返回最小的满足 nums[i] >= target 的 i
# 如果数组为空，或者所有数都 < target，则返回 len(nums)
# 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]# 闭区间写法
def lower_bound(nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1  # 闭区间 [left, right]while left <= right:  # 区间不为空# 循环不变量：# nums[left-1] < target# nums[right+1] >= targetmid = (left + right) // 2if nums[mid] < target:left = mid + 1  # 范围缩小到 [mid+1, right]else:right = mid - 1  # 范围缩小到 [left, mid-1]return left# 左闭右开区间写法
def lower_bound2(nums: List[int], target: int) -> int:left = 0right = len(nums)  # 左闭右开区间 [left, right)while left < right:  # 区间不为空# 循环不变量：# nums[left-1] < target# nums[right] >= targetmid = (left + right) // 2if nums[mid] < target:left = mid + 1  # 范围缩小到 [mid+1, right)else:right = mid  # 范围缩小到 [left, mid)return left  # 或者 right# 开区间写法
def lower_bound3(nums: List[int], target: int) -> int:left, right = -1, len(nums)  # 开区间 (left, right)while left + 1 < right:  # 区间不为空mid = (left + right) // 2# 循环不变量：# nums[left] < target# nums[right] >= targetif nums[mid] < target:left = mid  # 范围缩小到 (mid, right)else:right = mid  # 范围缩小到 (left, mid)return rightclass Solution:def searchInsert(self, nums: List[int], target: int) -> int:return lower_bound(nums, target)  # 选择其中一种写法即可

LeetCode34:在排序数组中寻找元素的第一个位置和最后一个位置

def lower_bound(nums:List[int],target:int) -> List[int]:l,r=0,len(nums)-1while l<=r:mid = (l+r)//2if nums[mid]<target:l=mid+1else:r=mid-1return l
class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:s=lower_bound(nums,target)if s==len(nums) or nums[s]!=target:return [-1,-1]e=lower_bound(nums,target+1)-1return [s,e]

>= x
> >=x+1
< (>=x)-1
<= (>x)-1

LeetCode153：寻找旋转排序数组中的最小值

二分查找，时间复杂度O(log(N))

class Solution:def findMin(self, nums: List[int]) -> int:left, right = 0, len(nums) - 1while left < right:mid = (left + right) // 2if nums[mid] > nums[right]:# 最小值在 mid 的右边left = mid + 1else:# 最小值可能就在 mid 或者在左边right = midreturn nums[left]

先进行排序，再直接取有序数组的第一个值即最小值，时间复杂度：O(nlog(N))

class Solution:def findMin(self, nums: List[int]) -> int:nums.sort()return nums[0]

LeetCode33：搜索旋转排序数组

二分查找，时间复杂度O(log(N))

class Solution:def search(self, nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return mid# 如果左半边是有序的if nums[left] <= nums[mid]:# 目标值位于左半边的范围内if nums[left] <= target < nums[mid]:right = mid - 1else:left = mid + 1# 右半边是有序的else:# 目标值位于右半边的范围内if nums[mid] < target <= nums[right]:left = mid + 1else:right = mid - 1return -1

用Python捕获异常来做，尝试检索target对应索引，异常情况则直接返回-1，时间复杂度：O(n)

class Solution:def search(self, nums: List[int], target: int) -> int:try:return nums.index(target)except Exception:return -1

LeetCode74：搜索二维矩阵

class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:# 把整个矩阵看成一个数组，某个数可以用matrix[x][y]表示# 记录行数m=len(matrix)# 记录列数n=len(matrix[0])l,r=-1,m*nwhile l+1<r:mid=(l+r)//2x=mid//ny=mid%nif matrix[x][y]>target:r=midelif matrix[x][y]==target:return Trueelse:l=midreturn False

滑动窗口

LeetCode3：无重复字符的最长子串

class Solution:def lengthOfLongestSubstring(self, s: str) -> int:ans=0l=0h=Counter()for r,x in enumerate(s):h[x]+=1while h[x]>1:h[s[l]]-=1l+=1ans=max(ans,r-l+1)return ans

LeetCode438：找到字符串中所有异位词

栈

LeetCode739：每日温度

方法一：暴力破解，时间复杂度O(n^2)，超时

class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:n=len(temperatures)ans=[0]*nfor i in range(n):for j in range(i+1,n):if temperatures[j] > temperatures[i]:ans[i]=j-ibreakreturn ans

方法二：单调栈

class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:# 空间复杂度O(min(n,U))   U=max-min+1# 时间复杂度O(n)n=len(temperatures)ans=[0]*nst=[]for i,t in enumerate(temperatures):while st and t>temperatures[st[-1]]:j=st.pop()ans[j]=i-jst.append(i)return ans