当前位置：首页 > news >正文

LeetCode 0486.预测赢家：深度优先搜索(DFS)

news 2026/8/2 4:38:06

【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 。 最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 true，表示玩家 1 可以成为赢家。

提示：

1 <= nums.length <= 20
0 <= nums[i] <= 10⁷

解题方法：深度优先搜索

写一个函数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(vector<int>&nums,intl,intr){if(l==r){returnnums[l];}returnmax(nums[l]-play(nums,l+1,r),nums[r]-play(nums,l,r-1));}public:boolpredictTheWinner(vector<int>&nums){returnplay(nums,0,nums.size()-1)>=0;}};

C++ —— 别看，双端队列版本

/* * @LastEditTime: 2026-08-01 18:54:52 */classSolution{private:intplay(deque<int>&q){if(q.empty()){return0;}intfirst=q.front();q.pop_front();intscore1=first-play(q);q.push_front(first);intlast=q.back();q.pop_back();intscore2=last-play(q);q.push_back(last);returnmax(score1,score2);}public:boolpredictTheWinner(vector<int>&nums){deque<int>q;for(intt:nums){q.push_back(t);}returnplay(q)>=0;}};#ifdef_DEBUG/* [1,567,1,1,99,100] true */intmain(){string s;while(cin>>s){vector<int>v=stringToVector(s);Solution sol;cout<<sol.predictTheWinner(v)<<endl;}return0;}#endif