Huahua's Tech Road

花花酱 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 1408. String Matching in an Array

By zxi on April 11, 2020

Given an array of string words. Return all strings in words which is substring of another word in any order.

String words[i] is substring of words[j], if can be obtained removing some characters to left and/or right side of words[j].

Example 1:

Input: words = ["mass","as","hero","superhero"]
Output: ["as","hero"]
Explanation: "as" is substring of "mass" and "hero" is substring of "superhero".
["hero","as"] is also a valid answer.

Example 2:

Input: words = ["leetcode","et","code"]
Output: ["et","code"]
Explanation: "et", "code" are substring of "leetcode".

Example 3:

Input: words = ["blue","green","bu"]
Output: []

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 30
words[i] contains only lowercase English letters.
It’s guaranteed that words[i] will be unique.

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

vector<string> stringMatching(vector<string>& words) {

vector<string> ans;

const int n = words.size();

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

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

if (i == j) continue;

if (words[j].find(words[i]) != string::npos) {

ans.push_back(words[i]);

break;

}

return ans;

}

};

花花酱 LeetCode 1406. Stone Game III

By zxi on April 5, 2020

Alice and Bob continue their games with piles of stones. There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.

Alice and Bob take turns, with Alice starting first. On each player’s turn, that player can take 1, 2 or 3 stones from the first remaining stones in the row.

The score of each player is the sum of values of the stones taken. The score of each player is 0 initially.

The objective of the game is to end with the highest score, and the winner is the player with the highest score and there could be a tie. The game continues until all the stones have been taken.

Assume Alice and Bob play optimally.

Return “Alice” if Alice will win, “Bob” if Bob will win or “Tie” if they end the game with the same score.

Example 1:

Input: values = [1,2,3,7]
Output: "Bob"
Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.

Example 2:

Input: values = [1,2,3,-9]
Output: "Alice"
Explanation: Alice must choose all the three piles at the first move to win and leave Bob with negative score.
If Alice chooses one pile her score will be 1 and the next move Bob's score becomes 5. The next move Alice will take the pile with value = -9 and lose.
If Alice chooses two piles her score will be 3 and the next move Bob's score becomes 3. The next move Alice will take the pile with value = -9 and also lose.
Remember that both play optimally so here Alice will choose the scenario that makes her win.

Example 3:

Input: values = [1,2,3,6]
Output: "Tie"
Explanation: Alice cannot win this game. She can end the game in a draw if she decided to choose all the first three piles, otherwise she will lose.

Example 4:

Input: values = [1,2,3,-1,-2,-3,7]
Output: "Alice"

Example 5:

Input: values = [-1,-2,-3]
Output: "Tie"

Constraints:

1 <= values.length <= 50000
-1000 <= values[i] <= 1000

Solution: DP with memorization

dp(i) := max relative score the current player can get if start the game from the i-th stone.

dp(i) = max(sum(values[i:i+k]) – dp(i + k)) 1 <= k <= 3

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

C++

// Author: Huahua

class Solution {

public:

string stoneGameIII(vector<int>& stoneValue) {

const int n = stoneValue.size();

vector<int> mem(n, INT_MIN);

// Maximum `relative score` the current player can achieve

// if start from the i-th stone.

function<int(int)> dp = [&](int i) {

if (i >= n) return 0; // end of game.

if (mem[i] != INT_MIN) return mem[i];

for (int j = 0, s = 0; j < 3 && i + j < n; ++j) {

s += stoneValue[i + j];

// s - dp(.) to get `relative score`.

mem[i] = max(mem[i], s - dp(i + j + 1));

}

return mem[i];

};

const int score = dp(0);

return score > 0 ? "Alice" : (score == 0 ? "Tie" : "Bob");

}

};

Python3

# Author: Huahua

class Solution:

def stoneGameIII(self, stoneValue: List[int]) -> str:

n = len(stoneValue)

stoneValue += [0, 0, 0]

dp = [-10**9] * n + [0, 0, 0]

