Skip to content

Commit 369524d

Browse files
liuyuboboboliuyubobobo
committed
2319-2322 solved.
1 parent 05f82d7 commit 369524d

File tree

10 files changed

+305
-0
lines changed

10 files changed

+305
-0
lines changed

‎2001-2500/2319-Check-if-Matrix-Is-X-Matrix/cpp-2319/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/2319-Check-if-Matrix-Is-X-Matrix/cpp-2319/main.cpp

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
/// Source : https://leetcode.com/problems/check-if-matrix-is-x-matrix/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-06-25
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
11+
/// Simulation
12+
/// Time Complexity: O(n^2)
13+
/// Space Complexity: O(1)
14+
class Solution {
15+
public:
16+
bool checkXMatrix(vector<vector<int>>& grid) {
17+
18+
int n = grid.size();
19+
20+
for(int i = 0; i < n; i ++)
21+
for(int j = 0; j < n; j ++){
22+
if(is_dia(i, j, n) && grid[i][j] == 0) return false;
23+
if(!is_dia(i, j, n) && grid[i][j] != 0) return false;
24+
}
25+
return true;
26+
}
27+
28+
private:
29+
bool is_dia(int i, int j, int n){
30+
return i == j || i + j == n - 1;
31+
}
32+
};
33+
34+
35+
int main() {
36+
37+
return 0;
38+
}

‎2001-2500/2320-Count-Number-of-Ways-to-Place-Houses/cpp-2320/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 main2.cpp)

‎2001-2500/2320-Count-Number-of-Ways-to-Place-Houses/cpp-2320/main.cpp

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
/// Source : https://leetcode.com/problems/count-number-of-ways-to-place-houses/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-06-25
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
11+
/// DP
12+
/// Time Complexity: O(n)
13+
/// Space Complexity: O(n)
14+
class Solution {
15+
16+
private:
17+
const long long MOD = 1e9 + 7;
18+
19+
public:
20+
int countHousePlacements(int n) {
21+
22+
vector<vector<long long>> dp(4, vector<long long>(n, 0));
23+
dp[0][0] = dp[1][0] = dp[2][0] = dp[3][0] = 1;
24+
for(int i = 1; i < n; i ++){
25+
for(int cur_state = 0; cur_state < 4; cur_state ++){
26+
int cur1 = cur_state / 2, cur2 = cur_state % 2;
27+
for(int pre_state = 0; pre_state < 4; pre_state ++){
28+
int pre1 = pre_state / 2, pre2 = pre_state % 2;
29+
if((cur1 && pre1) || (cur2 && pre2)) continue;
30+
dp[cur_state][i] += dp[pre_state][i - 1];
31+
}
32+
dp[cur_state][i] %= MOD;
33+
}
34+
}
35+
36+
long long res = 0;
37+
for(int state = 0; state < 4; state ++) res += dp[state][n - 1];
38+
return res % MOD;
39+
}
40+
};
41+
42+
int main() {
43+
44+
return 0;
45+
}

‎2001-2500/2320-Count-Number-of-Ways-to-Place-Houses/cpp-2320/main2.cpp

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
/// Source : https://leetcode.com/problems/count-number-of-ways-to-place-houses/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-06-27
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
11+
/// DP, just consider one line is enough
12+
/// Time Complexity: O(n)
13+
/// Space Complexity: O(n)
14+
class Solution {
15+
16+
private:
17+
const long long MOD = 1e9 + 7;
18+
19+
public:
20+
int countHousePlacements(int n) {
21+
22+
vector<vector<long long>> dp(2, vector<long long>(n, 1));
23+
for(int i = 1; i < n; i ++){
24+
dp[0][i] = (dp[0][i - 1] + dp[1][i - 1]) % MOD;
25+
dp[1][i] = dp[0][i - 1];
26+
}
27+
28+
long long res = (dp[0][n - 1] + dp[1][n - 1]) % MOD;
29+
return res * res % MOD;
30+
}
31+
};
32+
33+
34+
int main() {
35+
36+
return 0;
37+
}

