Press "Enter" to skip to content

Posts tagged as “simulation”

花花酱 LeetCode 799. Champagne Tower

题目大意:往一个香槟塔(i层有i个杯子)倒入n个杯子容量的香槟之后,求指定位置杯子中酒的容量。

Problem:

https://leetcode.com/problems/champagne-tower/description/

We stack glasses in a pyramid, where the first row has 1 glass, the second row has 2 glasses, and so on until the 100th row.  Each glass holds one cup (250ml) of champagne.

Then, some champagne is poured in the first glass at the top.  When the top most glass is full, any excess liquid poured will fall equally to the glass immediately to the left and right of it.  When those glasses become full, any excess champagne will fall equally to the left and right of those glasses, and so on.  (A glass at the bottom row has it’s excess champagne fall on the floor.)

For example, after one cup of champagne is poured, the top most glass is full.  After two cups of champagne are poured, the two glasses on the second row are half full.  After three cups of champagne are poured, those two cups become full – there are 3 full glasses total now.  After four cups of champagne are poured, the third row has the middle glass half full, and the two outside glasses are a quarter full, as pictured below.

Now after pouring some non-negative integer cups of champagne, return how full the j-th glass in the i-th row is (both i and j are 0 indexed.)

 

 

Note:

  • poured will be in the range of [0, 10 ^ 9].
  • query_glass and query_row will be in the range of [0, 99].

Idea: DP + simulation

define dp[i][j] as the volume of champagne will be poured into the j -th glass in the i-th row, dp[i][j] can be greater than 1.

Init dp[0][0] = poured.

Transition: if dp[i][j] > 1, it will overflow, the overflow part will be evenly distributed to dp[i+1][j], dp[i+1][j+1]

if dp[i][j] > 1:
dp[i+1][j] += (dp[i][j] – 1) / 2.0
dp[i+1][j + 1] += (dp[i][j] – 1) / 2.0

Answer: min(1.0, dp[query_row][query_index])

Solution 1:

C++

Time complexity: O(100*100)

Space complexity: O(100*100)

Pull

 

C++

Time complexity: O(rows * 100)

Space complexity: O(100)

Push

Pull

 

花花酱 LeetCode 495. Teemo Attacking

题目大意:给你攻击的时间序列以及中毒的时长,求总共的中毒时间。

Problem:

https://leetcode.com/problems/teemo-attacking/description/

In LOL world, there is a hero called Teemo and his attacking can make his enemy Ashe be in poisoned condition. Now, given the Teemo’s attacking ascending time series towards Ashe and the poisoning time duration per Teemo’s attacking, you need to output the total time that Ashe is in poisoned condition.

You may assume that Teemo attacks at the very beginning of a specific time point, and makes Ashe be in poisoned condition immediately.

Example 1:

Input: [1,4], 2
Output: 4
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned immediately. 
This poisoned status will last 2 seconds until the end of time point 2. 
And at time point 4, Teemo attacks Ashe again, and causes Ashe to be in poisoned status for another 2 seconds. 
So you finally need to output 4.

Example 2:

Input: [1,2], 2
Output: 3
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned. 
This poisoned status will last 2 seconds until the end of time point 2. 
However, at the beginning of time point 2, Teemo attacks Ashe again who is already in poisoned status. 
Since the poisoned status won't add up together, though the second poisoning attack will still work at time point 2, it will stop at the end of time point 3. 
So you finally need to output 3.

Note:

  1. You may assume the length of given time series array won’t exceed 10000.
  2. You may assume the numbers in the Teemo’s attacking time series and his poisoning time duration per attacking are non-negative integers, which won’t exceed 10,000,000.

Idea: Running Process

Compare the current attack time with the last one, if span is more than duration, add duration to total, otherwise add (curr – last).

C++

Java

Python3

 

花花酱 LeetCode 755. Pour Water

题目大意:

给你地形的高度,有V单位的水会从K位置落下,问你稳定之后水位的高度。

