Java | O(N) Solution with detailed explanation
Step 1\nWe turn the stones into its mod to 3 because the final result will only depends on the mods to 3. \neg. We can regard 1/4/7    2/5/8   3/6/9 as same num
Step 1\nWe turn the stones into its mod to 3 because the final result will only depends on the mods to 3. \neg. We can regard 1/4/7    2/5/8   3/6/9 as same number cause it makes same effects.\n\nStep 2\nMake an observation:\nIf Alice choose 1 first and they play the game optimally, they will have number sequence to choose like this:\n```\n1,1,2,1,2,1,2,1,2...\n```\nThen, If Alice choose 2 first they will have number sequence like this:\n```\n2,2,1,2,1,2,1,2,1...\n```\nNotice that Bob can also choose some numbers with 0 mod to 3. When there\'s odd numbers of number with 0 mod to 3, it will turn Alice and Bod\'s order.\n\nHere We have the winning strategies for Alice:\n1.Makes Bob\'s sum have to be divisible to 3\n```\n\t\t//choose1\n        if(freq[1]>0){\n            freq[1]--;\n            if(freq[0]%2==0){\n                choose1 = freq[2]>=freq[1];\n            } else {\n                choose1 = freq[2]<freq[1];\n            }\n            freq[1]++;\n        }\n\t\t\n\t\t//choose2\n        if(freq[2]>0){\n            freq[2]--;\n            if(freq[0]%2==0){\n                choose2 = freq[1]>=freq[2];\n            } else {\n                choose2 = freq[1]<freq[2];\n            }\n            freq[2]++;\n        }\n```\n2.Avoid having to remove the last number.\n```\n        //choose1\n        if(freq[1]>0){\n            freq[1]--;\n            if(freq[0]%2==0){\n                choose1 = freq[2]!=freq[1];\n            } else {\n                choose1 = freq[1]-1!=freq[2];\n            }\n            freq[1]++;\n        }\n        \n        //choose2\n        if(freq[2]>0){\n            freq[2]--;\n            if(freq[0]%2==0){\n                choose2 = freq[1]!=freq[2];\n            } else {\n                choose2 = freq[2]-1!=freq[1];\n            }\n            freq[2]++;\n        }\n```\nSo we put them together it will be:\n\n```\nclass Solution {\n    public boolean stoneGameIX(int[] stones) {\n        int[] freq = new int[3];\n        for(int stone:stones){\n            freq[stone%3]++;\n        }\n        \n        boolean choose1 = false;\n        boolean choose2 = false;\n        \n        //choose1\n        if(freq[1]>0){\n            freq[1]--;\n            if(freq[0]%2==0){\n                choose1 = freq[2]>=freq[1]&&(freq[2]!=freq[1]);\n            } else {\n                choose1 = freq[2]<freq[1]&&(freq[1]-1!=freq[2]);\n            }\n            freq[1]++;\n        }\n        \n        //choose2\n        if(freq[2]>0){\n            freq[2]--;\n            if(freq[0]%2==0){\n                choose2 = freq[1]>=freq[2]&&(freq[1]!=freq[2]);\n            } else {\n                choose2 = freq[1]<freq[2]&&(freq[2]-1!=freq[1]);\n            }\n            freq[2]++;\n        }\n        return choose1||choose2;\n    }\n}\n```\n\nVote if you like it.
[]