Title Address (464. Can I Win)

https://leetcode-cn.com/probl…

Topic describes

In "100 Game ", two players take turns choosing any number of integers from 1 to 10. The player who accumulates the number of integers to 100 or more is the winner. What if we changed the rules of the game to "players can't reuse integers"? For example, two players can take turns drawing integers from 1 to 15 from the common integer pool (not putting them back) until the cumulative integers and >= 100. Given one integer, maxChoosableInteger (the maximum number of integers that can be selected from the pool) and another integer, desiredTotal (the total sum), will the player who makes the first move win (assuming both players play best)? You can assume that maxChoosableInteger will not be greater than 20 and desiredTotal will not be greater than 300. Example: Input: maxChoosableInteger = 10 desiredTotal = 11 output: false Explanation: No matter which integer the first player chooses, he will fail. The first player can choose integers from 1 to 10. If the first player chooses 1, then the second player can only choose integers from 2 to 10. The second player can win by selecting the integer 10 (then the cumulative sum is 11 >= desiredTotal). Similarly, if the first player picks any other integer, the second player wins.

Front knowledge

  • Dynamic programming
  • back

The company

  • Ali.
  • linkedin

Violent solution (timeout)

Train of thought

The function signature of the title is as follows:

def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:

This gives you two integers, maxChoosableInteger and desiredTotal, and lets you return a Boolean value.

Two special cases

Let’s start with two special cases. All of the following solutions apply to both of these special cases, so I won’t go into detail here.

  • This is understandable if desiredTotal is less than or equal to maxChoosableInteger and returns True directly.
  • If the sum of all [1, maxChoosableInteger] numbers is less than desiredTotal, no one wins and False is returned.

The general situation

So now that we’re done with the special case, let’s move on to the general case.

First of all, let’s simplify things a little bit. What if we could just pick any number? This problem is much easier. It’s no different than climbing stairs. Here consider the solution of violence, using DFS + simulation way to solve.

Notice that the optional number stays the same each time, [1, maxChoosableInteger], so there is no need to pass an argument. Or if you want to pass it along, you can pass it down.

Here [1, MaxChoosableInteger] refers to an interval that is closed from left to right.

To make it easier for you to understand, I drew a logical tree:

Next, we can write code to traverse the tree.

The violence core code can be repeatedly selected as follows:

Class Solution: def CaniWin (self, maxChoosableInteger: int, desiredTotal: int) -> bool: # acc if acc >= desiredTotal: return False for n in range(1, maxChoosableInteger + 1): # If the opponent can't win in one situation, I will select this number to win. Returns true, which means I can win. If not backtrack(ACC + n): return True return False # Initialize the collection to hold the currently selected number. return dfs(0)

The above code is clear and annotated, so I won’t explain it much. So let’s move on to what happens if we don’t allow double selections of numbers?

An intuitive idea is to use a set to record the number that has been fetched. When a number is selected, if it is in a set, it is not selected. Because the optional numbers are changing dynamically. That is to say, in the logical tree section above, the optional number of each tree node is different.

So what can we do? It’s very simple, just by passing arguments. And:

  • Either sets are passed values, so they don’t affect each other.
  • Or it’s time to actively trace the state every time you recurse. For those unfamiliar, take a look at the retrospective I’ve written about before.

If you use value passing, the response would look like this:

If the state is actively traceback every time the recursion returns, the corresponding response would look like this:

Notice the new blue lines on the graph. They represent the recursive return process. We need to undo the selection during the return process. Let’s say I pick the array 2, recursively return it and remove the number 2 from the set.

A brief comparison of the two approaches.

  • Each node of the recursion tree will store a complete set. The space is approximately the number of nodes X the number of numbers in the set, so the space complexity is approximately $O(2^maxChoosableInteger * maxChoosableInteger)$, The space is unimaginable. It’s too big.
  • A way to use this state to backtrack. Since the specified number has to be removed from the set each time, the time complexity is $O(maxChoosableInteger X nodes)$, which is also too time complicated to do.

