The 222nd game of the week
Question 1:5641. Maximum number of units on a truck
Title description:
Please put some boxes on a truck. BoxTypes [I] = [numberOfBoxesi, numberOfUnitsPerBoxi] :
numberOfBoxesiIs a type ofiThe number of boxes.numberOfUnitsPerBoxiIs a type ofiThe number of units each bin can hold.
Integer truckSize indicates the maximum number of boxes that can be carried on a truck. As long as the number of boxes does not exceed truckSize, you can choose any box to load on the truck.
Returns the maximum number of units that a truck can load.
Example 1:
Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4 output: 8 - 2 type 2 boxes, each containing 2 units. - 3 type 3 boxes, each containing 1 unit. You can select all boxes in categories 1 and 2, as well as one box in category 3. Total number of cells = (1 * 3) + (2 * 2) + (1 * 1) = 8Copy the codeExample 2:
Input: boxTypes = [[5, 10], [2, 5], [4, 7], [3, 9]], truckSize = 10 output: 91Copy the codeTip:
1 <= boxTypes.length <= 10001 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 10001 <= truckSize <= 10^6
Greed
Load boxes with more units first
Code:
class Solution {
public:
/* Sort by the number of units in the box */
static bool cmp(vector<int>& a, vector<int>& b){
return a[1] > b[1];
}
int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
sort(boxTypes.begin(), boxTypes.end(), cmp);
int ans = 0;
for(int i = 0; i < boxTypes.size(a); i++){/* Select boxes from boxes with many units to boxes with few units and add them to the truck */
if(truckSize - boxTypes[i][0] > =0){
ans += boxTypes[i][0] * boxTypes[i][1];
truckSize -= boxTypes[i][0];
}
/* If the remaining capacity is not enough to complete the packing, special processing */
else{
int left = truckSize;
ans += left * boxTypes[i][1];
break; }}returnans; }};Copy the codeComplexity analysis:
-
Time complexity is O(n)O(n)O(n)
-
The space complexity is O(1)O(1)O(1)
Question 2:5642. Counting big meals
Title description:
A big meal is a meal that contains exactly two different dishes, the sum of which equals a power of two.
You can make a big meal with any two dishes.
Given an integer array deliciousness, where deliciousness[I] is the iciousness of the ith dish, returns the number of different dishes you can make from the array. I have to mod 10 to the ninth plus 7.
Note that as long as the subscripts are different, they can be considered different, even if they are equally delicious.
Example 1:
The degree of delicious food can be divided into (1,3), (1,7), (3,5) and (7,9). They add up to 4, 8, 8 and 16, all powers of 2.Copy the codeExample 2:
The degree of delicious food can be divided into 3 kinds (1,1), 9 kinds (1,3), and 3 kinds (1,7).Copy the codeTip:
1 <= deliciousness.length <= 10^50 <= deliciousness[i] <= 2^20
Hashing
- They want to calculate the sum of two different dishes to the power of 2, and they want to use a hash table to reduce the complexity to a linear level.
- For any given food, we included in the hash its “complementary” deliciousness, which is the sum of its deliciousness to the power of 222.
Code:
class Solution {
public:
int countPairs(vector<int>& d) {
sort(d.begin(),d.end());
const int M = 1e9 + 7;
vector<int> vec(3000000);
long long ans = 0;
for(int i = 0; i < d.size(a); i++){ ans += vec[d[i]];for(int j = 0; j < 22; j++){
if(((1<<j)-d[i])>=0) vec[(1<<j)-d[i]]++; }}returnans % M; }};Copy the codeComplexity analysis:
- Time complexity O(22n)O(22n)O(22n)
- The space complexity is O(n)O(n)O(n)
Question 3:5643. Number of schemes to divide an array into three subarrays
Title description:
We say a scheme for splitting an array of integers is good if it satisfies:
- The array is split into threeIs not emptyContinuous subarrays, named from left to right
left，mid，right。 leftThe sum is less than or equal tomidAnd,midThe sum is less than or equal torightThe sum of the elements in.
Given a non-negative integer array nums, please return the number of good split NUMs schemes. Since the answer may be large, return the result mod 10^9 + 7.
Example 1:
Input: nums = [1,1,1] Output: 1 Explanation: The only good partitioning scheme is to divide NUMs into [1] [1] [1].Copy the codeExample 2:
Input: nums =,2,2,2,5,0 [1] output: 3: nums there are three good segmentation scheme: [1] [2],2,5,0 [2] [1] [2],5,0 [2] [1, 2], [2] [5, 0]Copy the codeExample 3:
Input: nums = [3,2,1] output: 0 description: there is no good segmentation scheme.Copy the codeTip:
3 <= nums.length <= 10^50 <= nums[i] <= 10^4
The prefix and the + dichotomy
- A prefix and array VVV, v[I]v[I]v[I]v[I] record the sum of the elements in the range [0, I −1][0, I −1] (where I =1,2… ,ni = 1, 2, … , ni = 1, 2,… , n).
- NNN positions are traversed, and position III is taken as the dividing line of LeftLeftLeft and MIDMIDMid subarrays, and the dividing range of midMIDMid and Rightrightright are searched bisection.
- Assuming boundary range of (x, y) (x, y) (x, y), the position of XXX must satisfy the condition that v v [x] [x] – [x] v v [I] [I] > = v v [I] [I] > = v v > = v [I], [I] At this time to meet left < midleft < midleft < mids, the conditions to be fulfilled are similarly yyy position [n] [n] is v v v [n] -v [y] > [y] > [y] v = v = v [y] [y] v > = v [I] [y] – v v v [I], [I] In order to satisfy mid
Code:
class Solution {
public:
int waysToSplit(vector<int>& a) {
int n = a.size(a);vector<int> v(n + 1.0);
// Initialize the prefix and array
for(int i = 1; i <= n; i++) {
v[i] = v[i - 1] + a[i - 1];
}
// Return ret
long long ret = 0;
const int M = 1e9 + 7;
for(int i = 1; i < n; i++) {
/ / sentence
if(v[i] * 3 > v[n]) break;
// find the right boundary for the first time
int l = i + 1, r = n - 1;
while(l <= r) {
int mid = (l + r) / 2;
if(v[n] - v[mid] < v[mid] - v[i]) {
r = mid - 1;
} else {
l = mid + 1; }}// The second dichotomy finds the left boundary
int ll = i + 1, rr = n - 1;
while(ll <= rr) {
int mid = (ll + rr) / 2;
if(v[mid] - v[i] < v[i]) {
ll = mid + 1;
} else {
rr = mid - 1;
}
}
ret += l - ll;
}
returnret % M; }};Copy the codeComplexity analysis:
-
The time complexity is O(NLGN)O(NLGN)O(NLGN), traversing leftLeftLeft and midMIDMid boundary complexity O(n)O(n)O(n) O(n)O(LGN)O(LGN)O(LGN)O(LGN)O(LGN)O(LGN)O(LGN)O(LGN)O(LGN)O(LGN)O(LGN)O(LGN)O(LGN)O(LGN)O(LGN)
-
The space complexity is O(n)O(n)O(n), and prefixes and arrays are maintained