目录
  1. 1. 日常警醒
  2. 2. 剑指offer04-二维数组中的查找
    1. 2.1. 题目
    2. 2.2. 题解
  3. 3. 剑指offer12-矩阵中的路径
    1. 3.1. 题目
    2. 3.2. 题解
  4. 4. 剑指offer05-替换空格
    1. 4.1. 题目
    2. 4.2. 题解
每日一刷2

日常警醒

菜就要刷题,不要偷懒!

剑指offer04-二维数组中的查找

题目

  • 难度:简单

在一个 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

题解

  • 根据题目数组的排序特点,可以从左下角或右上角开始搜索,
  • 如果从左下角开始搜索,如果当前元素大于target,就向上找,否则向右找。
  • 如果从右下角开始搜索,如果当前元素大于target,就向左找,否则向下找。
  • 时间复杂度:O(n + m)
  • 空间复杂度:O(1)
def findNumberIn2DArray(matrix, target):

if not matrix or not target:
return False

#左下角
i = len(matrix[0]) - 1
j = 0

while i >= 0 and j <= len(matrix) - 1:
if target == matrix[i][j]:
return True
elif target < matrix[i][j]:
i -= 1
else:
j += 1
return False

if __name__ == '__main__':
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]]
target1 = 5
target2 = 20
print(findNumberIn2DArray(matrix, target1))
print(findNumberIn2DArray(matrix, target2))
def findNumberIn2DArray(matrix, target):

if not matrix or not target:
return False

#右上角
i = 0
j = len(matrix) - 1

while i <= len(matrix[0]) - 1 and j >= 0:
if target == matrix[i][j]:
return True
elif target < matrix[i][j]:
j -= 1
else:
i += 1
return False

if __name__ == '__main__':
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]]
target1 = 5
target2 = 20
print(findNumberIn2DArray(matrix, target1))
print(findNumberIn2DArray(matrix, target2))

剑指offer12-矩阵中的路径

题目

  • 难度:中等

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。例如,在下面的3×4的矩阵中包含一条字符串“bfce”的路径(路径中的字母用加粗标出)。

[[“a”,“b”,“c”,“e”],
[“s”,“f”,“c”,“s”],
[“a”,“d”,“e”,“e”]]

但矩阵中不包含字符串“abfb”的路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入这个格子。

示例1:

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出:true

示例2:

输入:board = [["a","b"],["c","d"]], word = "abcd"
输出:false

提示:

  • 1 <= board.length <= 200
  • 1 <= board[i].length <= 200

题解

  • DFS
  • 边界条件
    • 如果board为空,返回false
    • DFS搜索时,如果word检查完毕,即len(word)==0,返回true
    • DFS搜索时,如果边界超出或矩阵中的字符已访问或与目标字符不同,返回false
  • DFS搜索
    • 标记当前元素,将矩阵当前元素暂存temp,并标记为‘0’,代表已经访问过,避免再次访问到
    • 搜索下一个单元格:向上下左右四个方向搜索,并将结果记录到res
    • 还原当前矩阵:将temp暂存值还原
  • 回溯至返回res,代表是否搜到目标字符串
def exist(board, word):
if not board:
return False
for i in range(len(board)):
for j in range(len(board[0])):
if dfs(i, j, board, word):
return True
return False


def dfs(i, j, board, word):
if len(word) == 0:
return True
if i < 0 or i > len(board) - 1 or j < 0 or j > len(board[0]) - 1 or word[0] != board[i][j]:
return False

temp = board[i][j]
board[i][j] = '0'
res = dfs(i + 1, j, board, word[1:]) or dfs(i - 1, j, board, word[1:]) or dfs(i, j - 1, board, word[1:]) or dfs(i, j + 1, board, word[1:])

board[i][j] = temp
return res

if __name__ == '__main__':
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "ABCCED"
board1 = [["a","b"],["c","d"]]
word1 = "abcd"
print(exist(board, word))
print(exist(board1, word1))

剑指offer05-替换空格

题目

  • 难度:简单

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

示例1:

输入:s = "We are happy."
输出:"We%20are%20happy."

限制:

0 <= s 的长度 <= 10000

题解

  • 初始化数组
  • 遍历字符串,当遍历到空格,就往数组里加%20,否则就把当前遍历的字符加进去
  • 把数组转字符串
  • 时间复杂:O(n)
  • 空间复杂度:O(n)
def replaceSpace(s):
if not s:
return s
res = []
for c in s:
if c == ' ':
res.append('%20')
else:
res.append(c)
return ''.join(res)

if __name__ == '__main__':
s = "We are happy."
print(replaceSpace(s))
文章作者: Lesy
文章链接: https://lesylin.com/2020/08/02/%E6%AF%8F%E6%97%A5%E4%B8%80%E5%88%B72/
文章声明: 转载请注明文章链接
打赏
  • 微信
  • 支付宝

Comment