My C++ solution with explanation


  • 0
    W

    if first player can win. Means no matter player1 choice left or right ,at least one choice can make player1 win. But under player2' two choice. player1 must have chance to win under each of player2' choice.
    bool bstree(vector<int> nums,vector<int> player,int p,int left,int right)
    {
    p=p%2;
    if(right-left<2)
    {
    player[p]+=max(nums[left],nums[right]);
    player[(p+1)%2]+=min(nums[left],nums[right]);
    return (player[0]>=player[1])?true:false;
    }
    vector<int> p1,p2;
    p1.push_back(player[0]);
    p1.push_back(player[1]);
    p2.push_back(player[0]);
    p2.push_back(player[1]);
    p1[p]+=nums[left];
    p2[p]+=nums[right];
    if(p==1)
    return (bstree(nums,p1,p+1,left+1,right)&&bstree(nums,p2,p+1,left,right-1));
    else
    return (bstree(nums,p1,p+1,left+1,right)||bstree(nums,p2,p+1,left,right-1));
    }
    bool PredictTheWinner(vector<int>& nums) {
    int n=nums.size();
    if(n<2)
    return true;
    int left=0,right=n-1;
    vector<int> player(2,0);
    int p=0;
    vector<int> p1(2,0),p2(2,0);
    p1[p]+=nums[left];
    p2[p]+=nums[right];
    return (bstree(nums,p1,p+1,left+1,right)||bstree(nums,p2,p+1,left,right-1));
    }


  • 0
    X

    nice and clear solution


  • 0
    D

    @wzk623 Thanks. You can format the code by adding three ` before and after code when you post.

    bool bstree(vector<int> nums, vector<int> player, int p, int left, int right)
    {
    	p = p % 2;
    	if (right - left<2)
    	{
    		player[p] += max(nums[left], nums[right]);
    		player[(p + 1) % 2] += min(nums[left], nums[right]);
    		return (player[0] >= player[1]) ? true : false;
    	}
    	vector<int> p1, p2;
    	p1.push_back(player[0]);
    	p1.push_back(player[1]);
    	p2.push_back(player[0]);
    	p2.push_back(player[1]);
    	p1[p] += nums[left];
    	p2[p] += nums[right];
    	if (p == 1)
    		return (bstree(nums, p1, p + 1, left + 1, right) && bstree(nums, p2, p + 1, left, right - 1));
    	else
    		return (bstree(nums, p1, p + 1, left + 1, right) || bstree(nums, p2, p + 1, left, right - 1));
    }
    bool PredictTheWinner(vector<int>& nums) {
    	int n = nums.size();
    	if (n<2)
    		return true;
    	int left = 0, right = n - 1;
    	vector<int> player(2, 0);
    	int p = 0;
    	vector<int> p1(2, 0), p2(2, 0);
    	p1[p] += nums[left];
    	p2[p] += nums[right];
    	return (bstree(nums, p1, p + 1, left + 1, right) || bstree(nums, p2, p + 1, left, right - 1));
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.