Skip to content

Commit 4ee4b14

Browse files
liuyuboboboliuyubobobo
committed
2325-2328 solved.
1 parent 177af59 commit 4ee4b14

File tree

10 files changed

+329
-1
lines changed

10 files changed

+329
-1
lines changed

‎2001-2500/2325-Decode-the-Message/cpp-2325/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/2325-Decode-the-Message/cpp-2325/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/decode-the-message/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-07-02
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
11+
/// Simulation
12+
/// Time Complexity: O(|key| + |message|)
13+
/// Space Complexity: O(1)
14+
class Solution {
15+
public:
16+
string decodeMessage(string key, string message) {
17+
18+
vector<bool> used(26, false);
19+
vector<char> table(26);
20+
char ch = 'a';
21+
for(char c: key){
22+
if(c == ' ' || used[c - 'a']) continue;
23+
table[c - 'a'] = ch ++;
24+
used[c - 'a'] = true;
25+
}
26+
27+
for(char& c: message){
28+
if(c == ' ') continue;
29+
c = table[c - 'a'];
30+
}
31+
return message;
32+
}
33+
};
34+
35+
36+
int main() {
37+
38+
return 0;
39+
}

‎2001-2500/2326-Spiral-Matrix-IV/cpp-2326/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/2326-Spiral-Matrix-IV/cpp-2326/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/spiral-matrix-iv/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-07-02
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <cassert>
8+
9+
using namespace std;
10+
11+
12+
/// Simulation
13+
/// Time Complexity: O(m * n)
14+
/// Space Complexity: O(1)
15+
16+
/// Definition for singly-linked list.
17+
struct ListNode {
18+
int val;
19+
ListNode *next;
20+
ListNode() : val(0), next(nullptr) {}
21+
ListNode(int x) : val(x), next(nullptr) {}
22+
ListNode(int x, ListNode *next) : val(x), next(next) {}
23+
};
24+
25+
class Solution {
26+
27+
private:
28+
const int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
29+
int R, C;
30+
31+
public:
32+
vector<vector<int>> spiralMatrix(int R, int C, ListNode* node) {
33+
34+
this->R = R, this->C = C;
35+
vector<vector<int>> res(R, vector<int>(C, -1));
36+
37+
int cx = 0, cy = -1, d = 0;
38+
while(node){
39+
int nx = cx + dirs[d][0], ny = cy + dirs[d][1];
40+
if(!in_area(nx, ny) || res[nx][ny] != -1){
41+
d = (d + 1) % 4;
42+
nx = cx + dirs[d][0], ny = cy + dirs[d][1];
43+
// assert(in_area(nx, ny));
44+
}
45+
46+
res[nx][ny] = node->val;
47+
node = node->next;
48+
cx = nx, cy = ny;
49+
}
50+
return res;
51+
}
52+
53+
private:
54+
bool in_area(int x, int y){
55+
return 0 <= x && x < R && 0 <= y && y < C;
56+
}
57+
};
58+
59+
60+
int main() {
61+
62+
return 0;
63+
}

‎2001-2500/2327-Number-of-People-Aware-of-a-Secret/cpp-2327/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 main2.cpp)

‎2001-2500/2327-Number-of-People-Aware-of-a-Secret/cpp-2327/main.cpp

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
/// Source : https://leetcode.com/problems/number-of-people-aware-of-a-secret/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-07-02
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <numeric>
8+
9+
using namespace std;
10+
11+
12+
/// DP
13+
/// Time Complexity: O(n^2)
14+
/// Space Complexity: O(n)
15+
class Solution {
16+
17+
private:
18+
const long long MOD = 1e9 + 7;
19+
20+
public:
21+
int peopleAwareOfSecret(int n, int delay, int forget) {
22+
23+
vector<long long> pos(n, 0), neg(n, 0);
24+
pos[0] = 1;
25+
for(int i = 0; i < n; i ++){
26+
27+
for(int j = delay; j < forget && i + j < n; j ++){
28+
pos[i + j] += pos[i];
29+
pos[i + j] %= MOD;
30+
}
31+
32+
if(i + forget < n){
33+
neg[i + forget] += pos[i];
34+
neg[i + forget] %= MOD;
35+
}
36+
}
37+
38+
long long sum_pos = accumulate(pos.begin(), pos.end(), 0ll);
39+
long long sum_neg = accumulate(neg.begin(), neg.end(), 0ll);
40+
return (sum_pos % MOD - sum_neg % MOD + MOD) % MOD;
41+
}
42+
};
43+
44+
45+
int main() {
46+
47+
cout << Solution().peopleAwareOfSecret(6, 2, 4) << '\n';
48+
// 5
49+
50+
cout << Solution().peopleAwareOfSecret(4, 1, 3) << '\n';
51+
// 6
52+
53+
cout << Solution().peopleAwareOfSecret(6, 1, 2) << '\n';
54+
// 2
55+
56+
return 0;
57+
}

