# 记矩阵 m
m = [[1,2,3],
[4,5,6],
[7,8,9]]
# 转置
m = [list(it) for it in zip(*m)] # 因为 zip 后返回的是元组，故包了一层转换
# 顺时针旋转 90 度
m = [list(it) for it in zip(*m[::-1])]
# 逆时针旋转 90 度
m = [list(it) for it in zip(*m)][::-1]
# 旋转 180 度
m = [row[::-1] for row in m[::-1]]剑指Offer 2100 调整数组顺序使奇数位于偶数前面 (简单, 2021-11)剑指Offer 2900 顺时针打印矩阵（3种思路4个写法） (中等, 2021-11)剑指Offer 3000 包含min函数的栈 (简单, 2021-11)剑指Offer 3100 栈的压入、弹出序列 (中等, 2021-11)牛客 0018 顺时针旋转矩阵 (简单, 2022-01)牛客 0030 缺失的第一个正整数 (中等, 2022-02)牛客 0038 螺旋矩阵 (中等, 2022-03)牛客 0055 最长公共前缀 (简单, 2022-03)
给定整型数组，调整其顺序，使所有奇数在偶数之前（不要求顺序）。详细描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
提示：
0 <= nums.length <= 50000
0 <= nums[i] <= 10000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 头尾双指针，当头指针指向偶数，尾指针指向奇数时，交换；
- 注意边界判断；
Python
class Solution:
def exchange(self, nums: List[int]) -> List[int]:
l, r = 0, len(nums) - 1
while l < r:
# 注意需要始终保持 l < r
while l < r and nums[l] % 2 == 1:
l += 1
while l < r and nums[r] % 2 == 0:
r -= 1
nums[l], nums[r] = nums[r], nums[l]
return nums
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。详细描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
限制：
0 <= matrix.length <= 100
0 <= matrix[i].length <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 循环遍历 4 个方向的路线，中间做好边界判断（虽然思路简单，但是写起来很容易出错）；
Python：写法1（更朴素）
class Solution:
def spiralOrder(self, matrix: [[int]]) -> [int]:
""""""
ret = []
if not matrix or not matrix[0]:
return ret
m, n = len(matrix), len(matrix[0]) # m行n列
# 设置左、右、上、下边界
l, r, t, b, = 0, n - 1, 0, m - 1
while True:
# 依次遍历 4 个方向
# 因为最后一趟遍历哪个方向都有可能，所以需要 4 个 break
# left to right, top+=1
for i in range(l, r + 1):
ret.append(matrix[t][i])
t += 1
if t > b:
break
# top to bottom, right-=1
for i in range(t, b + 1):
ret.append(matrix[i][r])
r -= 1
if l > r:
break
# right to left, bottom-=1
for i in range(r, l - 1, -1): # 逆序
ret.append(matrix[b][i])
b -= 1
if t > b:
break
# bottom to top, left+=1
for i in range(b, t - 1, -1): # 逆序
ret.append(matrix[i][l])
l += 1
if l > r:
break
return ret- 写法 1 的逻辑足够清晰，但不够通用（优雅），比如要遍历 8 个方向时；
- 另一种写法会预先定义各方向的 step，详见代码；
Python：写法2（更优雅）
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix or not matrix[0]:
return []
# 4 个方向的 step
steps = [(0, 1), (1, 0), (0, -1), (-1, 0)]
m, n = len(matrix), len(matrix[0])
# 法1）使用一个 set 或矩阵记录已经访问过的位置
# visited = set()
# visited = [[False] * n for _ in range(m)] # m行n列
# 法2）直接在 matrix 上修改访问过的位置
visited = 10001
ret = []
i, j = 0, 0 # 记录当前访问的位置
k = 0 # 已经访问过的位置数量
d = 0 # 方向标记
while k < m * n:
ret.append(matrix[i][j])
matrix[i][j] = visited
# visited.add((i, j))
# visited[i][j] = True
k += 1
# 下一个位置
nxt_i, nxt_j = i + steps[d][0], j + steps[d][1]
# 判断下一个位置是否合法，或是否访问过
if not 0 <= nxt_i < m or not 0 <= nxt_j < n or matrix[nxt_i][nxt_j] == visited:
# 如果不合法或已经访问过，进入下一个方向
d = (d + 1) % 4
nxt_i, nxt_j = i + steps[d][0], j + steps[d][1]
i, j = nxt_i, nxt_j
return ret- 每次遍历完最外圈后，递归遍历下一圈；
Python
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
""""""
def dfs(M):
# 注意：这里除了要判断 M，还要判断 M[0]，因为之后代码中的切片操作可能会使行数据为空列表 []
if not M or not M[0]: return []
m, n = len(M), len(M[0])
# 如果最内圈是一行或一列，那么该行/列的遍历方向一定是 左→右 或 上→下
if m == 1:
return M[0]
if n == 1:
return [row[0] for row in M]
# 最外一圈的数据
ret = M[0] \
+ [row[-1] for row in M[1:]] \
+ M[-1][-2::-1] \
+ [row[0] for row in M[-2:0:-1]]
return ret + dfs([row[1:-1] for row in M[1:-1]])
return dfs(matrix)- 每次“削去”矩阵的第一层，然后将矩阵逆时针旋转 90 度，循环削去第一层；
- 而逆时针旋转的操作在 python 中可以用一行代码完成！
Python
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
ret = []
while matrix:
ret += list(matrix.pop(0)) # zip 后的结果是一个元组，这里转成 list，不过实际上不转换也可以；
# 核心操作，逆时针旋转 90 度
matrix = list(zip(*matrix))[::-1]
return ret# 图解 `list(zip(*matrix))[::-1]` 这一步做了什么：
# 假设已经 pop 了第一行，此时矩阵剩余的部分是：
[4 5 6] # 记为 l1
[7 8 9] # 记为 l2，如果有 n 行，则记为 ln
# zip(*matrix) 包含了两个知识点：一个是 zip() 函数，一个是 * 号的作用；
# zip(*matrix) 实际上等价于 zip(l1, l2, ..., ln)
# 经过这一步 matrix 将转化为（相当于做了一次转置）
[4 7]
[5 8]
[6 9]
# 这时再将 matrix 做一次逆序，就得到了逆时针旋转 90 度的结果
[6 9]
[5 8]
[4 7]
实现栈的 pop 和 push 方法，同时实现一个 min 方法，返回栈中的最小值，min、push 及 pop 的时间复杂度都是 O(1)。详细描述
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
提示：
- 各函数的调用总次数不超过 20000 次
- pop、top 和 min 操作总是在 非空栈 上调用。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 使用两个 list: Buf 和 Min；其中 Buf 正常模拟栈，Min 也是一个栈，但是它只会将小于等于栈顶的元素入栈；
- 当 Buf 的出栈元素等于 Min 的栈顶元素时，Min 也出栈；
- Python 中 list 自带的
append和pop方法默认行为就是栈的push和pop，top方法返回Buf[-1]即可；
Python
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.Buf = []
self.Min = []
def push(self, x: int) -> None:
self.Buf.append(x)
if not self.Min or x <= self.Min[-1]: # 注意这里是小于等于
self.Min.append(x)
def pop(self) -> None:
x = self.Buf.pop()
if x == self.Min[-1]:
self.Min.pop()
def top(self) -> int:
return self.Buf[-1]
def min(self) -> int:
return self.Min[-1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
假设压入栈的所有数字均不相等。详细描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
提示：
0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed 是 popped 的排列。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 设置一个模拟栈 s，将 pushed 中的元素顺序入栈；
- 期间，如果 popped 中的元素与 s 栈顶元素相同，则弹出栈顶元素，直到不再相同或 s 为空；
- 当结束循环时，如果 s 不为空，则返回 False，反之 True；
Python
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
s = [] # 模拟栈
# pop(0) 的操作很浪费时间，其实是不需要修改 pushed 和 popped 的，详见优化后的代码
while pushed:
s.append(pushed.pop(0))
while s and s[-1] == popped[0]:
s.pop()
popped.pop(0)
return True if not popped else FalsePython：优化后
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
s = [] # 模拟栈
idx = 0 # popped 索引
for x in pushed:
s.append(x)
while s and s[-1] == popped[idx]:
s.pop()
idx += 1
return True if not s else False
给定 NxN 矩阵，和矩阵的阶数 N，返回顺时针旋转 90 度后的矩阵。- 分两步，先按行逆序，再按列逆序（反过来也可以）；
Python
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param mat int整型二维数组
# @param n int整型
# @return int整型二维数组
#
class Solution:
def rotateMatrix(self , mat: List[List[int]], n: int) -> List[List[int]]:
# write code here
# 法1）先逆序
# return list(zip(*mat[::-1]))
# 法2）后逆序
return [[row[i] for row in mat][::-1] for i in range(n)]
给定一个无重复元素的整数数组nums，请你找出其中没有出现的最小的正整数
要求：空间复杂度 O(1)，时间复杂度 O(n)- 利用数组下标记录出现过的正数
写法1：先移除非正数
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型
#
class Solution:
def minNumberDisappeared(self , nums: List[int]) -> int:
# write code here
# 倒序移除所有非正数
for i in range(len(nums) - 1, -1, -1):
if nums[i] <= 0:
nums.pop(i)
# 利用数组下标这一隐含变量记录出现过的正数，避免使用额外空间
N = len(nums)
for x in nums:
x = abs(x)
if 0 < x <= N:
nums[x - 1] = -abs(nums[x - 1])
# 找到第一个非负数数，其下标就是没出现过的最小正数，如果没有，那么最小正数就是 N+1
for i in range(N):
if nums[i] > 0:
return i + 1
return N + 1写法2：修改非正数
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型
#
class Solution:
def minNumberDisappeared(self , nums: List[int]) -> int:
# write code here
N = len(nums)
# 将所有非正数修改为 N+1
for i in range(N):
if nums[i] <= 0:
nums[i] = N + 1
# 利用数组下标这一隐含变量记录出现过的正数，避免使用额外空间
for x in nums:
x = abs(x)
if 0 < x <= N:
nums[x - 1] = -abs(nums[x - 1])
# 找到第一个非负数数，其下标就是没出现过的最小正数，如果没有，那么最小正数就是 N+1
for i in range(N):
if nums[i] > 0:
return i + 1
return N + 1
给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。- 把矩阵及其元素看作坐标中的点，初始定义左上角和右下角两个点
(0, 0)和(m, n)； - 然后根据要求，每次打印一圈，注意边界条件，详见代码；
Python
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param matrix int整型二维数组
# @return int整型一维数组
#
class Solution:
def spiralOrder(self , M: List[List[int]]) -> List[int]:
# write code here
if not M: return []
ret = []
def dfs(a, b, c, d):
# 打印一行 (a,b) -> (a, d)
if a == c:
t = b
while t <= d:
ret.append(M[a][t])
t += 1
# 打印一列 (a, d) -> (c, d)
elif b == d:
t = a
while t <= c:
ret.append(M[t][b])
t += 1
# 打印一圈
else:
# 左到右: (a,b) -> (a, d-1)
t = b
while t < d:
ret.append(M[a][t])
t += 1
# 上到下: (a, d) -> (c-1, d)
t = a
while t < c:
ret.append(M[t][d])
t += 1
# 右到左: (c, d) -> (c, b+1)
t = d
while t > b:
ret.append(M[c][t])
t -= 1
# 下到上: (c, b) -> (a-1, b)
t = c
while t > a:
ret.append(M[t][b])
t -= 1
a, b, c, d = 0, 0, len(M) - 1, len(M[0]) - 1
while a <= c and b <= d:
dfs(a, b, c, d)
a, b = a + 1, b + 1
c, d = c - 1, d - 1
return ret
给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。- 利用 Python 内置的
zip函数每次纵向取所有字符串的第i个字符； - 对这些字符
set后，如果都相同，则加入前缀，否则退出循环，返回结果；
Python
class Solution:
def longestCommonPrefix(self , strs: List[str]) -> str:
ret = []
for it in zip(*strs):
if len(set(it)) == 1:
ret.append(it[0])
else:
break
return ''.join(ret)