‎2001-2500/2321-Maximum-Score-Of-Spliced-Array/cpp-2321/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/2321-Maximum-Score-Of-Spliced-Array/cpp-2321/main.cpp

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
/// Source : https://leetcode.com/problems/maximum-score-of-spliced-array/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-06-25
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
11+
/// Math
12+
/// Time Complexity: O(n)
13+
/// Space Complexity: O(n)
14+
class Solution {
15+
public:
16+
int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
17+
18+
int n = nums1.size();
19+
20+
vector<int> presum1(n + 1, 0), presum2(n + 1, 0);
21+
for(int i = 0; i < n; i ++){
22+
presum1[i + 1] = presum1[i] + nums1[i];
23+
presum2[i + 1] = presum2[i] + nums2[i];
24+
}
25+
26+
vector<int> presum12(n + 1, 0), presum21(n + 1, 0);
27+
for(int i = 0; i <= n; i ++){
28+
presum12[i] = presum1[i] - presum2[i];
29+
presum21[i] = presum2[i] - presum1[i];
30+
}
31+
32+
int max12 = 0, max21 = 0, res = max(presum1.back(), presum2.back());
33+
for(int i = 0; i < n; i ++){
34+
res = max(res, presum1.back() + presum21[i + 1] + max12);
35+
res = max(res, presum2.back() + presum12[i + 1] + max21);
36+
max12 = max(max12, presum12[i + 1]);
37+
max21 = max(max21, presum21[i + 1]);
38+
}
39+
return res;
40+
}
41+
};
42+
43+
44+
int main() {
45+
46+
return 0;
47+
}

‎2001-2500/2322-Minimum-Score-After-Removals-on-a-Tree/cpp-2322/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)

‎2001-2500/2322-Minimum-Score-After-Removals-on-a-Tree/cpp-2322/main.cpp

Lines changed: 110 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,110 @@
1+
/// Source : https://leetcode.com/problems/minimum-score-after-removals-on-a-tree/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-06-25
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <cassert>
8+
9+
using namespace std;
10+
11+
12+
/// DFS
13+
/// Time Complexity: O(n^2)
14+
/// Space Complexity: O(n^2)
15+
class Solution {
16+
public:
17+
int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
18+
19+
int n = nums.size();
20+
vector<vector<int>> tree(n);
21+
for(const vector<int>& e: edges){
22+
int u = e[0], v = e[1];
23+
tree[u].push_back(v), tree[v].push_back(u);
24+
}
25+
26+
vector<vector<bool>> is_ancestor(n, vector<bool>(n, false));
27+
vector<int> path;
28+
dfs_ancestor(tree, 0, -1, path, is_ancestor);
29+
30+
vector<int> xor_subtree(n, 0);
31+
dfs_xor_subtree(tree, 0, -1, nums, xor_subtree);
32+
33+
int res = INT_MAX;
34+
for(int i = 0; i < edges.size(); i ++){
35+
for(int j = i + 1; j < edges.size(); j ++){
36+
37+
int u1 = edges[i][0], v1 = edges[i][1];
38+
int root1 = (is_ancestor[u1][v1] ? v1 : u1);
39+
40+
int xor1 = (xor_subtree[0] ^ xor_subtree[root1]);
41+
int xor2 = xor_subtree[root1];
42+
int xor3 = 0;
43+
44+
int u2 = edges[j][0], v2 = edges[j][1];
45+
int root2 = is_ancestor[u2][v2] ? v2 : u2;
46+
47+
if(is_ancestor[root1][root2]){
48+
xor3 = xor_subtree[root2];
49+
xor2 ^= xor3;
50+
}
51+
else if(is_ancestor[root2][root1]){
52+
xor1 = (xor_subtree[0] ^ xor_subtree[root2]);
53+
xor3 = xor_subtree[root2] ^ xor2;
54+
}
55+
else{
56+
assert(is_ancestor[0][root2]);
57+
xor3 = xor_subtree[root2];
58+
xor1 ^= xor3;
59+
}
60+
61+
res = min(res, max3(xor1, xor2, xor3) - min3(xor1, xor2, xor3));
62+
}
63+
}
64+
return res;
65+
}
66+
67+
private:
68+
int max3(int a, int b, int c){
69+
return max(a, max(b, c));
70+
}
71+
72+
int min3(int a, int b, int c){
73+
return min(a, min(b, c));
74+
}
75+
76+
void dfs_xor_subtree(const vector<vector<int>>& tree, int u, int p,
77+
const vector<int>& nums, vector<int>& xor_subtree){
78+
79+
xor_subtree[u] ^= nums[u];
80+
for(int v: tree[u]){
81+
if(v == p) continue;
82+
dfs_xor_subtree(tree, v, u, nums, xor_subtree);
83+
xor_subtree[u] ^= xor_subtree[v];
84+
}
85+
}
86+
87+
void dfs_ancestor(const vector<vector<int>>& tree, int u, int p,
88+
vector<int>& path, vector<vector<bool>>& is_ancestor){
89+
90+
for(int x: path)
91+
is_ancestor[x][u] = true;
92+
93+
path.push_back(u);
94+
for(int v: tree[u]){
95+
if(v == p) continue;
96+
dfs_ancestor(tree, v, u, path, is_ancestor);
97+
}
98+
path.pop_back();
99+
}
100+
};
101+
102+
103+
int main() {
104+
105+
vector<int> nums2 = {5, 5, 2, 4, 4, 2};
106+
vector<vector<int>> edges2 = {{0, 1}, {1, 2}, {5, 2}, {4, 3}, {1, 3}};
107+
cout << Solution().minimumScore(nums2, edges2) << '\n';
108+
109+
return 0;
110+
}

