花花酱 LeetCode 927. Three Equal Parts

By zxi on October 20, 2018

Problem

Given an array A of 0s and 1s, divide the array into 3 non-empty parts such that all of these parts represent the same binary value.

If it is possible, return any [i, j] with i+1 < j, such that:

A[0], A[1], ..., A[i] is the first part;
A[i+1], A[i+2], ..., A[j-1] is the second part, and
A[j], A[j+1], ..., A[A.length - 1] is the third part.
All three parts have equal binary value.

If it is not possible, return [-1, -1].

Note that the entire part is used when considering what binary value it represents. For example, [1,1,0] represents 6 in decimal, not 3. Also, leading zeros are allowed, so [0,1,1] and [1,1] represent the same value.

Example 1:

Input: [1,0,1,0,1]
Output: [0,3]

Example 2:

Input: [1,1,0,1,1]
Output: [-1,-1]

Note:

3 <= A.length <= 30000
A[i] == 0 or A[i] == 1

Solution:

each part should have the same number of 1 s.

Find the suffix (without leading os) of the last part which should have 1/3 of the total ones.

Time complexity: O(n^2) in theory but close to O(n) in practice

Space complexity: O(n)

C++

// Author: Huahua, 44 ms

class Solution {

public:

vector<int> threeEqualParts(vector<int>& A) {

string s(begin(A), end(A));

int ones = accumulate(begin(A), end(A), 0);

if (ones % 3 != 0) return {-1, -1};

if (ones == 0) return {0, A.size() - 1};

ones /= 3;

int right = A.size() - 1;

while (ones) if (A[right--]) --ones;

string suffix(begin(s) + right + 1, end(s));

size_t l = suffix.length();

size_t left = s.find(suffix);

if (left == std::string::npos) return {-1, -1};

size_t mid = s.find(suffix, left + l);

if (mid == std::string::npos

|| mid + 2 * l > s.length()) return {-1, -1};

return {left + l - 1, mid + l};

}

};

花花酱 LeetCode 926. Flip String to Monotone Increasing

By zxi on October 20, 2018

Problem

A string of '0's and '1's is monotone increasing if it consists of some number of '0's (possibly 0), followed by some number of '1's (also possibly 0.)

We are given a string S of '0's and '1's, and we may flip any '0' to a '1' or a '1' to a '0'.

Return the minimum number of flips to make S monotone increasing.

Example 1:

Input: "00110"
Output: 1
Explanation: We flip the last digit to get 00111.

Example 2:

Input: "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.

Example 3:

Input: "00011000"
Output: 2
Explanation: We flip to get 00000000.

Note:

1 <= S.length <= 20000
S only consists of '0' and '1' characters.

Solution: DP

l[i] := number of flips to make S[0] ~ S[i] become all 0s.

r[i] := number of flips to make S[i] ~ S[n – 1] become all 1s.

Try all possible break point, S[0] ~ S[i – 1] are all 0s and S[i] ~ S[n-1] are all 1s.

ans = min{l[i – 1] + r[i]}

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int minFlipsMonoIncr(string S) {

const int n = S.size();

vector<int> l(n + 1); // 1 -> 0

vector<int> r(n + 1); // 0 -> 1

l[0] = S[0] - '0';

r[n - 1] = '1' - S[n - 1];

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

l[i] = l[i - 1] + S[i] - '0';

for (int i = n - 2; i >= 0; --i)

r[i] = r[i + 1] + '1' - S[i];

int ans = r[0]; // all 1s.

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

ans = min(ans, l[i - 1] + r[i]);

return ans;

}

};

C++ v2

// Author: Huahua

class Solution {

public:

int minFlipsMonoIncr(string S) {

const int n = S.length();

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

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

if (S[i - 1] == '0') {

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

dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + 1;

} else {

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

dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]);

}

return min(dp[n][0], dp[n][1]);

}

};

C++ v2 / O(1) Space

// Author: Huahua

class Solution {

public:

int minFlipsMonoIncr(string S) {

const int n = S.length();

int dp0 = 0;

int dp1 = 0;

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

int tmp0 = dp0 + (S[i - 1] == '1');

dp1 = min(dp0, dp1) + (S[i - 1] == '0');

dp0 = tmp0;

}

return min(dp0, dp1);

}

};

