本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!