Skip to content

Commit 5c15b1f

Browse files
liuyuboboboliuyubobobo
committed
2335-2338 added.
1 parent 1082534 commit 5c15b1f

File tree

10 files changed

+338
-0
lines changed

10 files changed

+338
-0
lines changed

‎2001-2500/2335-Minimum-Amount-of-Time-to-Fill-Cups/cpp-2335/CMakeLists.txt

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
cmake_minimum_required(VERSION 3.22)
2+
project(A)
3+
4+
set(CMAKE_CXX_STANDARD 14)
5+
6+
add_executable(A main.cpp)

‎2001-2500/2335-Minimum-Amount-of-Time-to-Fill-Cups/cpp-2335/main.cpp

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
/// Source : https://leetcode.com/problems/minimum-amount-of-time-to-fill-cups/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-07-10
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <queue>
8+
9+
using namespace std;
10+
11+
12+
/// Using PQ
13+
/// Time Complexity: O(sum(amount))
14+
/// Space Complexity: O(1)
15+
class Solution {
16+
public:
17+
int fillCups(vector<int>& amount) {
18+
19+
priority_queue<int> pq;
20+
for(int i = 0; i < 3; i ++)
21+
if(amount[i]) pq.push(amount[i]);
22+
23+
int res = 0;
24+
while(pq.size() >= 2){
25+
int a = pq.top(); pq.pop();
26+
int b = pq.top(); pq.pop();
27+
res ++, a --, b --;
28+
if(a) pq.push(a);
29+
if(b) pq.push(b);
30+
}
31+
32+
if(pq.size()) res += pq.top();
33+
return res;
34+
}
35+
};
36+
37+
38+
int main() {
39+
40+
return 0;
41+
}

‎2001-2500/2336-Smallest-Number-in-Infinite-Set/cpp-2336/CMakeLists.txt

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
cmake_minimum_required(VERSION 3.22)
2+
project(B)
3+
4+
set(CMAKE_CXX_STANDARD 14)
5+
6+
add_executable(B main.cpp)

‎2001-2500/2336-Smallest-Number-in-Infinite-Set/cpp-2336/main.cpp

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
/// Source : https://leetcode.com/problems/smallest-number-in-infinite-set/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-06-08
4+
5+
#include <iostream>
6+
#include <set>
7+
8+
using namespace std;
9+
10+
11+
/// Using Set
12+
/// Time Complexity: init: O(1)
13+
/// pop: O(logn)
14+
/// add: O(logn)
15+
/// Space Compelxity: O(n)
16+
class SmallestInfiniteSet {
17+
18+
private:
19+
int start = 1;
20+
set<int> others;
21+
22+
public:
23+
SmallestInfiniteSet() {}
24+
25+
int popSmallest() {
26+
27+
if(!others.empty()){
28+
int ret = *others.begin();
29+
others.erase(others.begin());
30+
return ret;
31+
}
32+
33+
int ret = start;
34+
start ++;
35+
return ret;
36+
}
37+
38+
void addBack(int num) {
39+
40+
if(others.count(num) || num >= start) return;
41+
42+
if(num == start - 1){
43+
start --;
44+
while(true){
45+
auto iter = others.find(start - 1);
46+
if(iter != others.end()){
47+
others.erase(iter);
48+
start --;
49+
}
50+
else break;
51+
}
52+
}
53+
else{
54+
others.insert(num);
55+
}
56+
}
57+
};
58+
59+
60+
int main() {
61+
62+
return 0;
63+
}

‎2001-2500/2337-Move-Pieces-to-Obtain-a-String/cpp-2337/CMakeLists.txt

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
cmake_minimum_required(VERSION 3.22)
2+
project(C)
3+
4+
set(CMAKE_CXX_STANDARD 14)
5+
6+
add_executable(C main.cpp)

