Posts tagged as “medium”

花花酱 LeetCode 528. Random Pick with Weight

By zxi on September 29, 2019

Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight.

Note:

1 <= w.length <= 10000
1 <= w[i] <= 10^5
pickIndex will be called at most 10000 times.

Example 1:

Input: 
["Solution","pickIndex"]
[[[1]],[]]
Output: [null,0]

Example 2:

Input: 
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output: [null,0,1,1,1,0]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution‘s constructor has one argument, the array w. pickIndex has no arguments. Arguments are always wrapped with a list, even if there aren’t any.

Solution: Binary Search

Crate a cumulative weight array, random sample a “weight”, do a binary search to see which bucket that weight falls in.
e.g. w = [2, 3, 1, 4], sum = [2, 5, 6, 10]
sample 3 => index = 1
sample 7 => index = 3

Time complexity: Init: O(n) Pick: O(logn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

Solution(vector<int> w): sums_(std::move(w)) {

partial_sum(begin(sums_), end(sums_), begin(sums_));

}

int pickIndex() {

int s = rand() % sums_.back();

return upper_bound(begin(sums_), end(sums_), s) - begin(sums_);

}

private:

vector<int> sums_;

};

花花酱 LeetCode 60. Permutation Sequence

By zxi on September 29, 2019

The set [1,2,3,...,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the k^th permutation sequence.

Note:

Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

Solution: Math

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

C++

// Author: Huahua

class Solution {

public:

string getPermutation(int n, int k) {

vector<int> num;

vector<int> fact(10, 1);

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

num.push_back(i);

fact[i] = fact[i - 1] * i;

}

string s;

k--;

while (n--) {

int d = k / fact[n];

k %= fact[n];

s += ('0' + num[d]);

for (int i = d + 1; i <= 9; i++)

num[i - 1] = num[i];

}

return s;

}

};

花花酱 LeetCode 59. Spiral Matrix II

By zxi on September 29, 2019

Given a positive integer n, generate a square matrix filled with elements from 1 to n² in spiral order.

Example:

Input: 3
Output:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int> > generateMatrix(int n) {

vector<vector<int>> ans(n, vector<int>(n));

int dir = 2, x = 0, y = 0;

int max_x = n - 1, max_y = n - 1;

int min_x = 0, min_y = 1;

int i = 0;

while (++i <= n*n) {

ans[y][x] = i;

switch (dir) {

// up

case 1: if (--y == min_y) { dir = 2; ++min_y; } break;

// right

case 2: if (++x == max_x) { dir = 3; --max_x; } break;

// down

case 3: if (++y == max_y) { dir = 4; --max_y; } break;

// left

case 4: if (--x == min_x) { dir = 1; ++min_x; } break;

}

return ans;

}

};

花花酱 LeetCode 1209. Remove All Adjacent Duplicates in String II

By zxi on September 29, 2019

Given a string s, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made.

It is guaranteed that the answer is unique.

Example 1:

Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete.

Example 2:

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: 
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"

Example 3:

Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"

Constraints:

1 <= s.length <= 10^5
2 <= k <= 10^4
s only contains lower case English letters.

Solution: Stack

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

C++

// Author: Huahua

class Solution {

public:

string removeDuplicates(string s, int k) {

vector<pair<char, int>> st{{'*', 0}};

for (char c : s)

if (c != st.back().first)

st.emplace_back(c, 1);

else if (++st.back().second == k)

st.pop_back();

string ans;

for (const auto& p : st)

ans.append(p.second, p.first);

return ans;

}

};

花花酱 LeetCode 1208. Get Equal Substrings Within Budget

By zxi on September 29, 2019

You are given two strings s and t of the same length. You want to change s to t. Changing the i-th character of s to i-th character of t costs |s[i] - t[i]| that is, the absolute difference between the ASCII values of the characters.

You are also given an integer maxCost.

Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of twith a cost less than or equal to maxCost.

If there is no substring from s that can be changed to its corresponding substring from t, return 0.

Example 1:

Input: s = "abcd", t = "bcdf", cost = 3
Output: 3
Explanation: "abc" of s can change to "bcd". That costs 3, so the maximum length is 3.

Example 2:

Input: s = "abcd", t = "cdef", cost = 3
Output: 1
Explanation: Each charactor in s costs 2 to change to charactor in t, so the maximum length is 1.

Example 3:

Input: s = "abcd", t = "acde", cost = 0
Output: 1
Explanation: You can't make any change, so the maximum length is 1.

Constraints:

1 <= s.length, t.length <= 10^5
0 <= maxCost <= 10^6
s and t only contain lower case English letters.

Solution 1: Binary Search

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

C++

// Author: Huahua

class Solution {

public:

int equalSubstring(string s, string t, int maxCost) {

const int n = s.length();

vector<int> c(n + 1);

auto cit = begin(c) + 1;

int ans = 0;

for (int i = 0; i < n; ++i, ++cit) {

*cit = c[i] + abs(s[i] - t[i]);

int len = cit - lower_bound(begin(c), cit, *cit - maxCost);

ans = max(ans, len);

}

return ans;

}

};

Solution 2: Sliding Window

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

C++

// Author: Huahua

class Solution {

public:

int equalSubstring(string s, string t, int maxCost) {

const int n = s.length();

int ans = 0;

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

while (j < n) {

int c = abs(s[j] - t[j]);

if (cost + c > maxCost) break;

cost += c;

++j;

}

ans = max(ans, j - i);

cost -= abs(s[i] - t[i]);

}

return ans;

}

};