花花酱 LeetCode 925. Long Pressed Name

By zxi on October 20, 2018

Problem

Your friend is typing his name into a keyboard. Sometimes, when typing a character c, the key might get long pressed, and the character will be typed 1 or more times.

You examine the typed characters of the keyboard. Return True if it is possible that it was your friends name, with some characters (possibly none) being long pressed.

Example 1:

Input: name = "alex", typed = "aaleex"
Output: true
Explanation: 'a' and 'e' in 'alex' were long pressed.

Example 2:

Input: name = "saeed", typed = "ssaaedd"
Output: false
Explanation: 'e' must have been pressed twice, but it wasn't in the typed output.

Example 3:

Input: name = "leelee", typed = "lleeelee" 
Output: true

Example 4:

Input: name = "laiden", typed = "laiden"
Output: true
Explanation: It's not necessary to long press any character.

Note:

name.length <= 1000
typed.length <= 1000
The characters of name and typed are lowercase letters.

Solution: Two Pointers

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua, 0 ms

class Solution {

public:

bool isLongPressedName(string name, string typed) {

int i = 0;

int j = 0;

while (i < name.size() && j < typed.size()) {

if (name[i] == typed[j]) {

++i;

++j;

} else if (j > 0 && typed[j] == typed[j - 1]) {

++j;

} else {

return false;

}

while (j < typed.size() && typed[j] == typed[j - 1]) ++j;

return i == name.size() && j == typed.size();

}

};

C++ / Iterator

// Author: Huahua

class Solution {

public:

bool isLongPressedName(string name, string typed) {

auto it1 = begin(name);

auto it2 = begin(typed);

while (it1 != end(name) && it2 != end(typed)) {

if (*it1 == *it2) {

++it1;

++it2;

} else if (it2 != begin(typed) && *it2 == *prev(it2)) {

++it2;

} else {

return false;

}

while (it2 != end(typed) && *it2 == *prev(it2)) ++it2;

return it1 == end(name) && it2 == end(typed);

}

};

花花酱 LeetCode 470. Implement Rand10() Using Rand7()

By zxi on October 15, 2018

Problem

Given a function rand7 which generates a uniform random integer in the range 1 to 7, write a function rand10 which generates a uniform random integer in the range 1 to 10.

Do NOT use system’s Math.random().

Example 1:

Input: 1
Output: [7]

Example 2:

Input: 2
Output: [8,4]

Example 3:

Input: 3
Output: [8,1,10]

Note:

rand7 is predefined.
Each testcase has one argument: n, the number of times that rand10 is called.

Follow up:

What is the expected value for the number of calls to rand7() function?
Could you minimize the number of calls to rand7()?

Solution:

Time complexity: O(1)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int rand10() {

int index = INT_MAX;

while (index >= 40)

index = 7 * (rand7() - 1) + (rand7() - 1);

return index % 10 + 1;

}

};

花花酱 LeetCode 922. Sort Array By Parity II

By zxi on October 13, 2018

Problem

Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.

Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.

You may return any answer array that satisfies this condition.

Example 1:

Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Note:

2 <= A.length <= 20000
A.length % 2 == 0
0 <= A[i] <= 1000

Solution 1: Brute Force

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> sortArrayByParityII(vector<int>& A) {

vector<int> evens;

vector<int> odds;

for (int a : A)

if (a % 2 == 0)

evens.push_back(a);

else

odds.push_back(a);

auto it1 = begin(evens);

auto it2 = begin(odds);

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

A[i] = *it1++;

swap(it1, it2);

}

return A;

}

};

Huahua's Tech Road

花花酱 LeetCode 927. Three Equal Parts

Problem

Solution:

C++

花花酱 LeetCode 926. Flip String to Monotone Increasing

Problem

Solution: DP

C++

C++ v2

C++ v2 / O(1) Space

花花酱 LeetCode 925. Long Pressed Name

Problem

Solution: Two Pointers

C++

C++ / Iterator

花花酱 LeetCode 470. Implement Rand10() Using Rand7()

Problem

Solution:

C++

花花酱 LeetCode 922. Sort Array By Parity II

Problem

Solution 1: Brute Force

C++