medium Archives - Page 81 of 115

花花酱 LeetCode 1052. Grumpy Bookstore Owner

By zxi on May 27, 2019

Today, the bookstore owner has a store open for customers.length minutes. Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

Example 1:

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
Output: 16
Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes. 
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

Note:

1 <= X <= customers.length == grumpy.length <= 20000
0 <= customers[i] <= 1000
0 <= grumpy[i] <= 1

Solution: Sliding Window

Sum the costumers of non grumpy minutes, recording the max sum of the sliding window of size X.

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

C++

// Author: Huahua

class Solution {

public:

int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {

int base = 0;

int window = 0;

int best_window = 0;

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

(grumpy[i] ? window : base) += customers[i];

if (i >= X && grumpy[i - X])

window -= customers[i - X];

best_window = max(best_window, window);

}

return base + best_window;

}

};

花花酱 LeetCode 718. Maximum Length of Repeated Subarray

By zxi on May 17, 2019

iven two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example 1:

Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation: 
The repeated subarray with maximum length is [3, 2, 1].

Note:

1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

Solution: DP

dp[i][j] := max length of (A[0:i], B[0:j])

dp[i][j] = dp[i – 1][j – 1] + 1 if A[i-1] == B[j-1] else 0

Time complexity: O(m*n)
Space complexity: O(m*n) -> O(n)

C++ S:O(mn)

// Author: Huahua, 176 ms / 106.4 MB

class Solution {

public:

int findLength(vector<int>& A, vector<int>& B) {

int m = A.size();

int n = B.size();

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

int ans = 0;

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

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

if (A[i - 1] == B[j - 1]) {

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

ans = max(ans, dp[i][j]);

}

return ans;

}

};

C++ S:O(min(m,n))

// Author: Huahua, 152 ms / 9.1 MB

class Solution {

public:

int findLength(vector<int>& A, vector<int>& B) {

if (A.size() < B.size()) swap(A, B);

int m = A.size();

int n = B.size();

vector<int> dp(n + 1);

int ans = 0;

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

for (int j = n; j >= 1; --j) {

dp[j] = A[i - 1] == B[j - 1] ? dp[j - 1] + 1 : 0;

ans = max(ans, dp[j]);

}

return ans;

}

};

花花酱 LeetCode 90. Subsets II

By zxi on May 15, 2019

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

<strong>Input:</strong> [1,2,2]

<strong>Output:</strong>

[

[2],

[1],

[1,2,2],

[2,2],

[1,2],

[]

]

Solution: DFS

The key to this problem is how to remove/avoid duplicates efficiently.

For the same depth, among the same numbers, only the first number can be used.

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

C++

class Solution {

public:

vector<vector<int>> subsetsWithDup(vector<int>& nums) {

const int n = nums.size();

sort(begin(nums), end(nums));

vector<vector<int>> ans;

vector<int> cur;

function<void(int)> dfs = [&](int s) {

ans.push_back(cur);

if (cur.size() == n)

return;

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

if (i > s && nums[i] == nums[i - 1]) continue;

cur.push_back(nums[i]);

dfs(i + 1);

cur.pop_back();

}

};

dfs(0);

return ans;

}

};

花花酱 LeetCode 1043. Partition Array for Maximum Sum

By zxi on May 14, 2019

Given an integer array A, you partition the array into (contiguous) subarrays of length at most K. After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning.

Example 1:

Input: A = [1,15,7,9,2,5,10], K = 3
Output: 84
Explanation: A becomes [15,15,15,9,10,10,10]

Note:

1 <= K <= A.length <= 500
0 <= A[i] <= 10^6

Solution: DP

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

dp[i] := max sum of A[1] ~ A[i]
init: dp[0] = 0
transition: dp[i] = max{dp[i – k] + max(A[i-k:i]) * k}, 1 <= k <= min(i, K)
ans: dp[n]

A = | 2 | 1 | 4 | 3 |
K = 3
dp[0] = 0
dp[1] = max(dp[0] + 2 * 1) = 2
dp[2] = max(dp[0] + 2 * 2, dp[1] + 1 * 1) = max(4, 3) = 4
dp[3] = max(dp[0] + 4 * 3, dp[1] + 4 * 2, dp[2] + 4 * 1) = max(12, 10, 8) = 12
dp[4] = max(dp[1] + 4 * 3, dp[2] + 4 * 2, dp[3] + 3 * 1) = max(14, 12, 15) = 15
best = | 4 | 4 | 4 | 3 |

C++

class Solution {

public:

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

int n = A.size();

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

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

int m = INT_MIN;

for (int k = 1; k <= K && i - k >= 0; ++k) {

m = max(m, A[i - k]);

dp[i] = max(dp[i], dp[i - k] + m * k);

}

return dp[n];

}

};

花花酱 LeetCode 640. Solve the Equation

By zxi on May 10, 2019

Solve a given equation and return the value of x in the form of string “x=#value”. The equation contains only ‘+’, ‘-‘ operation, the variable x and its coefficient.

If there is no solution for the equation, return “No solution”.

If there are infinite solutions for the equation, return “Infinite solutions”.

If there is exactly one solution for the equation, we ensure that the value of x is an integer.

Example 1:

Input: "x+5-3+x=6+x-2"
Output: "x=2"

Example 2:

Input: "x=x"
Output: "Infinite solutions"

Example 3:

Input: "2x=x"
Output: "x=0"

Example 4:

Input: "2x+3x-6x=x+2"
Output: "x=-1"

Example 5:

Input: "x=x+2"
Output: "No solution"

Solution: Parse the equation

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

C++

// Author: Huahua, 0 ms, 8.5 MB

class Solution {

public:

string solveEquation(const string& equation) {

auto parse = [](string_view s) -> vector<int> {

int a{0}, b{0};

int sign = 1;

long t = 0;

bool d = false;

for (char c : s) {

if (isdigit(c)) {

d = true;

t = t * 10 + c - '0';

} else {

if (c == 'x')

a += (d ? t : 1) * sign;

else {

b += t * sign;

sign = c == '+' ? 1 : -1;

}

d = false;

t = 0;

}

b += t * sign;

return {a, b};

};

auto pos = equation.find('=');

auto l = parse(string_view(equation).substr(0, pos));

auto r = parse(string_view(equation).substr(pos + 1));

l[0] -= r[0];

l[1] -= r[1];

if (l[0] == 0)

return l[1] == 0 ? "Infinite solutions" : "No solution";

return "x=" + to_string(-l[1] / l[0]);

}

};

Posts tagged as “medium”

花花酱 LeetCode 1052. Grumpy Bookstore Owner

Solution: Sliding Window

C++

花花酱 LeetCode 718. Maximum Length of Repeated Subarray

Solution: DP

C++ S:O(mn)

C++ S:O(min(m,n))

花花酱 LeetCode 90. Subsets II

C++

花花酱 LeetCode 1043. Partition Array for Maximum Sum

Solution: DP

C++

花花酱 LeetCode 640. Solve the Equation

Solution: Parse the equation

C++