Problem:

We are given an elevation map, heights[i] representing the height of the terrain at that index. The width at each index is 1. After V units of water fall at index K, how much water is at each index?

Water first drops at index K and rests on top of the highest terrain or water at that index. Then, it flows according to the following rules:

 

  • If the droplet would eventually fall by moving left, then move left.
  • Otherwise, if the droplet would eventually fall by moving right, then move right.
  • Otherwise, rise at it’s current position.

Here, “eventually fall” means that the droplet will eventually be at a lower level if it moves in that direction. Also, “level” means the height of the terrain plus any water in that column.

 

We can assume there’s infinitely high terrain on the two sides out of bounds of the array. Also, there could not be partial water being spread out evenly on more than 1 grid block – each unit of water has to be in exactly one block.

Idea:



Solution 1: Simulation

Time complexity: O(V*n)

Space complexity: O(1)

C++

Java

Python3

花花酱 LeetCode 749. Contain Virus

题目大意:给你一个格子地图上面有一些病毒用1表示,未受感染的格子用0表示。带有病毒的格子每天会向四周的格子传播病毒。在每一天,你必须在最大的病毒(连通区域)的周围建造墙阻挡病毒传播。问你一共需要多少个墙才能阻挡所有病毒传播。

Problems:

A virus is spreading rapidly, and your task is to quarantine the infected area by installing walls.

The world is modeled as a 2-D array of cells, where 0 represents uninfected cells, and 1 represents cells contaminated with the virus. A wall (and only one wall) can be installed between any two 4-directionally adjacent cells, on the shared boundary.

Every night, the virus spreads to all neighboring cells in all four directions unless blocked by a wall. Resources are limited. Each day, you can install walls around only one region — the affected area (continuous block of infected cells) that threatens the most uninfected cells the following night. There will never be a tie.

Can you save the day? If so, what is the number of walls required? If not, and the world becomes fully infected, return the number of walls used.

Example 1:

Input: grid = 
[[0,1,0,0,0,0,0,1],
 [0,1,0,0,0,0,0,1],
 [0,0,0,0,0,0,0,1],
 [0,0,0,0,0,0,0,0]]
Output: 10
Explanation:
There are 2 contaminated regions.
On the first day, add 5 walls to quarantine the viral region on the left. The board after the virus spreads is:

[[0,1,0,0,0,0,1,1],
 [0,1,0,0,0,0,1,1],
 [0,0,0,0,0,0,1,1],
 [0,0,0,0,0,0,0,1]]

On the second day, add 5 walls to quarantine the viral region on the right. The virus is fully contained.

Example 2:

Input: grid = 
[[1,1,1],
 [1,0,1],
 [1,1,1]]
Output: 4
Explanation: Even though there is only one cell saved, there are 4 walls built.
Notice that walls are only built on the shared boundary of two different cells.

Example 3:

Input: grid = 
[[1,1,1,0,0,0,0,0,0],
 [1,0,1,0,1,1,1,1,1],
 [1,1,1,0,0,0,0,0,0]]
Output: 13
Explanation: The region on the left only builds two new walls.

Note:

  1. The number of rows and columns of grid will each be in the range [1, 50].
  2. Each grid[i][j] will be either 0 or 1.
  3. Throughout the described process, there is always a contiguous viral region that will infect strictly more uncontaminated squares in the next round.

 

Idea:

Use DFS to find virus regions, next affected regions and # of walls needed to block each virus region.

Simulate the virus expansion process.

Solution:

C++ / DFS

Time complexity: O(n^3)

Space complexity: O(n^2)

Related Problems:

花花酱 LeetCode 735. Asteroid Collision

Problem:

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:

Example 2:

Example 3:

Example 4:

Note:

  • The length of asteroids will be at most 10000.
  • Each asteroid will be a non-zero integer in the range [-1000, 1000]..
Idea:
Simulation

Time complexity: O(n), Space complexity: O(n)

Solution:

C ++