Posts published in “Simulation”

花花酱 LeetCode 1441. Build an Array With Stack Operations

By zxi on May 11, 2020

Given an array target and an integer n. In each iteration, you will read a number from list = {1,2,3..., n}.

Build the target array using the following operations:

Push: Read a new element from the beginning list, and push it in the array.
Pop: delete the last element of the array.
If the target array is already built, stop reading more elements.

You are guaranteed that the target array is strictly increasing, only containing numbers between 1 to n inclusive.

Return the operations to build the target array.

You are guaranteed that the answer is unique.

Example 1:

Input: target = [1,3], n = 3
Output: ["Push","Push","Pop","Push"]
Explanation: 
Read number 1 and automatically push in the array -> [1]
Read number 2 and automatically push in the array then Pop it -> [1]
Read number 3 and automatically push in the array -> [1,3]

Example 2:

Input: target = [1,2,3], n = 3
Output: ["Push","Push","Push"]

Example 3:

Input: target = [1,2], n = 4
Output: ["Push","Push"]
Explanation: You only need to read the first 2 numbers and stop.

Example 4:

Input: target = [2,3,4], n = 4
Output: ["Push","Pop","Push","Push","Push"]

Constraints:

1 <= target.length <= 100
1 <= target[i] <= 100
1 <= n <= 100
target is strictly increasing.

Solution: Simulation

For each number in target, keep discarding i if i != num by “Push” + “Pop”, until i == num. One more “Push”.

Time complexity: O(n)
Space complexity: O(n) or O(1) w/o output.

C++

// Author: Huahua

class Solution {

public:

vector<string> buildArray(vector<int>& target, int n) {

vector<string> ans;

int i = 1;

for (int num : target) {

while (i != num) {

ans.push_back("Push");

ans.push_back("Pop");

++i;

}

ans.push_back("Push");

++i;

}

return ans;

}

};

LeetCode 1422. Maximum Score After Splitting a String

By zxi on April 25, 2020

Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring).

The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

Example 1:

Input: s = "011101"
Output: 5 
Explanation: 
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5 
left = "01" and right = "1101", score = 1 + 3 = 4 
left = "011" and right = "101", score = 1 + 2 = 3 
left = "0111" and right = "01", score = 1 + 1 = 2 
left = "01110" and right = "1", score = 2 + 1 = 3

Example 2:

Input: s = "00111"
Output: 5
Explanation: When left = "00" and right = "111", we get the maximum score = 2 + 3 = 5

Example 3:

Input: s = "1111"
Output: 3

Constraints:

2 <= s.length <= 500
The string s consists of characters ‘0’ and ‘1’ only.

Solution 1: Brute Force

Time complexity: O(n^2)
Space complexity: O(1)

Solution 2: Counting

2.1 Two passes,
1st, count the number of ones of the entire string
2nd, inc zeros or dec ones according to s[i]
ans = max(zeros + ones)

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

C++

// Author: Huahua

class Solution {

public:

int maxScore(string s) {

int ones = 0;

for (char c : s)

if (c == '1') ++ones;

int zeros = 0;

int ans = 0;

for (int i = 0; i < s.length() - 1; ++i) {

if (s[i] == '0') ++zeros;

else --ones;

ans = max(ans, zeros + ones);

}

return ans;

}

};

花花酱 LeetCode 1410. HTML Entity Parser

By zxi on April 11, 2020

HTML entity parser is the parser that takes HTML code as input and replace all the entities of the special characters by the characters itself.

The special characters and their entities for HTML are:

Quotation Mark: the entity is " and symbol character is ".
Single Quote Mark: the entity is ' and symbol character is '.
Ampersand: the entity is & and symbol character is &.
Greater Than Sign: the entity is > and symbol character is >.
Less Than Sign: the entity is < and symbol character is <.
Slash: the entity is &frasl; and symbol character is /.

Given the input text string to the HTML parser, you have to implement the entity parser.

Return the text after replacing the entities by the special characters.

Example 1:

Input: text = "&amp; is an HTML entity but &ambassador; is not."
Output: "& is an HTML entity but &ambassador; is not."
Explanation: The parser will replace the &amp; entity by &

Example 2:

Input: text = "and I quote: &quot;...&quot;"
Output: "and I quote: \"...\""

Example 3:

Input: text = "Stay home! Practice on Leetcode :)"
Output: "Stay home! Practice on Leetcode :)"

Example 4:

Input: text = "x &gt; y &amp;&amp; x &lt; y is always false"
Output: "x > y && x < y is always false"

Example 5:

Input: text = "leetcode.com&frasl;problemset&frasl;all"
Output: "leetcode.com/problemset/all"

Constraints:

1 <= text.length <= 10^5
The string may contain any possible characters out of all the 256 ASCII characters.

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

