Skip to content

Commit 1dbb556

Browse files
liuyuboboboliuyubobobo
committed
2022 zj future solved.
1 parent f2a35a0 commit 1dbb556

File tree

9 files changed

+246
-0
lines changed

9 files changed

+246
-0
lines changed

‎Others/2022-zj-future/A/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)

‎Others/2022-zj-future/A/main.cpp

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
/// Source : https://leetcode.cn/contest/zj-future2022/problems/WYKGLO/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-07-08
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <algorithm>
8+
9+
using namespace std;
10+
11+
12+
/// Sorting
13+
/// Time Complexity: O(nlogn)
14+
/// Space Complexity: O(1)
15+
class Solution {
16+
public:
17+
bool canReceiveAllSignals(vector<vector<int>>& intervals) {
18+
19+
sort(intervals.begin(), intervals.end());
20+
for(int i = 1; i < intervals.size(); i ++){
21+
int s1 = intervals[i - 1][0], e1 = intervals[i - 1][1];
22+
int s2 = intervals[i][0], e2 = intervals[i][1];
23+
if(s2 < e1) return false;
24+
}
25+
return true;
26+
}
27+
};
28+
29+
30+
int main() {
31+
32+
return 0;
33+
}

‎Others/2022-zj-future/B/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)

‎Others/2022-zj-future/B/main.cpp

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
/// Source : https://leetcode.cn/contest/zj-future2022/problems/GVbKaI/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-07-19
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <numeric>
8+
#include <algorithm>
9+
10+
using namespace std;
11+
12+
13+
/// Presum
14+
/// Time Complexity: O(n)
15+
/// Space Complexity: O(n)
16+
class Solution {
17+
public:
18+
int minSwaps(vector<int>& chess) {
19+
20+
int n = chess.size();
21+
22+
vector<int> presum(n + 1, 0);
23+
for(int i = 0; i < n; i ++) presum[i + 1] = presum[i] + chess[i];
24+
25+
int res = INT_MAX, total = accumulate(chess.begin(), chess.end(), 0);
26+
for(int start = 0; start + total <= n; start ++)
27+
res = min(res, total - (presum[start + total] - presum[start]));
28+
return res;
29+
}
30+
};
31+
32+
33+
int main() {
34+
35+
return 0;
36+
}

‎Others/2022-zj-future/C/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)

‎Others/2022-zj-future/C/main.cpp

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
/// Source : https://leetcode.cn/contest/zj-future2022/problems/kflZMc/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-07-19
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
11+
/// Sliding Window in 2D
12+
/// Time Complexity: O(R * C)
13+
/// Space Complexity: O(R + C)
14+
class Solution {
15+
public:
16+
int buildTransferStation(vector<vector<int>>& area) {
17+
18+
int R = area.size(), C = area[0].size();
19+
20+
vector<int> rows(R, 0), cols(C, 0);
21+
int total = 0;
22+
for(int i = 0; i < R; i ++)
23+
for(int j = 0; j < C; j ++)
24+
if(area[i][j]) rows[i] ++, cols[j] ++, total ++;
25+
26+
vector<int> pre_rows(R, rows[0]), pre_cols(C, cols[0]);
27+
for(int i = 1; i < R; i ++) pre_rows[i] = pre_rows[i - 1] + rows[i];
28+
for(int j = 1; j < C; j ++) pre_cols[j] = pre_cols[j - 1] + cols[j];
29+
30+
int prow = 0;
31+
for(int i = 1; i < R; i ++) prow += rows[i] * i;
32+
vector<int> row_res(R, prow);
33+
for(int i = 1; i < R; i ++){
34+
int crow = prow + pre_rows[i - 1] - (total - pre_rows[i - 1]);
35+
row_res[i] = crow;
36+
prow = crow;
37+
}
38+
39+
int pcol = 0;
40+
for(int j = 1; j < C; j ++) pcol += cols[j] * j;
41+
vector<int> col_res(C, pcol);
42+
for(int j = 1; j < C; j ++){
43+
int ccol = pcol + pre_cols[j - 1] - (total - pre_cols[j - 1]);
44+
col_res[j] = ccol;
45+
pcol = ccol;
46+
}
47+
48+
return *min_element(row_res.begin(), row_res.end()) + *min_element(col_res.begin(), col_res.end());
49+
}
50+
};
51+
52+
53+
int main() {
54+
55+
vector<vector<int>> area1 = {
56+
{0, 1, 0, 0, 0},
57+
{0, 0, 0, 0, 1},
58+
{0, 0, 1, 0, 0}
59+
};
60+
cout << Solution().buildTransferStation(area1) << '\n';
61+
// 5
62+
63+
return 0;
64+
}

