Posts published in “Simulation”

花花酱 LeetCode 803. Bricks Falling When Hit

By zxi on March 18, 2018

Problem

题目大意：给你一堵砖墙，求每次击碎一块后掉落的砖头数量。

We have a grid of 1s and 0s; the 1s in a cell represent bricks. A brick will not drop if and only if it is directly connected to the top of the grid, or at least one of its (4-way) adjacent bricks will not drop.

We will do some erasures sequentially. Each time we want to do the erasure at the location (i, j), the brick (if it exists) on that location will disappear, and then some other bricks may drop because of that erasure.

Return an array representing the number of bricks that will drop after each erasure in sequence.

Example 1:
Input: 
grid = [[1,0,0,0],[1,1,1,0]]
hits = [[1,0]]
Output: [2]
Explanation: 
If we erase the brick at (1, 0), the brick at (1, 1) and (1, 2) will drop. So we should return 2.

Example 2:
Input: 
grid = [[1,0,0,0],[1,1,0,0]]
hits = [[1,1],[1,0]]
Output: [0,0]
Explanation: 
When we erase the brick at (1, 0), the brick at (1, 1) has already disappeared due to the last move. So each erasure will cause no bricks dropping.  Note that the erased brick (1, 0) will not be counted as a dropped brick.

Idea

For each day, hit and clear the specified brick.
Find all connected components (CCs) using DFS.
For each CC, if there is no brick that is on the first row that the entire cc will drop. Clear those CCs.

Solution: DFS

C++

// Author: Huahua

// Running time: 1261 ms

class Solution {

public:

vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {

dirs_ = {0, -1, 0, 1, 0};

m_ = grid.size();

n_ = grid[0].size();

g_.swap(grid);

seq_ = 1;

vector<int> ans;

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

ans.push_back(hit(hits[i][1], hits[i][0]));

return ans;

}

private:

vector<vector<int>> g_;

vector<int> dirs_;

int seq_;

int m_;

int n_;

// hit x, y and return the number of bricks fallen.

int hit(int x, int y) {

if (x < 0 || x >= n_ || y < 0 || y >= m_) return 0;

g_[y][x] = 0;

int ans = 0;

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

++seq_;

int count = 0;

if (!fall(x + dirs_[i], y + dirs_[i + 1], false, count)) continue;

++seq_;

ans += count;

fall(x + dirs_[i], y + dirs_[i + 1], true, count);

}

return ans;

}

// Check whether the CC contains (x, y) will fall or not.

// Set all nodes in this CC as seq_ or 0 if clear.

// count: the # of nodes in this CC.

bool fall(int x, int y, bool clear, int& count) {

if (x < 0 || x >= n_ || y < 0 || y >= m_) return true;

if (g_[y][x] == seq_ || g_[y][x] == 0) return true;

if (y == 0) return false;

g_[y][x] = clear ? 0 : seq_;

++count;

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

if (!fall(x + dirs_[i], y + dirs_[i + 1], clear, count)) return false;

return true;

}

};

Java

// Author: Huahua

// Stack Overflow (1024 recursive calls)

class Solution {

int[] dirs = new int[]{0, -1, 0, 1, 0};

int m;

int n;

int[][] g;

int seq;

int count;

public int[] hitBricks(int[][] grid, int[][] hits) {

this.g = grid;

this.m = grid.length;

this.n = grid[0].length;

int[] ans = new int[hits.length];

for (int i = 0; i < hits.length; ++i)

ans[i] = hit(hits[i][1], hits[i][0]);

return ans;

}

private int hit(int x, int y) {

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

g[y][x] = 0;

int ans = 0;

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

++seq;

count = 0;

if (!fall(x + dirs[i], y + dirs[i + 1], false)) continue;

ans += count;

++seq;

fall(x + dirs[i], y + dirs[i + 1], true);

}

return ans;

}

private boolean fall(int x, int y, boolean clear) {

if (x < 0 || x >= n || y < 0 || y >= m) return true;

if (g[y][x] == seq || g[y][x] == 0) return true;

if (y == 0) return false;

g[y][x] = clear ? 0 : seq;

++count;

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

if (!fall(x + dirs[i], y + dirs[i + 1], clear)) return false;

return true;

}

Related Problems

