Posts published in “Simulation”

花花酱 LeetCode 1545. Find Kth Bit in Nth Binary String

By zxi on August 10, 2020

Given two positive integers n and k, the binary string S_n is formed as follows:

S₁ = "0"
S_i = S_i-1 + "1" + reverse(invert(S_i-1)) for i > 1

Where + denotes the concatenation operation, reverse(x) returns the reversed string x, and invert(x) inverts all the bits in x (0 changes to 1 and 1 changes to 0).

For example, the first 4 strings in the above sequence are:

S₁= "0"
S₂= "011"
S₃= "0111001"
S₄ = "011100110110001"

Return the k^th bit in S_n. It is guaranteed that k is valid for the given n.

Example 1:

Input: n = 3, k = 1
Output: "0"
Explanation: S₃ is "0111001". The first bit is "0".

Example 2:

Input: n = 4, k = 11
Output: "1"
Explanation: S₄ is "011100110110001". The 11th bit is "1".

Example 3:

Input: n = 1, k = 1
Output: "0"

Example 4:

Input: n = 2, k = 3
Output: "1"

Constraints:

1 <= n <= 20
1 <= k <= 2ⁿ - 1

Solution 1: Brute Force / Simulation

Generate the string till Sn or length >= k.

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

C++

class Solution {

public:

char findKthBit(int n, int k) {

string ans = "0";

for (int i = 2; i <= n && ans.length() < k; ++i) {

string tmp(rbegin(ans), rend(ans));

for (char& c : tmp)

c = '1' - c + '0';

ans = ans + "1" + tmp;

}

return ans[k - 1];

}

};

Solution 2: Recursion

All the strings have odd length of L = (1 << n) – 1,
Let say the center m = (L + 1) / 2
if n == 1, k should be 1 and ans is “0”.
Otherwise
if k == m, we know it’s “1”.
if k < m, the answer is the same as find(n-1, K)
if k > m, we are finding a flipped and mirror char in S(n-1), thus the answer is flip(find(n-1, L – k + 1)).

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

C++

class Solution {

public:

char findKthBit(int n, int k) {

if (n == 1) return '0';

int l = (1 << n) - 1;

if (k == (l + 1) / 2) return '1';

else if (k < (l + 1) / 2)

return findKthBit(n - 1, k);

else

return '1' - findKthBit(n - 1, l - k + 1) + '0';

}

};

Java

class Solution {

public char findKthBit(int n, int k) {

if (n == 1) return '0';

int l = (1 << n) - 1;

if (k == (l + 1) / 2) return '1';

else if (k < (l + 1) / 2)

return findKthBit(n - 1, k);

else

return (char)('1' - findKthBit(n - 1, l - k + 1) + '0');

}

Python3

class Solution:

def findKthBit(self, n: int, k: int) -> str:

if n == 1: return "0"

l = (1 << n) - 1

if k == (l + 1) / 2:

return "1"

elif k < (l + 1) / 2:

return self.findKthBit(n - 1, k)

else:

return str(1 - int(self.findKthBit(n - 1, l - k + 1)))

花花酱 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 1518. Water Bottles

By zxi on July 18, 2020

Given numBottles full water bottles, you can exchange numExchange empty water bottles for one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Return the maximum number of water bottles you can drink.

Example 1:

Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.

Example 2:

Input: numBottles = 15, numExchange = 4
Output: 19
Explanation: You can exchange 4 empty bottles to get 1 full water bottle. 
Number of water bottles you can drink: 15 + 3 + 1 = 19.

Example 3:

Input: numBottles = 5, numExchange = 5
Output: 6

Example 4:

Input: numBottles = 2, numExchange = 3
Output: 2

Constraints:

1 <= numBottles <= 100
2 <= numExchange <= 100

Solution: Simulation

Time complexity: O(logb/loge)?
Space complexity: O(1)

C++

class Solution {

public:

int numWaterBottles(int numBottles, int numExchange) {

int ans = 0;

while (numBottles <= numExchange) {

const int r = numBottles % numExchange;

ans += numBottles - r;

numBottles = r + numBottles / numExchange;

}

ans += numBottles;

return ans;

}

};

Java

class Solution {

public int numWaterBottles(int numBottles, int numExchange) {

int ans = 0;

while (numBottles <= numExchange) {

final int r = numBottles % numExchange;

ans += numBottles - r;

numBottles = r + numBottles / numExchange;

}

ans += numBottles;

return ans;

}

Python3

class Solution:

def numWaterBottles(self, numBottles: int, numExchange: int) ->; int:

ans = 0

while numBottles <= numExchange:

r = numBottles % numExchange

ans += numBottles - r

numBottles = r + numBottles // numExchange

ans += numBottles

return ans

花花酱 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 1470. Shuffle the Array

By zxi on June 6, 2020

Given the array nums consisting of 2n elements in the form [x₁,x₂,...,x_n,y₁,y₂,...,y_n].

Return the array in the form [x₁,y₁,x₂,y₂,...,x_n,y_n].

Example 1:

Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7] 
Explanation: Since x₁=2, x₂=5, x₃=1, y₁=3, y₂=4, y₃=7 then the answer is [2,3,5,4,1,7].

Example 2:

Input: nums = [1,2,3,4,4,3,2,1], n = 4
Output: [1,4,2,3,3,2,4,1]

Example 3:

Input: nums = [1,1,2,2], n = 2
Output: [1,2,1,2]

Constraints:

1 <= n <= 500
nums.length == 2n
1 <= nums[i] <= 10^3

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

vector<int> shuffle(vector<int>& nums, int n) {

vector<int> ans(n * 2);

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

ans[i] = nums[i / 2 + n * (i % 2)];

return ans;

}

};