Here I use the second method – state backtracking. It looks like this, but it has a set added to it. The only thing you will notice is that you will need to restore the state in the process of tracing.

code

Code support: Python3

Python3 Code:

class Solution: def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool: if desiredTotal <= maxChoosableInteger: return True if sum(range(maxChoosableInteger + 1)) < desiredTotal: Return False # Picked: This is used to save the number that has been picked. Def backtrack(picked, ACC): if ACC >= desiredTotal: Return False if Len (Picked) == MaxChoosableInteger: # return False for n in range(1, maxChoosableInteger + 1): if n not in picked: (N) # "I will pick this number and you will be able to win." If Not Backtrack (Pick, ACC + N): Pick. Remove (N) return True Pick. Remove (N) return False # return backtrack(set(), 0)

State Compression + Backtracking

Train of thought

Some of you might ask, why don’t you use memorized recursion? This effectively reduces the number of nodes in the logical tree from exponential to polynomial. The reason for this is that sets are not directly serializable and therefore cannot be directly stored in a data structure such as a hash table.

And if you write your own serialization, like the most crude of all, converting sets to strings or primitives. Seems to work. Set is ordered, so you need to order it if you want to serialize it correctly. Of course you could use an OrderedHashSet, but it’s still not very efficient, so you can study that if you’re interested.

As shown in the figure below, the two sets should be the same, but the traversal may result in a different order, and there may be errors if they are not sorted.

At this point, the key question is basically whether it is feasible to find a serializable and greatly reduced data structure to store.

It is a strong tip to note that maxChoosableInteger is not greater than 20. Since 20 is a number no larger than 32, it is possible that this question has something to do with state compression, such as storing state in four bytes. There are a lot of buckle related topics, we can refer to the specific topic at the end of the article.

We can compress the state and simulate it with bits. In fact, using state compression is exactly the same idea as above, just with a different API.

So let’s say the number picked for “set” is picked.

  • “Picked the first” shows how the number 1 is used.
  • The second “picked” shows how the number 2 is used.
  • The third place?? Looks at the use of the number three.
  • .

For example, we just used collections. The collection APIs we used are:

  • The in operator, which determines whether a number is in the collection
  • The add(n) function, used to add a number to a collection
  • Len (), which determines the size of the collection

So we’re just going to use bit emulation to implement all three APIs. 01.01. Determine if a character is unique

What if I implement the add operation?

It’s not hard. If I want to simulate? Add (n), I’ll just set the “N” value to 1. That means 1 means in the set, 0 means out.

The OR operation and the displacement operation can be used to fulfill this requirement.

The displacement computation

1 << a

The binary of 1 means that all of them move a bit to the left, and the same thing goes for the right

| operation

a | b

It refers to a structure in which each bit of a and b performs an or operation. The common usage is a and b, one of which is seen. So we can use it as binary arrays and hash tables. Such as:

Seen = 0 b0000000 = a = 0 b0000001 b ob0000010 seen | = after a seen to 0 b0000001 seen | = b, after seen b0000011 equal to 0

So I know that A and B have occurred. Of course, A, B, and anything else you need to count can only be in one digit. Typically, the problem only needs to store 26 letters, so an int(32 bits) is sufficient. If you include caps, it’s 52, and you need at least 52 bits.

How do I implement the in operator?

It’s easy with the groundwork. For example, N in Picking. So you can figure out if the NTH place in Picked is 0 or 1. If it’s 0, it’s not in the field, and if it’s 1, it’s in the field.

The OR operation and displacement operation can be very good to complete this requirement.

& operation

a & b

It’s a structure in which each bit of a and b performs an and operation. A is a mask B is a mask B is a mask So you have to specify whether the bit is 0 or 1. Such as:

Mask = 0B0000010 A & Mask == 1 A & Mask == 0 A & Mask == 0

How to implement LEN

If the current bit is 1, the counter will be + 1, and the value of the counter will be returned at last.

That’s fine. In fact, we only care if the collection size is equal to maxChoosableInteger. That is, I only care if the first maxChoosableInteger bit and the bits below maxChoosableInteger are all 1’s.