for i in range(n - 1, -1, -1):

for k in (1, 2, 3):

dp[i] = max(dp[i], sum(stoneValue[i:i+k]) - dp[i+k])

return "Alice" if dp[0] > 0 else "Bob" if dp[0] < 0 else "Tie"

花花酱 LeetCode 1405. Longest Happy String

By zxi on April 5, 2020

A string is called happy if it does not have any of the strings 'aaa', 'bbb' or 'ccc' as a substring.

Given three integers a, b and c, return any string s, which satisfies following conditions:

s is happy and longest possible.
s contains at most a occurrences of the letter 'a', at most b occurrences of the letter 'b' and at most c occurrences of the letter 'c'.
s will only contain 'a', 'b' and 'c' letters.

If there is no such string s return the empty string "".

Example 1:

Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.

Example 2:

Input: a = 2, b = 2, c = 1
Output: "aabbc"

Example 3:

Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It's the only correct answer in this case.

Constraints:

0 <= a, b, c <= 100
a + b + c > 0

Solution: Greedy

Put the char with highest frequency first if its consecutive length of that char is < 2
or put one char if any of other two chars has consecutive length of 2.

increase the consecutive length of itself and reset that for other two chars.

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

C++

// Author: Huahua

class Solution {

public:

string longestDiverseString(int a, int b, int c) {

const int total = a + b + c;

vector<int> f{a, b, c};

vector<int> l{0, 0, 0};

string ans;

for (int _ = 0; _ < total; ++_)

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

const int j = (i + 1) % 3;

const int k = (i + 2) % 3;

if ((f[i] >= f[j] && f[i] >= f[k] && l[i] != 2)

|| (f[i] > 0 && (l[j] == 2 || l[k] == 2))) {

ans += 'a' + i;

++l[i];

--f[i];

l[j] = l[k] = 0;

break;

}

return ans;

}

};

花花酱 LeetCode 1404. Number of Steps to Reduce a Number in Binary Representation to One

By zxi on April 5, 2020

Given a number s in their binary representation. Return the number of steps to reduce it to 1 under the following rules:

If the current number is even, you have to divide it by 2.
If the current number is odd, you have to add 1 to it.

It’s guaranteed that you can always reach to one for all testcases.

Example 1:

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.  
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1.

Example 2:

Input: s = "10"
Output: 1
Explanation: "10" corressponds to number 2 in their decimal representation.
Step 1) 2 is even, divide by 2 and obtain 1.

Example 3:

Input: s = "1"
Output: 0

Constraints:

1 <= s.length <= 500
s consists of characters ‘0’ or ‘1’
s[0] == '1'

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int numSteps(string s) {

int ans = 0;

int carry = 0;

// The highest bit must be 1,

// process to the 2nd highest bit

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

if (s[i] - '0' + carry == 1) {

ans += 2; // odd: +1, even: / 2

carry = 1; // always has a carry

} else {

ans += 1; // even: / 2

// carray remains e.g. 1 + 1 = 10, or 0 + 0 = 00

}

// If there is a carry, then it's even, one more step.

return ans + carry;

}

};

Python3

# Author: Huahua

class Solution:

def numSteps(self, s: str) -> int:

ans, carry = 0, 0

for i in range(1, len(s)):

if ord(s[-i]) - ord('0') + carry == 1:

ans += 2

carry = 1

else:

ans += 1

return ans + carry

Huahua's Tech Road

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

Solution1: Simulation + Hashtable

C++

Solution 2: Fenwick Tree + HashTable

C++

Python3

花花酱 LeetCode 1408. String Matching in an Array

Solution: Brute Force

C++

花花酱 LeetCode 1406. Stone Game III

Solution: DP with memorization

C++

Python3

Related Problems

花花酱 LeetCode 1405. Longest Happy String

Solution: Greedy

C++

花花酱 LeetCode 1404. Number of Steps to Reduce a Number in Binary Representation to One

Solution: Simulation

C++

Python3