“This is the sixth day of my participation in the First Challenge 2022. For details: First Challenge 2022”
describe
Alice and Bob take turns playing a game, with Alice starting first.
Initially, there are n stones in a pile. On each player’s turn, that player makes a move consisting of removing any non-zero square number of stones in the pile.
Also, if a player cannot make a move, he/she loses the game.
Given a positive integer n, return true if and only if Alice wins the game otherwise return false, assuming both players play optimally.
Example 1:
Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.
Copy the codeExample 2:
Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).
Copy the codeExample 3:
Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).
Copy the codeNote:
1 <= n <= 10^5
Copy the codeparsing
Alice and Bob took turns to play the game. There were n stones in the original pile. During each player’s turn, the player takes action, including removing any non-zero square stones from the heap. If the player is unable to perform the action, the match is lost. Now given a positive integer n, return true if and only if Alice wins the game, false otherwise.
I have a question: why must Alice win to return True in the end? Beautiful countries are not equal in human rights. Is Bob black… If Alice can force Bob into a state of defeat, Alice can win. It’s obviously playing Bob, Alice wants to play Bob and she’s trying to beat him up. It’s too small.
In fact, we can see from several examples that as long as the number of pebbles left in Alice’s turn is non-zero square, Alice can take them all at once, directly causing Bob to lose the game. Therefore, when we design DFS, we iterate over the non-zero square number I that can be operated under the condition that the number of remaining stones remain. If there is a DFS (remain-i* I) that is False, it means that the current player takes away I * I stones, In the remaining remain-i* I stones, the other player will lose no matter how he operates, which means that the current player must win and returns True. If he returns False after traversing all stones, it means that the current player does not have any operation plan to win.
Note that we use the lur_cache decorator here to ensure that there is no timeout, because the constraint is n and the maximum is 10^5, so we basically implement code with O(n) time complexity. The time complexity of a DFS call is O(N**0.5), and the time complexity of a DFS call is O(N**0.5), so there is O(N*N**0.5). However, because the lur_cache decorator is used, So a lot of the intermediate processes are O(1) in time, which actually reduces the time so much that it’s just barely AC. The space complexity is O(N) because the decorator holds the results of all DFS functions that have ever occurred.
answer
class Solution: def winnerSquareGame(self, n: int) -> bool: @lru_cache(maxsize=None) def dfs(remain): if remain == 0: Return False SQRT = int(remain**0.5) for I in range(1, remain +1): if not DFS (remain - I * I): return True return False return dfs(n)Copy the codeThe results
Given in the linked list in the given node. Submission 171.6 MB, less than 5.39% of Python3 online submissions for Stone Game IV.Copy the codeparsing
In fact, if the mnemonized DFS solution is used, dynamic programming will naturally occur, and there is no need for decorators, because the DP array of dynamic programming itself will store the results. We define DP [I] as the result of the current player’s match when there are still I stones left. Dp [I] True means that the current player must win when there are I stones, otherwise it must lose. At initialization we define a dp list of N+1 length all False. Finally, return dp[n] as our answer.
If dp[i-j*j] is False, the other party will definitely lose. That is, the current player will definitely win. At this point, we set dp[I] to True, so the result of the stone heap size of I has been found, so we can directly break the current loop, and then calculate the result of the stone heap size of I +1.
Because it is a two-layer cycle, the time complexity of the first layer is O(N), and the time complexity of the second layer is O(N**0.5), so the time complexity is O(N*N**0.5), and the space complexity is O(N).
answer
class Solution: def winnerSquareGame(self, n: int) -> bool: dp = [False] * (n + 1) for i in range(1, n + 1): if dp[i]: Continue for j in range(1, int(I ** 0.5) + 1): if not dp[i-j * j]: dp[I] = True return dp[n]Copy the codeThe results
Given in the linked list. Memory Usage: 10000 ms Submissions from Python3 online for Stone Game IV.Copy the codeThe original link
Leetcode.com/problems/st…
Your support is my biggest motivation