devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法试题（Python实现）dfs、矩阵路径_python dfs

作者：IT小白 | 2024-04-21 10:29:35

赞

踩

python dfs

目录

1. 分糖果问题（贪心思想）

2. 主持人调度（二）（贪心思想）

3. N皇后问题（递归）

4. 岛屿数量（dfs）

5. 设计LRU缓存结构（哈希表+双向链表）

6. 设计LFU缓存结构（双哈希表）

7. 螺旋矩阵（边界模拟法）

8. 顺时针旋转矩阵（倒置翻转法）

9. 不同路径的数目(一)

10. 矩阵最长递增路径（dfs+DP）

11. 矩阵的最小路径和

12. 编辑距离(一)

13. ​​​​​​​旋转数组（平移数组：三次翻转法）

1. 分糖果问题（贪心思想）

单独遍历两次，先从左往右遍历（右边大的+1），再从右往左遍历（左边大的+1）

  1. class Solution:
  2.     def candy(self , arr: List[int]) -> int:
  3.         # 记录每个位置的糖果数，每个孩子为默认为1
  4.         nums = [1] * len(arr)
  5.         # 从左到右遍历
  6.         for i in range(1, len(arr)):
  7.             # 如果右边大，则该位置糖果数为左边基础上加一
  8.             if arr[i-1] < arr[i]:
  9.                 nums[i] = nums[i-1] + 1
  10.  
  11.         res = nums[len(arr) - 1]
  12.         # 从右到左遍历
  13.         for i in range(len(arr)-2, -1, -1):
  14.             # 如果左边大且糖果数小，则该位置糖果数为右边基础上加一
  15.             if arr[i] > arr[i+1] and nums[i] <= nums[i+1]:
  16.                 nums[i] = nums[i+1] + 1
  17.             res += nums[i]
  18.         return res

2. 主持人调度（二）（贪心思想）

排序+遍历（新开始的节目大于等于上一轮结束的时间，主持人不变，否则主持人+1）

  1. class Solution:
  2.     def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int:
  3.         start = []
  4.         end = []
  5.         for i in range(n):
  6.             start.append(startEnd[i][0])
  7.             end.append(startEnd[i][1])
  8.         start.sort()
  9.         end.sort()
  10.         res = 0
  11.         j = 0
  12.         for i in range(n):
  13.             # 新开始的节目大于等于上一轮结束的时间，主持人不变
  14.             if start[i] >= end[j]:
  15.                 j += 1
  16.             else:
  17.                 # 主持人+1
  18.                 res += 1
  19.         return res

3. N皇后问题（递归）

  1. class Solution:
  2.     # 判断皇后是否符合条件
  3.     def isValid(self, pos: List[int], row: int, col: int):
  4.         # 遍历记录过的行
  5.         for i in range(row):
  6.             if row == i or col == pos[i] or abs(row-i) == abs(col-pos[i]):
  7.                 return False
  8.         return True
  9.     
  10.     # 递归查找皇后种类
  11.     def recursion(self, n: int, row: int, pos: List[int], res: int):
  12.         if row == n:
  13.             res += 1
  14.             return res
  15.         for i in range(n):
  16.             if self.isValid(pos, row, i):
  17.                 pos[row] = i
  18.                 res = self.recursion(n, row + 1, pos, res)
  19.         return res
  20.         
  21.     def Nqueen(self , n: int) -> int:
  22.         res = 0
  23.         # 下标为行号，元素为列号，记录皇后位置
  24.         pos = [0]*n
  25.         # 递归
  26.         result = self.recursion(n, 0, pos, res)
  27.         return result

4. 岛屿数量（dfs）

  1. class Solution:
  2.     # 深度优先遍历
  3.     def dfs(self, grid: List[List[chr]], i: int, j: int):
  4.         n = len(grid)
  5.         m = len(grid[0])
  6.         grid[i][j] = '0'
  7.         if i - 1 >= 0 and grid[i-1][j] == '1':
  8.             self.dfs(grid, i-1, j)
  9.         if i + 1 < n and grid[i+1][j] == '1':
  10.             self.dfs(grid, i+1, j)
  11.         if j - 1 >= 0 and grid[i][j-1] == '1':
  12.             self.dfs(grid, i, j-1)
  13.         if j + 1 < m and grid[i][j+1] == '1':
  14.             self.dfs(grid, i, j+1)
  15.  
  16.     def solve(self , grid: List[List[str]]) -> int:
  17.         n = len(grid)
  18.         if n == 0: return 0
  19.         m = len(grid[0])
  20.         count = 0
  21.         for i in range(n):
  22.             for j in range(m):
  23.                 if grid[i][j] == '1':
  24.                     count += 1
  25.                     self.dfs(grid, i, j)
  26.         return count

