Posts published in “Simulation”

花花酱 LeetCode 755. Pour Water

By zxi on January 7, 2018

题目大意：

给你地形的高度，有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++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

vector<int> pourWater(vector<int>& heights, int V, int K) {

while (V--) drop(heights, K);

return heights;

}

private:

void drop(vector<int>& heights, int K) {

int best = K;

for (int d = -1; d <= 1; d += 2) {

int i = K + d;

while (i >= 0 && i < heights.size()

&& heights[i] <= heights[i - d]) {

if (heights[i] < heights[best]) best = i;

i += d;

}

if (best != K) break;

}

++heights[best];

}

};

Java

// Author: Huahua

// Running time: 12 ms

class Solution {

public int[] pourWater(int[] heights, int V, int K) {

while (V-- > 0) {

dropWater(heights, K);

}

return heights;

}

private void dropWater(int[] heights, int K) {

int best = K;

for (int d = -1; d <= 1; d += 2) {

int i = K + d;

while (i >= 0 && i < heights.length && heights[i] <= heights[i - d]) {

if (heights[i] < heights[best]) best = i;

i += d;

}

if (best != K) break;

}

++heights[best];

}

Python3

"""

Author: Huahua

Running time: 207 ms

"""

class Solution:

def pourWater(self, heights, V, K):

def drop(h, K):

best = K

for d in (-1, 1):

i = K + d

while i >= 0 and i < len(h) and h[i] <= h[i - d]:

if h[i] < h[best]:

best = i

i += d

if best != K:

break

heights[best] += 1

for _ in range(V):

drop(heights, K)

return heights

花花酱 LeetCode 749. Contain Virus

By zxi on December 18, 2017

题目大意：给你一个格子地图上面有一些病毒用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:

The number of rows and columns of grid will each be in the range [1, 50].
Each grid[i][j] will be either 0 or 1.
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)

// Author: Huahua

// Runtime: 12 ms

