Posts tagged as “simulation”

花花酱 1528. Shuffle String

By zxi on July 25, 2020

Given a string s and an integer array indices of the same length.

The string s will be shuffled such that the character at the i^th position moves to indices[i] in the shuffled string.

Return the shuffled string.

Example 1:

Input: s = "codeleet", indices = [4,5,6,7,0,2,1,3]
Output: "leetcode"
Explanation: As shown, "codeleet" becomes "leetcode" after shuffling.

Example 2:

Input: s = "abc", indices = [0,1,2]
Output: "abc"
Explanation: After shuffling, each character remains in its position.

Example 3:

Input: s = "aiohn", indices = [3,1,4,2,0]
Output: "nihao"

Example 4:

Input: s = "aaiougrt", indices = [4,0,2,6,7,3,1,5]
Output: "arigatou"

Example 5:

Input: s = "art", indices = [1,0,2]
Output: "rat"

Constraints:

s.length == indices.length == n
1 <= n <= 100
s contains only lower-case English letters.
0 <= indices[i] < n
All values of indices are unique (i.e. indices is a permutation of the integers from 0 to n - 1).

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

string restoreString(string s, vector<int>& indices) {

string ans(s);

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

ans[indices[i]] = s[i];

return ans;

}

};

Java

// Author: Huahua