花花酱 LeetCode 749. Contain Virus

花花酱 LeetCode 799. Champagne Tower

By zxi on March 11, 2018

题目大意：往一个香槟塔（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.)

Example 1:

Input: poured = 1, query_glass = 1, query_row = 1

Output: 0.0

Explanation: We poured 1 cup of champagne to the top glass of the tower (which is indexed as (0, 0)). There will be no excess liquid so all the glasses under the top glass will remain empty.

Example 2:

Input: poured = 2, query_glass = 1, query_row = 1

Output: 0.5

Explanation: We poured 2 cups of champagne to the top glass of the tower (which is indexed as (0, 0)). There is one cup of excess liquid. The glass indexed as (1, 0) and the glass indexed as (1, 1) will share the excess liquid equally, and each will get half cup of champange.

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)

// Author: Huahua

// Running time: 22 ms

class Solution {

public:

double champagneTower(int poured, int query_row, int query_glass) {

constexpr int kRows = 100;

vector<vector<double>> dp(kRows, vector<double>(kRows));

dp[0][0] = poured;

for (int i = 0; i < kRows - 1; ++i)

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

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;

dp[i][j] = 1.0;

}

return std::min(1.0, dp[query_row][query_glass]);

}

};

Pull

// Author: Huahua

// Running time: 27 ms

class Solution {

public:

double champagneTower(int poured, int query_row, int query_glass) {

constexpr int kRows = 100;

vector<vector<double>> dp(kRows, vector<double>(kRows));

dp[0][0] = poured;

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

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

if (j > 0) dp[i][j] += max(0.0, (dp[i - 1][j - 1] - 1) / 2.0);

if (j < i) dp[i][j] += max(0.0, (dp[i - 1][j ] - 1) / 2.0);

}

return std::min(1.0, dp[query_row][query_glass]);

}

};

C++

Time complexity: O(rows * 100)

Space complexity: O(100)

Push

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

double champagneTower(int poured, int query_row, int query_glass) {

constexpr int kCols = 100;

vector<double> dp(kCols);

dp[0] = poured;

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

vector<double> tmp(kCols);

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

if (dp[j] > 1) {

tmp[j ] += (dp[j] - 1) / 2.0;

tmp[j + 1] += (dp[j] - 1) / 2.0;

}

dp.swap(tmp);

}

return std::min(1.0, dp[query_glass]);

}

};

Pull

class Solution {

public:

double champagneTower(int poured, int query_row, int query_glass) {

constexpr int kCols = 100;

vector<double> dp(kCols);

dp[0] = poured;

for (int i = 1; i <= query_row; ++i) {

vector<double> tmp(kCols);

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

if (j > 0) tmp[j] += max(0.0, (dp[j - 1] - 1) / 2.0);

if (j < i) tmp[j] += max(0.0, (dp[j ] - 1) / 2.0);

}

dp.swap(tmp);

}

return std::min(1.0, dp[query_glass]);

}

};

花花酱 LeetCode 495. Teemo Attacking

By zxi on March 8, 2018

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

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:

You may assume the length of given time series array won’t exceed 10000.
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++

// Author: Huahua

// Running time: 66 ms

class Solution {

public:

int findPoisonedDuration(vector<int>& t, int duration) {

if (t.empty()) return 0;

int total = 0;

for (int i = 1; i < t.size(); ++ i)

total += (t[i] > t[i - 1] + duration ? duration : t[i] - t[i - 1]);

return total + duration;

}

};

Java

// Author: Huahua

// Running time: 9 ms