‎2001-2500/2337-Move-Pieces-to-Obtain-a-String/cpp-2337/main.cpp

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
/// Source : https://leetcode.com/problems/move-pieces-to-obtain-a-string/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-07-10
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
11+
/// Ad-Hoc
12+
/// Time Complexity: O(n)
13+
/// Space Complexity: O(n)
14+
class Solution {
15+
public:
16+
bool canChange(string start, string target) {
17+
18+
vector<pair<char, int>> pos1, pos2;
19+
for(int i = 0; i < start.size(); i ++)
20+
if(start[i] != '_') pos1.push_back({start[i], i});
21+
for(int i = 0; i < target.size(); i ++)
22+
if(target[i] != '_') pos2.push_back({target[i], i});
23+
24+
if(pos1.size() != pos2.size()) return false;
25+
26+
for(int i = 0; i < pos1.size(); i ++){
27+
if(pos1[i].first != pos2[i].first) return false;
28+
if(pos1[i].first == 'L' && pos1[i].second < pos2[i].second) return false;
29+
if(pos1[i].first == 'R' && pos1[i].second > pos2[i].second) return false;
30+
}
31+
return true;
32+
}
33+
};
34+
35+
36+
int main() {
37+
std::cout << "Hello, World!" << std::endl;
38+
return 0;
39+
}

‎2001-2500/2338-Count-the-Number-of-Ideal-Arrays/cpp-2338/CMakeLists.txt

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
cmake_minimum_required(VERSION 3.22)
2+
project(D)
3+
4+
set(CMAKE_CXX_STANDARD 14)
5+
6+
add_executable(D main2.cpp)

‎2001-2500/2338-Count-the-Number-of-Ideal-Arrays/cpp-2338/main.cpp

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
/// Source : https://leetcode.com/problems/count-the-number-of-ideal-arrays/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-07-10
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
11+
/// Backtrack + Math
12+
/// Time Complexity: O(nlogn)
13+
/// Space Complexity: O(n)
14+
class Solution {
15+
16+
private:
17+
const long long MOD = 1e9 + 7;
18+
vector<long long> fac, ifac;
19+
20+
public:
21+
Solution(): fac(1e4 + 1, 1), ifac(1e4 + 1){}
22+
23+
int idealArrays(int n, int maxValue) {
24+
25+
for(int i = 1; i <= n; i ++)
26+
fac[i] = fac[i - 1] * i % MOD;
27+
for(int i = 0; i <= n; i ++)
28+
ifac[i] = quick_pow(fac[i], MOD - 2);
29+
30+
vector<int> seq;
31+
return go(seq, n, maxValue);
32+
}
33+
34+
private:
35+
long long go(vector<int>& seq, int n, int maxValue){
36+
37+
long long res = 0;
38+
if(seq.empty()){
39+
for(int i = 1; i <= maxValue; i ++){
40+
seq.push_back(i);
41+
res += go(seq, n, maxValue);
42+
seq.pop_back();
43+
}
44+
return res % MOD;
45+
}
46+
47+
int k = seq.size() - 1;
48+
res += fac[n - 1] * ifac[k] % MOD * ifac[n - 1 - k] % MOD;
49+
50+
if(seq.size() == n) return res;
51+
52+
for(int d = 2; seq.back() * d <= maxValue; d ++){
53+
seq.push_back(seq.back() * d);
54+
res += go(seq, n, maxValue);
55+
seq.pop_back();
56+
}
57+
return res % MOD;
58+
}
59+
60+
long long quick_pow(long long a, long long k) {
61+
long long res = 1ll;
62+
while (k) {
63+
if (k & 1) res = res * a % MOD;
64+
a = a * a % MOD;
65+
k >>= 1;
66+
}
67+
return res % MOD;
68+
}
69+
};
70+
71+
72+
int main() {
73+
74+
cout << Solution().idealArrays(2, 5) << '\n';
75+
// 10
76+
77+
cout << Solution().idealArrays(5, 3) << '\n';
78+
// 11
79+
80+
cout << Solution().idealArrays(5878, 2900) << '\n';
81+
// 465040898
82+
83+
cout << Solution().idealArrays(1e4, 1e4) << '\n';
84+
// 22940607
85+
86+
return 0;
87+
}