class Solution {

public String restoreString(String s, int[] indices) {

char[] ans = new char[s.length()];

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

ans[indices[i]] = s.charAt(i);

return new String(ans);

}

Pyhton3

class Solution:

def restoreString(self, s: str, indices: List[int]) -> str:

ans = [None] * len(s)

for i, idx in enumerate(indices):

ans[idx] = s[i]

return ''.join(ans)

花花酱 LeetCode 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits

By zxi on July 5, 2020

Given a string num representing the digits of a very large integer and an integer k.

You are allowed to swap any two adjacent digits of the integer at most k times.

Return the minimum integer you can obtain also as a string.

Example 1:

Input: num = "4321", k = 4
Output: "1342"
Explanation: The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.

Example 2:

Input: num = "100", k = 1
Output: "010"
Explanation: It's ok for the output to have leading zeros, but the input is guaranteed not to have any leading zeros.

Example 3:

Input: num = "36789", k = 1000
Output: "36789"
Explanation: We can keep the number without any swaps.

Example 4:

Input: num = "22", k = 22
Output: "22"

Example 5:

Input: num = "9438957234785635408", k = 23
Output: "0345989723478563548"

Constraints:

1 <= num.length <= 30000
num contains digits only and doesn’t have leading zeros.
1 <= k <= 10^9

Solution: Greedy + Recursion (Update: TLE after 7/6/2020)

Move the smallest number to the left and recursion on the right substring with length equals to n -= 1.

4321 k = 4 => 1 + solve(432, 4-3) = 1 + solve(432, 1) = 1 + 3 + solve(42, 0) = 1 + 3 + 42 = 1342.

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

C++

// Author: Huahua

class Solution {

public:

string minInteger(string num, int k) {

const int n = num.size();

if (k >= n * (n - 1) / 2) {

sort(begin(num), end(num));

return num;

}

int s = 0;

while (k > 0 && s < n) {

auto bit = begin(num);

auto it = min_element(bit + s, bit + min(s + k + 1, n));

k -= distance(bit + s, it);

rotate(bit + (s++), it, next(it));

}

return num;

}

};

Solution 2: Binary Indexed Tree / Fenwick Tree

Moving elements in a string is a very expensive operation, basically O(n) per op. Actually, we don’t need to move the elements physically, instead we track how many elements before i has been moved to the “front”. Thus we know the cost to move the i-th element to the “front”, which is i – elements_moved_before_i or prefix_sum(0~i-1) if we mark moved element as 1.

We know BIT / Fenwick Tree is good for dynamic prefix sum computation which helps to reduce the time complexity to O(nlogn).

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

C++

// Author: Huahua

class Fenwick {

public:

explicit Fenwick(int n) : sums_(n + 1) {}

void update(int i, int delta) {

++i;

while (i < sums_.size()) {

sums_[i] += delta;

i += i & -i;

}

int query(int i) {

++i;

int ans = 0;

while (i > 0) {

ans += sums_[i];

i -= i & -i;

}

return ans;

}

private:

vector<int> sums_;

};

class Solution {

public:

string minInteger(string num, int k) {

const int n = num.length();

vector<queue<int>> pos(10);

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

pos[num[i] - '0'].push(i);

Fenwick tree(n);

vector<int> used(n);

string ans;

while (k > 0 & ans.length() < n) {

for (int d = 0; d < 10; ++d) {

if (pos[d].empty()) continue;

const int i = pos[d].front();

const int cost = i - tree.query(i - 1);

if (cost > k) continue;

k -= cost;

ans += ('0' + d);

tree.update(i, 1);

used[i] = true;

pos[d].pop();

break;

}

};

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

if (!used[i]) ans += num[i];

return ans;

}

};

Java

// Author: Huahua

class Solution {

class Fenwick {

private int[] sums;

public Fenwick(int n) {

this.sums = new int[n + 1];

}

public void update(int i, int delta) {

++i;

while (i < sums.length) {

this.sums[i] += delta;

i += i & -i;

}

public int query(int i) {

int ans = 0;

++i;

while (i > 0) {

ans += this.sums[i];

i -= i & -i;

}

return ans;

}

public String minInteger(String num, int k) {

int n = num.length();

var used = new boolean[n];

var pos = new ArrayList<ArrayDeque<Integer>>();

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

pos.add(new ArrayDeque<Integer>());

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

pos.get(num.charAt(i) - '0').offer(i);

var tree = new Fenwick(n);

var sb = new StringBuilder();

while (k > 0 && sb.length() < n) {

for (int d = 0; d <= 9; ++d) {

Integer i = pos.get(d).peek();

if (i == null) continue;

int cost = i - tree.query(i - 1);

if (cost > k) continue;

sb.append((char)(d + '0'));

k -= cost;

pos.get(d).removeFirst();

tree.update(i, 1);

used[i] = true;

break;

}

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

if (!used[i]) sb.append(num.charAt(i));

return sb.toString();

}

Python3

# Author: Huahua

class Fenwick:

def __init__(self, n):

self.sums = [0] * (n + 1)

def query(self, i):

ans = 0

i += 1

while i > 0:

ans += self.sums[i];

i -= i & -i

return ans

def update(self, i, delta):

i += 1

while i < len(self.sums):

self.sums[i] += delta

i += i & -i

class Solution:

def minInteger(self, num: str, k: int) -> str:

n = len(num)

used = [False] * n

pos = [deque() for _ in range(10)]

for i, c in enumerate(num):

pos[ord(c) - ord("0")].append(i)

tree = Fenwick(n)

ans = []

while k > 0 and len(ans) < n:

for d in range(10):

if not pos[d]: continue

i = pos[d][0]

cost = i - tree.query(i - 1)

if cost > k: continue

k -= cost

ans.append(chr(d + ord("0")))

tree.update(i, 1)

used[i] = True

pos[d].popleft()

break

for i in range(n):

if not used[i]: ans.append(num[i])

return "".join(ans)

花花酱 LeetCode 1496. Path Crossing

By zxi on June 28, 2020

Given a string path, where path[i] = 'N', 'S', 'E' or 'W', each representing moving one unit north, south, east, or west, respectively. You start at the origin (0, 0) on a 2D plane and walk on the path specified by path.

Return True if the path crosses itself at any point, that is, if at any time you are on a location you’ve previously visited. Return False otherwise.

Example 1:

Input: path = "NES"
Output: false 
Explanation: Notice that the path doesn't cross any point more than once.

Example 2:

Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.

Constraints:

1 <= path.length <= 10^4
path will only consist of characters in {'N', 'S', 'E', 'W}

Solution: Simulation + Hashtable

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

C++

// Author: Huahua

class Solution {

public:

bool isPathCrossing(string path) {

unordered_set<int> s;

int x = 0;

int y = 0;

s.insert(x * 10000 + y);

for (char d : path) {

if (d == 'N') ++y;

else if (d == 'S') --y;

else if (d == 'E') ++x;

else if (d == 'W') --x;

if (!s.insert(x * 10000 + y).second)

return true;

}

return false;

}

};

花花酱 LeetCode 1486. XOR Operation in an Array

By zxi on June 20, 2020

Given an integer n and an integer start.

Define an array nums where nums[i] = start + 2*i (0-indexed) and n == nums.length.

Return the bitwise XOR of all elements of nums.

Example 1:

Input: n = 5, start = 0
Output: 8
Explanation: Array nums is equal to [0, 2, 4, 6, 8] where (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8.
Where "^" corresponds to bitwise XOR operator.

Example 2:

Input: n = 4, start = 3
Output: 8
Explanation: Array nums is equal to [3, 5, 7, 9] where (3 ^ 5 ^ 7 ^ 9) = 8.

Example 3:

Input: n = 1, start = 7
Output: 7

Example 4:

Input: n = 10, start = 5
Output: 2

Constraints:

1 <= n <= 1000
0 <= start <= 1000
n == nums.length

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int xorOperation(int n, int start) {

int ans = 0;

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

ans ^= (start + 2 * i);

return ans;

}

};

花花酱 LeetCode 1475. Final Prices With a Special Discount in a Shop

By zxi on June 13, 2020

Given the array prices where prices[i] is the price of the ith item in a shop. There is a special discount for items in the shop, if you buy the ith item, then you will receive a discount equivalent to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i], otherwise, you will not receive any discount at all.

Return an array where the ith element is the final price you will pay for the ith item of the shop considering the special discount.

Example 1:

Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]
Explanation: 
For item 0 with price[0]=8 you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is 8 - 4 = 4. 
For item 1 with price[1]=4 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 4 - 2 = 2. 
For item 2 with price[2]=6 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 6 - 2 = 4. 
For items 3 and 4 you will not receive any discount at all.

Example 2:

Input: prices = [1,2,3,4,5]
Output: [1,2,3,4,5]
Explanation: In this case, for all items, you will not receive any discount at all.

Example 3:

Input: prices = [10,1,1,6]
Output: [9,0,1,6]

Constraints:

1 <= prices.length <= 500
1 <= prices[i] <= 10^3

Solution 1: Simulation

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

C++

// Author: Huahua

class Solution {

public:

vector<int> finalPrices(vector<int> prices) {

const int n = prices.size();

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

for (int j = i + 1; j < n; ++j)

if (prices[j] <= prices[i]) {

prices[i] -= prices[j];

break;

}

return prices;

}

};

Solution 2: Monotonic Stack

Use a stack to store monotonically increasing items, when the current item is cheaper than the top of the stack, we get the discount and pop that item. Repeat until the current item is no longer cheaper or the stack becomes empty.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> finalPrices(vector<int> prices) {

// stores pointers of monotonically incraseing elements.

stack<int*> s;

for (int& p : prices) {

while (!s.empty() && *s.top() >= p) {

*s.top() -= p;

s.pop();

}

s.push(&p);

}

return prices;

}

};

index version

C++

// Author: Huahua

class Solution {

public:

vector<int> finalPrices(vector<int> prices) {

// stores indices of monotonically incraseing elements.

stack<int> s;

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

while (!s.empty() && prices[s.top()] >= prices[i]) {

prices[s.top()] -= prices[i];

s.pop();

}

s.push(i);

}

return prices;

}

};