编程知识 cdmana.com

An algorithm problem that can be solved in one line of code

After reading this article , You can go and get the following questions :

292.Nim game

877. Stone game

319. Bulb switch

-----------

I'm in LeetCode There are three interesting things in the process of writing questions 「 brain twists 」 subject , It can be solved by algorithmic programming , But with a little thought , You can find the pattern , Come up with the answer directly .

One 、Nim game

The rules of the game are like this : You and your friends have a pile of stones in front of you , You take turns , Take at least one at a time , Three at most , Who takes the last stone wins .

Suppose you're all smart , Start with you first , Please write an algorithm , Enter a positive integer n, Back to whether you can win (true or false).

For example, there is now 4 Stone , The algorithm should return false. Because whatever you take 1 star 2 Or is it 3 star , Each other can take it all at once , Take the last stone , So you're bound to lose .

First , Dynamic programming can certainly be used in this problem , Because obviously the original problem has subproblems , And the subproblem has repetition . But because you're all smart , It's about your game with your opponent , Dynamic planning can be complicated .

Our thinking to solve this problem is generally counter thinking

If I can win , Then when it's my turn to pick up the stones, I have to leave 1~3 Stone , In this way, I can finish .

How to create such a situation ? obviously , If the opponent only has 4 Stone , So no matter how he takes , There will always be 1~3 Stone , I can win .

How to force an opponent to face 4 A stone ? Try to find a way , Let me choose when there is 5~7 Stone , In this way, I'm sure that the other side will have to face 4 Stone .

How to build 5~7 The situation of a stone ? Let the opponent face 8 Stone , No matter how he takes , Will give me the rest 5~7 star , I can win .

It goes on and on , We found that just step on 4 Multiple , They fall into a trap , Never escape 4 Multiple , And it's bound to lose . So the solution to this problem is very simple :

bool canWinNim(int n) {
    //  If you come up, step on  4  Multiple , Then give in 
    //  otherwise , You can control the other side in  4  Multiple , A winning 
    return n % 4 != 0;
}

PS: I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .

Two 、 Stone game

The rules of the game are like this : You and your friends have a row of stones in front of you , Use an array piles Express ,piles[i] It means the first one i How many stones are there . You take turns taking the stones , Take one pile at a time , But you can only take the leftmost or rightmost pile of stones . When all the stones are taken , Who owns more stones , Who wins .

Suppose you're all smart , Start with you first , Please write an algorithm , Enter an array piles, Back to whether you can win (true or false).

Be careful , The number of piles of stones is even , So you two must have taken the same number of piles . The total number of stones is odd , That is, you can't end up with the same number of stones , There must be a winner or loser .

for instance ,piles=[2, 1, 9, 5], Take... First , Can take 2 perhaps 5, You choose 2.

piles=[1, 9, 5], It's the opponent's turn , Can take 1 or 5, He chose 5.

piles=[1, 9] It's your turn to take , You take it 9.

Last , Your opponent can only take 1 了 .

So down , You all have 2 + 9 = 11 A stone , The opponent has 5 + 1 = 6 A stone , You can win , So the algorithm should return true.

You see , It's not a simple choice with big numbers , Why choose... For the first time 2 instead of 5 Well ? because 5 And then 9, If you are greedy for temporary benefits , Just put 9 The pile of stones was exposed to the opponent , Then you're going to lose .

That's why both sides emphasize it , The algorithm is also about whether you can win in the process of optimal decision .

This problem involves the game between two people , You can also use dynamic programming algorithm to try , More trouble . But we just have to think deeply about the rules , You'll be shocked : As long as you're smart enough , You are sure to win , Because you're the first one .

boolean stoneGame(int[] piles) {
    return true;
}

Why is that , Because the title has two conditions that are very important : One is that there are even piles of stones , The total number of stones is odd . These two conditions seem to increase the fairness of the game , Instead, the game became a leek cutting game . We use piles=[2, 1, 9, 5] Explain , Suppose that the indexes of the four piles of stones from left to right are 1,2,3,4.