This is easy, we just need to move 1 left to MaxChoosableInteger + 1 bit and subtract 1. One line of code to do it:

picked == (1 << (maxChoosableInteger + 1)) - 1

The above code returns true to indicate full, otherwise not full.

As you can see by this point, using bits instead of sets makes no difference in thinking. The only difference is the API. If you only use sets and do not use bitwise operations for state compression, you are not familiar with the bitwise API. Just practice a few more words. At the end of the article, I listed a few similar questions. Don’t miss them

Key point analysis

  • back
  • Dynamic programming
  • State of compression

code

Code support: Java,CPP,Python3,JS

Java Code:

public class Solution { public boolean canIWin(int maxChoosableInteger, int desiredTotal) { if (maxChoosableInteger >= desiredTotal) return true; if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false; Boolean[] dp = new Boolean[(1 << maxChoosableInteger) - 1]; return dfs(maxChoosableInteger, desiredTotal, 0, dp); } private boolean dfs(int maxChoosableInteger, int desiredTotal, int state, Boolean[] dp) { if (dp[state] ! = null) return dp[state]; for (int i = 1; i <= maxChoosableInteger; i++){ int tmp = (1 << (i - 1)); if ((tmp & state) == 0){ if (desiredTotal - i <= 0 || ! dfs(maxChoosableInteger, desiredTotal - i, tmp|state, dp)) { dp[state] = true; return true; } } } dp[state] = false; return false; }}

C++ Code:

class Solution { public: bool canIWin(int maxChoosableInteger, int desiredTotal) { int sum = (1+maxChoosableInteger)*maxChoosableInteger/2; if(sum < desiredTotal){ return false; } unordered_map<int,int> d; return dfs(maxChoosableInteger,0,desiredTotal,0,d); } bool dfs(int n,int s,int t,int S,unordered_map<int,int>& d){ if(d[S]) return d[S]; int& ans = d[S]; if(s >= t){ return ans = true; } if(S == (((1 << n)-1) << 1)){ return ans = false; } for(int m = 1; m <=n; ++m){ if(S & (1 << m)){ continue; } int nextS = S|(1 << m); if(s+m >= t){ return ans = true; } bool r1 = dfs(n,s+m,t,nextS,d); if(! r1){ return ans = true; } } return ans = false; }};

Python3 Code:


class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if desiredTotal <= maxChoosableInteger:
            return True
        if sum(range(maxChoosableInteger + 1)) < desiredTotal:
            return False

        @lru_cache(None)
        def dp(picked, acc):
            if acc >= desiredTotal:
                return False
            if picked == (1 << (maxChoosableInteger + 1)) - 1:
                return False
            for n in range(1, maxChoosableInteger + 1):
                if picked & 1 << n == 0:
                    if not dp(picked | 1 << n, acc + n):
                        return True
            return False

        return dp(0, 0)

JS Code:

var canIWin = function (maxChoosableInteger, DesiredTotal) {if (maxChoosableInteger >= desiredTotal) return true; Var sum = (maxChoosableInteger * (maxChoosableInteger + 1)) / 2; if (desiredTotal > sum) return false; Var dp = {}; /** * @Param {number} total * @Param {number} state */ function f(total, number) If (dp[state]! == undefined) return dp[state]; for (var i = 1; i <= maxChoosableInteger; i++) { var curr = 1 << i; If (curr & state) continue; If (I >= total) return (dp[state] = true); // If (! f(total - i, state | curr)) return (dp[state] = true); Return (dp[state] = false);} return (dp[state] = false); } return f(desiredTotal, 0); };

Related topics

  • 01.01. Determine whether a character is unique pure state compressed, no DP
  • 698. Divide into k equal subsets
  • 1681. Minimum incompatibility

If you have any opinions on this, please leave a message to me. I will check all the answers when I have time. More algorithm routine can access my LeetCode antithesis warehouse: https://github.com/azl3979858… . It’s already 37K Star. You can also pay attention to my public number “force buckle plus” take you to bite the algorithm this hard bone.