-
一、数组经典题型
* 前言
后续题目基于基础算法部分，请参考：算法刷题总结 (一) 数组
1、元素查找 (暴力解法、二分查找)
35.搜索插入位置
(1). 暴力解法，遍历列表：
class Solution: def searchInsert(self, nums: List[int], target: int) -> int: # 分别处理如下三种情况 # 目标值在数组所有元素之前 # 目标值等于数组中某一个元素 # 目标值插入数组中的位置 for i in range(len(nums)): # 一旦发现大于或者等于target的num[i]，那么i就是我们要的结果 if nums[i]>=target: return i # 目标值在数组所有元素之后的情况 # 如果target是最大的，或者 nums为空，则返回nums的长度 return len(nums)- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
(2). 二分法，二分列表：
class Solution: def searchInsert(self, nums: List[int], target: int) -> int: # 分别处理如下四种情况 # 目标值在数组所有元素之前 [0, -1] # 目标值等于数组中某一个元素 return middle; # 目标值插入数组中的位置 [left, right]，return right + 1 # 目标值在数组所有元素之后的情况 [left, right]， 因为是右闭区间，所以 return right + 1 # 1. 使用二分法快速查找(比遍历快)，如果能找到target，返回索引 left, right = 0, len(nums)-1 # 定义target在左闭右闭的区间里，[left, right] while left<=right: mid = (left+right)//2 if nums[mid]>target: # target 在左区间，所以[left, middle - 1] right = mid-1 elif nums[mid]<target: # target 在右区间，所以[middle + 1, right] left = mid +1 else: return mid # 2. 如果找不到 # 返回right+1 或者 返回 left return left- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
一个简单的中间过程
nums = [1,2,5,8,10] target = 9 searchInsert(nums, target) """ [left, right]: [0, 4] [left, right]: [3, 4] [left, right]: [4, 4] [left, right]: [4, 3] # 交叉退出 """- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
暴力与二分法的区别在于暴力是遍历列表，而二分法是二分查找，速度相对快。
34.在排序数组中查找元素的第一个和最后一个位置
(1). 暴力法：
class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: if target in nums: start = nums.index(target) end = len(nums)-(nums[::-1].index(target)+1) return [start, end] return [-1, -1]- 1
- 2
- 3
- 4
- 5
- 6
- 7
(2). 二分法：
""" 寻找target在数组里的左右边界，有如下三种情况： 情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1} 情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1} 情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1} """ class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: # 二分查找，寻找target的右边界（不包括target） # 如果rightBorder为没有被赋值（即target在数组范围的左边，例如数组[3,3]，target为2），为了处理情况一 def getRightBorder(nums:List[int], target:int) -> int: # 定义target在左闭右闭的区间里，[left, right] left, right = 0, len(nums)-1 # 记录一下rightBorder没有被赋值的情况 rightBoder = -2 # 当left==right，区间[left, right]依然有效 while left <= right: middle = left + (right-left) // 2 if nums[middle] > target: right = middle - 1 # 当nums[middle] == target的时候，更新left，这样才能得到target的右边界 # 寻找右边界，nums[middle] == target的时候更新left else: left = middle + 1 rightBoder = left return rightBoder def getLeftBorder(nums:List[int], target:int) -> int: left, right = 0, len(nums)-1 leftBoder = -2 # 记录一下leftBorder没有被赋值的情况 while left <= right: middle = left + (right-left) // 2 if nums[middle] >= target: # 寻找左边界，nums[middle] == target的时候更新right right = middle - 1; leftBoder = right; else: left = middle + 1 return leftBoder leftBoder = getLeftBorder(nums, target) rightBoder = getRightBorder(nums, target) # 情况一 if leftBoder == -2 or rightBoder == -2: return [-1, -1] # 情况三 if rightBoder -leftBoder >1: return [leftBoder + 1, rightBoder - 1] # 情况二 return [-1, -1]- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
69.x的平方根
二分法：
class Solution: def mySqrt(self, x: int) -> int: left, right, ans = 0, x, -1 # 遍历整数的平方，最大的小于x的值就是结果 while left<=right: # 不断找中值分界点 mid = (left+right)//2 # 不断将结果存起来，最后更新保存的结果为最大值 if mid*mid<=x: ans = mid left = mid + 1 # 缩减大的值 else: right = mid - 1 return ans- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
此题还有牛顿迭代法解，只是套用一个公式。
367.有效的完全平方数
二分法：
class Solution: def isPerfectSquare(self, num: int) -> bool: left, right, ans = 0, num, False while left<=right: mid = (left+right)//2 if mid*mid<num: left = mid+1 elif mid*mid>num: right = mid-1 else: ans=True return ans return ans- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
875.爱吃香蕉的珂珂
暴力解法（超时）:
class Solution: def minEatingSpeed(self, piles: List[int], h: int) -> int: # 最慢一次吃一根，最快按最大值去吃每棵树，时间为树的个数 # 遍历，寻找某个最小速度，使时间刚好为h for i in range(1, max(piles)+1): nums = 0 # 遍历树 for j in piles: # 累加每棵树的次数 nums = nums + math.ceil(j/i) # 第一次累计到h，就为吃的最慢，并且在警卫来之前走 # 后面存在时间还为h，但是速度稍微快一些的情况，这个就不符合题意了 if h==nums: return i- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
双指针法：
接着上一个代码进行修改，因为是遍历查找，所以可以使用快速查找的算法，二分法。class Solution: def minEatingSpeed(self, piles: List[int], h: int) -> int: # 最慢一次吃一根，最快按最大值去吃每棵树，时间为树的个数 # 遍历，寻找某个最小速度，使时间刚好为h left, right = 1, max(piles) while left<=right: # 代替循环 for i in range(1, max(piles)+1):直接选取中点为速度 mid = (left+right)//2 # 累积时间 nums = 0 # 遍历树 for j in piles: # 累加每棵树的次数 nums = nums + math.ceil(j/mid) # 时间花的过多，增加速度, if nums>h: left = mid+1 else: right = mid-1 # 最后的mid与h可能不相等，不能为判断条件 return left- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
注意这个例子：
piles,h = [312884470], 312884469
v只能取2，但是取2后，时间最多只能为156442235，不可能等于h，因为若等于1则又超时。
那么，二分法的条件判断，不能以nums==h为条件，最后倒数第二步为left=right=1，nums
2、元素移除 (暴力解法、双指针法)
26.删除有序数组中的重复项
leetcode链接
注意：当删除单个重复元素时，list可以无序，而删除多个重复元素时，保持相似的算法步骤则需要list有序，(这道题也指明了有序)，否则需要较多的更改逻辑结构，比如下面(2)中的第二个解法。(1). 暴力遍历：
class Solution: def removeDuplicates(self, nums: List[int]) -> int: # 选取所有不重复，待遍历的元素 for i in set(nums): # 设置计数器，方便后续大于1则删除 count = 0 # 遍历新创建的列表，防止删除原列表造成索引位移 for j in nums[:]: # 重复则+1 if i==j: count+=1 # 多于一次重复则删除，否则不管 if count>1: nums.remove(i) return len(nums)- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
(2). 快慢指针：
class Solution: def removeDuplicates(self, nums: List[int]) -> int: fast = 0 slow = 0 while fast<len(nums): if nums[fast] != nums[slow]: # 下一个索引赋值给新的不重复的值 slow+=1 nums[slow] = nums[fast] fast+=1 # 这里要+1，表示下一位，即表示数组有效长度。 # 因为原快慢指针算法，上面slow+1是在赋值之后，而这里是在赋值之前。 return slow+1- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
第二个解法，可以删除无序list的重复元素，但较多的修改了原算法：
class Solution: def removeDuplicates(self, nums: List[int]) -> int: fast = 0 # 从1开始，因为nums[:0]为空，慢指针这相当于取了域值，而不是前面的单个值 slow = 1 while fast<len(nums): # 这里取nums的slow索引之前的所有值进行重复元素的排查 if nums[fast] not in nums[:slow]: # 相当于slow的阈值扩展 nums[slow] = nums[fast] # 指向下一个待扩展进阈值的索引 slow+=1 fast+=1 return slow- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
283.移动零
leetcode链接
(1). 暴力遍历：class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ for i in nums[:]: # 查询到0就删除原表的0，结尾添加0 if i==0: nums.remove(0) nums.append(0)- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
(2). 快慢指针：
先快慢指针把非零的选出来，再根据slow的长度将list后续非有效部分变成0class Solution: def moveZeroes(self, nums: List[int]) -> None: fast = 0 slow = 0 while fast<len(nums): if nums[fast] != 0: nums[slow] = nums[fast] slow += 1 fast+=1 nums[slow:]=[0]*(len(nums)-slow)- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
每次遇到0就交换，把0换到fast的索引位置，把非0的值换到slow的位置，最后0都在结尾。有点类似冒泡。
class Solution: def moveZeroes(self, nums: List[int]) -> None: fast = 0 slow = 0 while fast<len(nums): if nums[fast] != 0: nums[slow], nums[fast] = nums[fast], nums[slow] slow += 1 fast+=1- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
844.比较含退格的字符串
leetcode链接
(1). 重构字符串：class Solution: def backspaceCompare(self, s: str, t: str) -> bool: def change(x): tmp = [] for p in x: if p != '#': tmp.append(p) elif tmp: tmp.pop() return ''.join(tmp) return change(s) == change(t)- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
(2). 双指针：
class Solution: def backspaceCompare(self, S: str, T: str) -> bool: i, j = len(S) - 1, len(T) - 1 skipS = skipT = 0 while i >= 0 or j >= 0: while i >= 0: if S[i] == "#": skipS += 1 i -= 1 elif skipS > 0: skipS -= 1 i -= 1 else: break while j >= 0: if T[j] == "#": skipT += 1 j -= 1 elif skipT > 0: skipT -= 1 j -= 1 else: break if i >= 0 and j >= 0: if S[i] != T[j]: return False elif i >= 0 or j >= 0: return False i -= 1 j -= 1 return True- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
977.有序数组的平方
leetcode链接
(1). 重构后排序：class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: nums = list(map(lambda x:x**2, nums)) nums.sort() return nums- 1
- 2
- 3
- 4
- 5
(2). 双指针法：
参考答案
3、长度最小的子数组(暴力解法、滑动窗口)
904.水果成篮
(1). 暴力遍历：
算法同上，但会超时。(2). 滑动窗口：
因为普通算法会超时，这里用Counter进行存储每次遍历的值。def totalFruit(fruits): # ind表示起始点 # s用来存储最大长度 ind,s = 0,0 # 使用Counter，累次计数，不然会超时 d = Counter() # 开始遍历 for i in range(len(fruits)): print('-------------------------------') # 计数 d[fruits[i]]+= 1 print(d) # 种类大于2则删除起始元素 # 该被删除的元素有多少个数，起始点就后移多少位 while len(d)>2: print('***1***') print('d1',d) print('dd',fruits[ind]) # 起始点前移，减去起始点一次 # 如果减到0则删除，避免占用一个种类 d[fruits[ind]]-=1 if d[fruits[ind]] == 0: del d[fruits[ind]] print('d2',d) # 起始点前移 ind += 1 print('***2***') # 选取原长度与处理后(删除或增加后)的长度的最大长度保留下来 s = max(s, i-ind+1) print(s) return s test = [3,3,3,1,2,1,1,2,3,3,4] totalFruit(test)- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
结果打印：
------------------------------- Counter({3: 1}) 1 ------------------------------- Counter({3: 2}) 2 ------------------------------- Counter({3: 3}) 3 ------------------------------- Counter({3: 3, 1: 1}) 4 ------------------------------- Counter({3: 3, 1: 1, 2: 1}) ***1*** d1 Counter({3: 3, 1: 1, 2: 1}) dd 3 d2 Counter({3: 2, 1: 1, 2: 1}) ***2*** ***1*** d1 Counter({3: 2, 1: 1, 2: 1}) dd 3 d2 Counter({3: 1, 1: 1, 2: 1}) ***2*** ***1*** d1 Counter({3: 1, 1: 1, 2: 1}) dd 3 d2 Counter({1: 1, 2: 1}) ***2*** 4 ------------------------------- Counter({1: 2, 2: 1}) 4 ------------------------------- Counter({1: 3, 2: 1}) 4 ------------------------------- Counter({1: 3, 2: 2}) 5 ------------------------------- Counter({1: 3, 2: 2, 3: 1}) ***1*** d1 Counter({1: 3, 2: 2, 3: 1}) dd 1 d2 Counter({1: 2, 2: 2, 3: 1}) ***2*** ***1*** d1 Counter({1: 2, 2: 2, 3: 1}) dd 2 d2 Counter({1: 2, 2: 1, 3: 1}) ***2*** ***1*** d1 Counter({1: 2, 2: 1, 3: 1}) dd 1 d2 Counter({1: 1, 2: 1, 3: 1}) ***2*** ***1*** d1 Counter({1: 1, 2: 1, 3: 1}) dd 1 d2 Counter({2: 1, 3: 1}) ***2*** 5 ------------------------------- Counter({3: 2, 2: 1}) 5 ------------------------------- Counter({3: 2, 2: 1, 4: 1}) ***1*** d1 Counter({3: 2, 2: 1, 4: 1}) dd 2 d2 Counter({3: 2, 4: 1}) ***2*** 5 5- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
76.最小覆盖子串
(1). 暴力遍历：
方法同上，但会超时(2). 滑动窗口：
大致思路同上，但是这里需要加上flag进行判断，进入while循环，也就是起始点后移的的条件，因为字母会出现重复增删，flag只计算一次，d仍然需要计算每次改变。def minWindow(s, t): ind,l = 0,'*'*len(s)+'*' # 动态改变 d = Counter(t) # while判断 flag = Counter(t) print('d:',d) # 遍历s for i in range(len(s)): print('-------------------------') print('1l',l) # s出现在t中 if s[i] in d: d[s[i]] -= 1 # 为0则t中都出现过，小于0则出现的次数多于t # flag变为0，表示出现过 if d[s[i]] <= 0: flag[s[i]]=0 print('1d:',d) # 缩小窗口，前移起始索引 print('******************') while sum(flag.values()) == 0: # 缩小前，保留值 print('cmp:', l, s[ind:i+1]) l = min(l, s[ind:i+1], key=len) # 如果删的是t中的字符，d中减去 if s[ind] in d: d[s[ind]] +=1 # 待出现的数量大于等于标准 # flag变为1表示没出现 if d[s[ind]]>0: flag[s[ind]]=1 # 索引前移 ind += 1 print('******************') print('2l',l) print('2d:',d) print('ind, end', ind, i) return '' if l == '*'*len(s)+'*' else l a="ADOBECODEBANC" b="ABC" # "BANC" minWindow(a,b)- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
结果过程展示：
d: Counter({'A': 1, 'B': 1, 'C': 1}) ------------------------- 1l ************** 1d: Counter({'B': 1, 'C': 1, 'A': 0}) ****************** ****************** 2l ************** 2d: Counter({'B': 1, 'C': 1, 'A': 0}) ind, end 0 0 ------------------------- 1l ************** 1d: Counter({'B': 1, 'C': 1, 'A': 0}) ****************** ****************** 2l ************** 2d: Counter({'B': 1, 'C': 1, 'A': 0}) ind, end 0 1 ------------------------- 1l ************** 1d: Counter({'B': 1, 'C': 1, 'A': 0}) ****************** ****************** 2l ************** 2d: Counter({'B': 1, 'C': 1, 'A': 0}) ind, end 0 2 ------------------------- 1l ************** 1d: Counter({'C': 1, 'A': 0, 'B': 0}) ****************** ****************** 2l ************** 2d: Counter({'C': 1, 'A': 0, 'B': 0}) ind, end 0 3 ------------------------- 1l ************** 1d: Counter({'C': 1, 'A': 0, 'B': 0}) ****************** ****************** 2l ************** 2d: Counter({'C': 1, 'A': 0, 'B': 0}) ind, end 0 4 ------------------------- 1l ************** 1d: Counter({'A': 0, 'B': 0, 'C': 0}) ****************** cmp: ************** ADOBEC ****************** 2l ADOBEC 2d: Counter({'A': 1, 'B': 0, 'C': 0}) ind, end 1 5 ------------------------- 1l ADOBEC 1d: Counter({'A': 1, 'B': 0, 'C': 0}) ****************** ****************** 2l ADOBEC 2d: Counter({'A': 1, 'B': 0, 'C': 0}) ind, end 1 6 ------------------------- 1l ADOBEC 1d: Counter({'A': 1, 'B': 0, 'C': 0}) ****************** ****************** 2l ADOBEC 2d: Counter({'A': 1, 'B': 0, 'C': 0}) ind, end 1 7 ------------------------- 1l ADOBEC 1d: Counter({'A': 1, 'B': 0, 'C': 0}) ****************** ****************** 2l ADOBEC 2d: Counter({'A': 1, 'B': 0, 'C': 0}) ind, end 1 8 ------------------------- 1l ADOBEC 1d: Counter({'A': 1, 'C': 0, 'B': -1}) ****************** ****************** 2l ADOBEC 2d: Counter({'A': 1, 'C': 0, 'B': -1}) ind, end 1 9 ------------------------- 1l ADOBEC 1d: Counter({'A': 0, 'C': 0, 'B': -1}) ****************** cmp: ADOBEC DOBECODEBA cmp: ADOBEC OBECODEBA cmp: ADOBEC BECODEBA cmp: ADOBEC ECODEBA cmp: ADOBEC CODEBA ****************** 2l ADOBEC 2d: Counter({'C': 1, 'A': 0, 'B': 0}) ind, end 6 10 ------------------------- 1l ADOBEC 1d: Counter({'C': 1, 'A': 0, 'B': 0}) ****************** ****************** 2l ADOBEC 2d: Counter({'C': 1, 'A': 0, 'B': 0}) ind, end 6 11 ------------------------- 1l ADOBEC 1d: Counter({'A': 0, 'B': 0, 'C': 0}) ****************** cmp: ADOBEC ODEBANC cmp: ADOBEC DEBANC cmp: ADOBEC EBANC cmp: EBANC BANC ****************** 2l BANC 2d: Counter({'B': 1, 'A': 0, 'C': 0}) ind, end 10 12 'BANC'- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
239.滑动窗口最大值
滑动窗口
class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: n = len(nums) # 注意 Python 默认的优先队列是小根堆 q = [(-nums[i], i) for i in range(k)] # 将列表转化为堆 heapq.heapify(q) # 最大值为堆顶 ans = [-q[0][0]] for i in range(k, n): # 插入一个值以及索引 heapq.heappush(q, (-nums[i], i)) # 不用每次删除窗口外的值，而是当最大值在窗口外再进行删除 # 判断堆顶是否在窗口外 while q[0][1] <= i - k: # 在窗口外则弹出 heapq.heappop(q) # 每次存储堆顶为最大值 ans.append(-q[0][0]) return ans- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
4、过程模拟 (无算法，逻辑思维理解)
54.螺旋矩阵
过程模拟：
套用螺旋矩阵二的模板：class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: # 存储遍历的值 res = [] # 长和宽 length, width = len(matrix), len(matrix[0]) # 上下左右走一圈的次数，最小边长整除2 loop = min(length, width)//2 # 起始点，用来定位遍历点 startx, starty = 0, 0 # 开始循环 for offset in range(1,loop+1): # 从左到右，左闭右开 for i in range(starty, width-offset): res.append(matrix[startx][i]) # 从上到下，上闭下开 for i in range(startx, length-offset): res.append(matrix[i][width-offset]) # 从右到左，右闭左开 for i in range(width-offset, starty, -1): res.append(matrix[length-offset][i]) # 从下到上，下闭上开 for i in range(length-offset, startx, -1): res.append(matrix[i][starty]) # 起始点下移 startx += 1 starty += 1 # 为正方形时，当为奇数，中间有一个点没被遍历到，手动添加，为中点 if length == width and length%2!=0: res.append(matrix[length//2][length//2]) # 为非长方形时 else: # 短的边为奇数时，添加没被遍历到的点 if width>length and length%2!=0: for i in range(width-length+1): res.append(matrix[length//2][i+loop]) elif width<length and width%2!=0: for i in range(length-width+1): res.append(matrix[i+loop][width//2]) return res- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
剑指Offer29.顺时针打印矩阵
思路同上：
class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: res = [] if matrix: length, width = len(matrix),len(matrix[0]) loop = min(length, width)//2 startx, starty = 0, 0 for offset in range(1, loop+1): for i in range(starty, width-offset): res.append(matrix[startx][i]) for i in range(startx, length-offset): res.append(matrix[i][width-offset]) for i in range(width-offset, starty, -1): res.append(matrix[length-offset][i]) for i in range(length-offset, startx, -1): res.append(matrix[i][starty]) startx+=1 starty+=1 if length==width and length%2!=0: res.append(matrix[length//2][length//2]) else: if length>width and width%2!=0: for i in range(length-width+1): res.append(matrix[i+loop][width//2]) elif length<width and length%2!=0: for i in range(width-length+1): res.append(matrix[length//2][i+loop]) return res else: return res- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
参考
-
相关阅读:
Logstash对接 SNMP v2和 v3
阿里云云边一体容器架构创新论文被云计算顶会 ACM SoCC 录用
删除两个字典中非公共的键和值
力扣刷题：169. 多数元素
运维工程师面试题及答案(网络运维工程师面试题)
【操作系统 | Linux】 文件管理四件套（切换,创建删除，复制移动）
YOLOv5的Tricks | 【Trick12】YOLOv5使用的数据增强方法汇总
实现客户端pineline的思路
C#语言实例源码系列-实现自定义屏保
flutter解决多个类名重名问题
- 原文地址：https://blog.csdn.net/weixin_44225602/article/details/126796991