string entityParser(string text) {

map<string, string> m{

{""", "\""}, {"'", "'"}, {"&", "&"},

{">", ">"}, {"<", "<"}, {"&frasl;", "/"}};

string ans;

string buf;

for (char c : text) {

buf += c;

if (buf.back() != ';') continue;

const int l = buf.size();

for (const auto& [k, v] : m) {

const int kl = k.length();

if (l >= kl && buf.substr(l - kl) == k) {

ans += buf.substr(0, l - kl) + v;

buf.clear();

break;

}

return ans + buf;

}

};

花花酱 LeetCode 1409. Queries on a Permutation With Key

By zxi on April 11, 2020

Given the array queries of positive integers between 1 and m, you have to process all queries[i] (from i=0 to i=queries.length-1) according to the following rules:

In the beginning, you have the permutation P=[1,2,3,...,m].
For the current i, find the position of queries[i] in the permutation P (indexing from 0) and then move this at the beginning of the permutation P. Notice that the position of queries[i] in P is the result for queries[i].

Return an array containing the result for the given queries.

Example 1:

Input: queries = [3,1,2,1], m = 5
Output: [2,1,2,1] 
Explanation: The queries are processed as follow: 
For i=0: queries[i]=3, P=[1,2,3,4,5], position of 3 in P is 2, then we move 3 to the beginning of P resulting in P=[3,1,2,4,5]. 
For i=1: queries[i]=1, P=[3,1,2,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,3,2,4,5]. 
For i=2: queries[i]=2, P=[1,3,2,4,5], position of 2 in P is 2, then we move 2 to the beginning of P resulting in P=[2,1,3,4,5]. 
For i=3: queries[i]=1, P=[2,1,3,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,2,3,4,5]. 
Therefore, the array containing the result is [2,1,2,1].

Example 2:

Input: queries = [4,1,2,2], m = 4
Output: [3,1,2,0]

Example 3:

Input: queries = [7,5,5,8,3], m = 8
Output: [6,5,0,7,5]

Constraints:

1 <= m <= 10^3
1 <= queries.length <= m
1 <= queries[i] <= m

Solution1: Simulation + Hashtable

Use a hashtable to store the location of each key.
For each query q, use h[q] to get the index of q, for each key, if its current index is less than q, increase their indices by 1. (move right). Set h[q] to 0.

Time complexity: O(q*m)
Space complexity: O(m)

C++

class Solution {

public:

vector<int> processQueries(vector<int>& queries, int m) {

vector<int> p(m + 1);

iota(begin(p), end(p), -1);

vector<int> ans;

for (int q : queries) {

ans.push_back(p[q]);

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

if (p[i] < p[q]) ++p[i];

p[q] = 0;

}

return ans;

}

};

Solution 2: Fenwick Tree + HashTable

Time complexity: O(qlogm)
Space complexity: O(m)

C++

// Author: Huahua

class Fenwick {

public:

explicit Fenwick(int n): vals_(n) {}

// sum(A[1~i])

int query(int i) const {

int s = 0;

while (i > 0) {

s += vals_[i];

i -= i & -i;

}

return s;

}

// A[i] += delta

void update(int i, int delta) {

while (i < vals_.size()) {

vals_[i] += delta;

i += i & -i;

}

private:

vector<int> vals_;

};

class Solution {

public:

vector<int> processQueries(vector<int>& queries, int m) {

Fenwick tree(m * 2 + 1);

vector<int> pos(m + 1);

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

tree.update(pos[i] = i + m, 1);

vector<int> ans;

for (int q : queries) {

ans.push_back(tree.query(pos[q] - 1));

tree.update(pos[q], -1); // set to 0.

tree.update(pos[q] = m--, 1); // move to the front.

}

return ans;

}

};

Python3

class Fenwick:

def __init__(self, n):

self.n = n

self.val = [0] * n

def query(self, i):

s = 0

while i > 0:

s += self.val[i]

i -= i & -i

return s

def update(self, i, delta):

while i < self.n:

self.val[i] += delta

i += i & -i

class Solution:

def processQueries(self, queries: List[int], m: int) -> List[int]:

pos = [i + m for i in range(m + 1)]

tree = Fenwick(2 * m + 1)

for i in range(1, m + 1): tree.update(i + m, 1)

ans = []

for q in queries:

ans.append(tree.query(pos[q] - 1))

tree.update(pos[q], -1)

pos[q] = m

m -= 1

tree.update(pos[q], 1)

return ans

花花酱 LeetCode 1389. Create Target Array in the Given Order

By zxi on March 22, 2020

Given two arrays of integers nums and index. Your task is to create target array under the following rules:

Initially target array is empty.
From left to right read nums[i] and index[i], insert at index index[i] the value nums[i] in target array.
Repeat the previous step until there are no elements to read in nums and index.

Return the target array.

It is guaranteed that the insertion operations will be valid.

Example 1:

Input: nums = [0,1,2,3,4], index = [0,1,2,2,1]
Output: [0,4,1,3,2]
Explanation:
nums       index     target
0            0        [0]
1            1        [0,1]
2            2        [0,1,2]
3            2        [0,1,3,2]
4            1        [0,4,1,3,2]

Example 2:

Input: nums = [1,2,3,4,0], index = [0,1,2,3,0]
Output: [0,1,2,3,4]
Explanation:
nums       index     target
1            0        [1]
2            1        [1,2]
3            2        [1,2,3]
4            3        [1,2,3,4]
0            0        [0,1,2,3,4]

Example 3:

Input: nums = [1], index = [0]
Output: [1]

Constraints:

1 <= nums.length, index.length <= 100
nums.length == index.length
0 <= nums[i] <= 100
0 <= index[i] <= i

Solution: Simulation

Time complexity: O(n) ~ O(n^2)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {

vector<int> target;

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

target.insert(begin(target) + index[i], nums[i]);

return target;

}

};