‎readme.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2165,6 +2165,10 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
21652165
| 2316 | [Count Unreachable Pairs of Nodes in an Undirected Graph](https://leetcode.com/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/) | [无] | [C++](2001-2500/2316-Count-Unreachable-Pairs-of-Nodes-in-an-Undirected-Graph/cpp-2316/) | | |
21662166
| 2317 | [Maximum XOR After Operations](https://leetcode.com/problems/maximum-xor-after-operations/) | [无] | [C++](2001-2500/2317-Maximum-XOR-After-Operations/cpp-2317/) | | |
21672167
| 2318 | [Number of Distinct Roll Sequences](https://leetcode.com/problems/number-of-distinct-roll-sequences/) | [无] | [C++](2001-2500/2318-Number-of-Distinct-Roll-Sequences/cpp-2318/) | | |
2168+
| 2319 | [Check if Matrix Is X-Matrix](https://leetcode.com/problems/check-if-matrix-is-x-matrix/) | [无] | [C++](2001-2500/2319-Check-if-Matrix-Is-X-Matrix/cpp-2319/) | | |
2169+
| 2320 | [Count Number of Ways to Place Houses](https://leetcode.com/problems/count-number-of-ways-to-place-houses/) | [无] | [C++](2001-2500/2320-Count-Number-of-Ways-to-Place-Houses/cpp-2320/) | | |
2170+
| 2321 | [Maximum Score Of Spliced Array](https://leetcode.com/problems/maximum-score-of-spliced-array/) | [无] | [C++](2001-2500/2321-Maximum-Score-Of-Spliced-Array/cpp-2321/) | | |
2171+
| 2322 | [Minimum Score After Removals on a Tree](https://leetcode.com/problems/minimum-score-after-removals-on-a-tree/) | [无] | [C++](2001-2500/2322-Minimum-Score-After-Removals-on-a-Tree/cpp-2322/) | | |
21682172
| | | | | | |
21692173

21702174
## 力扣中文站比赛

0 commit comments

Comments
 (0)