5. 设计LRU缓存结构（哈希表+双向链表）

使用数组实现

  1. class Solution:
  2.     def __init__(self, capacity: int):
  3.         self.capacity = capacity
  4.         self.q = []
  5.  
  6.     def get(self, key: int) -> int:
  7.         flag = True
  8.         for i in range(len(self.q)):
  9.             if self.q[i][0] == key:
  10.                 res = self.q[i][1]
  11.                 self.q.append(self.q.pop(i))
  12.                 flag = False
  13.                 break
  14.         return -1 if flag else res
  15.  
  16.     def set(self, key: int, value: int) -> None:
  17.         flag = True
  18.         hasKey = False
  19.         if len(self.q) >= self.capacity:
  20.             for i in range(len(self.q)):
  21.                 if self.q[i][0] == key:
  22.                     self.q.pop(i)
  23.                     flag = False
  24.                     break
  25.             if flag:
  26.                 self.q.pop(0)
  27.         for i in range(len(self.q)):
  28.             if self.q[i][0] == key:
  29.                 self.q[i][1] = value
  30.                 hasKey = True
  31.         if not hasKey:
  32.             self.q.append([key, value])
  33.         return None

使用双向链表+双向链表实现。用哈希表的key值对应链表的节点。

  1. # 构建双向链表结点
  2. class Node:
  3.     def __init__(self, key, value):
  4.         self.key = key
  5.         self.value = value
  6.         self.pre = None
  7.         self.next = None
  8.  
  9. class Solution:
  10.     # 约定：链表尾的元素最新
  11.     def __init__(self, capacity: int):
  12.         self.capacity = capacity
  13.         # 双向链表头尾
  14.         self.head = Node(-1,-1)
  15.         self.tail = Node(-1,-1)
  16.         self.head.next = self.tail
  17.         self.tail.pre = self.head
  18.         # 哈希表记录Node
  19.         self.map = dict()
  20.  
  21.     # 获得当前大小
  22.     def getSize(self) -> int:
  23.         cur = self.head.next
  24.         res = 0
  25.         while cur != self.tail:
  26.             cur = cur.next
  27.             res += 1
  28.         return res
  29.  
  30.     # 表尾插入新元素
  31.     def insert(self, node: Node):
  32.         node.pre = self.tail.pre
  33.         node.next = self.tail
  34.         self.tail.pre.next = node
  35.         self.tail.pre = node
  36.         
  37.     # 移至表尾
  38.     def moveToTail(self, node: Node):
  39.         node.pre.next = node.next
  40.         node.next.pre = node.pre
  41.         self.insert(node)
  42.     
  43.     # 移除表头元素
  44.     def moveHead(self):
  45.         self.map.pop(self.head.next.key)
  46.         self.head.next.next.pre = self.head
  47.         self.head.next = self.head.next.next
  48.     
  49.     def get(self, key: int) -> int:
  50.         res = -1
  51.         if key in self.map:
  52.             res = self.map[key].value
  53.             self.moveToTail(self.map[key])
  54.         return res
  55.  
  56.     def set(self, key: int, value: int) -> None:
  57.         if key in self.map:
  58.             self.moveToTail(self.map[key])
  59.             self.map[key].value = value
  60.         else:
  61.             if self.getSize() >= self.capacity:
  62.                 self.moveHead()
  63.             node = Node(key, value)
  64.             self.map[key] = node
  65.             self.insert(node)

