设计公司 网站,关于文案的网站,台州网站建设方案推广,微网站 html51、数组Array
时间复杂度
数组访问#xff1a;O(1)
数组搜索#xff1a;O(N)
数组插入#xff1a;O(N)
数组删除#xff1a;O(N)
特点
适合读#xff0c;不适合写
数组常用操作 # 1、创建数组
a []
# 2、尾部添加元素
a.append(1)
a.append(2)
a.append(3)
# 3、…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(reverseTrue)相应练习题
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 num1: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 slow1fast fast1return 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(nexthead) #添加一个虚拟节点cur dummy_headwhile(cur.next!None):if(cur.next.val val):cur.next cur.next.next #删除cur.next节点else:cur cur.nextreturn dummy_head.nextLeetCode206反转链表 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 TrueLeetCode705设计哈希集合
思路创建一个10**61大小的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 resultLeetCode145二叉树后序遍历
递归法 迭代法 # 后序遍历-迭代-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 p1p2:# 如果头和尾相加小于限制则头指针1表示可以坐一艘船if people[p1]people[p2]limit:p11# 如果超重则尾指针-1表示尾部单独坐一艘船p2-1res1return 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 -1l0rlen(nums)-1while lr:mid(lr)//2s nums[mid]if starget:rmid-1elif starget:return midelse:lmid1return -1 LeetCode162寻找峰值 class Solution:def findPeakElement(self, nums: List[int]) - int:# 开区间[0,n-2],(-1,n-1)l,r-1,len(nums)-1while l1r:mid(lr)//2if nums[mid]nums[mid1]:rmidelse:lmidreturn 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 right1
return bestResult# 最短模板
# 初始化left、right、result、bestResult
while (右指针未到达末尾):窗口扩大加入right对应元素更新当前resultwhile (result满足要求):# 更新最优结果bestResult窗口缩小移除left对应元素left右移right right1
return bestResult 滑动窗口方法的优点在于它可以有效地减少不必要的计算避免了对每个子数组/子串都重新计算一遍。通过维护一个当前窗口的状态并根据窗口的变化动态调整状态滑动窗口可以在线性时间内解决问题这比穷举法即检查所有可能的子数组/子串要高效得多。
使用滑动窗口时关键是要正确设置初始状态并确定何时扩大窗口何时收缩窗口以及如何更新窗口的状态以便能够快速地找到满足条件的答案。
应用实例
LeetCode209:长度最小的子数组 class Solution:def minSubArrayLen(self, target: int, nums: List[int]) - int:l,r,curSum,minLegth0,0,0,0while (rlen(nums)):curSumcurSumnums[r]while (curSumtarget):if (r-l1minLegth or minLegth0):minLegthr-l1curSumcurSum-nums[l]ll1rr1return minLegth LeetCode713乘积小于k的子数组 class Solution:def numSubarrayProductLessThanK(self, nums: List[int], k: int) - int:# lr指针# 如果[l,r]区间满足条件则[l1,r],[l2,r]...[r,r]都满足条件# 因此如果找到对应区间就有r-l1个子数组满足乘积小于K# 因为元素乘积要小于K数组元素是正整数因此1和0都不可能存在if k1:return 0ans0result1l0for r,x in enumerate(nums):# xnums[r]resultresult*xwhile resultk:resultresult/nums[l]ll1ansansr-l1return ans 13、递归
相应练习题
LeetCode509斐波那契数列 class Solution:def fib(self, n: int) - int:if n0:return 0if n1:return 1m self.fib(n-1)self.fib(n-2)return mLeetCode208反转链表 # Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]:if not head or not head.next:return headpself.reverseList(head.next)head.next.nextheadhead.nextNonereturn 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,qheadA,headBwhile p:h.add(p)pp.nextwhile q:if q in h:return qq q.nextreturn None LeetCode21合并两个有序链表 # Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) - Optional[ListNode]:p1list1p2list2dummyListNode(-1)pdummywhile p1 is not None and p2 is not None:if p1.valp2.val:p.nextp2p2p2.nextelse:p.nextp1p1p1.nextpp.next# 如果l1l2还有元素需要拼接起来if p1 is not None:p.nextp1if p2 is not None:p.nextp2return dummy.next LeetCode86分隔链表 # Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def partition(self, head: Optional[ListNode], x: int) - Optional[ListNode]:# 需要两个链表一个用来存储小于x的节点另外一个存储大于等于x的节点dummy1ListNode(-1)dummy2ListNode(-2)p1dummy1p2dummy2pheadwhile p:if p.valx:p1.nextpp1p1.nextelse:p2.nextpp2p2.next# 这里不能让p指针直接动要断开连接否则会形成环tempp.nextp.nextNoneptempp1.nextdummy2.nextreturn dummy1.next LeetCode19删除链表的倒数第n个数
方法一暴力破解循环遍历链表获得长度再遍历获得倒数第n个数 # Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]:dummy ListNode(-1)dummy.nexthead# 计算链表长度cur,sumhead,0while cur ! None:sum1curcur.next# 遍历链表找到倒数第n个节点的前一个数cur dummyfor _ in range(sum-n):curcur.next# 删除节点并重新连接cur.nextcur.next.nextreturn dummy.next 方法二快慢指针让p1指针先走k步然后p1p2指针走n-k步这样p2指针就指向了n-k1即题目要求的那个数的位置 # Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def find(self,head:ListNode,k:int) - ListNode:p1headfor _ in range(k):p1p1.nextp2headwhile p1!None:p2p2.nextp1p1.next# p2指向n-k1个节点即倒数第k个节点return p2def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]:dummy ListNode(-1)dummy.nextheadxself.find(dummy,n1)x.nextx.next.nextreturn dummy.nextLeetCode141环形链表 # 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,fhead,headwhile f and f.next:ss.nextff.next.nextif sf:breakif f is None or f.next is None:return Nonesheadwhile s!f:ss.nextff.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]:nlen(nums)for i in range(n):for j in range(i1,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:snums.sort()c1m1if not nums:return 0for i in range(1,len(nums)):if nums[i]nums[i-1]1:c1elif nums[i]!nums[i-1]:mmax(c,m)c1return max(c,m)方法二哈希表先判断数是不是连续子序列第一个数不是就跳过是的话就向上计算直到找到最大子序列长度。 class Solution:def longestConsecutive(self, nums: List[int]) - int:# 将数组转换为哈希集合方便查找是否存在某个元素set_numsset(nums)res0for num in set_nums:if num-1 in set_nums:# num不是连续子序列第一个跳过continue# num是连续子序列的第一个开始向上计算连续子序列cur_numnumcur_len1while cur_num1 in set_nums:cur_num1cur_len1# 更新最长连续序列长度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]numindexindex1for 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 []nlen(nums)for i in range(n-2):xnums[i]if i0 and xnums[i-1]:continueli1rn-1while lr:sxnums[l]nums[r]if s0:l1elif s0:r-1else:res.append([x,nums[l],nums[r]])l1while lr and nums[l]nums[l-1]:l1r-1while lr and nums[r]nums[r1]: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[right1] targetmid (left right) // 2if nums[mid] target:left mid 1 # 范围缩小到 [mid1, 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 # 范围缩小到 [mid1, 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,r0,len(nums)-1while lr:mid (lr)//2if nums[mid]target:lmid1else:rmid-1return l
class Solution:def searchRange(self, nums: List[int], target: int) - List[int]:slower_bound(nums,target)if slen(nums) or nums[s]!target:return [-1,-1]elower_bound(nums,target1)-1return [s,e]x x1 (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]表示# 记录行数mlen(matrix)# 记录列数nlen(matrix[0])l,r-1,m*nwhile l1r:mid(lr)//2xmid//nymid%nif matrix[x][y]target:rmidelif matrix[x][y]target:return Trueelse:lmidreturn False 滑动窗口
LeetCode3无重复字符的最长子串 class Solution:def lengthOfLongestSubstring(self, s: str) - int:ans0l0hCounter()for r,x in enumerate(s):h[x]1while h[x]1:h[s[l]]-1l1ansmax(ans,r-l1)return ans LeetCode438找到字符串中所有异位词 栈
LeetCode739每日温度
方法一暴力破解时间复杂度O(n^2)超时 class Solution:def dailyTemperatures(self, temperatures: List[int]) - List[int]:nlen(temperatures)ans[0]*nfor i in range(n):for j in range(i1,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)) Umax-min1# 时间复杂度O(n)nlen(temperatures)ans[0]*nst[]for i,t in enumerate(temperatures):while st and ttemperatures[st[-1]]:jst.pop()ans[j]i-jst.append(i)return ans 文章转载自： http://www.morning.ishoufeipin.cn.gov.cn.ishoufeipin.cn http://www.morning.xbmwm.cn.gov.cn.xbmwm.cn http://www.morning.fdrwk.cn.gov.cn.fdrwk.cn http://www.morning.sgnxl.cn.gov.cn.sgnxl.cn http://www.morning.hcsqznn.cn.gov.cn.hcsqznn.cn http://www.morning.jbtlf.cn.gov.cn.jbtlf.cn http://www.morning.zcncb.cn.gov.cn.zcncb.cn http://www.morning.sqdjn.cn.gov.cn.sqdjn.cn http://www.morning.kntsd.cn.gov.cn.kntsd.cn http://www.morning.rdmz.cn.gov.cn.rdmz.cn http://www.morning.dhmll.cn.gov.cn.dhmll.cn http://www.morning.yydeq.cn.gov.cn.yydeq.cn http://www.morning.gbfuy28.cn.gov.cn.gbfuy28.cn http://www.morning.lndongguan.com.gov.cn.lndongguan.com http://www.morning.fkyqt.cn.gov.cn.fkyqt.cn http://www.morning.xgbq.cn.gov.cn.xgbq.cn http://www.morning.tfsyk.cn.gov.cn.tfsyk.cn http://www.morning.bprsd.cn.gov.cn.bprsd.cn http://www.morning.ljyqn.cn.gov.cn.ljyqn.cn http://www.morning.rmlz.cn.gov.cn.rmlz.cn http://www.morning.hdrsr.cn.gov.cn.hdrsr.cn http://www.morning.gfrjs.cn.gov.cn.gfrjs.cn http://www.morning.srbfz.cn.gov.cn.srbfz.cn http://www.morning.zlnyk.cn.gov.cn.zlnyk.cn http://www.morning.wlnr.cn.gov.cn.wlnr.cn http://www.morning.qwwcf.cn.gov.cn.qwwcf.cn http://www.morning.tpnx.cn.gov.cn.tpnx.cn http://www.morning.jwdys.cn.gov.cn.jwdys.cn http://www.morning.bypfj.cn.gov.cn.bypfj.cn http://www.morning.mzjbz.cn.gov.cn.mzjbz.cn http://www.morning.smdiaosu.com.gov.cn.smdiaosu.com http://www.morning.brnwc.cn.gov.cn.brnwc.cn http://www.morning.bfybb.cn.gov.cn.bfybb.cn http://www.morning.zbgqt.cn.gov.cn.zbgqt.cn http://www.morning.jwxmn.cn.gov.cn.jwxmn.cn http://www.morning.fqtzn.cn.gov.cn.fqtzn.cn http://www.morning.gjqnn.cn.gov.cn.gjqnn.cn http://www.morning.mtgkq.cn.gov.cn.mtgkq.cn http://www.morning.tkflb.cn.gov.cn.tkflb.cn http://www.morning.zkqsc.cn.gov.cn.zkqsc.cn http://www.morning.mqxrx.cn.gov.cn.mqxrx.cn http://www.morning.lzqtn.cn.gov.cn.lzqtn.cn http://www.morning.jwwfk.cn.gov.cn.jwwfk.cn http://www.morning.xtkw.cn.gov.cn.xtkw.cn http://www.morning.wqfj.cn.gov.cn.wqfj.cn http://www.morning.bhznl.cn.gov.cn.bhznl.cn http://www.morning.ppbqz.cn.gov.cn.ppbqz.cn http://www.morning.yrfxb.cn.gov.cn.yrfxb.cn http://www.morning.geledi.com.gov.cn.geledi.com http://www.morning.mymz.cn.gov.cn.mymz.cn http://www.morning.hlrtzcj.cn.gov.cn.hlrtzcj.cn http://www.morning.ljngm.cn.gov.cn.ljngm.cn http://www.morning.jftl.cn.gov.cn.jftl.cn http://www.morning.rqbr.cn.gov.cn.rqbr.cn http://www.morning.lgnrl.cn.gov.cn.lgnrl.cn http://www.morning.tjqcfw.cn.gov.cn.tjqcfw.cn http://www.morning.qsfys.cn.gov.cn.qsfys.cn http://www.morning.chfxz.cn.gov.cn.chfxz.cn http://www.morning.nkpls.cn.gov.cn.nkpls.cn http://www.morning.pjftk.cn.gov.cn.pjftk.cn http://www.morning.wfwqr.cn.gov.cn.wfwqr.cn http://www.morning.mlnby.cn.gov.cn.mlnby.cn http://www.morning.zkqsc.cn.gov.cn.zkqsc.cn http://www.morning.tmfhx.cn.gov.cn.tmfhx.cn http://www.morning.wncb.cn.gov.cn.wncb.cn http://www.morning.jghty.cn.gov.cn.jghty.cn http://www.morning.xmnlc.cn.gov.cn.xmnlc.cn http://www.morning.cfynn.cn.gov.cn.cfynn.cn http://www.morning.gfqj.cn.gov.cn.gfqj.cn http://www.morning.fyxtn.cn.gov.cn.fyxtn.cn http://www.morning.gpsr.cn.gov.cn.gpsr.cn http://www.morning.hrnrx.cn.gov.cn.hrnrx.cn http://www.morning.jqllx.cn.gov.cn.jqllx.cn http://www.morning.cdrzw.cn.gov.cn.cdrzw.cn http://www.morning.xhqr.cn.gov.cn.xhqr.cn http://www.morning.jljwk.cn.gov.cn.jljwk.cn http://www.morning.bpmnz.cn.gov.cn.bpmnz.cn http://www.morning.rzcmn.cn.gov.cn.rzcmn.cn http://www.morning.ghxzd.cn.gov.cn.ghxzd.cn http://www.morning.xbtlt.cn.gov.cn.xbtlt.cn
