- 最小覆盖子串">最小覆盖子串
- 无重复字符的最长子串">无重复字符的最长子串
- 判断是否是子序列">判断是否是子序列
- 三数之和">三数之和
- 四数之和">四数之和
- 平方数之和">平方数之和
- 删除有序数组中的重复项">删除有序数组中的重复项
- 删除有序数组中的重复项 II">删除有序数组中的重复项 II
- 字符串的排列*">字符串的排列*
- 滑动窗口最大值*">滑动窗口最大值*
- 合并两个有序数组">合并两个有序数组
- 调整数组顺序使奇数位于偶数前面">调整数组顺序使奇数位于偶数前面
- 长度最小的子数组*">长度最小的子数组*
- 二维数组中的查找(双指针)">二维数组中的查找(双指针)
- 旋转矩阵">旋转矩阵
- 二维数组求每列的最小值
- 盛最多水的容器">盛最多水的容器
- 接雨水">接雨水
- 颜色分类">颜色分类
- 螺旋矩阵,顺时针打印矩阵">螺旋矩阵,顺时针打印矩阵
核心:使用快慢指针
滑动窗口算法的思路是这样:
- 我们在字符串 S 中使用双指针中的左右指针技巧,初始化 left = right = 0,把索引闭区间 [left, right] 称为一个「窗口」。
- 我们先不断地增加 right 指针扩大窗口 [left, right],直到窗口中的字符串符合要求(包含了 T 中的所有字符)。
- 此时,我们停止增加 right,转而不断增加 left 指针缩小窗口 [left, right],直到窗口中的字符串不再符合要求(不包含 T 中的所有字符了)。同时,每次增加 left,我们都要更新一轮结果。
- 重复第 2 和第 3 步,直到 right 到达字符串 S 的尽头。
这个思路其实也不难,第 2 步相当于在寻找一个「可行解」,然后第 3 步在优化这个「可行解」,最终找到最优解。左右指针轮流前进,窗口大小增增减减,窗口不断向右滑动。
模版:
"""给定待查串s和目标串t"""
need, window = {}, {}
for c in t:
记录need # 视具体问题而定
left, right = 0, 0
valid = 0
while right < len(s): # 窗口右边界不断扩大,本质是搜索问题的可能解
c = s[right] # 即将加入到窗口中的字符
right += 1
更新窗口中的数据
while 满足窗口收缩条件: # 窗口的左边界收缩,本质是优化可行解
记录或返回结果
d = s[left] # 即将从窗口中删除的字符
left += 1
更新窗口中的数据
return 结果
最小覆盖子串
给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字母的最小子串。
输入: S = “ADOBECODEBANC”, T = “ABC”
输出: “BANC”
class Solution:
def minWindow(self, s, t):
# 只要保证窗口(队列)字符串含有t中字符的个数大于等于t里相应元素个数
# 这种方法key不存在不会报错
from collections import defaultdict
lookup = defaultdict(int)
for c in t:
lookup[c] += 1
right = 0
left = 0
min_len = float("inf") # 正无穷
counter = len(t)
res = ""
# right指针小于len(s)的情况下,用counter计数器记录left到right之间的s的子串包含t的数量
while right < len(s):
if lookup[s[right]] > 0:
counter -= 1
lookup[s[right]] -= 1
right += 1
# 如果s在left到right之间的子串完全包含t,即满足counter = 0 时,通过不断缩小left来缩小窗口
while counter == 0:
# 记录最小值和res
if min_len > right - left:
min_len = right - left
res = s[left:right]
# left向右移动的过程,如果匹配字母被去掉,counter要更新
if lookup[s[left]] == 0:
counter += 1
lookup[s[left]] += 1
left += 1
return res
无重复字符的最长子串
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
class Solution(object):
def lengthOfLongestSubstring(self, s):
# 方法一:快慢指针+散列表,cur先走,遇到重复的就移动pre到第一个重复的cur位置
if len(s) == 0:
return 0
dicts = {}
pre = 0
cur = 0
max_p = 0
while cur < len(s):
if s[cur] in dicts:
# 将pre移动到cur的位置
pre = max(pre, dicts[s[cur]] + 1)
dicts[s[cur]] = cur
max_p = max(max_p, cur-pre + 1)
cur += 1
return max_p
判断是否是子序列
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,”ace”是”abcde”的一个子序列,而”aec”不是)。
s = “abc”, t = “ahbgdc”
返回 true.
s = “axc”, t = “ahbgdc”
返回 false.
class Solution(object):
def isSubsequence(self, s, t):
cur = 0
pre = 0
while cur < len(s) and pre < len(t):
if s[cur] == t[pre]:
cur += 1
pre += 1
else:
pre += 1
if cur == len(s):
return True
else:
return False
三数之和
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
输入:nums = []
输出:[]
# 固定一个指针,然后创建另外两个指针,一个放前面,一个放后面,
class Solution(object):
def threeSum(self, nums):
# 方法一:三个指针,固定一个,另外两个滑动窗口,去重放里面
if not nums or len(nums) < 3:
return []
nums.sort()
res = []
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i - 1]:
continue
left = i + 1
right = len(nums) - 1
while left < right:
if nums[i] + nums[left] + nums[right] == 0:
res.append([nums[i], nums[left], nums[right]])
# 去重
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
elif nums[i] + nums[left] + nums[right] > 0:
right -= 1
else:
left += 1
return res
# 方法二:三个指针,感觉这种更好理解,固定一个,另外两个滑动窗口,去重放外面
if not nums or len(nums) < 3:
return []
lists = []
nums.sort()
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
left = i + 1
right = len(nums) - 1
while left < right:
if nums[i] + nums[left] + nums[right] == 0:
lists.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
elif nums[i] + nums[left] + nums[right] > 0:
right -= 1
else:
left += 1
# 去重
res = []
for j in lists:
if j not in res:
res.append(j)
return res
四数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。
注意:答案中不可以包含重复的四元组。
输入:nums = [1,0,-1,0,-2,2], target = 0
输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
输入:nums = [], target = 0
输出:[]
class Solution(object):
def fourSum(self, nums, target):
# 方法一:四个指针,固定两个,另外两个滑动窗口,去重放里面
lists = []
nums.sort()
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
left = j + 1
right = len(nums) - 1
while right > left:
if nums[i] + nums[j] + nums[left] + nums[right] == target:
lists.append((nums[i], nums[j], nums[left], nums[right]))
left += 1
right -= 1
elif nums[i] + nums[j] + nums[left] + nums[right] > target:
right -= 1 # 太大了,右指针左移
else:
left += 1 # 反之
# 去重
res = []
for j in lists:
if j not in res:
res.append(j)
return res
class Solution(object):
def fourSum(self, nums, target):
# 方法二:递归,对于n数之和问题,固定第1个数,即变成求n-1数之和的问题,固定前两个数,就变成了求n-2个数之和的问题,最基本的情况就是求两数之和问题
if len(nums) < 4:
return []
def dfs(nums, n, target):
if len(nums) < n:
return []
res = []
if n == 2:
left, right = 0, len(nums)-1
while left < right:
if nums[left] + nums[right] == target:
res.append([nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
elif nums[left] + nums[right] > target:
right -= 1
else:
left += 1
return res
else:
for first_idx in range(len(nums)):
if first_idx > 0 and nums[first_idx] == nums[first_idx-1]:
continue
subres = dfs(nums[first_idx+1:], n-1, target-nums[first_idx])
for i in range(len(subres)):
res.append([nums[first_idx]] + subres[i])
return res
nums.sort()
return dfs(nums, 4, target)
平方数之和
给定一个非负整数 c ,你要判断是否存在两个整数 a 和 b,使得 a2 + b2 = c 。
输入:c = 5
输出:true
解释:1 1 + 2 2 = 5
输入:c = 3
输出:false
输入:c = 4
输出:true
class Solution(object):
def judgeSquareSum(self, c):
# 这种开平方的题都比较死,掌握
left = 0
right = int(c**0.5)
while left <= right:
tmp = left*left + right*right
if tmp > c:
right -= 1
elif tmp < c:
left += 1
else:
return True
return False
删除有序数组中的重复项
给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
class Solution:
def removeDuplicates(self, nums):
# 快慢指针,把所有重复的值都一点点换到最后
if not nums:
return 0
left, right = 0, 0
while left < len(nums):
if nums[left] == nums[right]:
left += 1
else:
right += 1
nums[right] = nums[left]
return right + 1
删除有序数组中的重复项 II
给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 最多出现两次 ,返回删除后数组的新长度。
输入:nums = [1,1,1,2,2,3]
输出:5, nums = [1,1,2,2,3]
输入:nums = [0,0,1,1,1,1,2,3,3]
输出:7, nums = [0,0,1,1,2,3,3]
class Solution(object):
def removeDuplicates(self, nums):
left = 0
right = 0
while right < len(nums):
if left < 2 or nums[right] != nums[left-2]:
nums[left] = nums[right]
left += 1
right += 1
return left
# 数据结果
# [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
# [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
# [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
# [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
# [0, 0, 1, 1, 2, 2, 2, 3, 3, 4]
# [0, 0, 1, 1, 2, 2, 2, 3, 3, 4]
# [0, 0, 1, 1, 2, 2, 3, 3, 3, 4]
# [0, 0, 1, 1, 2, 2, 3, 3, 3, 4]
# [0, 0, 1, 1, 2, 2, 3, 3, 4, 4]
字符串的排列*
给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。
换句话说,第一个字符串的排列之一是第二个字符串的 子串 。
输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).
输入: s1= “ab” s2 = “eidboaoo”
输出: False
class Solution(object):
def checkInclusion(self, s1, s2):
# 因为 s1 的字母的顺序不要求,所以判断是 s2 的子串只要,字母的个数相同即可
first = {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
second = {'a': 0, 'b': 0, 'c': 0, 'd': 0, 'e': 0, 'f': 0, 'g': 0, 'h': 0, 'i': 0, 'j': 0, 'k': 0, 'l': 0, 'm': 0, 'n': 0, 'o': 0, 'p': 0, 'q': 0, 'r': 0, 's': 0, 't': 0, 'u': 0, 'v': 0, 'w': 0, 'x': 0, 'y': 0, 'z': 0}
for i in s1:
first[i] += 1
for i in range(len(s2)):
second[s2[i]] += 1
# 窗口比s1大时,要把前面的元素删掉
if i >= len(s1):
second[s2[i-len(s1)]] -= 1
if first == second:
return True
return False
滑动窗口最大值*
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
———————- ——-
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
输入:nums = [1], k = 1
输出:[1]
class Solution(object):
def maxSlidingWindow(self, nums, k):
# 方法一:使用双端队列,并且存入index
queue = []
res = []
for i in range(len(nums)):
# 如果当前元素大于单调队列中的尾端元素的话:pop单调队列中的尾端元素
while queue and nums[queue[-1]] < nums[i]:
queue.pop()
queue.append(i)
# 当单调队列的第一个元素(即最大的元素)不在[i - k + 1, i],
# 说明该最大元素在当前的窗口之外,则pop(0)单调队列中的第一个元素
if queue[0] <= i - k:
queue.pop(0)
# 在当前index >= k - 1的时候(即这时候已经能够构成长度为k的窗口)把单调队列的第一个元素加入到结果中去
if i >= k - 1:
res.append(nums[queue[0]])
return res
合并两个有序数组
给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
class Solution:
def merge(self, nums1, m, nums2, n):
# 方法一:正向双指针,空间复杂度On
cur = 0
pre = 0
res = []
nums1[:] = nums1[:m]
while cur < m and pre < n:
if nums1[cur] < nums2[pre]:
res.append(nums1[cur])
cur += 1
else:
res.append(nums2[pre])
pre += 1
if pre < n:
res += nums2[pre:]
else:
res += nums1[cur:]
nums1[:] = res
return nums1
# 方法二:最优解,逆向双指针,空间复杂度是常数,直接在nums1的末尾更新
cur = m - 1
pre = n - 1
tmp = m + n - 1
while cur >= 0 and pre >= 0:
if nums1[cur] < nums2[pre]:
nums1[tmp] = nums2[pre]
pre -= 1
tmp -= 1
else:
nums1[tmp] = nums1[cur]
cur -= 1
tmp -= 1
# nums2没有遍历完
nums1[:pre + 1] = nums2[:pre + 1]
return nums1
调整数组顺序使奇数位于偶数前面
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。
输入:nums = [1,2,3,4]
输出:[1,3,2,4]
注:[3,1,2,4] 也是正确的答案之一。
class Solution(object):
def exchange(self, nums):
# 方法一:暴力法
odd = [] # 奇数
even = [] # 偶数
for i in nums:
if i % 2 == 0: # i 是偶数:
even.append(i)
else:
odd.append(i)
return odd + even
# 方法二:left向右移找偶数,right向左移找奇数,交换left和right所指数字
left = 0
right = len(nums) -1
while left < right:
while left < right and nums[left] % 2 == 1:
left += 1
while left < right and nums[right] % 2 == 0:
right -=1
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return nums
长度最小的子数组*
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
输入:target = 4, nums = [1,4,4]
输出:1
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0
class Solution(object):
def minSubArrayLen(self, target, nums):
res = 0
count = len(nums) + 1
left = 0
right = 0
while right < len(nums):
res += nums[right]
while res >= target:
count = min(right-left+1, count)
res -= nums[left]
left += 1
right += 1
if count == len(nums) + 1:
return 0
else:
return count
二维数组中的查找(双指针)
在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
现有矩阵 matrix 如下:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5
,返回 true
。
给定 target = 20
,返回 false
。
class Solution(object):
def findNumberIn2DArray(self, matrix, target):
# 从左下角开始判断,如果大target就向上移动,如果小于target就向右移动
if not matrix:
return False
x = 0
y = len(matrix) - 1
while x < len(matrix[0]) and y >= 0:
if matrix[y][x] > target:
y -= 1
elif matrix[y][x] < target:
x += 1
else:
return True
return False
# 从右上角开始
if not matrix:
return False
x = len(matrix[0]) - 1
y = 0
while x >= 0 and y <len(matrix):
if matrix[y][x] > target:
x -= 1
elif matrix[y][x] < target:
y += 1
else:
return True
return False
旋转矩阵
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
输入:matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出:[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
输入:matrix = [[1]]
输出:[[1]]
class Solution(object):
def rotate(self, matrix):
# 方法一:只支持正方形
# 上下翻转
matrix[:] = matrix[::-1]
# 左右翻转
for i in range(len(matrix[0])):
for j in range(i, len(matrix)):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
return matrix
# 方法二:只支持正方形,空间复杂度On2
matrix_new = [[0] * len(matrix) for _ in range(len(matrix))]
for i in range(len(matrix)):
for j in range(len(matrix)):
matrix_new[j][len(matrix)-i-1] = matrix[i][j]
matrix[:] = matrix_new
return matrix
二维数组求每列的最小值
martix = [
[72, 76, 44, 62, 81, 31],
[54, 36, 82, 71, 40, 45],
[63, 59, 84, 36, 34, 51],
[58, 53, 59, 22, 77, 64],
[35, 77, 60, 76, 57, 44]]
# 方法一:暴力法
res = []
# 因为是6列,所以得把[0]放在前面
for i in range(len(martix[0])):
tmp = []
for j in range(len(martix)):
tmp.append(martix[j][i])
res.append(min(tmp))
print(res)
# 方法二:翻转过来,如果是正方形可以用上面的方法旋转,如果是长方形翻转需要占用额外的空间,所以用暴力法就行
盛最多水的容器
给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
class Solution(object):
def maxArea(self, height):
# 矩阵的面积与两个因素有关
# 1.两条垂直线的距离
# 2.两条垂直线其中较短一条的长度
left = 0
right = len(height) - 1
res = 0
while left < right:
# 两条垂直线的距离
min_x = right-left
# 两条垂直线其中较短一条的长度
min_y = min(height[right], height[left])
# 求面积
res = max(res, min_x * min_y)
if height[right] > height[left]:
left += 1
else:
right -= 1
return res
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
输入:height = [4,2,0,3,2,5]
输出:9
class Solution(object):
def trap(self, height):
left = 0
right = len(height) - 1
leftMax = 0
rightMax = 0
# 记录总面积
res = 0
while left < right:
# 使用height[left]和height[right]的值更新leftMax和rightMax的值
leftMax = max(leftMax, height[left])
rightMax = max(rightMax, height[right])
# 如果height[left] < height[right],则必有leftMax < rightMax,下标left处能接的雨水量等于leftMax−height[left],将下标left处能接的雨水量加到能接的雨水总量,然后将left加1(即向右移动一位)
if height[left] < height[right]:
res += leftMax - height[left]
left += 1
# 如果height[left] >= height[right],则必有leftMax >= rightMax,下标right处能接的雨水量等于rightMax−height[right],将下标right 处能接的雨水量加到能接的雨水总量,然后将right减1(即向左移动一位)
else:
res += rightMax - height[right]
right -= 1
return res
颜色分类
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
输入:nums = [2,0,2,1,1,0]
输出:[0,0,1,1,2,2]
输入:nums = [2,0,1]
输出:[0,1,2]
输入:nums = [0]
输出:[0]
class Solution(object):
def sortColors(self, nums):
# 方法一:好理解,第一次把0都换回来,第二次再第一次位置的基础上把1都换回来
cur = 0
for i in range(len(nums)):
if nums[i] == 0:
nums[i], nums[cur] = nums[cur], nums[i]
cur += 1
for i in range(cur, len(nums)):
if nums[i] == 1:
nums[i], nums[cur] = nums[cur], nums[i]
cur += 1
return nums
# 方法二:双指针,如果是1就直接交换位置,如果是0还需要和1比较一次大小
p0 = 0
p1 = 0
for i in range(len(nums)):
if nums[i] == 1:
nums[i], nums[p1] = nums[p1], nums[i]
p1 += 1
elif nums[i] == 0:
nums[i], nums[p0] = nums[p0], nums[i]
if p0 < p1:
nums[i], nums[p1] = nums[p1], nums[i]
p0 += 1
p1 += 1
return nums
螺旋矩阵,顺时针打印矩阵
给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。
输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]
class Solution(object):
def spiralOrder(self, matrix):
if not matrix:
return []
res = []
# 表示从左数第l列
left = 0
# 总列数
right = len(matrix[0]) - 1
# 表示从上数第t层
above = 0
# 总层数
below = len(matrix) - 1
while True:
# 从左到右
for i in range(left, right + 1):
res.append(matrix[above][i])
above += 1
if above > below:
break
# 从上到下
for i in range(above, below + 1):
res.append(matrix[i][right])
right -= 1
if left > right:
break
# 从右到左
for i in range(right, left - 1, -1):
res.append(matrix[below][i])
below -= 1
if above > below:
break
# 从下到上
for i in range(below, above - 1, -1):
res.append(matrix[i][left])
left += 1
if left > right:
break
return res