Posts published in March 2019

花花酱 LeetCode 1000. Minimum Cost to Merge Stones

By zxi on March 2, 2019

There are N piles of stones arranged in a row. The i-th pile has stones[i] stones.

A move consists of merging exactly K consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these K piles.

Find the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.

Example 1:

Input: stones = [3,2,4,1], K = 2
Output: 20
Explanation: 
We start with [3, 2, 4, 1].
We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
We merge [4, 1] for a cost of 5, and we are left with [5, 5].
We merge [5, 5] for a cost of 10, and we are left with [10].
The total cost was 20, and this is the minimum possible.

Example 2:

Input: stones = [3,2,4,1], K = 3
Output: -1
Explanation: After any merge operation, there are 2 piles left, and we can't merge anymore.  So the task is impossible.

Example 3:

Input: stones = [3,5,1,2,6], K = 3
Output: 25
Explanation: 
We start with [3, 5, 1, 2, 6].
We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].
We merge [3, 8, 6] for a cost of 17, and we are left with [17].
The total cost was 25, and this is the minimum possible.

Note:

1 <= stones.length <= 30
2 <= K <= 30
1 <= stones[i] <= 100

Solution: DP

dp[i][j][k] := min cost to merge subarray i ~ j into k piles
Init: dp[i][j][k] = 0 if i==j and k == 1 else inf
ans: dp[0][n-1][1]
transition:
1. dp[i][j][k] = min{dp[i][m][1] + dp[m+1][j][k-1]} for all i <= m < j
2. dp[i][j][1] = dp[i][j][K] + sum(A[i]~A[j])

Time complexity: O(n^3)
Space complexity: O(n^2*K)

C++

// Running time: 12 ms, 12.1 MB

class Solution {

public:

int mergeStones(vector<int>& stones, int K) {

const int n = stones.size();

if ((n - 1) % (K - 1)) return -1;

const int kInf = 1e9;

vector<int> sums(n + 1);

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

sums[i + 1] = sums[i] + stones[i];

// dp[i][j][k] := min cost to merge subarray i~j into k piles.

vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(K + 1, kInf)));

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

dp[i][i][1] = 0;

for (int l = 2; l <= n; ++l) // subproblem length

for (int i = 0; i <= n - l; ++i) { // start

int j = i + l - 1; // end

for (int k = 2; k <= K; ++k) // piles

for (int m = i; m < j; m += K - 1) // split point

dp[i][j][k] = min(dp[i][j][k], dp[i][m][1] + dp[m + 1][j][k - 1]);

dp[i][j][1] = dp[i][j][K] + sums[j + 1] - sums[i];

}

return dp[0][n - 1][1];

}

};

C++/top down

// Author: Huahua, running time: 12 ms

class Solution {

public:

int mergeStones(vector<int>& stones, int K) {

const int n = stones.size();

if ((n - 1) % (K - 1)) return -1;

const int kInf = 1e9;

vector<int> sums(n + 1);

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

sums[i + 1] = sums[i] + stones[i];

vector<vector<vector<int>>> cache(n, vector<vector<int>>(n, vector<int>(K + 1, INT_MAX)));

std::function<int(int, int, int)> dp = [&stones, &sums, &cache, kInf, n, K, &dp](int i, int j, int k) {

if ((j - i + 1 - k) % (K - 1)) return kInf;

if (i == j) return k == 1 ? 0 : kInf;

if (cache[i][j][k] != INT_MAX) return cache[i][j][k];

if (k == 1)

return cache[i][j][k] = dp(i, j, K) + sums[j + 1] - sums[i];

int ans = kInf;

for (int m = i; m < j; m += K - 1) {

int l = dp(i, m, 1);

if (l >= ans) continue;

int r = dp(m + 1, j, k - 1);

if (r >= ans) continue;

ans = min(ans, l + r);

}

return cache[i][j][k] = ans;

};

return dp(0, n - 1, 1);

}

};

Solution 2: DP

dp[l][i] := min cost to merge [i, i + l) into as less piles as possible. Number of merges will be (l-1) / (K – 1) and
Transition: dp[l][i] = min(dp[m][i] + dp[l – m][i + m]) for 1 <= m < l
if ((l – 1) % (K – 1) == 0) [i, i + l) can be merged into 1 pile, dp[l][i] += sum(A[i:i+l])

Time complexity: O(n^3 / k)
Space complexity: O(n^2)

C++

// Author: Huahua 4ms, 9.6 MB

class Solution {

public:

int mergeStones(vector<int>& stones, int K) {

const int n = stones.size();

if ((n - 1) % (K - 1)) return -1;

vector<int> sums(n + 1);

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

sums[i + 1] = sums[i] + stones[i];

const int kInf = 1e9;

// dp[i][j] := min cost to merge subarray A[i] ~ A[j] into (j-i)%(K-1) + 1 piles

vector<vector<int>> dp(n, vector<int>(n, kInf));

for (int i = 0; i < n; ++i) dp[i][i] = 0;

for (int l = 2; l <= n; ++l) // subproblem length

for (int i = 0; i <= n - l; ++i) { // start

int j = i + l - 1;

for (int m = i; m < j ; m += K - 1) // split point

dp[i][j] = min(dp[i][j], dp[i][m] + dp[m + 1][j]);

// If the current length can be merged into 1 pile

// The cost is independent of the merge orders.

if ((l - 1) % (K - 1) == 0)

dp[i][j] += sums[j + 1] - sums[i];

}

return dp[0][n - 1];

}

};

C++/Top-Down

// Author: Huahua, 4 ms

