文章目录

    • 剑指 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 等语言中,字符串都被设计成「不可变」的类型,即无法直接修改字符串的某一位字符,需要新建一个字符串实现。

算法流程:

  1. 初始化一个 list (Python) / StringBuilder (Java) ,记为 res
  2. 遍历列表 s 中的每个字符 c
    • c 为空格时:向 res 后添加字符串 "%20"
    • c 不为空格时:向 res 后添加字符 c
  3. 将列表res 转化为字符串并返回。

复杂度分析:

  • 时间复杂度 O(N) : 遍历使用 O(N) ,每轮添加(修改)字符操作使用 O(1) ;
  • 空间复杂度 O(N): Python 新建的 list 和 Java 新建的 StringBuilder 都使用了线性大小的额外空间。

方法二:原地修改
在 C++ 语言中, string 被设计成「可变」的类型(参考资料),因此可以在不新建字符串的情况下实现原地修改。

  • 由于需要将空格替换为 “%20” ,字符串的总字符数增加,因此需要扩展原字符串 s 的长度,
  • 计算公式为:新字符串长度 = 原字符串长度 + 2 * 空格个数 ,
  • 示例如下图所示。

    算法流程:
  1. 初始化:空格数量 count ,字符串 s 的长度 len
  2. 统计空格数量:遍历 s ,遇空格则 count++
  3. 修改 s 长度:添加完 “%20” 后的字符串长度应为 len + 2 * count
  4. 倒序遍历修改i 指向原字符串尾部元素, j 指向新字符串尾部元素;
    • 当 i = j 时跳出(代表左方已没有空格,无需继续遍历);
    • 当 s[i] 不为空格时:执行 s[j] = s[i]
    • 当 s[i] 为空格时:将字符串闭区间[j-2, j]的元素修改为 "%20" ;由于修改了 3 个元素,因此需要 j -= 2
  5. 返回值:已修改的字符串 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)

算法步骤

  1. 初始化下标 leftright
  2. 每次计算中间下标 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 解决此问题,证明:
        1. 此操作不会使数组越界:因为迭代条件保证了 right > left >= 0;
        2. 此操作不会使最小值丢失:假设 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. 首先求出要打印的数字范围,
  2. 然后再从 1 开始打印到最大的数字
    时间复杂度:O(1 0 n10 ^n 10n ),空间复杂度:O(1 0 n10 ^n 10n )

算法流程

  1. 初始化 sum = 1
  2. 循环遍历乘 10 让 sum 变为边界值
  3. 新建 res 数组,大小为 sum-1
  4. 从 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 )

算法流程

  1. 初始化字符串 str,另其初始值n-1 个 "0"
  2. 递增 str,使用字符去递增
    • 递增过程中判断是否存在进位,存在进位进位处 +1
    • 直到达到最大值为止,结束循环
  3. 每获取到一个值之后,遍历前方多余的 “0”,将多余的 “0” 去掉
    • 转换为 int 存到结果数组中


大数问题!】实际上,本题的主要考点是大数越界情况下的打印。
需要解决以下三个问题:

  1. 表示大数的变量类型

    • 无论是 short / int / long … 任意变量类型,数字的取值范围都是有限的。
    • 因此,大数的表示应用字符串 String 类型
  2. 生成数字的字符串集

    • 使用 int 类型时,每轮可通过 +1 生成下个数字,而此方法无法应用至 String 类型
    • 并且, String 类型的数字的进位操作效率较低,例如 “9999” 至 “10000” 需要从个位到千位循环判断,进位 4 次。
    • 观察可知,生成的列表实际上是 n 位 000 – 999 的 全排列 ,因此可避开进位操作,通过递归生成数字的 String 列表
  3. 递归生成全排列

    • 基于分治算法的思想,先固定高位,向低位递归,当个位已被固定时,添加数字的字符串。
    • 例如当 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"

