剑指 Offer —— 数组和字符串

剑指 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)-1
        col=0
        while( row>=0 and col<len(matrix[0]) ):
            if(matrix[row][col]==target):
                return True
            else:
                if(matrix[row][col]>target):
                    row=row-1
                else:
                    col=col+1
        return 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 np

class 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 =0
        for row in matrix:
            left = 0
            right = col-1
            while(left<=right):
                mid = (left+right+1)/2
                if row[mid]<target:
                    left=mid+1
                elif row[mid]>target:
                    right=mid-1
                else:
                    return True
        return 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,  8    12, 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 +=c
        return 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=j
                else:
                    j=numbers[i]
            return j

• 二分法

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]: left = mid + 1
            elif nums[mid] < nums[right]: right = mid
            else: right = right - 1 # key
        return nums[left]

解题方案 + 思路

• 标签：二分查找
• 整体思路：
  • 首先数组是一个有序数组的旋转，从这个条件可以看出，数组是有大小规律的，
  • 可以使用二分查找利用存在的规律快速找出结果
• 时间复杂度：O(logn)，空间复杂度：O(1)

算法步骤

1. 初始化下标 left 和 right
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($10^n$ )，空间复杂度：O($10^n$ )

算法流程

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($10^n$ )，空间复杂度：O($10^n$ )

算法流程

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 尾部
                return
            for i in range(10): # 遍历 0 - 9
                num[x] = str(i) # 固定第 x 位为 i
                dfs(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-start=nine$$

• 统计 nine 的方法：

  • 固定第 $x$ 位时，当 $i=9$ 则执行 $nine=nine+1$ ，
  • 并在回溯前恢复 $nine=nine-1$

2. 列表从 1 开始：

• 在以上方法的基础上，添加数字字符串前判断其是否为 “0” ，若为 “0” 则直接跳过。

复杂度分析：

• 时间复杂度 $O(10^n)$： 递归的生成的排列的数量为 $10^n$
• 空间复杂度 $O(10^n)$： 结果列表 res 的长度为 $10^n-1$，各数字字符串的长度区间为 $1,2,...,n$，因此占用 $O(10^n)$大小的额外空间。

为 正确表示大数 ，以下代码的返回值为数字字符串集拼接而成的长字符串。

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 -= 1
                return
            for i in range(10):
                if i == 9: self.nine += 1
                num[x] = str(i)
                dfs(x + 1)
            self.nine -= 1
        
        num, res = ['0'] * n, []
        self.nine = 0
        self.start = n - 1
        dfs(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 -= 1
                return
            for i in range(10):
                if i == 9: self.nine += 1
                num[x] = str(i)
                dfs(x + 1)
            self.nine -= 1
        
        num, res = ['0'] * n, []
        self.nine = 0
        self.start = n - 1
        dfs(0)
        return res

【其他】全排列解法简洁版

在数字很大的情况下，哪怕long类型也无法承载，那必须要用字符串保存。

• 对于本题其实就是对数字09的全排列，到n位数0~9的全排列，其中要注意的是数字开头不应该有0。

简单提一下全排列，比如对于数字1，2，3的全排列是:

123, 132, 213, 231, 312, 321

为了能够测试通过，最后把字符串形式变成了int形式，其实应该返回字符串数组

以下是具体步骤

1. 为了避免数字开头出现 $0$ ，先把首位first固定，first取值范围为$19$
2. 用digit表示要生成的数字的位数，本题要从 $1$ 位数一直生成到 $n$ 位数，对每种数字的位数都生成一下首位，所以有个双重for循环
3. 生成首位之后进入递归生成剩下的digit - 1位数，从 $0到9$ 中取值
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)))
                return
            for 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 = 0
        end = len(nums)-1
        
        while(start < end):
            while(nums[start] %2 != 0) and start < end:
                start+=1
            while(nums[end]%2 ==0)and start < end:
                end-=1
            tmp = nums[start]
            nums[start] = nums[end]
            nums[end] = tmp
            start+=1
            end-=1
        
        return nums

解题思路（双指针）：

考虑定义双指针 iii , jjj 分列数组左右两端，循环执行：

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

===> 可始终保证： 指针 $i$ 左边都是奇数，指针$j$右边都是偶数 。

算法流程：

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

