Skip to content

Commit 70a4718

Browse files
liuyuboboboliuyubobobo
committed
2315-2318 solved.
1 parent 282cee5 commit 70a4718

File tree

9 files changed

+218
-0
lines changed

9 files changed

+218
-0
lines changed

‎2001-2500/2315-Count-Asterisks/cpp-2315/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(cpp_2315)
3+
4+
set(CMAKE_CXX_STANDARD 14)
5+
6+
add_executable(cpp_2315 main.cpp)

‎2001-2500/2315-Count-Asterisks/cpp-2315/main.cpp

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
/// Source : https://leetcode.com/problems/count-asterisks/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-06-25
4+
5+
#include <iostream>
6+
7+
using namespace std;
8+
9+
10+
/// Linear Scan
11+
/// Time Complexity: O(n)
12+
/// Space Complexity: O(1)
13+
class Solution {
14+
public:
15+
int countAsterisks(string s) {
16+
17+
bool out = true;
18+
int res = 0;
19+
for(char c: s){
20+
if(c == '|') out = !out;
21+
else if(c == '*') res += out;
22+
}
23+
return res;
24+
}
25+
};
26+
27+
28+
int main() {
29+
30+
return 0;
31+
}

‎2001-2500/2316-Count-Unreachable-Pairs-of-Nodes-in-an-Undirected-Graph/cpp-2316/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(cpp_2316)
3+
4+
set(CMAKE_CXX_STANDARD 14)
5+
6+
add_executable(cpp_2316 main.cpp)

‎2001-2500/2316-Count-Unreachable-Pairs-of-Nodes-in-an-Undirected-Graph/cpp-2316/main.cpp

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
/// Source : https://leetcode.com/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-06-25
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
11+
/// CC
12+
/// Time Complexity: O(n)
13+
/// Space Complexity: O(n)
14+
class Solution {
15+
public:
16+
long long countPairs(int n, vector<vector<int>>& edges) {
17+
18+
vector<vector<int>> g(n);
19+
for(const vector<int>& e: edges){
20+
int u = e[0], v = e[1];
21+
g[u].push_back(v), g[v].push_back(u);
22+
}
23+
24+
vector<bool> visited(n, false);
25+
vector<long long> cc_sz;
26+
for(int i = 0; i < n; i ++)
27+
if(!visited[i]){
28+
cc_sz.push_back(dfs(g, i, visited));
29+
}
30+
31+
long long res = 0;
32+
for(long long sz: cc_sz)
33+
res += sz * (n - sz);
34+
return res / 2;
35+
}
36+
37+
private:
38+
int dfs(const vector<vector<int>>& g, int u, vector<bool>& visited){
39+
40+
visited[u] = true;
41+
int res = 1;
42+
for(int v: g[u]){
43+
if(visited[v]) continue;
44+
res += dfs(g, v, visited);
45+
}
46+
return res;
47+
}
48+
};
49+
50+
51+
int main() {
52+
53+
return 0;
54+
}

‎2001-2500/2317-Maximum-XOR-After-Operations/cpp-2317/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(cpp_2317)
3+
4+
set(CMAKE_CXX_STANDARD 14)
5+
6+
add_executable(cpp_2317 main.cpp)

‎2001-2500/2317-Maximum-XOR-After-Operations/cpp-2317/main.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/maximum-xor-after-operations/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-06-25
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
11+
/// bitwise
12+
/// Time Compelxity: O(nlogA)
13+
/// Space Complexity: O(1)
14+
class Solution {
15+
public:
16+
int maximumXOR(vector<int>& nums) {
17+
18+
int n = nums.size();
19+
20+
vector<int> f(31, 0);
21+
for(int num: nums){
22+
for(int p = 30; p >= 0; p --)
23+
f[p] += ((num >> p) & 1);
24+
}
25+
26+
int res = 0;
27+
for(int p = 30; p >= 0; p --)
28+
if(f[p]) res += (1 << p);
29+
return res;
30+
}
31+
};
32+
33+
34+
int main() {
35+
36+
return 0;
37+
}