观察可知,当前的生成方法仍有以下问题:

  1. 诸如 00,01,02,⋯,⋯ 应显示为 0,1,2,⋯
    • 即应 删除高位多余的 0 ;
  2. 此方法从 0 开始生成,而题目要求 列表从 1 开始 ;

以上两个问题的解决方法如下:

  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=ninenstart=nine
  • 统计 nine 的方法:

    • 固定第 xx x 位时,当 i=9i=9 i=9 则执行 nine=nine+1nine=nine+1 nine=nine+1
    • 并在回溯前恢复 nine=nine−1nine=nine−1 nine=nine1
  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 10n1,各数字字符串的长度区间为 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形式,其实应该返回字符串数组

以下是具体步骤

  1. 为了避免数字开头出现 00 0 ,先把首位first固定,first取值范围为191~9 19
  2. digit表示要生成的数字的位数,本题要从 11 1 位数一直生成到 nn n 位数,对每种数字的位数都生成一下首位,所以有个双重for循环
  3. 生成首位之后进入递归生成剩下的digit - 1位数,从 0到90 到 9 09 中取值
  4. 递归的中止条件为已经生成了 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)

算法流程

  1. 初始化指针 start = 0指针 end = nums.length - 1
  2. start < end 时表示该数组还未遍历完成,则继续进行奇数和偶数的交换
  3. nums[start] 为奇数时,则 start++,直到找到不为奇数的下标为止
  4. nums[end] 为偶数时,则 end--,直到找到不为偶数的下标为止
  5. 交换 nums[start]nums[end],继续下一轮交换
  6. 返回 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 分列数组左右两端,循环执行:

  1. 指针 ii i 从左向右寻找偶数
  2. 指针 jj j 从右向左寻找奇数
  3. 将 偶数 nums[i]nums[i] nums[i] 和 奇数 nums[j]nums[j] nums[j] 交换。

===> 可始终保证: 指针 iii 左边都是奇数,指针 jjj右边都是偶数 。

算法流程:

  1. 初始化: i , j 双指针,分别指向数组 nums 左右两端;

  2. 循环交换: 当 i = ji=ji=j 时跳出;

    • 指针 i 遇到奇数则执行 i=i+1i=i+1 i=i+1 跳过,直到找到偶数
    • 指针 j 遇到偶数则执行 j=j−1j=j−1 j=j1 跳过,直到找到奇数
    • 交换 nums[i]nums[j] 值;
  3. 返回值: 返回已修改的 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)

算法流程

  1. 题目中 matrixmatrix matrix可能为空直接返回空数组即可
  2. 初始化边界 left、right、top、bottomleft、right、top、bottom leftrighttopbottom 四个值,初始化结果数组 resres res 和数组下标 xx x
  3. 按照遍历方向循环取出数字放入结果数组中
    • 从左至右:遍历完成后 ++top,如果 top>bottom​top > bottom​ top>bottom,到达边界循环结束
    • 从上至下:遍历完成后 --right,如果 left>right​left > right​ left>right,到达边界循环结束
    • 从右至左:遍历完成后 --bottom,如果 top>bottom​top > bottom​ top>bottom,到达边界循环结束
    • 从下至上:遍历完成后 ++left,如果 left>right​left > 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),按照如下顺序遍历当前层的元素。
  1. 从左到右遍历上侧元素,依次为 (top,left) 到 (top,right)。
  2. 从上到下遍历右侧元素,依次为 (top+1,right) 到 (bottom,right)。
  3. 如果 left<right且top<bottomleft<right 且 top<bottom left<righttop<bottom,则从右到左遍历下侧元素,依次为
    • (bottom,right−1) 到 (bottom,left+1)
    • 以及从下到上遍历左侧元素,依次为
    • (bottom,left) 到 (top+1,left)。

遍历完当前层的元素之后,

  • left和topleft 和 top lefttop 分别增加 1,
  • right和bottomright 和 bottom rightbottom 分别减少 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)。除了输出数组以外,空间复杂度是常数。