class Solution {

public int findPoisonedDuration(int[] t, int duration) {

if (t.length == 0) return 0;

int total = 0;

for (int i = 1; i < t.length; ++ i)

total += (t[i] > t[i - 1] + duration ? duration : t[i] - t[i - 1]);

return total + duration;

}

Python3

"""

Author: Huahua

Running time: 64 ms (beats 100%)

"""

class Solution:

def findPoisonedDuration(self, timeSeries, duration):

if not timeSeries: return 0

l = timeSeries[0]

total = 0

for t in timeSeries:

total += duration if t - l > duration else t - l

l = t

return total + duration

import numpy as np

class Solution:

def findPoisonedDuration(self, timeSeries, duration):

if not timeSeries: return 0

d = np.diff(timeSeries)

d = np.clip(d, 0, duration)

return int(np.sum(d) + duration)

class Solution:

def findPoisonedDuration(self, t, duration):

return sum([min(c - l, duration) for l, c in zip(t, t[1:] + [1e9])])

花花酱 LeetCode 794. Valid Tic-Tac-Toe State

By zxi on March 3, 2018

题目大意：判断一个井字棋的棋盘是否有效。

A Tic-Tac-Toe board is given as a string array board. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

The board is a 3 x 3 array, and consists of characters " ", "X", and "O". The ” ” character represents an empty square.

Here are the rules of Tic-Tac-Toe:

Players take turns placing characters into empty squares (” “).
The first player always places “X” characters, while the second player always places “O” characters.
“X” and “O” characters are always placed into empty squares, never filled ones.
The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
The game also ends if all squares are non-empty.
No more moves can be played if the game is over.

Example 1:

Input: board = ["O ", " ", " "]

Output: false

Explanation: The first player always plays "X".

Example 2:

Input: board = ["XOX", " X ", " "]

Output: false

Explanation: Players take turns making moves.

Example 3:

Input: board = ["XXX", " ", "OOO"]

Output: false

Example 4:

Input: board = ["XOX", "O O", "XOX"]

Output: true

Note:

board is a length-3 array of strings, where each string board[i] has length 3.
Each board[i][j] is a character in the set {" ", "X", "O"}.

Idea: Verify all rules

C++

class Solution {

public:

bool validTicTacToe(vector<string>& board) {

int x = 0;

int o = 0;

int wins_x = getWins(board, 'X', x);

int wins_o = getWins(board, 'O', o);

return wins_x + wins_o <= 1 && x >= o + wins_x && x <= o + 1 - wins_o;

}

private:

int getWins(const vector<string>& board, char p, int& count) {

vector<string> rows(3);

string diag1, diag2;

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

diag1 += board[i][i];

diag2 += board[i][2 - i];

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

char c = board[i][j];

rows[j] += c;

count += c == p;

}

string win(3, p);

int wins = (diag1 == win) + (diag2 == win);

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

wins += rows[i] == win;

wins += board[i] == win;

}

return wins;

}

};

花花酱 LeetCode 636. Exclusive Time of Functions

By zxi on February 5, 2018

题目大意：给你一些函数的起始/终止时间的日志，让你输出每个函数的总运行时间。假设单核单线程，支持递归函数。

Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions.

Each function has a unique id, start from 0 to n-1. A function may be called recursively or by another function.

A log is a string has this format : function_id:start_or_end:timestamp. For example, "0:start:0" means function 0 starts from the very beginning of time 0. "0:end:0" means function 0 ends to the very end of time 0.

Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function’s exclusive time. You should return the exclusive time of each function sorted by their function id.

Example 1:

Input:

n = 2

logs =

["0:start:0",

"1:start:2",

"1:end:5",

"0:end:6"]

Output:[3, 4]

Explanation:

Function 0 starts at time 0, then it executes 2 units of time and reaches the end of time 1.

Now function 0 calls function 1, function 1 starts at time 2, executes 4 units of time and end at time 5.

Function 0 is running again at time 6, and also end at the time 6, thus executes 1 unit of time.

So function 0 totally execute 2 + 1 = 3 units of time, and function 1 totally execute 4 units of time.

Note:

Input logs will be sorted by timestamp, NOT log id.
Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.
Two functions won’t start or end at the same time.
Functions could be called recursively, and will always end.
1 <= n <= 100

Solution: Simulate using stack

// Author: Huahua

// Running time: 35 ms

class Solution {

public:

vector<int> exclusiveTime(int n, vector<string>& logs) {

vector<int> ans(n, 0);

char action[6];

int fid;

int curr;

int prev;

stack<int> s;

for (const string& log : logs) {

sscanf(log.c_str(), "%d:%[a-z]:%d", &fid, action, &curr);

if (action[0] == 's') {

if (!s.empty())

ans[s.top()] += curr - prev;

s.push(fid);

prev = curr;

} else {

ans[s.top()] += curr - prev + 1;

s.pop();

prev = curr + 1;

}

return ans;

}

};