文章目录
- 剑指 Offer 04. 二维数组中的查找
- 代码实现
- 解题方案 + 思路
- 算法步骤
- 其他实现思路——二分查找
- 其他实现思路_变形的二分法
- 剑指 Offer 05. 替换空格
- 题目描述
- 代码实现
- 解题方案 + 思路
- 算法步骤
- 方法总结
- 剑指 Offer 11. 旋转数组的最小数字 – 解决方案
- 题目描述
- 代码实现
- 解题方案 + 思路
- 算法步骤
- 算法思路(二分)
- 剑指 Offer 17. 打印从 1 到最大的 n 位数
- 题目描述
- 解题方案
- 思路 1
- 思路 2
- 【其他】全排列解法简洁版
- 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
- 题目描述
- 解题方案
- 思路
- 算法流程
- 解题思路(双指针):
- tips:
- 其他做法——快慢双指针
- 剑指 Offer 29. 顺时针打印矩阵
- 题目描述
- 解题方案
- 思路
- 算法流程
- 代码实现
- 方法解析——按层模拟
- 复杂度分析
剑指 Offer 04. 二维数组中的查找
在一个 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
限制:
0 <= n <= 1000
0 <= m <= 1000
代码实现
class Solution:def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:row=len(matrix)-1col=0while( row>=0 and col<len(matrix[0]) ):if(matrix[row][col]==target):return Trueelse:if(matrix[row][col]>target):row=row-1else:col=col+1return False
解题方案 + 思路
- 标签:数组遍历
- 从矩阵的左下角看,上方的数字都比其小,右方的数字都比其大,所以依据该规律去判断数字是否存在
- 设当前数字为
cur
,目标数字为target
- 当
target < cur
时,cur 更新为其上面的数字 - 当
target > cur
时,cur 更新为其右侧的数字
- 当
- 直到相等则返回
true
,否则到了矩阵边界返回false
- 设当前数字为
- 时间复杂度:
O(m+n)
算法步骤
其他实现思路——二分查找
- 看到有序,第一反应就是二分查找。最直接的做法,一行一行的进行二分查找即可。
此外,结合有序的性质,一些情况可以提前结束。
- 比如某一行的第一个元素大于了 target ,当前行和后边的所有行都不用考虑了,直接返回 false。
- 某一行的最后一个元素小于了 target ,当前行就不用考虑了,换下一行。
本题没有确保「每行的第一个整数大于前一行的最后一个整数」,因此我们无法采取「两次二分」的做法。
- 只能退而求之,遍历行/列,然后再对列/行进行二分。
时间复杂度的话,如果是 m 行 n 列,就是 O(mlog(n))
。
import numpy as npclass Solution(object):def searchMatrix(self, matrix, target):""":type matrix: List[List[int]]:type target: int:rtype: bool"""matrix = np.array(matrix)row = matrix.shape[0]col = matrix.shape[1]flag =0for row in matrix:left = 0right = col-1while(left<=right):mid = (left+right+1)/2if row[mid]<target:left=mid+1elif row[mid]>target:right=mid-1else:return Truereturn False
其他实现思路_变形的二分法
二分法的思想就是,目标值和中点值进行比较,然后可以丢弃一半的元素。
- 这道题的话是矩阵
- 如果我们找到矩阵的中心,然后和目标值比较看能不能丢弃一些元素。
如下图,中心位置是 9[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]通过中心位置, 我们可以把原矩形分成四个矩形, 左上, 右上, 左下, 右下[1, 4,7 [11, 15 2, 5,812, 19 3, 6, /9/]16, 22][10, 13, 14 [17, 24[18, 21, 23] 26, 30]如果 target = 10,此时中心值小于目标值,左上角矩形中所有的数都小于目标值,我们可以丢弃左上角的矩形,继续从剩下三个矩形中寻找如果 target = 5,此时中心值大于目标值,右下角矩形中所有的数都大于目标值,那么我们可以丢弃右下角的矩形,继续从剩下三个矩形中寻找
我们找到了丢弃元素的原则,可以写代码了。
这里的话,矩形我们用左上角和右下角坐标的形式表示,下图是分割后矩形的坐标情况。
我们可以用递归的形式去写,
- 递归出口的话,当矩阵中只有一个元素,直接判断当前元素是不是目标值即可。
还有就是分割的时候可能越界,
- 比如原矩阵只有一行,左下角和右下角的矩阵其实是不存在的,
- 按照上边的坐标公式计算出来后,我们要判断一下是否越界。
剑指 Offer 05. 替换空格
题目描述
请实现一个函数,把字符串 s
中的每个空格替换成 “%20”。
示例 1:
- 输入:s = “We are happy.”
- 输出:“We%20are%20happy.”
限制:
0 <= s 的长度
<= 10000
代码实现
Python简单法:
class Solution:def replaceSpace(self, s: str) -> str:return "%20".join(s.split(' '))
Python法:
class Solution {public:string replaceSpace(string s) {for(int i = 0; i < s.length(); i++){if(s.find(" ") == i){s.erase(i, 1);s.insert(i, "%20");}}return s;}};
class Solution(object):def replaceSpace(self, s):""":type s: str:rtype: str"""s1=""for c in s:if c == ' ': s1 += '%20'else:s1 +=creturn s1
C++:
class Solution {public:string replaceSpace(string s) {for(int i = 0; i < s.length(); i++){if(s.find(" ") == i){ # 查找到空格所在的位置s.erase(i, 1); # 先清除空格所占的一个字符s.insert(i, "%20"); # 在该位置插入%20}}return s;}};
解题方案 + 思路
- 标签:字符串
- 最简单的方案自然是直接使用库函数啦!当然题目肯定是不希望我们这样做的!
- 增加一个新字符串,遍历原来的字符串,遍历过程中,
- 如果非空格则将原来的字符直接拼接到新字符串中
- 如果遇到空格则将
%20
拼接到新字符串中
- 时间复杂度:
O(n)
,空间复杂度:O(n)
算法步骤
方法总结
法一:遍历添加
在 Python 和 Java 等语言中,字符串都被设计成「不可变」的类型,即无法直接修改字符串的某一位字符,需要新建一个字符串实现。
算法流程:
- 初始化一个 list (Python) / StringBuilder (Java) ,记为
res
; - 遍历列表
s
中的每个字符c
:- 当
c
为空格时:向res
后添加字符串"%20"
; - 当
c
不为空格时:向res
后添加字符c
;
- 当
- 将列表
res
转化为字符串并返回。
复杂度分析:
- 时间复杂度 O(N) : 遍历使用 O(N) ,每轮添加(修改)字符操作使用 O(1) ;
- 空间复杂度 O(N): Python 新建的 list 和 Java 新建的 StringBuilder 都使用了线性大小的额外空间。
方法二:原地修改
在 C++ 语言中, string 被设计成「可变」的类型(参考资料),因此可以在不新建字符串的情况下实现原地修改。
- 由于需要将空格替换为 “%20” ,字符串的总字符数增加,因此需要扩展原字符串 s 的长度,
- 计算公式为:新字符串长度 = 原字符串长度 + 2 * 空格个数 ,
- 示例如下图所示。
算法流程:
- 初始化:空格数量
count
,字符串 s 的长度len
; - 统计空格数量:遍历 s ,遇空格则
count++
; - 修改 s 长度:添加完 “%20” 后的字符串长度应为
len + 2 * count
; - 倒序遍历修改:
i
指向原字符串尾部元素,j
指向新字符串尾部元素;- 当 i = j 时跳出(代表左方已没有空格,无需继续遍历);
- 当 s[i] 不为空格时:执行
s[j] = s[i]
; - 当 s[i] 为空格时:将字符串闭区间
[j-2, j]
的元素修改为"%20"
;由于修改了 3 个元素,因此需要j -= 2
;
- 返回值:已修改的字符串
s
;
复杂度分析:
- 时间复杂度 O(N) : 遍历统计、遍历修改皆使用 O(N)时间。
- 空间复杂度 O(1): 由于是原地扩展 s 长度,因此使用 O(1)额外空间。
class Solution {public:string replaceSpace(string s) {int count = 0, len = s.size();// 统计空格数量for (char c : s) {if (c == ' ') count++;}// 修改 s 长度s.resize(len + 2 * count);// 倒序遍历修改for(int i = len - 1, j = s.size() - 1; i < j; i--, j--) {if (s[i] != ' ')s[j] = s[i];else {s[j - 2] = '%';s[j - 1] = '2';s[j] = '0';j -= 2;}}return s;}};
剑指 Offer 11. 旋转数组的最小数字 – 解决方案
题目描述
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
- 输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。
- 例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。
- 注意,数组
[a[0], a[1], a[2], ..., a[n-1]]
旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]
。
示例 1:
- 输入:[3,4,5,1,2]
- 输出:1
示例 2:
- 输入:[2,2,2,0,1]
- 输出:0
提示:
- n ==
numbers.length
- 1 <=
n
<= 5000 - -5000 <=
numbers[i]
<= 5000 - numbers 原来是一个升序排序的数组,并进行了 1 至 n 次旋转
代码实现
- python遍历
class Solution:def minArray(self, numbers: List[int]) -> int:j=numbers[0]for i in range(len(numbers)):if j<=numbers[i]:j=jelse:j=numbers[i]return j
- 二分法
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]: left = mid + 1elif nums[mid] < nums[right]: right = midelse: right = right - 1 # keyreturn nums[left]
解题方案 + 思路
- 标签:二分查找
- 整体思路:
- 首先数组是一个有序数组的旋转,从这个条件可以看出,数组是有大小规律的,
- 可以使用二分查找利用存在的规律快速找出结果
- 时间复杂度:O(logn),空间复杂度:O(1)
算法步骤
- 初始化下标
left
和right
- 每次计算中间下标
mid = (right + left) / 2
,这里的除法是取整运算,不能出现小数
- 当
numbers[mid] < numbers[right]
时,说明最小值在 [left, mid]
区间中,则令right = mid
,用于下一轮计算 - 当
numbers[mid] > numbers[right]
时,说明最小值在[mid, right]
区间中,则令left = mid + 1
,用于下一轮计算 - 【注意】当
numbers[mid] == numbers[right]
时,无法判断最小值在哪个区间之中,此时让right--
,缩小区间范围,在下一轮进行判断
为什么是 right– 缩小范围,而不是 left++?
- 因为数组是升序的,所以最小值一定靠近左侧,而不是右侧
- 比如,当存在 [1,2,2,2,2] 这种情况时,left = 0,right = 4,mid = 2,数值满足
numbers[mid] == numbers[right]
这个条件,如果 left++,则找不到最小值
算法思路(二分)
- 旋转排序数组
nums
可以被拆分为 2 个排序数组 nums1 , nums2,并且 nums1任一元素 >= nums2任一元素;因此,考虑二分法寻找此两数组的分界点 nums[i] (即第 2 个数组的首个元素)。 - 设置 left, right 指针在 nums数组两端,mid为每次二分的中点:
- 当
nums[mid] > nums[right]
时,mid一定在第 1 个排序数组中,iii 一定满足 mid < i <= right,因此执行 left = mid + 1; - 当
nums[mid] < nums[right]
时,mid 一定在第 2 个排序数组中,iii 一定满足 left < i <= mid,因此执行 right = mid; - 当
nums[mid] == nums[right]
时,是此题对比 153题 的难点(原因是此题中数组的元素可重复,难以判断分界点 iii 指针区间);- 例如 [1,0,1,1,1],在 left = 0, right = 4, mid = 2 时,无法判断 midmidmid 在哪个排序数组中。
- 我们采用
right = right - 1
解决此问题,证明:- 此操作不会使数组越界:因为迭代条件保证了 right > left >= 0;
- 此操作不会使最小值丢失:假设 nums[right] 是最小值,有两种情况:
- 若 nums[right]是唯一最小值:那就不可能满足判断条件 nums[mid] == nums[right],因为 mid < right(left != right 且 mid = (left + right) // 2 向下取整);
- 若 nums[right]不是唯一最小值,由于 mid < right 而 nums[mid] == nums[right],即还有最小值存在于 [left,right−1] 区间,因此不会丢失最小值。
- 当
以上是理论分析,可以代入以下数组辅助思考:
[1,2,3]
[1,1,0,1]
[1,0,1,1,1]
[1,1,1,1]
- 时间复杂度 O(logN),在特例情况下会退化到 O(N)(例如 [1,1,1,1])。
剑指 Offer 17. 打印从 1 到最大的 n 位数
题目描述
输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。
- 比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。
示例 1:
- 输入:
n = 1
- 输出:
[1,2,3,4,5,6,7,8,9]
说明:
- 用返回一个整数列表来代替打印
- n 为正整数
解题方案
思路 1
标签:数组
整体思路:
- 首先求出要打印的数字范围,
- 然后再从 1 开始打印到最大的数字
时间复杂度:O(1 0 n10 ^n 10n ),空间复杂度:O(1 0 n10 ^n 10n )
算法流程
- 初始化
sum = 1
- 循环遍历乘 10 让 sum 变为边界值
- 新建 res 数组,大小为
sum-1
- 从 1 开始打印,直到 sum-1 为止
class Solution(object):def printNumbers(self, n):""":type n: int:rtype: List[int]"""max = 10**(n)list=[]for i in range(1,max):list.append(i)return list
思路 2
标签:字符串
整体思路:
- 原题的题意其实是希望考察大数计算,因为 int 数组有可能会溢出,所以用字符串处理可以保证一定不会溢出,
- 但是呢,由于返回值规定是 int 数组,所以其实从返回值上来看,是一定不会溢出的,比较矛盾。
- 所以给出个思路 2,学习下如何用字符串处理大数即可,不用特别纠结溢出这件事情
时间复杂度:O(1 0 n10 ^n 10n ),空间复杂度:O(1 0 n10 ^n 10n )
算法流程
- 初始化字符串
str
,另其初始值为 n-1 个"0"
- 递增 str,使用字符去递增
- 递增过程中判断是否存在进位,存在进位则进位处 +1,
- 直到达到最大值为止,结束循环
- 每获取到一个值之后,遍历前方多余的 “0”,将多余的 “0” 去掉
- 转换为 int 存到结果数组中
【大数问题!】实际上,本题的主要考点是大数越界情况下的打印。
需要解决以下三个问题:
表示大数的变量类型:
- 无论是
short / int / long
… 任意变量类型,数字的取值范围都是有限的。 - 因此,大数的表示应用字符串 String 类型。
- 无论是
生成数字的字符串集:
- 使用
int
类型时,每轮可通过+1
生成下个数字,而此方法无法应用至 String 类型。 - 并且, String 类型的数字的进位操作效率较低,例如 “9999” 至 “10000” 需要从个位到千位循环判断,进位 4 次。
- 观察可知,生成的列表实际上是
n
位 000 – 999 的 全排列 ,因此可避开进位操作,通过递归生成数字的 String 列表。
- 使用
递归生成全排列:
- 基于分治算法的思想,先固定高位,向低位递归,当个位已被固定时,添加数字的字符串。
- 例如当
n=2
时(数字范围 1−991 – 991−99 ),固定十位为 000 – 999 ,按顺序依次开启递归,固定个位 000 – 999 ,终止递归并添加数字字符串。
根据以上方法,可初步编写全排列代码:
class Solution:def printNumbers(self, n: int) -> [int]:def dfs(x):if x == n: # 终止条件:已固定完所有位res.append(''.join(num)) # 拼接 num 并添加至 res 尾部returnfor i in range(10): # 遍历 0 - 9num[x] = str(i) # 固定第 x 位为 idfs(x + 1) # 开启固定第 x + 1 位num = ['0'] * n # 起始数字定义为 n 个 0 组成的字符列表res = [] # 数字字符串列表dfs(0) # 开启全排列递归return ','.join(res)# 拼接所有数字字符串,使用逗号隔开,并返回
在此方法下,各数字字符串被逗号隔开,共同组成长字符串。
返回的数字集字符串如下所示:
输入:n = 1输出:"0,1,2,3,4,5,6,7,8,9"输入:n = 2输出:"00,01,02,...,10,11,12,...,97,98,99"输入:n = 3输出:"000,001,002,...,100,101,102,...,997,998,999"
观察可知,当前的生成方法仍有以下问题:
- 诸如 00,01,02,⋯,⋯ 应显示为 0,1,2,⋯
- 即应 删除高位多余的 0 ;
- 此方法从
0
开始生成,而题目要求 列表从1
开始 ;
以上两个问题的解决方法如下:
- 删除高位多余的 0 :
字符串左边界定义:
- 声明变量
start
规定字符串的左边界,以保证添加的数字字符串num[start:]
中无高位多余的 0 。 - 例如当 n=2 时, 1−9 时 start=1 , 10−99 时 start=0。
- 声明变量
左边界 start 变化规律:
- 观察可知,当输出数字的所有位都是 9 时,则下个数字需要向更高位进 1,此时左边界 start 需要减 1 (即高位多余的 0 减少一个)。
- 例如当 n=3(数字范围 1−999 )时,左边界 start 需要减 1 的情况有: “009” 进位至 “010” , “099” 进位至 “100” 。
- 设数字各位中 999 的数量为 nine ,所有位都为 9 的判断条件可用以下公式表示:
n − s t a r t = n i n en−start=ninen−start=nine
统计
nine
的方法:- 固定第 xx x 位时,当 i=9i=9 i=9 则执行 nine=nine+1nine=nine+1 nine=nine+1 ,
- 并在回溯前恢复 nine=nine−1nine=nine−1 nine=nine−1
- 列表从 1 开始:
- 在以上方法的基础上,添加数字字符串前判断其是否为 “0” ,若为 “0” 则直接跳过。
复杂度分析:
- 时间复杂度 O(1 0 n)O(10^n) O(10n): 递归的生成的排列的数量为 1 0 n10^n 10n
- 空间复杂度 O(1 0 n)O(10^n) O(10n): 结果列表 res 的长度为 1 0 n−110^n – 1 10n−1,各数字字符串的长度区间为 1,2,…,n1,2,…,n 1,2,…,n,因此占用 O(1 0 n)O(10^n) O(10n)大小的额外空间。
为 正确表示大数 ,以下代码的返回值为数字字符串集拼接而成的长字符串。
class Solution:def printNumbers(self, n: int) -> [int]:def dfs(x):if x == n:s = ''.join(num[self.start:])if s != '0': res.append(s)if n - self.start == self.nine: self.start -= 1returnfor i in range(10):if i == 9: self.nine += 1num[x] = str(i)dfs(x + 1)self.nine -= 1num, res = ['0'] * n, []self.nine = 0self.start = n - 1dfs(0)return ','.join(res)
本题要求输出 int 类型数组。
- 为 运行通过 ,可在添加数字字符串 s前,将其转化为 int 类型。
代码如下所示:
class Solution:def printNumbers(self, n: int) -> [int]:def dfs(x):if x == n:s = ''.join(num[self.start:])if s != '0': res.append(int(s))if n - self.start == self.nine: self.start -= 1returnfor i in range(10):if i == 9: self.nine += 1num[x] = str(i)dfs(x + 1)self.nine -= 1num, res = ['0'] * n, []self.nine = 0self.start = n - 1dfs(0)return res
【其他】全排列解法简洁版
在数字很大的情况下,哪怕long类型也无法承载,那必须要用字符串保存。
- 对于本题其实就是对数字09的全排列,到n位数0~9的全排列,其中要注意的是数字开头不应该有0。
简单提一下全排列,比如对于数字1,2,3的全排列是:
123, 132, 213, 231, 312, 321
为了能够测试通过,最后把字符串形式变成了int形式,其实应该返回字符串数组
以下是具体步骤
- 为了避免数字开头出现 00 0 ,先把首位
first
固定,first
取值范围为191~9 19 - 用
digit
表示要生成的数字的位数,本题要从 11 1 位数一直生成到 nn n 位数,对每种数字的位数都生成一下首位,所以有个双重for循环 - 生成首位之后进入递归生成剩下的
digit - 1
位数,从 0到90 到 9 0到9 中取值 - 递归的中止条件为已经生成了
digit
位的数字,即index == digit
,将此时的数 num转为int加到结果res中
class Solution:def printNumbers(self, n: int) -> List[int]:def dfs(index, num, digit):if index == digit:res.append(int(''.join(num)))returnfor i in range(10):num.append(str(i))dfs(index + 1, num, digit)num.pop()res = []for digit in range(1, n + 1):for first in range(1, 10):num = [str(first)]dfs(1, num, digit)return res
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
题目描述
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,
- 使得所有奇数位于数组的前半部分,
- 所有偶数位于数组的后半部分。
示例:
- 输入:
nums = [1,2,3,4]
- 输出:
[1,3,2,4]
- 注:
[3,1,2,4]
也是正确的答案之一。
- 注:
提示:
- 1 <=
nums.length
<= 50000 - 1 <=
nums[i]
<= 10000
解题方案
思路
- 标签:双指针
- 整体思路:
- 首先指定前指针
start
和后指针end
, - 然后前指针定位偶数,后指针定位奇数,
- 定位到之后将两个值互换,直到数组遍历完成
- 首先指定前指针
- 时间复杂度:
O(n)
,空间复杂度:O(1)
算法流程
- 初始化前指针
start = 0
,后指针end = nums.length - 1
- 当
start < end
时表示该数组还未遍历完成,则继续进行奇数和偶数的交换 - 当
nums[start]
为奇数时,则start++
,直到找到不为奇数的下标为止 - 当
nums[end]
为偶数时,则end--
,直到找到不为偶数的下标为止 - 交换
nums[start]
和nums[end]
,继续下一轮交换 - 返回
nums
,即为交换后的结果
- 普通遍历法
class Solution(object):def exchange(self, nums):""":type nums: List[int]:rtype: List[int]"""List1 = []List2 = []for i in nums:if (i % 2) == 0:List1.append(i)else:List2.append(i)List2.extend(List1)return List2
- 双指针法
class Solution(object):def exchange(self, nums):start = 0end = len(nums)-1while(start < end):while(nums[start] %2 != 0) and start < end:start+=1while(nums[end]%2 ==0)and start < end:end-=1tmp = nums[start]nums[start] = nums[end]nums[end] = tmpstart+=1end-=1return nums
解题思路(双指针):
考虑定义双指针 iii , jjj 分列数组左右两端,循环执行:
- 指针 ii i 从左向右寻找偶数;
- 指针 jj j 从右向左寻找奇数;
- 将 偶数 nums[i]nums[i] nums[i] 和 奇数 nums[j]nums[j] nums[j] 交换。
===> 可始终保证: 指针 iii 左边都是奇数,指针 jjj右边都是偶数 。
算法流程:
初始化: i , j 双指针,分别指向数组 nums 左右两端;
循环交换: 当 i = ji=ji=j 时跳出;
- 指针 i 遇到奇数则执行 i=i+1i=i+1 i=i+1 跳过,直到找到偶数;
- 指针 j 遇到偶数则执行 j=j−1j=j−1 j=j−1 跳过,直到找到奇数;
- 交换
nums[i]
和nums[j]
值;
返回值: 返回已修改的 nums 数组。
复杂度分析:
- 时间复杂度 O(N)O(N) O(N) : NN N 为数组 nums 长度,双指针 i,ji, j i,j共同遍历整个数组。
- 空间复杂度 O(1)O(1) O(1) : 双指针 i,ji, j i,j 使用常数大小的额外空间
代码:
x & 1
位运算 等价于 x % 2
取余运算,即皆可用于判断数字奇偶性。
class Solution:def exchange(self, nums: List[int]) -> List[int]:i, j = 0, len(nums) - 1while i < j:while i < j and nums[i] & 1 == 1: i += 1while i < j and nums[j] & 1 == 0: j -= 1nums[i], nums[j] = nums[j], nums[i]return nums
tips:
- 快速排序的基础
- 就是快速排序的将小于基点的放前面, 大于基点的放后面
其他做法——快慢双指针
- 定义快慢双指针 fast 和 low ,fast 在前, low 在后 .
- fast 的作用是向前搜索奇数位置,low 的作用是指向下一个奇数应当存放的位置
- fastfast fast 向前移动,当它搜索到奇数时,将它和 n u m s [ l o w ]nums[low]nums[low] 交换,此时 l o wlowlow 向前移动一个位置 .
- 重复上述操作,直到 fast 指向数组末尾 .
class Solution {public:vector<int> exchange(vector<int>& nums) {int low = 0, fast = 0;while (fast < nums.size()) {if (nums[fast] & 1) {swap(nums[low], nums[fast]);low ++;}fast ++;}return nums;}};
剑指 Offer 29. 顺时针打印矩阵
题目描述
输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1:
- 输入:matrix=[[1,2,3],[4,5,6],[7,8,9]]matrix = [[1,2,3],[4,5,6],[7,8,9]] matrix=[[1,2,3],[4,5,6],[7,8,9]]
- 输出:[1,2,3,6,9,8,7,4,5][1,2,3,6,9,8,7,4,5] [1,2,3,6,9,8,7,4,5]
示例 2:
- 输入:matrix=[[1,2,3,4],[5,6,7,8],[9,10,11,12]]matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 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][1,2,3,4,8,12,11,10,9,5,6,7] [1,2,3,4,8,12,11,10,9,5,6,7]
限制:
- 0<=matrix.length<=1000 <= matrix.length <= 100 0<=matrix.length<=100
- 0<=matrix[i].length<=1000 <= matrix[i].length <= 100 0<=matrix[i].length<=100
解题方案
思路
- 标签:二维数组
- 整体思路:
- 循环遍历整个数组,循环中再嵌套四个循环,
- 分别是从左至右,从上至下,从右至左,从下至上这几个方向,
- 按照题意将整个数组遍历完成,控制好边界
- mm m 为行数,nn n 为列数,时间复杂度:O(mn)O(mn) O(mn),空间复杂度:O(1)O(1) O(1)
算法流程
- 题目中 matrixmatrix matrix 有可能为空,直接返回空数组即可
- 初始化边界 left、right、top、bottomleft、right、top、bottom left、right、top、bottom 四个值,初始化结果数组 resres res 和数组下标 xx x
- 按照遍历方向循环取出数字放入结果数组中
- 从左至右:遍历完成后
++top
,如果 top>bottomtop > bottom top>bottom,到达边界循环结束 - 从上至下:遍历完成后
--right
,如果 left>rightleft > right left>right,到达边界循环结束 - 从右至左:遍历完成后
--bottom
,如果 top>bottomtop > bottom top>bottom,到达边界循环结束 - 从下至上:遍历完成后
++left
,如果 left>rightleft > right left>right,到达边界循环结束
- 从左至右:遍历完成后
代码实现
- 遍历的策略:遍历到底
class Solution(object):def spiralOrder(self, matrix):""":type matrix: List[List[int]]:rtype: List[int]"""if len(matrix) ==0 : return None# if not matrix or not matrix[0]:# return list()right = len(matrix[0])-1bottom = len(matrix)-1top =0left=0res = []maxSize = (right+1)*(bottom+1)while(maxSize>0):for i in range(left,right+1):if maxSize>0:res.append(matrix[top][i])maxSize-=1top+=1for j in range(top,bottom+1):if maxSize>0:res.append(matrix[j][right])maxSize-=1right-=1for k in range(right,left-1,-1):if maxSize>0:res.append(matrix[bottom][k])maxSize-=1bottom-=1for l in range(bottom,top-1,-1):if maxSize>0:res.append(matrix[l][left])maxSize-=1left+=1return res
方法解析——按层模拟
- 可以将矩阵看成若干层
- 首先,输出最外层的元素
- 其次,输出次外层的元素
- 直到,输出最内层的元素。
定义矩阵的第 kkk 层是到最近边界距离为 kkk 的所有顶点。
- 例如,下图矩阵最外层元素都是第 11 1 层,次外层元素都是第 22 2 层,剩下的元素都是第 33 3 层。
[[1, 1, 1, 1, 1, 1, 1], [1, 2, 2, 2, 2, 2, 1], [1, 2, 3, 3, 3, 2, 1], [1, 2, 2, 2, 2, 2, 1], [1, 1, 1, 1, 1, 1, 1]]
对于每层,从左上方开始以顺时针的顺序遍历所有元素。
- 假设当前层的左上角位于
(top,left)
,右下角位于(bottom,right)
,按照如下顺序遍历当前层的元素。
- 从左到右遍历上侧元素,依次为 (top,left) 到 (top,right)。
- 从上到下遍历右侧元素,依次为 (top+1,right) 到 (bottom,right)。
- 如果 left<right且top<bottomleft<right 且 top<bottom left<right且top<bottom,则从右到左遍历下侧元素,依次为
- (bottom,right−1) 到 (bottom,left+1)
- 以及从下到上遍历左侧元素,依次为
- (bottom,left) 到 (top+1,left)。
遍历完当前层的元素之后,
- 将 left和topleft 和 top left和top 分别增加 1,
- 将 right和bottomright 和 bottom right和bottom 分别减少 1,
- 进入下一层继续遍历,
- 直到遍历完所有元素为止。
class Solution:def spiralOrder(self, matrix: List[List[int]]) -> List[int]:if not matrix or not matrix[0]:return list()rows, columns = len(matrix), len(matrix[0])order = list()left, right, top, bottom = 0, columns - 1, 0, rows - 1while left <= right and top <= bottom:for column in range(left, right + 1):order.append(matrix[top][column])for row in range(top + 1, bottom + 1):order.append(matrix[row][right])if left < right and top < bottom:for column in range(right - 1, left, -1):order.append(matrix[bottom][column])for row in range(bottom, top, -1):order.append(matrix[row][left])left, right, top, bottom = left + 1, right - 1, top + 1, bottom - 1return order
复杂度分析
- 时间复杂度:O(mn),其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。
- 空间复杂度:O(1)。除了输出数组以外,空间复杂度是常数。