Force deduction solution summary 2029 stone game IX

Original link ： Power button

describe ：

Alice and Bob Designed a new stone game again . Existing row n A stone , Each stone has an associated number indicating its value . Give you an array of integers stones , among stones[i] It's No i The value of a stone .

Alice and Bob Take turns on your own round ,Alice First of all . Every round , Players need to start from stones  Remove any stone from the .

If the player removes the stone , Lead to All removed stones The value of   The sum of the Can be 3 to be divisible by , Then the player will Lose the game .
If you don't meet the previous one , And there are no stones left after removal , that Bob Will win directly （ Even in the Alice The round of ）.
Suppose both players use   The best Decision making . If Alice win victory , return true ; If Bob win victory , return false .

Example 1：

Input ：stones = [2,1]
Output ：true
explain ： The game proceeds as follows ：
- round 1：Alice You can remove any stone .
- round 2：Bob Remove the remaining stones . 
The sum of the values of the removed stones is 1 + 2 = 3 And can be 3 to be divisible by . therefore ,Bob transport ,Alice win victory .
Example 2：

Input ：stones = [2]
Output ：false
explain ：Alice Will remove the only stone , The sum of the values of the removed stones is 2 . 
Since all stones have been removed , And the sum of values cannot be 3 to be divisible by ,Bob win victory .
Example 3：

Input ：stones = [5,1,2,4,3]
Output ：false
explain ：Bob Always win . One possible way to play the game is as follows ：
- round 1：Alice The values that can be removed are 1 Of the 2 A stone . The sum of the removed stone values is 1 .
- round 2：Bob The values that can be removed are 3 Of the 5 A stone . The sum of the removed stone values is = 1 + 3 = 4 .
- round 3：Alices The values that can be removed are 4 Of the 4 A stone . The sum of the removed stone values is = 1 + 3 + 4 = 8 .
- round 4：Bob The values that can be removed are 2 Of the 3 A stone . The sum of the removed stone values is = 1 + 3 + 4 + 2 = 10.
- round 5：Alice The values that can be removed are 5 Of the 1 A stone . The sum of the removed stone values is = 1 + 3 + 4 + 2 + 5 = 15.
Alice Lose the game , Because the sum of stone values has been removed （15） Can be 3 to be divisible by ,Bob win victory .
 

Tips ：

1 <= stones.length <= 105
1 <= stones[i] <= 104

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/stone-game-ix
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  First of all , There are many types of numbers , But in fact, we can divide it into two categories , Because it's based on 3 To calculate the multiple of , therefore 18 Actually sum 3 It's the same thing ,1,4,7,10... The function of is the same .
*  So we just follow %3 The remainder of , It is divided into 0,1,2 Three categories are good .
*  second , If checked, 0 Words , Then it is equivalent to giving the current position to the object . Empathy , You can also choose the opposite 0 Give the option back . So we just need to make statistics 0 Whether the number of times is even . Odd numbers represent the right to choose and hand over to the other party , Even numbers do not .
*  Third , such , The rest is 1,2 The number of two categories . Suppose I choose in the first round 1 perhaps 2 It is a sure result , Then no matter how you choose the opposite side , I choose one who can choose and be with each other 3 The number of . So these steps can be omitted ,
*  therefore ,1 individual 1,N individual 2 The end result of , and 11 individual 1,10+N individual 2 The result is the same . Empathy ,N individual 1,1 individual 2 The final result and 10+N individual 1,11 individual 2 The result is the same .
*  Fourth ,1 individual 1,N individual 2 Result , If num0 When the number of is even . It must be the first choice to win .2 individual 1,1 individual 2, It must be the first choice to win . Because the first choice is the only one 1 perhaps 2, The latter can only choose 2 perhaps 1, Then the selected input .
*  Fourth ,1 individual 1,N individual 2 Result , If num0 When the quantity of is skill number . Then judge whether the difference between the two is greater than or equal to 3, Greater than or equal to 3 The person who chooses first must also win . such as A choice 2,B Can only choose 2,A choice 1,B choice 2,A choice 0, be B choice 2 Lose the game .
*  The sixth , If 1 and 2 The quantity of one party is 0 when , Then judge 1 perhaps 2 Whether the number of is greater than 3 that will do . Greater than 3 Words , The person who chooses first must lose .

Code ：

public boolean stoneGameIX(int[] stones) {

        int num0 = 0;
        int num1 = 0;
        int num2 = 0;
        for (int i = 0; i < stones.length; i++) {
            int value = stones[i] % 3;
            if (value == 0) {
                num0++;
            } else if (value == 1) {
                num1++;
            } else {
                num2++;
            }
        }

        boolean firstSelectWin = num0 % 2 == 0;
        if (num1 == 0 && num2 == 0) {
            return false;
        }
        if (num1 > 0 && num2 > 0) {
            //a If you choose first and 0 If the number of is even, you must win 
            if (firstSelectWin) {
                return true;
            }
            int abs = Math.abs(num1 - num2);
            if (abs >= 3) {
                return true;
            }
            return false;
        }
        if (num1 >= 3 || num2 >= 3) {
            return !firstSelectWin;
        }
        return false;
    }