Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit88f9a14

Browse files
committed
New Problem Solution - "1712. Ways to Split Array Into Three Subarrays"
1 parent24c5f61 commit88f9a14

File tree

2 files changed

+119
-0
lines changed

2 files changed

+119
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -105,6 +105,7 @@ LeetCode
105105
|1718|[Construct the Lexicographically Largest Valid Sequence](https://leetcode.com/problems/construct-the-lexicographically-largest-valid-sequence/)|[C++](./algorithms/cpp/constructTheLexicographicallyLargestValidSequence/ConstructTheLexicographicallyLargestValidSequence.cpp)|Medium|
106106
|1717|[Maximum Score From Removing Substrings](https://leetcode.com/problems/maximum-score-from-removing-substrings/)|[C++](./algorithms/cpp/maximumScoreFromRemovingSubstrings/MaximumScoreFromRemovingSubstrings.cpp)|Medium|
107107
|1716|[Calculate Money in Leetcode Bank](https://leetcode.com/problems/calculate-money-in-leetcode-bank/)|[C++](./algorithms/cpp/calculateMoneyInLeetcodeBank/CalculateMoneyInLeetcodeBank.cpp)|Easy|
108+
|1712|[Ways to Split Array Into Three Subarrays](https://leetcode.com/problems/ways-to-split-array-into-three-subarrays/)|[C++](./algorithms/cpp/waysToSplitArrayIntoThreeSubarrays/WaysToSplitArrayIntoThreeSubarrays.cpp)|Medium|
108109
|1711|[Count Good Meals](https://leetcode.com/problems/count-good-meals/)|[C++](./algorithms/cpp/countGoodMeals/CountGoodMeals.cpp)|Medium|
109110
|1710|[Maximum Units on a Truck](https://leetcode.com/problems/maximum-units-on-a-truck/)|[C++](./algorithms/cpp/maximumUnitsOnATruck/MaximumUnitsOnATruck.cpp)|Easy|
110111
|1700|[Number of Students Unable to Eat Lunch](https://leetcode.com/problems/number-of-students-unable-to-eat-lunch/)|[C++](./algorithms/cpp/numberOfStudentsUnableToEatLunch/NumberOfStudentsUnableToEatLunch.cpp)|Easy|
Lines changed: 118 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,118 @@
1+
// Source : https://leetcode.com/problems/ways-to-split-array-into-three-subarrays/
2+
// Author : Hao Chen
3+
// Date : 2021-05-11
4+
5+
/*****************************************************************************************************
6+
*
7+
* A split of an integer array is good if:
8+
*
9+
* The array is split into three non-empty contiguous subarrays - named left, mid, right
10+
* respectively from left to right.
11+
* The sum of the elements in left is less than or equal to the sum of the elements in mid,
12+
* and the sum of the elements in mid is less than or equal to the sum of the elements in right.
13+
*
14+
* Given nums, an array of non-negative integers, return the number of good ways to split nums. As the
15+
* number may be too large, return it modulo 10^9 + 7.
16+
*
17+
* Example 1:
18+
*
19+
* Input: nums = [1,1,1]
20+
* Output: 1
21+
* Explanation: The only good way to split nums is [1] [1] [1].
22+
*
23+
* Example 2:
24+
*
25+
* Input: nums = [1,2,2,2,5,0]
26+
* Output: 3
27+
* Explanation: There are three good ways of splitting nums:
28+
* [1] [2] [2,2,5,0]
29+
* [1] [2,2] [2,5,0]
30+
* [1,2] [2,2] [5,0]
31+
*
32+
* Example 3:
33+
*
34+
* Input: nums = [3,2,1]
35+
* Output: 0
36+
* Explanation: There is no good way to split nums.
37+
*
38+
* Constraints:
39+
*
40+
* 3 <= nums.length <= 10^5
41+
* 0 <= nums[i] <= 10^4
42+
******************************************************************************************************/
43+
44+
constint MOD = (int) (1e9 +7);
45+
46+
classSolution {
47+
public:
48+
intwaysToSplit(vector<int>& nums) {
49+
int len = nums.size();
50+
vector<int>presum(len,0);
51+
presum[0] = nums[0];
52+
for(int i=1; i<nums.size(); i++){
53+
presum[i] = presum[i-1] + nums[i];
54+
}
55+
56+
returnwaysToSplit_BS(presum);// Binary Search
57+
//return waysToSplit_TLE(presum); // Time Limit Error
58+
}
59+
60+
intbinary_search(vector<int>& presum,int left,int i,bool searchLeft ) {
61+
int len = presum.size();
62+
int l = i, r = len-1;
63+
int res = -1;
64+
while(l <= r) {
65+
int m = l + (r - l) /2;
66+
// if search Left, let middle item belong to left
67+
// if search Right, let middle item belong to right
68+
int x = searchLeft?0 :1;
69+
int right = presum[len-1] - presum[m-x];
70+
int mid = presum[m-x] - presum[i-1];
71+
72+
if (left <= mid && mid <= right) {
73+
res = m;
74+
if (searchLeft) r = m -1;
75+
else l = m +1;
76+
}elseif (left > mid) {
77+
l = m +1;
78+
}else {
79+
r = m -1;
80+
}
81+
82+
}
83+
return res;
84+
}
85+
intwaysToSplit_BS(vector<int>& presum) {
86+
int len = presum.size();
87+
long cnt =0;
88+
for(int i=0; i<len-2; i++){
89+
if (presum[i] > (presum[len-1] - presum[i]) /2)break;
90+
//find the most right position
91+
long l =binary_search(presum, presum[i], i+1,true);
92+
//find the most right position
93+
long r =binary_search(presum, presum[i], i+1,false);
94+
if (l == -1 || r == -1 )continue;
95+
cnt += (r-l);
96+
//cout << i << " - [" << l << "," << r << "]" << endl;
97+
}
98+
//cout << endl;
99+
return cnt % MOD;
100+
}
101+
102+
intwaysToSplit_TLE(vector<int>& presum) {
103+
int len = presum.size();
104+
int cnt =0;
105+
int left, mid, right;
106+
for(int i=0; i<len-2; i++){
107+
left = presum[i];
108+
for (int j=i+1; j<len-1; j++) {
109+
mid = presum[j] - presum[i];
110+
right = presum[len-1] - presum[j];
111+
if (left <= mid && mid <= right) {
112+
cnt++;
113+
}
114+
}
115+
}
116+
return cnt;
117+
}
118+
};

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp