preface
The concept is introduced
- In the previous section “Algorithms: What is the Asteroid Impact Problem?” We have already described in detail the basic concepts of the asteroid impact problem, so we will not repeat them here.
- Let’s use concrete examples to illustrate the principle of solving this problem
- Pay attention to
- For each asteroid, the absolute value indicates its size and the sign indicates the direction it is moving (positive to the right, negative to the left)
- If two asteroids meet, the smaller one will explode
The principle of interpretation
- For the first time, an asteroid A, of size 5, arrived. Since there is only one asteroid, it will not collide with any planets, and the planets are in a stable state. The effect is shown below.
- The second time, there was an asteroid B of size 2. Since asteroid A is moving to the right, and asteroid B is also moving to the right, there will definitely be no collision, with the effect shown below.
- The third time, an asteroid C, of -5 in size, arrived. The effect is shown below.
- Since asteroid A is moving to the right, asteroid B is also moving to the right, and asteroid C is moving to the left, so asteroid B and C must meet first and asteroid B will explode, leaving only asteroid A and C. The effect is shown below.
- Since asteroid A is moving to the right and asteroid C is moving to the left, asteroid A and Asteroid C must also meet and asteroid C will explode, leaving only asteroid A. The effect is shown below.
- Conclusion: From the above principle, we can know that the data structure used to solve the problem of asteroid collision is stack.
Results show
instructions
- In the public number to reply to the “algorithm source” can get the top ten classic sorting algorithm source
- Reply “Algorithm books” in the public account to get the classic introduction algorithm books
- Reply “data structure” in the public number to obtain data structure related source code