花花酱 LeetCode 1416. Restore The Array

By zxi on April 18, 2020

A program was supposed to print an array of integers. The program forgot to print whitespaces and the array is printed as a string of digits and all we know is that all integers in the array were in the range [1, k] and there are no leading zeros in the array.

Given the string s and the integer k. There can be multiple ways to restore the array.

Return the number of possible array that can be printed as a string s using the mentioned program.

The number of ways could be very large so return it modulo 10^9 + 7

Example 1:

Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]

Example 2:

Input: s = "1000", k = 10
Output: 0
Explanation: There cannot be an array that was printed this way and has all integer >= 1 and <= 10.

Example 3:

Input: s = "1317", k = 2000
Output: 8
Explanation: Possible arrays are [1317],[131,7],[13,17],[1,317],[13,1,7],[1,31,7],[1,3,17],[1,3,1,7]

Example 4:

Input: s = "2020", k = 30
Output: 1
Explanation: The only possible array is [20,20]. [2020] is invalid because 2020 > 30. [2,020] is ivalid because 020 contains leading zeros.

Example 5:

Input: s = "1234567890", k = 90
Output: 34

Constraints:

1 <= s.length <= 10^5.
s consists of only digits and doesn’t contain leading zeros.
1 <= k <= 10^9.

Solution: DP

dp[i] := # of ways to restore the array for s[i:n].

dp[i] = sum(dp[j]), where 0 < j < n, int(s[i:j]) <= k, s[i] != 0

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

Top-down

C++

// Author: Huahua

class Solution {

public:

int numberOfArrays(string s, int k) {

constexpr int kMod = 1e9 + 7;

const int n = s.length();

vector<int> mem(n, -1);

// dp(i) returns # of ways for s[i:n]

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

if (i == n) return 1;

if (s[i] == '0') return 0;

if (mem[i] >= 0) return mem[i];

long num = 0;

int ans = 0;

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

num = num * 10 + (s[j - 1] - '0');

if (num > k) break;

ans = (ans + dp(j)) % kMod;

}

return mem[i] = ans;

};

return dp(0);

}

};

bottom-up

C++

// Author: Huahua

class Solution {

public:

int numberOfArrays(string s, int k) {

constexpr int kMod = 1e9 + 7;

const int n = s.length();

vector<int> dp(n + 1); // # of ways for s[i:n]

dp.back() = 1;

for (int i = n - 1; i >= 0; --i) {

if (s[i] == '0') continue;

long num = 0;

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

num = num * 10 + (s[j - 1] - '0');

if (num > k) break;

dp[i] = (dp[i] + dp[j]) % kMod;

}

return dp[0];

}

};

花花酱 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 805. Split Array With Same Average

By zxi on March 24, 2018

Problem

题目大意：问能否将一个数组分成两部分，每部分的平均值相同。

In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)

Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.

Example :
Input: 
[1,2,3,4,5,6,7,8]
Output: true
Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have the average of 4.5.

Note:

The length of A will be in the range [1, 30].
A[i] will be in the range of [0, 10000].

Solution: Search

Time complexity: O(2^n)

Space complexity: O(n)

// Author: Huahua

// Running time: 771 ms

class Solution {

public:

bool splitArraySameAverage(vector<int>& A) {

std::sort(A.begin(), A.end());

sum = std::accumulate(A.begin(), A.end(), 0);

n = A.size();

return dfs(A, 1, 0, 0);

}

private:

int sum;

int n;

bool dfs(const vector<int>& A, int c, int s, int cur) {

if (c > A.size() / 2) return false;

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

cur += A[i];

if (cur * (n - c) == (sum - cur) * c) return true;

if (cur * (n - c) > (sum - cur) * c) break;

if (dfs(A, c + 1, i + 1, cur)) return true;

cur -= A[i];

}

return false;

}

};

Posts tagged as “split”

花花酱 LeetCode 1416. Restore The Array

Solution: DP

C++

C++

花花酱 LeetCode 927. Three Equal Parts

Problem

Solution:

C++

花花酱 LeetCode 805. Split Array With Same Average

Problem

Solution: Search