class Solution {

public:

int mergeStones(vector<int>& stones, int K) {

const int n = stones.size();

if ((n - 1) % (K - 1)) return -1;

const int kInf = 1e9;

vector<vector<int>> cache(n, vector<int>(n, kInf));

vector<int> sums(n + 1);

for (int i = 0; i < stones.size(); ++i) sums[i + 1] = sums[i] + stones[i];

std::function<int(int, int)> dp;

dp = [&stones, &sums, &cache, &dp, K, kInf](int i, int j) {

const int l = j - i + 1;

if (l < K) return 0;

if (cache[i][j] != kInf) return cache[i][j];

int ans = kInf;

for (int m = i; m < j ; m += K - 1) // split point

ans = min(ans, dp(i, m) + dp(m + 1, j));

if ((l - 1) % (K - 1) == 0)

ans += sums[j + 1] - sums[i];

return cache[i][j] = ans;

};

return dp(0, n - 1);

}

};

花花酱 LeetCode 1003. Check If Word Is Valid After Substitutions

By zxi on March 2, 2019

We are given that the string "abc" is valid.

From any valid string V, we may split V into two pieces X and Y such that X + Y (X concatenated with Y) is equal to V. (X or Y may be empty.) Then, X + "abc" + Y is also valid.

If for example S = "abc", then examples of valid strings are: "abc", "aabcbc", "abcabc", "abcabcababcc". Examples of invalid strings are: "abccba", "ab", "cababc", "bac".

Return true if and only if the given string S is valid.

Example 1:

Input: "aabcbc"
Output: true
Explanation: 
We start with the valid string "abc".
Then we can insert another "abc" between "a" and "bc", resulting in "a" + "abc" + "bc" which is "aabcbc".

Example 2:

Input: "abcabcababcc"
Output: true
Explanation: 
"abcabcabc" is valid after consecutive insertings of "abc".
Then we can insert "abc" before the last letter, resulting in "abcabcab" + "abc" + "c" which is "abcabcababcc".

Example 3:

Input: "abccba"
Output: false

Example 4:

Input: "cababc"
Output: false

Note:

1 <= S.length <= 20000
S[i] is 'a', 'b', or 'c'

Solution: Stack

If current char can be appended to the stack do so, if the top of stack is “abc” pop, otherwise push the current char to the stack. Check whether the stack is empty after all chars were processed.

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

C++

// Author: Huahua, running time: 28 ms, 11.9 MB

class Solution {

public:

bool isValid(string S) {

stack<string> st;

for (char ch : S) {

if (st.empty()) {

st.push("");

}

string& s = st.top();

char exp = 'a' + s.length();

if (ch == exp) {

s += ch;

if (s == "abc") st.pop();

} else if (ch != 'a'){

return false;

} else {

st.push("a");

}

return st.empty();

}

};

花花酱 LeetCode 1002. Find Common Characters

By zxi on March 2, 2019

Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer.

You may return the answer in any order.

Example 1:

Input: ["bella","label","roller"]
Output: ["e","l","l"]

Example 2:

Input: ["cool","lock","cook"]
Output: ["c","o"]

Note:

1 <= A.length <= 100
1 <= A[i].length <= 100
A[i][j] is a lowercase letter

Solution: Min count for each character

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

C++

// Author: Huahua, running time: 12 ms

class Solution {

public:

vector<string> commonChars(vector<string>& A) {

vector<int> min_count(26, INT_MAX);

for (const string& a : A) {

vector<int> count(26, 0);

for (const char ch : a)

++count[ch - 'a'];

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

min_count[i] = min(min_count[i], count[i]);

}

vector<string> ans;

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

if (min_count[i] == INT_MAX) continue;

for (int j = 0; j < min_count[i]; ++j)

ans.push_back(string(1, 'a' + i));

}

return ans;

}

};

花花酱 LeetCode 1004. Max Consecutive Ones III

By zxi on March 2, 2019

Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s.

Example 1:

Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
Output: 6
Explanation: 
[1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Example 2:

Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
Output: 10
Explanation: 
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Note:

1 <= A.length <= 20000
0 <= K <= A.length
A[i] is 0 or 1

Solution : Sliding Window

Maintain a window that has at most K zeros

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

C++

class Solution {

public:

int longestOnes(vector<int>& A, int K) {

int l = 0;

int zeros = 0;

int ans = 0;

for (int r = 0; r < A.size(); ++r) {

if (A[r] == 0) ++zeros;

while (zeros > K)

if (A[l++] == 0) --zeros;

ans = max(ans, r - l + 1);

}

return ans;

}

};

花花酱 LeetCode 30. Substring with Concatenation of All Words

By zxi on March 2, 2019

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in sthat is a concatenation of each word in words exactly once and without any intervening characters.

Example 1:

Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
Output: []

Solution1: HashTable + Brute Force

Time complexity: O((|S| – |W|*l) * |W|*l))
Space complexity: O(|W|*l)

C++

// Author: Huahua

// std::string_view running time: 128 ms, 16 MB

// std::string running time: 156 ms, 22.4 MB

class Solution {

public:

vector<int> findSubstring(string s, vector<string>& words) {

if (words.empty() || s.empty()) return {};

const int n = words.size();

const int l = words[0].length();

if (n * l > s.length()) return {};

std::string_view ss(s);

std::unordered_map<std::string_view, int> expected;

for (const string& word : words)

++expected[string_view(word)];

vector<int> ans;

for (int i = 0; i <= ss.length() - n * l; ++i) {

std::unordered_map<std::string_view, int> seen;

int count = 0;

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

std::string_view w = ss.substr(i + j * l, l);

auto it = expected.find(w);

if (it == expected.end()) break;

if (++seen[w] > it->second) break;

++count;

}

if (count == n)

ans.push_back(i);

}

return ans;

}

};