‎2001-2500/2338-Count-the-Number-of-Ideal-Arrays/cpp-2338/main2.cpp

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
/// Source : https://leetcode.com/problems/count-the-number-of-ideal-arrays/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-07-10
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
11+
/// Backtrack + Math
12+
/// Using dp is faster than multiplication reverse in this problem
13+
/// Time Complexity: O(nlogn)
14+
/// Space Complexity: O(n)
15+
class Solution {
16+
17+
private:
18+
const long long MOD = 1e9 + 7;
19+
20+
public:
21+
int idealArrays(int n, int maxValue) {
22+
23+
vector<vector<long long>> dp(n + 1, vector<long long>(20, 0ll));
24+
dp[1][0] = dp[1][1] = 1;
25+
for(int i = 2; i <= n; i ++){
26+
dp[i][0] = 1;
27+
if(i < 20) dp[i][i] = 1;
28+
for(int k = 1; k < min(i, 20); k ++)
29+
dp[i][k] = (dp[i - 1][k - 1] + dp[i - 1][k]) % MOD;
30+
}
31+
32+
vector<int> seq;
33+
return go(seq, n, maxValue, dp);
34+
}
35+
36+
private:
37+
long long go(vector<int>& seq, int n, int maxValue,
38+
const vector<vector<long long>>& dp){
39+
40+
long long res = 0;
41+
if(seq.empty()){
42+
for(int i = 1; i <= maxValue; i ++){
43+
seq.push_back(i);
44+
res += go(seq, n, maxValue, dp);
45+
seq.pop_back();
46+
}
47+
return res % MOD;
48+
}
49+
50+
res += dp[n - 1][seq.size() - 1];
51+
52+
if(seq.size() == n) return res;
53+
54+
for(int d = 2; seq.back() * d <= maxValue; d ++){
55+
seq.push_back(seq.back() * d);
56+
res += go(seq, n, maxValue, dp);
57+
seq.pop_back();
58+
}
59+
return res % MOD;
60+
}
61+
};
62+
63+
64+
int main() {
65+
66+
cout << Solution().idealArrays(2, 5) << '\n';
67+
// 10
68+
69+
cout << Solution().idealArrays(5, 3) << '\n';
70+
// 11
71+
72+
cout << Solution().idealArrays(5878, 2900) << '\n';
73+
// 465040898
74+
75+
cout << Solution().idealArrays(1e4, 1e4) << '\n';
76+
// 22940607
77+
78+
return 0;
79+
}

‎readme.md

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2176,6 +2176,11 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
21762176
| 2327 | [Number of People Aware of a Secret](https://leetcode.com/problems/number-of-people-aware-of-a-secret/) | [无] | [C++](2001-2500/2327-Number-of-People-Aware-of-a-Secret/cpp-2327/) | | |
21772177
| 2328 | [Number of Increasing Paths in a Grid](https://leetcode.com/problems/number-of-increasing-paths-in-a-grid/) | [无] | [C++](2001-2500/2328-Number-of-Increasing-Paths-in-a-Grid/cpp-2328/) | | |
21782178
| | | | | | |
2179+
| 2335 | [Minimum Amount of Time to Fill Cups](https://leetcode.com/problems/minimum-amount-of-time-to-fill-cups/) | [无] | [C++](2001-2500/2335-Minimum-Amount-of-Time-to-Fill-Cups/cpp-2335/) | | |
2180+
| 2336 | [Smallest Number in Infinite Set](https://leetcode.com/problems/smallest-number-in-infinite-set/) | [无] | [C++](2001-2500/2336-Smallest-Number-in-Infinite-Set/cpp-2336/) | | |
2181+
| 2337 | [Move Pieces to Obtain a String](https://leetcode.com/problems/move-pieces-to-obtain-a-string/) | [无] | [C++](2001-2500/2337-Move-Pieces-to-Obtain-a-String/cpp-2337/) | | |
2182+
| 2338 | [Count the Number of Ideal Arrays](https://leetcode.com/problems/count-the-number-of-ideal-arrays/) | [无] | [C++](2001-2500/2338-Count-the-Number-of-Ideal-Arrays/cpp-2338/) | | |
2183+
| | | | | | |
21792184

21802185
## 力扣中文站比赛
21812186

0 commit comments

Comments
 (0)