class Solution {

public:

int containVirus(vector<vector<int>>& grid) {

int m = grid.size();

int n = grid[0].size();

int total_walls = 0;

while (true) {

vector<int> visited(m * n, 0);

vector<int> virus_area;

vector<unordered_set<int>> nexts;

int block_index = -1;

int block_walls = -1;

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j) {

int key = i * n + j;

if (grid[i][j] != 1 || visited[key]) continue;

vector<int> curr;

unordered_set<int> next;

int walls = 0;

getArea(j, i, m, n, grid, visited, curr, next, walls);

if (next.empty()) continue;

if (nexts.empty() || next.size() > nexts[block_index].size()) {

virus_area.swap(curr);

block_index = nexts.size();

block_walls = walls;

}

nexts.push_back(std::move(next));

}

if (nexts.empty()) break;

total_walls += block_walls;

for (int i = 0; i < nexts.size(); ++i) {

if (i == block_index) {

for (const int key : virus_area) {

int y = key / n;

int x = key % n;

grid[y][x] = 2; // blocked.

}

} else {

for (const int key : nexts[i]) {

int y = key / n;

int x = key % n;

grid[y][x] = 1; // newly affected

}

return total_walls;

}

private:

void getArea(

int x, int y, int m, int n,

vector<vector<int>>& grid,

vector<int>& visited,

vector<int>& curr,

unordered_set<int>& next,

int& walls) {

static int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

if (x < 0 || x >= n || y < 0 || y >= m || grid[y][x] == 2) return;

int key = y * n + x;

// need one wall

if (grid[y][x] == 0) {

++walls;

next.insert(key);

return;

}

if (visited[key]) return;

visited[key] = 1;

curr.push_back(key);

for (int i = 0; i < 4; ++i)

getArea(x + dirs[i][0], y + dirs[i][1], m, n, grid, visited, curr, next, walls);

}

};

Related Problems:

[解题报告] LeetCode 200. Number of Islands

花花酱 LeetCode 735. Asteroid Collision

By zxi on December 3, 2017

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:

Input:

asteroids = [5, 10, -5]

Output: [5, 10]

Explanation:

The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2:

Input:

asteroids = [8, -8]

Output: []

Explanation:

The 8 and -8 collide exploding each other.

Example 3:

Input:

asteroids = [10, 2, -5]

Output: [10]

Explanation:

The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

Example 4:

Input:

asteroids = [-2, -1, 1, 2]

Output: [-2, -1, 1, 2]

Explanation:

The -2 and -1 are moving left, while the 1 and 2 are moving right.

Asteroids moving the same direction never meet, so no asteroids will meet each other.

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 ++

// Author: Huahua

// Runtime: 22 ms

class Solution {

public:

vector<int> asteroidCollision(vector<int>& asteroids) {

vector<int> s;

for (int i = 0 ; i < asteroids.size(); ++i) {

const int size = asteroids[i];

if (size > 0) { // To right, OK

s.push_back(size);

} else {

// To left

if (s.empty() || s.back() < 0) // OK when all are negtives

s.push_back(size);

else if (abs(s.back()) <= abs(size)) {

// Top of the stack is going right.

// Its size is less than the current one.

// The current one still alive!

if (abs(s.back()) < abs(size)) --i;

s.pop_back(); // Destory the top one moving right

}

// s must look like [-s1, -s2, ... , si, sj, ...]

return s;

}

};

花花酱 LeetCode 657. Judge Route Circle

By zxi on November 27, 2017

Problem:

Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place.

The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are R (Right), L (Left), U (Up) and D (down). The output should be true or false representing whether the robot makes a circle.

Example 1:

1 2	Input: "UD" Output: true

Example 2:

1 2	Input: "LL" Output: false

Idea:

Simulation

Solution:

C++

// Author: Huahua

// Runtime: 19 ms

class Solution {

public:

bool judgeCircle(string moves) {

int cx{0};

int cy{0};

for (const char move : moves) {

switch(move) {

case 'U':

cy--;

break;

case 'D':

cy++;

break;

case 'R':

cx++;

break;

case 'L':

cx--;

break;

}

return cx==0 && cy==0;

}

};

花花酱 LeetCode 683. K Empty Slots

By zxi on September 29, 2017

题目大意：有n个花盆，第i天，第flowers[i]个花盆的花会开。问是否存在一天，两朵花之间有k个空花盆。

Problem:

There is a garden with N slots. In each slot, there is a flower. The N flowers will bloom one by one in N days. In each day, there will be exactly one flower blooming and it will be in the status of blooming since then.

Given an array flowers consists of number from 1 to N. Each number in the array represents the place where the flower will open in that day.

For example, flowers[i] = x means that the unique flower that blooms at day i will be at position x, where i and x will be in the range from 1 to N.

Also given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and these flowers are not blooming.

If there isn’t such day, output -1.

Example 1:

Input: 
flowers: [1,3,2]
k: 1
Output: 2
Explanation: In the second day, the first and the third flower have become blooming.

Example 2:

Input: 
flowers: [1,2,3]
k: 1
Output: -1

Note:

The given array will be in the range [1, 20000].

Idea:

BST/Buckets

Solution 2: BST

C++

// Author: Huahua

// Runtime: 228 ms

class Solution {

public:

int kEmptySlots(vector<int>& flowers, int k) {

int n = flowers.size();

if (n == 0 || k >= n) return -1;

set<int> xs;

for (int i = 0; i < n; ++i) {

int x = flowers[i];

auto r = xs.insert(x).first;

auto l = r;

if (++r != xs.end() && *r == x + k + 1) return i + 1;

if (l != xs.begin() && *(--l) == x - k - 1) return i + 1;

}

return -1;

}

};

Solution 3: Buckets

C++

// Author: Huahua

// Runtime: 196 ms (better than 94%)

class Solution {

public:

int kEmptySlots(vector<int>& flowers, int k) {

int n = flowers.size();

if (n == 0 || k >= n) return -1;

++k;

int bs = (n + k - 1) / k;

vector<int> lows(bs, INT_MAX);

vector<int> highs(bs, INT_MIN);

for (int i = 0; i < n; ++i) {

int x = flowers[i];

int p = x / k;

if (x < lows[p]) {

lows[p] = x;

if (p > 0 && highs[p - 1] == x - k) return i + 1;

}

if (x > highs[p]) {

highs[p] = x;

if (p < bs - 1 && lows[p + 1] == x + k) return i + 1;

}

return -1;

}

};

Solution 1: TLE with latest test cases

C++

// Author: Huahua

// Runtime: 192 ms (better than 97.85%)

class Solution {

public:

int kEmptySlots(vector<int>& flowers, int k) {

int n = flowers.size();

if (n == 0 || k >= n) return -1;

std::unique_ptr<char[]> f(new char[n+1]);

memset(f.get(), 0, (n + 1)*sizeof(char));

for (int i = 0; i < n; ++i)

if (IsValid(flowers[i], k, n, f.get()))

return i + 1;

return -1;

}

private:

bool IsValid(int x, int k, int n, char* f) {

f[x] = 1;

if (x + k + 1 <= n && f[x + k + 1]) {

bool valid = true;

for (int i = 1; i <= k; ++i)

if (f[x + i]) {

valid = false;

break;

}

if (valid) return true;

}

if (x - k - 1 > 0 && f[x - k - 1]) {

for (int i = 1; i <= k; ++i)

if (f[x - i]) return false;

return true;

}

return false;

}

};

Java

// Author: Huahua

// Runtime: 17 ms

class Solution {

public int kEmptySlots(int[] flowers, int k) {

int n = flowers.length;

if (n == 0 || k >= n) return -1;

int[] f = new int[n + 1];

for (int i = 0; i < n; ++i)

if (IsValid(flowers[i], k, n, f))

return i + 1;

return -1;

}

private boolean IsValid(int x, int k, int n, int[] f) {

f[x] = 1;

if (x + k + 1 <= n && f[x + k + 1] == 1) {

boolean valid = true;

for (int i = 1; i <= k; ++i)

if (f[x + i] == 1) {

valid = false;

break;

}

if (valid) return true;

}

if (x - k - 1 > 0 && f[x - k - 1] == 1) {

for (int i = 1; i <= k; ++i)

if (f[x - i] == 1) return false;

return true;

}

return false;

}

Python

"""

Author: Huahua

Runtime: 398 ms

"""

class Solution:

def kEmptySlots(self, flowers, k):

n = len(flowers)

f = [0] * (n + 1)

i = 0

def isValid(x, k, n, f):

f[x] = 1

if x + k + 1 <= n and f[x + k + 1] == 1:

valid = True

for i in range(k):

if f[x + i + 1] == 1:

valid = False

break

if valid: return True

if x - k - 1 > 0 and f[x - k - 1] == 1:

for i in range(k):

if f[x - i - 1] == 1:

return False

return True

return False

for x in flowers:

i += 1

if isValid(x, k, n, f): return i

return -1