文章目录

• 前言
• 03. 数组中重复的数字
• 04. 二维数组中的查找
• 05. 替换空格
• 结语

前言

😃 大家好，我是writer桑，这是自己的一个 Python 做题记录，方便自己学习的同时分享出来。

03. 数组中重复的数字

题目描述：

找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

代码实现：

class Solution:def findRepeatNumber(self, nums: [int]) -> int:my_set = set()for num in nums:if num in my_set: return nummy_set.add(num)return -1if __name__ == '__main__': s = Solution() nums = [2, 3, 1, 0, 2, 5, 3]print(s.findRepeatNumber(nums))

提交结果：

思路分析：

• 首先创建一个集合 my_set
• 循环遍历列表 nums 中的元素，如果元素不在集合中则直接添加，如果在集合中则证明这个元素是重复的，直接返回。
• 返回 -1 表示没有发现重复元素

代码实现2：

from typing import List
from collections import Counterclass Solution:def findRepeatNumber(self, nums: List[int]) -> int:count_nums = Counter(nums)              # 使用Counter类列出列表中元素出现的次数sort_nums = sorted(count_nums, key = count_nums.get)        # 以元素出现的次数进行升序排序return sort_nums[-1] if __name__ == '__main__': s = Solution() nums = [2, 3, 1, 0, 2, 5, 3]print(s.findRepeatNumber(nums))

提交结果2：

思路分析：

• 需要导入第三方库 collections 中的 Counter 类
• 使用 Counter 方法列出列表中元素出现的次数
• 使用 sorted 方法以元素出现的次数为基准进行升序排序，返回一个列表 sort_nums
• 那么列表 sort_nums 最后一个元素一定是出现2次以上的元素（前提是列表一定包含重复元素，如果没有重复元素就没有返回值）

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。

代码实现：

from typing import Listclass Solution:def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:if len(matrix) == 0 or matrix == None: return Falsei, j = len(matrix) - 1, 0while i >= 0 and j < len(matrix[0]):if matrix[i][j] > target: i -= 1elif matrix[i][j] < target: j += 1else: return Truereturn Falseif __name__ == "__main__": s = Solution() 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 = 5print(s.findNumberIn2DArray(matrix, target)) 

提交结果：

思路分析：

• 将矩阵逆时针旋转 45° 并展开，可以发现类似于二叉搜索树， 那么从根节点开始搜索时，遇到比 target 大的元素就向左，反之则向右，以此来找到目标值 target 。
• 需要事先判断 matrix 是否为空，为空直接返回 false 。根据二叉搜索树的特性，选用矩阵的左下角的元素作为标志数 flag，若 flag > target ，则 target 一定在 flag 所在 行的上方, 若 flag < target ，则 target 一定在 flag 所在 列的右方，以此类推直到找到目标数 target 。
• 算法本身比较好理解，难点在于根据题目的描述找到突破口。

代码实现2：

from typing import Listclass Solution:def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:for arr in matrix:if target in arr:return True return Falseif __name__ == "__main__": s = Solution() 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 = 5print(s.findNumberIn2DArray(matrix, target)) 

提交结果2：

思路分析：

• 简单的循环输出，逐个数组进行判断有无包含目标数，有则直接返回 true 。当循环结束时，也即表示没有该目标数，返回 false 。
• 对比第一种解法，代码量更少， 但是因为每次都需要逐个遍历数组，所以有时候性能较低，更推荐第一种解法。

05. 替换空格

题目实现：

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例：

输入：s = “We are happy.”
输出：“We%20are%20happy.”

代码实现：

class Solution:def replaceSpace(self, s: str) -> str:return "%20".join(s.split(' '))if __name__ == "__main__": s = Solution() my_str = "We are happy."print(s.replaceSpace(my_str))

提交结果：

思路分析：

• 使用 split 方法指定空格 ’ ’ 进行分割，再使用 join 方法指定 “%20” 进行连接， 然后直接返回即可。
• 这种解法很容易想到，而且代码量很少、很简洁，一行代码搞定。

代码实现2：

class Solution:def replaceSpace(self, s: str) -> str:res = []for i in  s:if i == ' ':res.append("%20")else: res.append(i) return "".join(res)if __name__ == "__main__":s = Solution()my_str = "We are happy." print(s.replaceSpace(my_str))

提交结果2：

思路分析：

• 声明列表 res 用于存放返回结果，for 循环遍历字符串 s 依次判断字符元素， 如果为空格 ’ ’ 则替换为"%20"放入 res , 如果不为空格则直接放入 res 中。循环结束使用 join 方法连接 res 列表返回即可。
• 与第一种解法相比，这种解法更常见，代码量较多，两者在性能上前者更好一点。

结语

🌻 以上就是本次的做题记录啦，希望大家看完有所收获。