6. 设计LFU缓存结构（双哈希表）

  1. import collections
  2. class Node:
  3.     def __init__(self, freq, key, val):
  4.         self.freq = freq
  5.         self.key = key
  6.         self.val = val
  7.         
  8. class Solution:
  9.     def __init__(self):
  10.         #记录剩余空间
  11.         self.size = 0
  12.         #key到双向链表节点的哈希表
  13.         self.mp = dict()
  14.         #频率到链表的哈希表
  15.         self.freq_mp = dict(collections.deque())
  16.         #记录当前最小频次
  17.         self.min_freq = 0
  18.     
  19.     #调用函数时更新频率或者val值
  20.     def update(self, node: Node, key: int, value: int): 
  21.         #找到频率
  22.         freq = node.freq
  23.         #原频率中删除该节点
  24.         self.freq_mp[freq].remove(node) 
  25.         #哈希表中该频率已无节点，直接删除
  26.         if len(self.freq_mp[freq]) == 0: 
  27.             self.freq_mp.pop(freq)
  28.             #若当前频率为最小，最小频率加1
  29.             if self.min_freq == freq: 
  30.                 self.min_freq += 1
  31.         #插入频率加一的双向链表表头，链表中对应：freq key value
  32.         node = Node(freq + 1, key, value)
  33.         if freq + 1 not in self.freq_mp:
  34.             self.freq_mp[freq + 1] = collections.deque()
  35.         self.freq_mp[freq + 1].appendleft(node)
  36.         self.mp[key] = self.freq_mp[freq + 1][0]
  37.     
  38.     #set操作函数
  39.     def set(self, key:int, value: int):
  40.         #在哈希表中找到key值
  41.         if key in self.mp:
  42.             #若是哈希表中有，则更新值与频率
  43.             self.update(self.mp[key], key, value)
  44.         else:
  45.             #哈希表中没有，即链表中没有
  46.             if self.size == 0:
  47.                 #满容量取频率最低且最早的删掉
  48.                 oldnode = self.freq_mp[self.min_freq].pop() 
  49.                 #频率哈希表的链表中删除
  50.                 if len(self.freq_mp[self.min_freq]) == 0:
  51.                     self.freq_mp.pop(self.min_freq) 
  52.                 #链表哈希表中删除
  53.                 self.mp.pop(oldnode.key)
  54.             #若有空闲则直接加入，容量减1
  55.             else: 
  56.                 self.size -= 1
  57.             #最小频率置为1
  58.             self.min_freq = 1
  59.             node = Node(1, key, value)
  60.             if 1 not in self.freq_mp:
  61.                 self.freq_mp[1] = collections.deque()
  62.             self.freq_mp[1].appendleft(node)
  63.             #哈希表key值指向链表中该位置
  64.             self.mp[key] = self.freq_mp[1][0]
  65.             
  66.     #get操作函数
  67.     def get(self, key: int) -> int:
  68.         res = -1
  69.         #查找哈希表
  70.         if key in self.mp:
  71.             node = self.mp[key]
  72.             #根据哈希表直接获取值
  73.             res = node.val
  74.             #更新频率 
  75.             self.update(node, key, res)
  76.         return res
  77.  
  78.     def LFU(self , operators: List[List[int]], k: int) -> List[int]:
  79.         res = []
  80.         #构建初始化连接
  81.         #链表剩余大小
  82.         self.size = k
  83.         #遍历所有操作
  84.         for i in range(len(operators)):
  85.             op = operators[i]
  86.             if op[0] == 1: 
  87.                 #set操作
  88.                 self.set(op[1], op[2])
  89.             else:
  90.                 #get操作
  91.                 res.append(self.get(op[1]))
  92.         return resnd(self.get(op[1]))
  93.         return res

7. ​​​​​​​螺旋矩阵（边界模拟法）

  1. class Solution:
  2.     def spiralOrder(self , matrix: List[List[int]]) -> List[int]:
  3.         res = []
  4.         n = len(matrix)
  5.         if n == 0: return res
  6.         # 上下左右边界
  7.         left = 0
  8.         right = len(matrix[0]) - 1
  9.         up = 0
  10.         down = n - 1
  11.         while left <= right and up <= down:
  12.             # 上边界的从左到右
  13.             for i in range(left, right + 1):
  14.                 res.append(matrix[up][i])
  15.             # 上边界下移
  16.             up += 1
  17.             if up > down: break
  18.             # 右边界的从上到下
  19.             for i in range(up, down + 1):
  20.                 res.append(matrix[i][right])
  21.             # 右边界左移
  22.             right -= 1
  23.             if left > right: break
  24.             # 下边界的从右到左
  25.             for i in range(right, left - 1, -1):
  26.                 res.append(matrix[down][i])
  27.             # 下边界上移
  28.             down -= 1
  29.             if up > down: break
  30.             # 左边界的从下到上
  31.             for i in range(down, up - 1, -1):
  32.                 res.append(matrix[i][left])
  33.             # 左边界右移
  34.             left += 1
  35.             if left > right:
  36.                 break
  37.         return res

8. 顺时针旋转矩阵（倒置翻转法）

  1. class Solution:
  2.     def rotateMatrix(self , mat: List[List[int]], n: int) -> List[List[int]]:
  3.         # 矩阵转置
  4.         for i in range(n):
  5.             for j in range(i):
  6.                 # 交换上三角与下三角对应的元素
  7.                 mat[i][j], mat[j][i] = mat[j][i], mat[i][j]
  8.         # 每行翻转
  9.         for i in range(n):
  10.             mat[i].reverse()
  11.         return mat

9. 不同路径的数目(一)

  1. class Solution:
  2.     def uniquePaths(self , m: int, n: int) -> int:
  3.         dp = [[0] * (n+1) for i in range(m + 1)]
  4.         for i in range(1, m + 1):
  5.             for j in range(1, n + 1):
  6.                 if i == 1:
  7.                     dp[i][j] = 1
  8.                     continue
  9.                 if j == 1:
  10.                     dp[i][j] = 1
  11.                     continue
  12.                 dp[i][j] = dp[i-1][j] + dp[i][j-1]
  13.         return dp[m][n]