‎2001-2500/2318-Number-of-Distinct-Roll-Sequences/cpp-2318/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(cpp_2318)
3+
4+
set(CMAKE_CXX_STANDARD 14)
5+
6+
add_executable(cpp_2318 main.cpp)

‎2001-2500/2318-Number-of-Distinct-Roll-Sequences/cpp-2318/main.cpp

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
/// Source : https://leetcode.com/problems/number-of-distinct-roll-sequences/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-06-25
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <numeric>
8+
#include <algorithm>
9+
10+
using namespace std;
11+
12+
13+
/// DP
14+
/// Time Complexity: O(n)
15+
/// Space Complexity: O(n)
16+
class Solution {
17+
18+
private:
19+
const long long MOD = 1e9 + 7;
20+
21+
public:
22+
int distinctSequences(int n) {
23+
24+
if(n == 1) return 6;
25+
26+
vector<vector<vector<long long>>> dp(7, vector<vector<long long>>(7, vector<long long>(n, 0)));
27+
for(int cur = 1; cur <= 6; cur ++) dp[0][cur][0] = 1;
28+
29+
for(int cur = 1; cur <= 6; cur ++)
30+
for(int pre = 1; pre <= 6; pre ++)
31+
if(gcd(pre, cur) == 1 && cur != pre) dp[pre][cur][1] += dp[0][pre][0];
32+
33+
for(int i = 2; i < n; i ++){
34+
for(int cur = 1; cur <= 6; cur ++){
35+
for(int p1 = 1; p1 <= 6; p1 ++)
36+
for(int p2 = 1; p2 <= 6; p2 ++){
37+
if(gcd(p2, cur) == 1 && cur != p2 && cur != p1)
38+
dp[p2][cur][i] += dp[p1][p2][i - 1];
39+
dp[p2][cur][i] %= MOD;
40+
}
41+
}
42+
}
43+
44+
long long res = 0;
45+
for(int p = 1; p <= 6; p ++)
46+
for(int cur = 1; cur <= 6; cur ++)
47+
res += dp[p][cur][n - 1];
48+
return res % MOD;
49+
}
50+
51+
private:
52+
int gcd(int a, int b){
53+
if(a > b) swap(a, b);
54+
if (a == 0) return b;
55+
return gcd(b % a, a);
56+
}
57+
};
58+
59+
60+
int main() {
61+
62+
cout << Solution().distinctSequences(2) << '\n';
63+
64+
cout << Solution().distinctSequences(4) << '\n';
65+
66+
return 0;
67+
}

‎readme.md

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2161,6 +2161,11 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
21612161
| 2312 | [Selling Pieces of Wood](https://leetcode.com/problems/selling-pieces-of-wood/) | [无] | [C++](2001-2500/2312-Selling-Pieces-of-Wood/cpp-2312/) | | |
21622162
| 2313 | [Minimum Flips in Binary Tree to Get Result](https://leetcode.com/problems/minimum-flips-in-binary-tree-to-get-result/) | [无] | [C++](2001-2500/2313-Minimum-Flips-in-Binary-Tree-to-Get-Result/cpp-2313/) | | |
21632163
| | | | | | |
2164+
| 2315 | [Count Asterisks](https://leetcode.com/problems/count-asterisks/) | [无] | [C++](2001-2500/2315-Count-Asterisks/cpp-2315/) | | |
2165+
| 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/) | | |
2166+
| 2317 | [Maximum XOR After Operations](https://leetcode.com/problems/maximum-xor-after-operations/) | [无] | [C++](2001-2500/2317-Maximum-XOR-After-Operations/cpp-2317/) | | |
2167+
| 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+
| | | | | | |
21642169

21652170
## 力扣中文站比赛
21662171

0 commit comments

Comments
 (0)