怎么建网站教程图解,wordpress 漏洞利用工具,建设工程获奖查询网站,wordpress 在线手册LeetCode刷题小记 一、【数组】 文章目录 LeetCode刷题小记 一、【数组】写在前面1. 数组1.1 理论基础1.2 二分查找1.3 移除元素1.4 有序数组的平方1.5 长度最小的子数组1.6 螺旋矩阵II Reference 写在前面
本系列笔记主要作为笔者刷题的题解#xff0c;所用的语言为Python3所用的语言为Python3若于您有助不胜荣幸。
1. 数组
1.1 理论基础
数组[array]是一种线性的数据结构将相同的数据类型存储在连续的内存空间当中我们将元素在数组中的位置称为该元素的索引[index]。由于数组是连续存储的特性我们访问其中单个元素变得十分容易我们只需要知道其索引就能访问其中的元素索引本质上是内存地址的偏移量。
由于数组中元素的连续存在的因此要在数组中插入、删除元素需要移动后续的所有元素。所以数组的各项操作的时间复杂度如下
OperationTime Complexity插入、删除 O ( n ) \mathcal{O}(n) O(n)查找 O ( 1 ) \mathcal{O}(1) O(1)
1.2 二分查找
704二分查找
二分查找的前提是有序数组升序或者降序且无重复元素。
给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。
二分查找的第一种写法是要定义在一个左闭右闭的区间里[left, right]所以终止条件就可以写为while (left right)
class Solution:def search(self, nums: List[int], target: int) - int:left: int 0right: int len(nums) - 1 #左闭右闭while left right:mid: int (left right) // 2if target nums[mid]:left mid 1elif target nums[mid]:right mid - 1else:return midreturn -1时间复杂度 O ( log n ) \mathcal{O}(\log n) O(logn)空间复杂度 O ( 1 ) \mathcal{O}(1) O(1)
第二种写法是将其定义在一个左闭右开的区间[left, right)当中所以终止条件必须写为while (left right)
class Solution:def search(self, nums: List[int], target: int) - int:left: int 0right: int len(nums) #左闭右开while left right:mid: int left (right - left) // 2if target nums[mid]:left mid 1elif target nums[mid]:right midelse:return midreturn -135搜索插入位置
class Solution:def searchInsert(self, nums: List[int], target: int) - int:left: int 0right: int len(nums)-1while left right:mid left (right - left) // 2if nums[mid] target:right mid - 1elif nums[mid] target:left mid 1else:return midreturn left34在排序数组中查找元素的第一个和最后一个位置
# 1、首先在 nums 数组中二分查找 target
# 2、如果二分查找失败则 binarySearch 返回 -1表明 nums 中没有 target。此时searchRange 直接返回 {-1, -1}
# 3、如果二分查找成功则 binarySearch 返回 nums 中值为 target 的一个下标。然后通过左右滑动指针来找到符合题意的区间
class Solution:def searchRange(self, nums: List[int], target: int) - List[int]:def binarySearch(nums: List[int], target: int) - int:left: int 0right: int len(nums) - 1while left right:mid left (right - left) // 2if nums[mid] target:right mid - 1elif nums[mid] target:left mid 1else:return midreturn -1index binarySearch(nums, target)if index -1: return [-1, -1]left right indexwhile left - 1 0 and nums[left - 1] target: left - 1while right 1 len(nums) - 1 and nums[right1] target: right 1return [left, right]69x的平方根
class Solution:def mySqrt(self, x: int) - int:if x 0 or x 1:return xleft: int 1right: int xres: int -1while left right:mid left (right - left) // 2if mid * mid x: # 平方更要小于等于当前的x所以这里用来限制区间res midleft mid 1else:right mid - 1return res367有效的完全平方数
class Solution:def isPerfectSquare(self, num: int) - bool:left: int 1right: int numwhile left right:mid left (right - left)//2if mid * mid num:right mid - 1elif mid * mid num:left mid 1else:return Truereturn False1.3 移除元素
27移除元素
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(1) 额外空间并原地修改输入数组。
可以使用双指针法通过一个快指针和慢指针在一个for循环中完成两个for循环的工作。
定义快慢指针
快指针寻找新数组的元素新数组就是不含有目标元素的数组如果快指针指向的元素不等于val那么它一定是输出数组中的元素所以将其赋值给慢指针的位置慢指针指向更新新数组的下标位置如果快指针指向的元素等于val说明它不是输出数组中的元素我们直接移动快指针即可
双指针的方法在处理数组和链表的操作当中都是非常常见的。
class Solution:def removeElement(self, nums: List[int], val: int) - int:slowIndex: int 0for fastIndex in range(len(nums)):if nums[fastIndex] ! val:nums[slowIndex] nums[fastIndex]slowIndex 1return slowIndexclass Solution:def removeElement(self, nums: List[int], val: int) - int:slowIndex: int 0fastIndex: int 0while fastIndex len(nums):if nums[fastIndex] ! val:nums[slowIndex] nums[fastIndex]slowIndex 1fastIndex 1return slowIndex26删除有序数组中的重复项
class Solution:def removeDuplicates(self, nums: List[int]) - int:fastIndex: int 1slowIndex: int 0while fastIndex len(nums) - 1:if nums[slowIndex] nums[fastIndex]:fastIndex 1elif nums[slowIndex] ! nums[fastIndex]:slowIndex 1nums[slowIndex] nums[fastIndex]return slowIndex 1283移动零
class Solution:def moveZeroes(self, nums: List[int]) - None:Do not return anything, modify nums in-place instead.slowIndex: int 0fastIndex: int 0while fastIndex len(nums) - 1:if nums[fastIndex] ! 0:nums[slowIndex] nums[fastIndex]slowIndex 1fastIndex 1for i in range(slowIndex, fastIndex):nums[i] 01.4 有序数组的平方
977有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。
思路该数组已经知道为有序数组那么数组的中间值的平方一定是最小的最大值一定是从两侧值的平方中进行选取所以我们可以使用左右指针开始查找。
class Solution:def sortedSquares(self, nums: List[int]) - List[int]:leftIndex: int 0rightIndex: int len(nums) - 1resIndex: int len(nums) - 1res: List[any] [float(inf)] * len(nums)while leftIndex rightIndex:elem1 nums[leftIndex] ** 2elem2 nums[rightIndex] ** 2if elem1 elem2:res[resIndex] elem1leftIndex 1else:res[resIndex] elem2rightIndex - 1resIndex - 1return res1.5 长度最小的子数组
209长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] 并返回其长度**。**如果不存在符合条件的子数组返回 0 。
本题采用的思想是滑动窗口滑动窗口可以分为最大滑动窗口和最小滑动窗口具体的区别在于最大滑动窗口目的在于最大化满足条件的区间长度而最小化滑动窗口目的在于最小化满足条件的区间长度。
最小滑窗模板给定数组 nums定义滑窗的左右边界 i, j求满足某个条件的滑窗的最小长度。
while j len(nums):判断[i, j]是否满足条件while 满足条件不断更新结果(注意在while内更新)i 1 最大程度的压缩i使得滑窗尽可能的小j 1最大滑窗模板给定数组 nums定义滑窗的左右边界 i, j求满足某个条件的滑窗的最大长度。
while j len(nums):判断[i, j]是否满足条件while 不满足条件i 1 最保守的压缩i一旦满足条件了就退出压缩i的过程使得滑窗尽可能的大不断更新结果注意在while外更新j 1class Solution:def minSubArrayLen(self, target: int, nums: List[int]) - int:startIndex: int 0result: any float(inf)s: int 0for endIndex in range(len(nums)):s nums[endIndex]while s target:result min(result, endIndex - startIndex 1)s - nums[startIndex]startIndex 1return result if result ! float(inf) else 0defaultdict的用法
python中的defaultdict是collections库中的一种字典与python中默认字典dict的区别在于我们可以指定defaultdict当访问到不存在的key是的返回值比如
from collections import defaultdict
d1 defaultdict(int) #设置d1访问不存在的key时返回0
d2 defaultdict(list) #设置d2访问不存在的key时返回空列表[]
d2 defaultdict(bool) #设置d3访问不存在的key时返回False
print(d1[a])
print(d2[a])
print(d3[a])返回的结果为
0
[]
False904. 水果成篮
class Solution:def totalFruit(self, fruits: List[int]) - int:left: int 0right: int 0result: int 0classMap: dict defaultdict(int) #访问不存在的key返回0classCnt: int 0while right len(fruits) - 1:# 判断是否满足情况if classMap[fruits[right]] 0:classCnt 1classMap[fruits[right]] 1# 当不满情况的时候才对left进行移动这样能够保证滑动窗口为最大while classCnt 2:if classMap[fruits[left]] 1:classCnt - 1classMap[fruits[left]] - 1 left 1# 结果在外面进行更新result max(result, right - left 1)right 1return result76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 。
class Solution:def minWindow(self, s: str, t: str) - str:left: int 0right: int 0strMap: dict collections.defaultdict(int) #访问不存在的key时返回0strCnt: int len(t)result: str for char in t:strMap[char] 1# 移动右边界while right len(s) - 1:# 判断当前字母是否被需要if s[right] in strMap:if strMap[s[right]] 0:strCnt - 1strMap[s[right]] - 1# 压缩左边界while strCnt 0:# 更新resultif not result or right - left 1 len(result):result s[left: right 1]# 判断当前字母是否可压缩if s[left] in strMap:if strMap[s[left]] 0:strCnt 1strMap[s[left]] 1left 1right 1return result1.6 螺旋矩阵II
59. 螺旋矩阵 II
给你一个正整数 n 生成一个包含 1 到 n2 所有元素且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
这道题的重点在于确定循环不变量我们要保证每次循环的写法的区间都具有一致性所以我们在这里采用左闭右开的方式来进行循环。
class Solution:def generateMatrix(self, n: int) - List[List[int]]:nums: List[List[int]] [[0] * n for _ in range(n)]startx: int 0starty: int 0loop: int n // 2count: int 1offset: int 1for _ in range(loop):for j in range(starty, n - offset):nums[startx][j] countcount 1for i in range(startx, n - offset):nums[i][n - offset] countcount 1for j in range(n - offset, starty, -1):nums[n - offset][j] countcount 1for i in range(n - offset, startx, -1):nums[i][starty] countcount 1startx 1starty 1offset 1if n % 2 1:nums[n // 2][n // 2] countreturn nums54. 螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix 请按照 顺时针螺旋顺序 返回矩阵中的所有元素。
class Solution:def spiralOrder(self, matrix: List[List[int]]) - List[int]:m: int len(matrix)n: int len(matrix[0])loop: int min(m, n) // 2print(loop)startx: int 0starty: int 0offset: int 1res: List[int] []for _ in range(loop):for j in range(starty, n - offset):res.append(matrix[startx][j])for i in range(startx, m - offset):res.append(matrix[i][n - offset])for j in range(n - offset, starty, -1):res.append(matrix[m - offset][j])for i in range(m - offset, startx, -1):res.append(matrix[i][starty])startx 1starty 1offset 1if min(m, n) % 2 1:if m n:for j in range(starty, n - (offset-1)): #注意这里转完一圈之后offset实际上是被1了我们需要还原上一圈中的offsetres.append(matrix[startx][j])else:for i in range(startx, m - (offset-1)):res.append(matrix[i][starty])return resReference
[1] Hello 算法 [2] 代码随想录