2. 循环交换： 当 $i=j$ 时跳出；

   • 指针 i 遇到奇数则执行 $i=i+1$ 跳过，直到找到偶数；
   • 指针 j 遇到偶数则执行 $j=j-1$ 跳过，直到找到奇数；
   • 交换 nums[i] 和 nums[j] 值；

3. 返回值： 返回已修改的 nums 数组。

复杂度分析：

• 时间复杂度 $O(N)$ ： $N$ 为数组 nums 长度，双指针 $i,j$共同遍历整个数组。
• 空间复杂度 $O(1)$ ： 双指针 $i,j$ 使用常数大小的额外空间

代码：

x & 1 位运算 等价于 x % 2 取余运算，即皆可用于判断数字奇偶性。

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        i, j = 0, len(nums) - 1
        while i < j:
            while i < j and nums[i] & 1 == 1: i += 1
            while i < j and nums[j] & 1 == 0: j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        return nums

tips:

• 快速排序的基础
  • 就是快速排序的将小于基点的放前面, 大于基点的放后面

其他做法——快慢双指针

• 定义快慢双指针 fast 和 low ，fast 在前， low 在后 .
• fast 的作用是向前搜索奇数位置，low 的作用是指向下一个奇数应当存放的位置
• $fast$ 向前移动，当它搜索到奇数时，将它和 $nums[low]$ 交换，此时 $low$ 向前移动一个位置 .
• 重复上述操作，直到 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]]$
• 输出：$[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$

解题方案

思路

• 标签：二维数组
• 整体思路：
  • 循环遍历整个数组，循环中再嵌套四个循环，
  • 分别是从左至右，从上至下，从右至左，从下至上这几个方向，
  • 按照题意将整个数组遍历完成，控制好边界
• $m$ 为行数，$n$ 为列数，时间复杂度：$O(mn)$，空间复杂度：$O(1)$

算法流程

1. 题目中 $matrix$ 有可能为空，直接返回空数组即可
2. 初始化边界 $left、right、top、bottom$ 四个值，初始化结果数组 $res$ 和数组下标 $x$
3. 按照遍历方向循环取出数字放入结果数组中
   • 从左至右：遍历完成后 ++top，如果 $top>bottom$，到达边界循环结束
   • 从上至下：遍历完成后 --right，如果 $left>right$，到达边界循环结束
   • 从右至左：遍历完成后 --bottom，如果 $top>bottom$，到达边界循环结束
   • 从下至上：遍历完成后 ++left，如果 $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])-1
        bottom = len(matrix)-1
        top =0
        left=0
        res = []
        maxSize = (right+1)*(bottom+1)
        
        while(maxSize>0):
            for i in range(left,right+1):
                if maxSize>0:
                    res.append(matrix[top][i])
                    maxSize-=1
            top+=1
            for j in range(top,bottom+1):
                if maxSize>0:
                    res.append(matrix[j][right])
                    maxSize-=1
            right-=1
            for k in range(right,left-1,-1):
                if maxSize>0:
                    res.append(matrix[bottom][k])
                    maxSize-=1
            bottom-=1
            for l in range(bottom,top-1,-1):
                if maxSize>0:
                    res.append(matrix[l][left])
                    maxSize-=1
            left+=1

        return res

方法解析——按层模拟

• 可以将矩阵看成若干层
  • 首先，输出最外层的元素
  • 其次，输出次外层的元素
  • 直到，输出最内层的元素。

定义矩阵的第 $k$ 层是到最近边界距离为 $k$ 的所有顶点。

• 例如，下图矩阵最外层元素都是第 $1$ 层，次外层元素都是第 $2$ 层，剩下的元素都是第 $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<bottom$，则从右到左遍历下侧元素，依次为
   • (bottom,right−1) 到 (bottom,left+1)
   • 以及从下到上遍历左侧元素，依次为
   • (bottom,left) 到 (top+1,left)。

遍历完当前层的元素之后，文章来源地址https://www.toymoban.com/news/detail-423931.html

• 将 $left和top$ 分别增加 1，
• 将 $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 - 1
        while 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 - 1
        return order

复杂度分析

• 时间复杂度：O(mn)，其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。
• 空间复杂度：O(1)。除了输出数组以外，空间复杂度是常数。

到了这里，关于剑指 Offer —— 数组和字符串的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！