每日一题 力扣 3418. 机器人可以获得的最大金币数 力扣 215. 数组中的第K个最大元素 动态规划 TopK问题 C++ 题解

文章目录力扣 3418. 机器人可以获得的最大金币数题目描述思路简介代码实现复杂度分析力扣 215. 数组中的第K个最大元素题目描述思路简介代码实现复杂度分析踩坑记录力扣 3418. 机器人可以获得的最大金币数题目描述力扣 3418. 机器人可以获得的最大金币数示例 1输入 coins [[0,1,-1],[1,-2,3],[2,-3,4]]输出 8解释一个获得最多金币的最优路径如下从 (0, 0) 出发初始金币为 0总金币 0。移动到 (0, 1)获得 1 枚金币总金币 0 1 1。移动到 (1, 1)遇到强盗抢走 2 枚金币。机器人在此处使用一次感化能力避免被抢总金币 1。移动到 (1, 2)获得 3 枚金币总金币 1 3 4。移动到 (2, 2)获得 4 枚金币总金币 4 4 8。示例 2输入 coins [[10,10,10],[10,10,10]]输出 40解释一个获得最多金币的最优路径如下从 (0, 0) 出发初始金币为 10总金币 10。移动到 (0, 1)获得 10 枚金币总金币 10 10 20。移动到 (0, 2)再获得 10 枚金币总金币 20 10 30。移动到 (1, 2)获得 10 枚金币总金币 30 10 40。提示m coins.lengthn coins[i].length1 m, n 500-1000 coins[i][j] 1000思路简介这道题是典型的带状态约束的网格动态规划问题。机器人只能向右或向下移动核心约束是最多可使用2次感化能力因此无法用常规的二维DP解决需要引入第三个维度记录感化能力的使用次数。我们设已知的金币数组大小m,n为了规避网格边界第一行、第一列的特殊初始化处理我们将DP数组的维度定义为(m1) x (n1) x 3其中dp[i][j][k]表示机器人从起点(0,0)走到网格单元格(i-1,j-1)时累计使用了k次感化能力能够获得的最大金币数k的取值为0、1、2对应0次、1次、2次感化。状态转移方程推导机器人到达(i-1,j-1)只有两种路径从上方(i-2,j-1)向下走或从左方(i-1,j-2)向右走。针对当前单元格是否使用感化能力分两种情况处理k0未使用过感化能力此时无法对当前单元格使用感化只能直接累加当前单元格的金币值。取上方和左方路径中的最大值加上当前单元格的金币即可dp[i][j][0] max(dp[i-1][j][0], dp[i][j-1][0]) coins[i-1][j-1]1≤k≤2已使用k次感化能力此时有两种选择取两者的最优解选择1当前单元格不使用感化逻辑和k0一致感化次数保持k不变累加当前单元格金币。选择2当前单元格使用感化coins[i][j] 0的单元格才有强盗也就是这种单元格刚才会进入当前情况即当前单元格中负数单元格不扣钱收益为 0所以我们直接去找上方和左方dp[i-1][j], dp[i][j-1]的k-1时当前为k那么使用本次感化前的使用次数为k-1的最大值即可。最终状态转移方程dp[i][j][k]max(max(dp[i-1][j][k],dp[i][j-1][k])coins[i-1][j-1],// 不使用感化max(dp[i-1][j][k-1],dp[i][j-1][k-1])// 使用感化当前单元格无金币损失)注当当前单元格为正数时「不使用感化」的收益一定更高因此选择2会自动被舍弃无需额外判断。初始化逻辑对dp数组的初始化用的是INT_MIN/2而不是INT_MIN是因为INT_MIN是 int 类型的最小值-2^31后续状态转移时如果加上负数会触发整型溢出导致未定义行为除以 2 可以留出足够的数值余量避免溢出。起点(0,0)对应DP数组的dp[1][1][k]分情况初始化dp[1][1][0]不使用感化直接获取起点的金币值即coins[0][0]。dp[1][1][1]、dp[1][1][2]使用感化能力哪怕起点是负数也能避免扣钱因此收益为max(coins[0][0], 0)。由于题目并没有说明所以起点的值不一定为固定值所以我们的初始化不能够合并成一个循环进行最终结果题目允许最多使用2次感化能力因此最终结果为dp[m][n][2]。dp[m][n][2](0,0)~(m-1,n-1)这个范围中用了2次感化技能之后取得的最大金币数量为什么直接返回dp[m][n][2]而不是max(dp[m][n][0], dp[m][n][1], dp[m][n][2])—— 因为感化次数越多可选的操作越多最优收益一定满足dp[m][n][2] dp[m][n][1] dp[m][n][0]代码实现#includevector#includeclimits// 用于INT_MINusingnamespacestd;classSolution{public:intmaximumAmount(vectorvectorintcoins){intmcoins.size();// 网格的行数intncoins[0].size();// 网格的列数// 定义三维DP数组维度为(m1) x (n1) x 3// 初始化为INT_MIN/2代表初始状态不可达// 除以2是为了避免后续状态转移时加上负数导致整型溢出vectorvectorvectorintdp(m1,vectorvectorint(n1,vectorint(3,INT_MIN/2)));// 初始化起点(0,0)对应的dp[1][1]dp[1][1][0]coins[0][0];// 不使用感化直接拿起点金币for(intk1;k2;k){// 使用1次或2次感化起点收益为max(金币值, 0)负数不扣钱dp[1][1][k]max(coins[0][0],0);}// 遍历网格所有单元格for(inti1;im;i){for(intj1;jn;j){if(i1j1)continue;// 起点已初始化跳过// 处理k0的情况从未使用过感化dp[i][j][0]max(dp[i-1][j][0],dp[i][j-1][0])coins[i-1][j-1];// 处理k1和k2的情况使用过1次或2次感化for(intk1;k2;k){// 两种选择取最大值不使用当前感化 / 对当前单元格使用感化dp[i][j][k]max(max(dp[i-1][j][k],dp[i][j-1][k])coins[i-1][j-1],max(dp[i-1][j][k-1],dp[i][j-1][k-1]));}}}// 返回最多使用2次感化的最大收益returndp[m][n][2];}};复杂度分析时间复杂度O(m*n)。m和n为网格的行列数感化次数k的最大值为2固定常数因此总循环次数为m*n*3时间复杂度为线性级别。空间复杂度O(m*n)。三维DP数组的总大小为(m1)*(n1)*3k为常数因此空间复杂度为O(m*n)。补充优化由于每个状态仅依赖上一行和当前行的左侧状态可将空间进一步优化为O(n)二维滚动数组。力扣 215. 数组中的第K个最大元素题目描述力扣 215. 数组中的第K个最大元素示例 1:输入: [3,2,1,5,6,4], k 2输出: 5示例 2:输入: [3,2,3,1,2,4,5,5,6], k 4输出: 4提示1 k nums.length 105-104 nums[i] 104思路简介本题是经典的TopK问题题目要求实现时间复杂度为O(n)的算法因此最优解为快速选择算法基于三指针快排的分治剪枝优化。核心思路快速选择算法的核心是「分治剪枝」基于三指针快排的逻辑随机选择一个基准值将数组划分为三个区间小于基准值、等于基准值、大于基准值。无需对整个数组排序只需根据三个区间的长度判断第K大的元素落在哪个区间仅对目标区间递归处理舍弃无关区间的计算从而将平均时间复杂度从快排的O(nlogn)优化到O(n)。我们要找的是「第K个最大元素」等价于数组升序排序后「第nums.size() - k 1个最小元素」。本文代码基于「找第K小元素」的逻辑实现因此在调用递归函数时会先对k值做上述转换。如果快排和解决Topk问题有遗忘的朋友可以看下我这两个博客其中讲解非常详细并由完整的手绘图片说明看不懂你打我快排优化C 分治 快速排序优化 三指针快排 力扣 912. 排序数组 题解 每日一题TopK的几种解决方法堆排快排C 分治 快速选择算法 堆排序 TopK问题 力扣 215. 数组中的第K个最大元素 题解 每日一题代码实现#includevector#includecstdlib#includectimeusingnamespacestd;classSolution{public:// 递归函数在nums的[begin, end]闭区间内找第k个最小的元素intTopK(vectorintnums,intbegin,intend,intk){// 递归终止条件区间只有一个元素该元素就是目标if(beginend)returnnums[begin];// 1. 随机选择基准值避免有序数组下的最坏时间复杂度intmarknums[(rand()%(end-begin1))begin];// 三指针定义intleftbegin-1;// 左区间mark的右边界intrightend1;// 右区间mark的左边界intibegin;// 遍历指针// 2. 三指针分区将数组划分为 mark、mark、mark 三个区间while(iright){if(nums[i]mark){// 元素归入左区间左边界右移交换元素遍历指针后移left;swap(nums[left],nums[i]);i;}elseif(nums[i]mark){// 元素归入中间区间直接后移遍历指针i;}else{// 元素归入右区间右边界左移交换元素遍历指针不动交换来的元素未处理right--;swap(nums[right],nums[i]);}}// 3. 计算三个区间的长度判断目标元素所在区间intlessLenleft-begin1;// 左区间长度小于基准值的元素个数intequalLenright-left-1;// 中间区间长度等于基准值的元素个数if(klessLen){// 目标在左区间递归处理左区间returnTopK(nums,begin,left,k);}elseif(klessLenequalLen){// 目标在中间区间基准值就是目标元素returnmark;// 原代码返回nums[left1]等价于mark此处更直观}else{// 目标在右区间调整k值后递归处理右区间returnTopK(nums,right,end,k-lessLen-equalLen);}}intfindKthLargest(vectorintnums,intk){// 初始化随机数种子确保每次运行基准值随机srand(time(nullptr));// 第k大元素 升序数组中第 (nums.size() - k 1) 小的元素returnTopK(nums,0,nums.size()-1,nums.size()-k1);}};复杂度分析时间复杂度平均O(n)最坏O(n²)。快速选择每次仅递归处理一个子区间平均情况下子区间长度每次减半总操作次数为n n/2 n/4 ... 1 ≈ 2n因此平均时间复杂度为O(n)最坏情况为每次分区仅排除一个元素时间复杂度退化为O(n²)但随机基准值可将最坏情况的出现概率降至极低。空间复杂度平均O(logn)最坏O(n)。空间消耗主要来自递归栈平均情况下递归深度为O(logn)最坏情况下为O(n)。踩坑记录三维DP数组的初始化与溢出问题3418题中DP数组初始值必须设为INT_MIN/2而非INT_MIN。因为路径的金币可能为负数若直接用INT_MIN后续状态转移时加上负数会导致整型溢出触发未定义行为。同时开m1、n1的数组维度能有效规避第一行、第一列的边界判断减少初始化的复杂度。DP状态定义的一致性3418题的DP数组存在「数组下标与网格坐标的错位」写状态转移时必须严格保持dp[i][j]对应coins[i-1][j-1]否则会出现数组越界或逻辑错误。TopK问题的第k大/第k小转换215题中第k大和第k小的转换极易出错必须明确长度为n的数组中第k大元素 升序排序后第n-k1小的元素转换时k值计算错误会直接导致结果错误还有要注意在递归过程中K由于舍弃部分数组导致的变化。快速选择的随机基准值面试中实现快速选择时必须添加随机基准值的逻辑。若使用固定基准如区间第一个元素在有序数组的测试用例中会直接退化为O(n²)的时间复杂度不仅会超时也会影响面试官的评价。三指针分区的指针移动逻辑215题的三指针分区中元素归入右区间时遍历指针i不能后移——因为交换过来的元素还未经过判断需要重新处理否则会出现分区错误、元素遗漏的问题。如果有哪里没讲清楚、或者有更优的解法欢迎在评论区交流我会通知漂泊者第一时间回复大家如果这篇博客对你有帮助别忘了点赞支持一下也可以收藏起来方便后续刷题复习时随时翻看。要是能顺手点个关注爱弥斯还能得到漂泊者批准的游戏时间哦