‎Others/2022-zj-future/D/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 main.cpp)

‎Others/2022-zj-future/D/main.cpp

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
/// Source : https://leetcode.cn/contest/zj-future2022/problems/NBCXIp/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-07-19
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <climits>
8+
9+
using namespace std;
10+
11+
12+
/// Backtrack
13+
/// Time Complexity: O(12!)
14+
/// Space Complexity: O(12)
15+
class Solution {
16+
public:
17+
int minTransfers(vector<vector<int>>& distributions) {
18+
19+
int max_id = -1;
20+
for(const vector<int>& v: distributions)
21+
max_id = max(max_id, max(v[0], v[1]));
22+
23+
vector<int> cnt(max_id + 1, 0);
24+
for(const vector<int>& v: distributions){
25+
int from_id = v[0], to_id = v[1], e = v[2];
26+
cnt[from_id] -= e;
27+
cnt[to_id] += e;
28+
}
29+
30+
vector<int> pos, neg;
31+
for(int i = 0; i < cnt.size(); i ++) {
32+
if (cnt[i] > 0) pos.push_back(cnt[i]);
33+
else if (cnt[i] < 0) neg.push_back(-cnt[i]);
34+
}
35+
36+
sort(pos.begin(), pos.end(), greater<int>());
37+
sort(neg.begin(), neg.end(), greater<int>());
38+
39+
return dfs(pos, 0, neg);
40+
}
41+
42+
private:
43+
int dfs(vector<int>& pos, int index, vector<int>& neg){
44+
45+
if(index == pos.size()) return 0;
46+
47+
int res = INT_MAX;
48+
for(int& e: neg){
49+
if(e){
50+
int t = min(pos[index], e);
51+
pos[index] -= t;
52+
e -= t;
53+
res = min(res, 1 + dfs(pos, index + (pos[index] == 0), neg));
54+
pos[index] += t;
55+
e += t;
56+
}
57+
}
58+
return res;
59+
}
60+
};
61+
62+
63+
int main() {
64+
65+
vector<vector<int>> distrubution1 = {
66+
{0,1,5},{2,3,1},{2,0,1},{4,0,2}
67+
};
68+
cout << Solution().minTransfers(distrubution1) << '\n';
69+
// 4
70+
71+
vector<vector<int>> distrubution2 = {
72+
{1,5,8},{8,9,8},{2,3,9},{4,3,1}
73+
};
74+
cout << Solution().minTransfers(distrubution2) << '\n';
75+
// 4
76+
77+
vector<vector<int>> distrubution3 = {
78+
{0,2,4},{1,2,4},{3,4,5}
79+
};
80+
cout << Solution().minTransfers(distrubution3) << '\n';
81+
// 3
82+
83+
return 0;
84+
}

‎readme.md

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2255,6 +2255,11 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
22552255
| ID | Problem | Official<br/>Solution | C++ | Java | Python |
22562256
| --- | --- | :---: | :---: | :---: | :---: |
22572257
| | | | | | |
2258+
| 22 zj-future01 | [信号接收](https://leetcode.cn/contest/zj-future2022/problems/WYKGLO/) | [无] | [C++](Others/2022-zj-future/A/) | | |
2259+
| 22 zj-future02 | [黑白棋游戏](https://leetcode.cn/contest/zj-future2022/problems/GVbKaI/) | [无] | [C++](Others/2022-zj-future/B/) | | |
2260+
| 22 zj-future03 | [快递中转站选址](https://leetcode.cn/contest/zj-future2022/problems/kflZMc/) | [无] | [C++](Others/2022-zj-future/C/) | | |
2261+
| 22 zj-future04 | [门店商品调配](https://leetcode.cn/contest/zj-future2022/problems/NBCXIp/) | [无] | [C++](Others/2022-zj-future/D/) | | |
2262+
| | | | | | |
22582263
| 22 顺丰01 | [顺丰鄂州枢纽运转中心环线检测](https://leetcode.cn/contest/sf-tech/problems/EUpcmh/) | [无] | [C++](Others/2022-sf-tech/A/) | | |
22592264
| 22 顺丰02 | [小哥派件装载问题](https://leetcode.cn/contest/sf-tech/problems/cINqyA/) | [无] | [C++](Others/2022-sf-tech/B/) | | |
22602265
| 22 顺丰03 | [收件节节高](https://leetcode.cn/contest/sf-tech/problems/8oimK4/) | [无] | [C++](Others/2022-sf-tech/C/) | | |

0 commit comments

Comments
 (0)