If we divide these four piles of stones into two groups according to the parity of the index , That is to say 1、3 Heaps and rows 2、4 Pile up , So the number of stones in these two groups must be different , That is to say, a lot more and less . Because the total number of stones is odd , Can't be shared equally .

And as the first person to take a stone , You can control yourself to get all the even piles , Or all the odd heaps .

You can start with 1 Pile or pile 4 Pile up . If you want even piles , You take the first one 4 Pile up , The only choice left to the opponent is 1、3 Pile up , He doesn't care how he takes it , The first 2 The pile will be exposed again , You can take . Empathy , If you want odd piles , You take the first one 1 Pile up , The only thing left for the opponent is 2、4 Pile up , He doesn't care how he takes it , The first 3 The pile is exposed to you again .

in other words , You can observe it in the first step , There are many stones in odd piles , Or even piles of stones , Then step by step , Everything is under control . Knowing this loophole , It's time to get rid of the unknown students .

PS: I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .

3、 ... and 、 There's something wrong with the light switch

The problem is described as follows : Yes n An electric light , In the beginning, they were all closed . Now it's time to n Wheel operation :

The first 1 Wheel operation is to press the switch of each light ( Turn it all on ).

The first 2 Wheel operation is to press the switch of every two lights ( That's to say, press number 2,4,6... A light switch , They're shut down ).

The first 3 Wheel operation is to press the switch of every three lights ( That's to say, press number 3,6,9... A light switch , Some have been shut down , such as 3, Some of them are opened , such as 6)...

So back and forth , Until the first n round , That is to say, just click on number one n A light switch .

Now I'll give you a positive integer n Represents the number of electric lights , Ask you by n After wheel operation , How many of these lights are on ?

Of course, we can use a Boolean array to show the switching of these lights , And then simulate these operations , Finally, count it and you'll get the result . But it doesn't seem spiritual , The best solution is like this :

int bulbSwitch(int n) {
    return (int)Math.sqrt(n);
}

what ? What does this have to do with square roots ? In fact, this solution is very ingenious , If no one tells you the solution , It's hard to understand .

First , Because the lights were off at first , So if a certain lamp turns on at last , It must be pressed an odd number of times .

We assume that there is only 6 Lights , And we only look at the 6 Lights . Need to carry out 6 Wheel operation right , Excuse me for the 6 Lights , It's going to be pushed a few times ? It's not hard to get , The first 1 The wheel will be pressed , The first 2 round , The first 3 round , The first 6 The wheel will be pressed .

Why the 1、2、3、6 The wheel will be pressed ? because 6=1*6=2*3. In general , The factors are all in pairs , That is to say, the number of times the switch is pressed is usually even . But there are special circumstances , For example, there are 16 Lights , So the first 16 The lamp will be pressed several times ?

16=1*16=2*8=4*4

One of the factors 4 Recurring , So the first 16 The lamp will be pressed 5 Time , Odd number . Now you should understand why this problem is related to the square root ?

however , Don't we count the last few lights on , What do you mean by this direct square root ? Just think about it and you'll understand .

Let's assume that there is now a total of 16 Lights , We ask 16 The square root of , be equal to 4, This means that there will be 4 The light is on , They are the first 1*1=1 A 、 The first 2*2=4 A 、 The first 3*3=9 Zhan and di 4*4=16 A .

Even if there is n Square root result is decimal , Strong conversion int type , It's also equivalent to a maximum integer upper bound , All integers smaller than this upper bound , The index after the square is the index of the last light . So let's turn the square root directly into an integer , It's the answer to this question .

_____________

my Online e-books Yes 100 Original articles , Hands with brushes 200 Daoli is the subject , Recommended collection ! Corresponding GitHub Algorithm Repository We've got it 70k star, Welcome to mark star !

版权声明
本文为[labuladong]所创,转载请带上原文链接,感谢

Scroll to Top