10. 矩阵最长递增路径（dfs+DP）

  1. class Solution:
  2.     global dirs
  3.     dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
  4.     global n, m
  5.     # 深度优先搜索，返回最大单元格数
  6.     def dfs(self, matrix: List[List[int]], dp: List[List[int]], i: int, j: int):
  7.         if dp[i][j] != 0:
  8.             return dp[i][j]
  9.         dp[i][j] += 1
  10.         for k in range(4):
  11.             nexti = i + dirs[k][0]
  12.             nextj = j + dirs[k][1]
  13.             if nexti >= 0 and nexti < n and nextj >= 0 and nextj < m and matrix[nexti][nextj] > matrix[i][j]:
  14.                 dp[i][j] = max(dp[i][j], self.dfs(matrix, dp, nexti, nextj) + 1)
  15.         return dp[i][j]
  16.     def solve(self , matrix: List[List[int]]) -> int:
  17.         global n, m
  18.         if len(matrix) == 0 or len(matrix[0]) == 0:
  19.             return 0
  20.         res = 0
  21.         n = len(matrix)
  22.         m = len(matrix[0])
  23.         dp = [[0 for col in range(m)] for row in range(n)]
  24.         for i in range(n):
  25.             for j in range(m):
  26.                 res = max(res, self.dfs(matrix, dp, i, j))
  27.         return res

11. 矩阵的最小路径和

  1. class Solution:
  2.     def minPathSum(self, matrix: List[List[int]]) -> int:
  3.         n = len(matrix)
  4.         # 因为n,m均大于等于1
  5.         m = len(matrix[0])
  6.         # dp[i][j]表示以当前i，j位置为终点的最短路径长度
  7.         dp = [[0] * (m + 1) for i in range(n + 1)]
  8.         dp[0][0] = matrix[0][0]
  9.         # 处理第一列
  10.         for i in range(1, n):
  11.             dp[i][0] = matrix[i][0] + dp[i - 1][0]
  12.         # 处理第一行
  13.         for j in range(1, m):
  14.             dp[0][j] = matrix[0][j] + dp[0][j - 1]
  15.         # 其他按照公式来
  16.         for i in range(1, n):
  17.             for j in range(1, m):
  18.                 if dp[i - 1][j] > dp[i][j - 1]:
  19.                     dp[i][j] = matrix[i][j] + dp[i][j - 1]
  20.                 else:
  21.                     dp[i][j] = matrix[i][j] + dp[i - 1][j]
  22.         return dp[n - 1][m - 1]

12. 编辑距离(一)

  1. class Solution:
  2.     def editDistance(self, str1: str, str2: str) -> int:
  3.         n1 = len(str1)
  4.         n2 = len(str2)
  5.         # dp[i][j]表示到str1[i]和str2[j]为止的子串需要的编辑距离
  6.         dp = [[0] * (n2 + 1) for i in range(n1 + 1)]
  7.         # 初始化边界
  8.         for i in range(1, n1 + 1):
  9.             dp[i][0] = dp[i - 1][0] + 1
  10.         for i in range(1, n2 + 1):
  11.             dp[0][i] = dp[0][i - 1] + 1
  12.         # 遍历第一个字符串的每个位置
  13.         for i in range(1, n1 + 1):
  14.             # 对应第二个字符串每个位置
  15.             for j in range(1, n2 + 1):
  16.                 # 若是字符相同，此处不用编辑
  17.                 if str1[i - 1] == str2[j - 1]:
  18.                     # 直接等于二者前一个的距离
  19.                     dp[i][j] = dp[i - 1][j - 1]
  20.                 else:
  21.                     # 选取最小的距离加上此处编辑距离1
  22.                     dp[i][j] = (
  23.                         min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1
  24.                     )
  25.         return dp[n1][n2]

13. ​​​​​​​旋转数组（平移数组：三次翻转法）

  1. class Solution:
  2.     def solve(self , n: int, m: int, a: List[int]) -> List[int]:
  3.         # 取余，因为每次长度为n的旋转数组相当于没有变化
  4.         m = m % n
  5.         # 第一次 逆转全部数组元素
  6.         a.reverse()
  7.         b = a[:m]
  8.         # 第二次 逆转开头m个
  9.         b.reverse()
  10.         c = a[m:]
  11.         # 第三次 只逆转结尾n-m个
  12.         c.reverse()
  13.         a[:m] = b
  14.         a[m:] = c
  15.         return a

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/462512
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号