本文主要是介绍Python算法练习 11.6，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
leetcode 994 腐烂的橘子
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
- 值
0代表空单元格； - 值
1代表新鲜橘子； - 值
2代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
示例 1：
输入：grid = [[2,1,1],[1,1,0],[0,1,1]] 输出：4示例 2：
输入：grid = [[2,1,1],[0,1,1],[1,0,1]] 输出：-1 解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。示例 3：
输入：grid = [[0,2]] 输出：0 解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
直接看了题解里的思路，自己复原一下
学到了层序的BFS思路——每一次循环都将队列中现有结点清空。
第一次循环先加入所有已经腐烂的橘子，然后再将队列中每一个腐烂的橘子四个方向（注意判断越界）的新鲜橘子加入队列。每次循环就是一分钟。
还有一个情况就是如果本来初始状态没有新鲜的橘子，要直接返回0（我忘记了）
class Solution(object):def orangesRotting(self, grid):""":type grid: List[List[int]]:rtype: int"""height = len(grid)width = len(grid[0])direction = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 下 右 左 上queue = deque([])freshTotal = 0for i in range(height):for j in range(width):if grid[i][j] == 2:queue.append((i, j))elif grid[i][j] == 1:freshTotal += 1if freshTotal == 0:return 0changeTotal = 0depth = -1while queue:depth += 1n = len(queue)for i in range(n):curHeight, curWidth = queue.popleft()for d in direction:newHeight = curHeight + d[0]newWidth = curWidth + d[1]if newHeight >= 0 and newWidth >= 0 and newHeight < height and newWidth < width:if grid[newHeight][newWidth] == 1:grid[newHeight][newWidth] = 2changeTotal += 1queue.append((newHeight, newWidth))if changeTotal == freshTotal:return depthelse:return -1
leetcode 215 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入:[3,2,1,5,6,4],k = 2 输出: 5示例 2:
输入:[3,2,3,1,2,4,5,5,6],k = 4 输出: 4
不想直接sorted，看题解吧，和快速排序很像
时间复杂度O(N)
因为N + N/2 + N/4 + ... + N/N = 2N-1
class Solution:def findKthLargest(self, nums, k):def quick_select(nums, k):# 随机选择基准数pivot = random.choice(nums)big, equal, small = [], [], []# 将大于、小于、等于 pivot 的元素划分至 big, small, equal 中for num in nums:if num > pivot:big.append(num)elif num < pivot:small.append(num)else:equal.append(num)if k <= len(big):# 第 k 大元素在 big 中，递归划分return quick_select(big, k)if len(nums) - len(small) < k:# 第 k 大元素在 small 中，递归划分return quick_select(small, k - len(nums) + len(small))# 第 k 大元素在 equal 中，直接返回 pivotreturn pivotreturn quick_select(nums, k)这篇关于Python算法练习 11.6的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