‎2001-2500/2327-Number-of-People-Aware-of-a-Secret/cpp-2327/main2.cpp

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
/// Source : https://leetcode.com/problems/number-of-people-aware-of-a-secret/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-07-02
4+
5+
#include <iostream>
6+
#include <vector>
7+
#include <numeric>
8+
9+
using namespace std;
10+
11+
12+
/// DP with diff array
13+
/// Time Complexity: O(n^2)
14+
/// Space Complexity: O(n)
15+
class Solution {
16+
17+
private:
18+
const long long MOD = 1e9 + 7;
19+
20+
public:
21+
int peopleAwareOfSecret(int n, int delay, int forget) {
22+
23+
vector<long long> diff_pos(n, 0), neg(n, 0);
24+
diff_pos[0] = 1;
25+
if(1 < n) diff_pos[1] = MOD - 1;
26+
long long presum = 0;
27+
for(int i = 0; i < n; i ++){
28+
29+
presum += diff_pos[i];
30+
presum %= MOD;
31+
32+
if(i + delay < n){
33+
diff_pos[i + delay] += presum;
34+
diff_pos[i + delay] %= MOD;
35+
}
36+
37+
if(i + forget < n){
38+
diff_pos[i + forget] -= presum;
39+
diff_pos[i + forget] += MOD;
40+
diff_pos[i + forget] %= MOD;
41+
42+
neg[i + forget] += presum;
43+
neg[i + forget] %= MOD;
44+
}
45+
}
46+
47+
long long sum_pos = 0;
48+
presum = 0;
49+
for(int i = 0; i < n; i ++){
50+
presum += diff_pos[i];
51+
presum %= MOD;
52+
sum_pos += presum;
53+
}
54+
long long sum_neg = accumulate(neg.begin(), neg.end(), 0ll);
55+
56+
return (sum_pos % MOD - sum_neg % MOD + MOD) % MOD;
57+
}
58+
};
59+
60+
61+
int main() {
62+
63+
cout << Solution().peopleAwareOfSecret(6, 2, 4) << '\n';
64+
// 5
65+
66+
cout << Solution().peopleAwareOfSecret(4, 1, 3) << '\n';
67+
// 6
68+
69+
cout << Solution().peopleAwareOfSecret(6, 1, 2) << '\n';
70+
// 2
71+
72+
return 0;
73+
}

‎2001-2500/2328-Number-of-Increasing-Paths-in-a-Grid/cpp-2328/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/2328-Number-of-Increasing-Paths-in-a-Grid/cpp-2328/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-increasing-paths-in-a-grid/
2+
/// Author : liuyubobobo
3+
/// Time : 2022-07-02
4+
5+
#include <iostream>
6+
#include <vector>
7+
8+
using namespace std;
9+
10+
11+
/// DAG DP
12+
/// Time Complexity: O(m * n)
13+
/// Space Complexity: O(m * n)
14+
class Solution {
15+
16+
private:
17+
const long long MOD = 1e9 + 7;
18+
const int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
19+
int R, C;
20+
21+
public:
22+
int countPaths(vector<vector<int>>& grid) {
23+
24+
R = grid.size(), C = grid[0].size();
25+
26+
vector<vector<long long>> dp(R, vector<long long>(C, -1));
27+
long long res = 0;
28+
for(int i = 0; i < R; i ++)
29+
for(int j = 0; j < C; j ++)
30+
res += dfs(grid, i, j, dp);
31+
return res % MOD;
32+
}
33+
34+
private:
35+
long long dfs(const vector<vector<int>>& g, int cx, int cy,
36+
vector<vector<long long>>& dp){
37+
38+
if(dp[cx][cy] != -1) return dp[cx][cy];
39+
40+
long long res = 1;
41+
for(int d = 0; d < 4; d ++){
42+
int nx = cx + dirs[d][0], ny = cy + dirs[d][1];
43+
if(!in_area(nx, ny) || g[nx][ny] <= g[cx][cy]) continue;
44+
res += dfs(g, nx, ny, dp);
45+
}
46+
47+
return dp[cx][cy] = res % MOD;
48+
}
49+
50+
bool in_area(int x, int y){
51+
return 0 <= x && x < R && 0 <= y && y < C;
52+
}
53+
};
54+
55+
56+
int main() {
57+
58+
vector<vector<int>> grid1 = {{1, 1}, {3, 4}};
59+
cout << Solution().countPaths(grid1) << '\n';
60+
// 8
61+
62+
vector<vector<int>> grid2 = {{1}, {2}};
63+
cout << Solution().countPaths(grid2) << '\n';
64+
// 3
65+
66+
return 0;
67+
}

‎readme.md

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2160,7 +2160,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
21602160
| | | | | | |
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/) | | |
2163-
| | | | | | |
2163+
| 2314 | Database Problem: [Link](https://github.com/liuyubobobo/Play-Leetcode-Database/) | - | - | - | - |
21642164
| 2315 | [Count Asterisks](https://leetcode.com/problems/count-asterisks/) | [无] | [C++](2001-2500/2315-Count-Asterisks/cpp-2315/) | | |
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/) | | |
@@ -2170,6 +2170,11 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
21702170
| 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/) | | |
21712171
| 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/) | | |
21722172
| 2323 | [Find Minimum Time to Finish All Jobs II](https://leetcode.com/problems/find-minimum-time-to-finish-all-jobs-ii/) | [无] | [C++](2001-2500/2323-Find-Minimum-Time-to-Finish-All-Jobs-II/cpp-2323/) | | |
2173+
| 2324 | Database Problem: [Link](https://github.com/liuyubobobo/Play-Leetcode-Database/) | - | - | - | - |
2174+
| 2325 | [Decode the Message](https://leetcode.com/problems/decode-the-message/) | [无] | [C++](2001-2500/2325-Decode-the-Message/cpp-2325/) | | |
2175+
| 2326 | [Spiral Matrix IV](https://leetcode.com/problems/spiral-matrix-iv/) | [无] | [C++](2001-2500/2326-Spiral-Matrix-IV/cpp-2326/) | | |
2176+
| 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/) | | |
2177+
| 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/) | | |
21732178
| | | | | | |
21742179

21752180
## 力扣中文站比赛

0 commit comments

Comments
 (0)