剑指 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)-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)

算法步骤

---

---

剑指 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;}
};

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)

---

算法步骤

---

剑指 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 次旋转