)
【LetMeFly】486.预测赢家深度优先搜索(DFS)力扣题目链接https://leetcode.cn/problems/predict-the-winner/给你一个整数数组nums。玩家 1 和玩家 2 基于这个数组设计了一个游戏。玩家 1 和玩家 2 轮流进行自己的回合玩家 1 先手。开始时两个玩家的初始分值都是0。每一回合玩家从数组的任意一端取一个数字即nums[0]或nums[nums.length - 1]取到的数字将会从数组中移除数组长度减1。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时游戏结束。如果玩家 1 能成为赢家返回true。如果两个玩家得分相等同样认为玩家 1 是游戏的赢家也返回true。你可以假设每个玩家的玩法都会使他的分数最大化。示例 1输入nums [1,5,2]输出false解释一开始玩家 1 可以从 1 和 2 中进行选择。 如果他选择 2或者 1 那么玩家 2 可以从 1或者 2 和 5 中进行选择。如果玩家 2 选择了 5 那么玩家 1 则只剩下 1或者 2 可选。 所以玩家 1 的最终分数为 1 2 3而玩家 2 为 5 。 因此玩家 1 永远不会成为赢家返回 false 。示例 2输入nums [1,5,233,7]输出true解释玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个玩家 1 都可以选择 233 。 最终玩家 1234 分比玩家 212 分获得更多的分数所以返回 true表示玩家 1 可以成为赢家。提示1 nums.length 200 nums[i] 107解题方法深度优先搜索写一个函数play计算当前可选范围是nums[l]到nums[r]时的最大得分。计算规则选l和选r得分中最大的一个终止条件nums中仅剩下一个元素返回初始状态下play结果是否≥ 0 \geq 0≥0时间复杂度O ( l e n ( n u m s ) 2 ) O(len(nums)^2)O(len(nums)2)可以看参数l ll和r rr最多有n 2 n^2n2种组合。空间复杂度O ( l e n ( n u m s ) ) O(len(nums))O(len(nums))AC代码C/* * LastEditTime: 2026-08-01 19:00:00 */classSolution{private:intplay(vectorintnums,intl,intr){if(lr){returnnums[l];}returnmax(nums[l]-play(nums,l1,r),nums[r]-play(nums,l,r-1));}public:boolpredictTheWinner(vectorintnums){returnplay(nums,0,nums.size()-1)0;}};C —— 别看双端队列版本/* * LastEditTime: 2026-08-01 18:54:52 */classSolution{private:intplay(dequeintq){if(q.empty()){return0;}intfirstq.front();q.pop_front();intscore1first-play(q);q.push_front(first);intlastq.back();q.pop_back();intscore2last-play(q);q.push_back(last);returnmax(score1,score2);}public:boolpredictTheWinner(vectorintnums){dequeintq;for(intt:nums){q.push_back(t);}returnplay(q)0;}};#ifdef_DEBUG/* [1,567,1,1,99,100] true */intmain(){string s;while(cins){vectorintvstringToVector(s);Solution sol;coutsol.predictTheWinner(v)endl;}return0;}#endif同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源
)
