亚麻Tag题

875. Koko Eating Bananas题意解释Koko 有n堆香蕉第i堆有piles[i]根。她每小时选一堆吃吃的速度是k根/小时。如果那堆不足k根她吃完就停下来等到下一个小时再吃下一堆不会同一小时吃两堆。守卫h小时后回来问 Koko 吃完所有香蕉的最小速度k。思路归纳核心知识点二分查找Binary Search on Answer为什么是二分速度k越大花的时间越少。存在一个临界点k小于它就吃不完k大于等于它就能吃完。这种找最小的满足条件的值就是经典的二分搜索答案。需要记录的变量l, r二分的左右边界。l 1最慢每小时 1 根r max(piles)最快每小时吃最大那堆hours(k)辅助函数算速度为k时吃完所有香蕉需要多少小时关键计算每堆需要的小时数 ceil(pile / k)用整数写法就是(pile k - 1) // k流程二分范围[1, max(piles)]算mid速度下需要的总小时数总小时数 h→ 速度够快尝试更慢 →r mid总小时数 h→ 速度不够 →l mid 1返回l代码classSolution:defminEatingSpeed(self,piles,h):l,r1,max(piles)whilelr:mid(lr)//2# 计算速度为 mid 时需要多少小时hours0forpileinpiles:hours(pilemid-1)//mid# 向上取整ifhoursh:# 吃得完尝试更慢的速度rmidelse:# 吃不完速度要更快lmid1returnl时空复杂度复杂度说明时间O(n × log(max(piles)))二分 log(max(piles)) 次每次遍历 n 堆空间O(1)只用了几个变量这道题属于二分搜索答案模板不是在数组里找目标值而是在一个范围里找满足条件的最小值/最大值。判断条件是这个速度能不能在 h 小时内吃完。以后遇到最小化最大值或最大化最小值的题都可以往这个方向想。答案有单调性。速度k和吃完的时间之间是单调关系k越大花的时间越少k越小花的时间越多。所以在[1, max(piles)]这个范围里一定存在一个分界点速度: 1 2 3 4 5 6 7 8 9 10 能吃完: ✗ ✗ ✗ ✗ ✓ ✓ ✓ ✓ ✓ ✓ ↑ 这就是答案左边全是 ✗右边全是 ✓不会出现 ✗✓✗✓ 交替的情况。这种左边全不满足、右边全满足的结构就是二分查找的前提条件。二分搜索答案的通用判断标准当你发现答案越大越容易满足条件或反过来就说明有单调性就能用二分。这道题就是速度越大越容易吃完所以二分找最小的能吃完的速度。977. Squares of a Sorted Array题意解释给你一个已按非递减排序的整数数组nums可能包含负数返回每个数的平方结果也要按非递减排序。比如nums [-4, -1, 0, 3, 10]平方后是[16, 1, 0, 9, 100]排序后返回[0, 1, 9, 16, 100]。思路归纳核心知识点双指针从两端向中间关键洞察原数组有负数和正数平方后最大的值一定出现在两端最左边的负数绝对值可能很大最右边的正数也可能很大中间的反而小。所以用两个指针从两端往中间走每次比较两端的平方把大的放到结果数组的末尾从后往前填。需要记录的变量l左指针从 0 开始r右指针从末尾开始res结果数组从后往前填入pos结果数组当前填入位置从末尾开始流程比较abs(nums[l])和abs(nums[r])谁大把谁的平方放到res[pos]移动对应指针pos - 1继续直到l r代码classSolution:defsortedSquares(self,nums):nlen(nums)res[0]*n l,r0,n-1posn-1# 从后往前填whilelr:ifabs(nums[l])abs(nums[r]):res[pos]nums[l]**2l1else:res[pos]nums[r]**2r-1pos-1returnres时空复杂度复杂度说明时间O(n)每个元素只处理一次空间O(n)结果数组为什么不直接平方后排序可以return sorted(x**2 for x in nums)一行搞定但时间是 O(nlogn)。双指针利用了原数组已排序这个条件做到 O(n)。面试中两种都说一下先给暴力再给优化面试官会喜欢这个思路。79. Word Search题意解释给你一个m x n的字符网格board和一个字符串word判断word是否能在网格中通过上下左右相邻的格子拼出来。同一个格子在一条路径中不能重复使用。思路归纳核心知识点回溯Backtracking DFS为什么用回溯你要在网格中找一条路径每一步有上下左右四个选择走错了要退回来换方向。这就是经典的做选择 → 递归 → 撤销选择。为什么需要visited同一条路径中不能重复走同一个格子需要标记哪些格子已经走过。回溯时要撤销标记。需要记录的变量visited集合记录当前路径中已经走过的(r, c)i当前正在匹配word的第几个字符流程遍历网格找到所有等于word[0]的起点从起点开始 DFS每一步检查当前格子是否等于word[i]等于 → 标记 visited往四个方向递归匹配word[i1]匹配完word所有字符 → 返回True走不通 → 撤销 visited回溯代码classSolution:defexist(self,board,word):rows,colslen(board),len(board[0])visitedset()defdfs(r,c,idx):# base case: 全部匹配完ifidxlen(word):returnTrue# 越界 / 已访问 / 不匹配if(r0orrrowsorc0orccolsor(r,c)invisitedorboard[r][c]!word[idx]):returnFalse# 标记已访问visited.add((r,c))# 四个方向递归found(dfs(r1,c,idx1)ordfs(r-1,c,idx1)ordfs(r,c1,idx1)ordfs(r,c-1,idx1))# 回溯撤销标记visited.remove((r,c))returnfoundforrinrange(rows):forcinrange(cols):ifdfs(r,c,0):returnTruereturnFalse时空复杂度复杂度说明时间O(m × n × 4^L)每个格子作为起点最多探索 4 个方向深度为 Lword 长度空间O(L)递归深度 visited 最多存 L 个格子回溯的核心三步在这里的体现visited.add((r,c))# 1. 做选择dfs(rdr,cdc,i1)# 2. 递归visited.remove((r,c))# 3. 撤销选择和岛屿问题的区别岛屿问题标记了就不撤销每个格子只访问一次。这道题必须撤销因为一条路径走不通时这个格子可能被另一条路径用到。