Huahua’s Tech Road

花花酱 LeetCode 1431. Kids With the Greatest Number of Candies

By zxi on May 3, 2020

Given the array candies and the integer extraCandies, where candies[i] represents the number of candies that the ith kid has.

For each kid check if there is a way to distribute extraCandies among the kids such that he or she can have the greatest number of candies among them. Notice that multiple kids can have the greatest number of candies.

Example 1:

Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true] 
Explanation: 
Kid 1 has 2 candies and if he or she receives all extra candies (3) will have 5 candies --- the greatest number of candies among the kids. 
Kid 2 has 3 candies and if he or she receives at least 2 extra candies will have the greatest number of candies among the kids. 
Kid 3 has 5 candies and this is already the greatest number of candies among the kids. 
Kid 4 has 1 candy and even if he or she receives all extra candies will only have 4 candies. 
Kid 5 has 3 candies and if he or she receives at least 2 extra candies will have the greatest number of candies among the kids.

Example 2:

Input: candies = [4,2,1,1,2], extraCandies = 1
Output: [true,false,false,false,false] 
Explanation: There is only 1 extra candy, therefore only kid 1 will have the greatest number of candies among the kids regardless of who takes the extra candy.

Example 3:

Input: candies = [12,1,12], extraCandies = 10
Output: [true,false,true]

Constraints:

2 <= candies.length <= 100
1 <= candies[i] <= 100
1 <= extraCandies <= 50

Solution: Finding max

Find the maximum candies that a kid has.

ans[i] = (candies[i] + extra) >= max_candies

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

C++

// Author: Huahua

class Solution {

public:

vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {

const int threshold = *max_element(begin(candies), end(candies));

vector<bool> ans(candies.size());

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

ans[i] = (candies[i] + extraCandies) >= threshold;

return ans;

}

};

Python

# Author: Huahua

class Solution:

def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:

m = max(candies)

return [c + extraCandies >= m for c in candies]

花花酱 LeetCode 1425. Constrained Subset Sum

By zxi on April 26, 2020

Given an integer array nums and an integer k, return the maximum sum of a non-empty subset of that array such that for every two consecutive integers in the subset, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied.

A subset of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.

Example 1:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subset is [10, 2, 5, 20].

Example 2:

Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subset must be non-empty, so we choose the largest number.

Example 3:

Input: nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: The subset is [10, -2, -5, 20].

Constraints:

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

Solution: DP / Sliding window / monotonic queue

dp[i] := max sum of a subset that include nums[i]
dp[i] := max(dp[i-1], dp[i-2], …, dp[i-k-1], 0) + nums[i]

C++

// Author: Huahua

class Solution {

public:

int constrainedSubsetSum(vector<int>& nums, int k) {

const int n = nums.size();

vector<int> dp(n);

multiset<int> s{INT_MIN};

int ans = INT_MIN;

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

if (i > k) s.erase(s.equal_range(dp[i - k - 1]).first);

dp[i] = max(*rbegin(s), 0) + nums[i];

s.insert(dp[i]);

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

}

return ans;

}

};

Use a monotonic queue to track the maximum of a sliding window dp[i-k-1] ~ dp[i-1].

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

C++

// Author: Huahua 184 ms

class Solution {

public:

int constrainedSubsetSum(vector<int>& nums, int k) {

const int n = nums.size();

vector<int> dp(n);

deque<int> q;

int ans = INT_MIN;

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

if (i > k && q.front() == i - k - 1)

q.pop_front();

dp[i] = (q.empty() ? 0 : max(dp[q.front()], 0))

+ nums[i];

while (!q.empty() && dp[i] >= dp[q.back()])

q.pop_back();

q.push_back(i);

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

}

return ans;

}

};

花花酱 LeetCode 1424. Diagonal Traverse II

By zxi on April 26, 2020

Given a list of lists of integers, nums, return all elements of nums in diagonal order as shown in the below images.

Example 1:

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

Example 2:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

Example 3:

Input: nums = [[1,2,3],[4],[5,6,7],[8],[9,10,11]]
Output: [1,4,2,5,3,8,6,9,7,10,11]

Example 4:

Input: nums = [[1,2,3,4,5,6]]
Output: [1,2,3,4,5,6]

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i].length <= 10^5
1 <= nums[i][j] <= 10^9
There at most 10^5 elements in nums.

Solution: Hashtable

Use diagonal index (i + j) as key.

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

C++

// Author: Huahua

class Solution {

public:

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

vector<vector<int>> m;

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

for (int j = 0; j < nums[i].size(); ++j) {

if (m.size() <= i + j) m.push_back({});

m[i + j].push_back(nums[i][j]);

}

vector<int> ans;

for (const auto& d : m)

ans.insert(end(ans), rbegin(d), rend(d));

return ans;

}

};

Python

# Author: Huahua

class Solution:

def findDiagonalOrder(self, nums):

m = []

for i, row in enumerate(nums):

for j, v in enumerate(row):

if i + j >= len(m): m.append([])

m[i+j].append(v)

return [v for d in m for v in reversed(d)]

花花酱 LeetCode 1423. Maximum Points You Can Obtain from Cards

By zxi on April 25, 2020

There are several cards arranged in a row, and each card has an associated number of points The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

Example 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.

Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

Example 4:

Input: cardPoints = [1,1000,1], k = 1
Output: 1
Explanation: You cannot take the card in the middle. Your best score is 1.

Example 5:

Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3
Output: 202

Constraints:

1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length

Solution: Sliding Window

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

C++

// Author: Huahua

class Solution {

public:

int maxScore(vector<int>& p, int k) {

const int n = p.size();

int cur = accumulate(begin(p), begin(p) + k, 0);

int ans = cur;

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

cur = cur - p[k - i - 1] + p[n - i - 1];

ans = max(ans, cur);

}

return ans;

}

};

LeetCode 1422. Maximum Score After Splitting a String

By zxi on April 25, 2020

Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring).

The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

Example 1:

Input: s = "011101"
Output: 5 
Explanation: 
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5 
left = "01" and right = "1101", score = 1 + 3 = 4 
left = "011" and right = "101", score = 1 + 2 = 3 
left = "0111" and right = "01", score = 1 + 1 = 2 
left = "01110" and right = "1", score = 2 + 1 = 3

Example 2:

Input: s = "00111"
Output: 5
Explanation: When left = "00" and right = "111", we get the maximum score = 2 + 3 = 5

Example 3:

Input: s = "1111"
Output: 3

Constraints:

2 <= s.length <= 500
The string s consists of characters ‘0’ and ‘1’ only.

Solution 1: Brute Force

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

Solution 2: Counting

2.1 Two passes,
1st, count the number of ones of the entire string
2nd, inc zeros or dec ones according to s[i]
ans = max(zeros + ones)

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

C++

// Author: Huahua

class Solution {

public:

int maxScore(string s) {

int ones = 0;

for (char c : s)

if (c == '1') ++ones;

int zeros = 0;

int ans = 0;

for (int i = 0; i < s.length() - 1; ++i) {

if (s[i] == '0') ++zeros;

else --ones;

ans = max(ans, zeros + ones);

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1431. Kids With the Greatest Number of Candies

Solution: Finding max

C++

Python

花花酱 LeetCode 1425. Constrained Subset Sum

Solution: DP / Sliding window / monotonic queue

C++

C++

花花酱 LeetCode 1424. Diagonal Traverse II

Solution: Hashtable

C++

Python

花花酱 LeetCode 1423. Maximum Points You Can Obtain from Cards

C++

LeetCode 1422. Maximum Score After Splitting a String

Solution 1: Brute Force

Solution 2: Counting

C++