2024-03-01
题目传送门：2369. 检查数组是否存在有效划分 - 力扣（LeetCode）
非常基础的DP，DP方程如下：
1
2
3
| if (nums[i-1] == nums[i-2]) dp[i] = dp[i]||dp[i-2];
if (nums[i-1] == nums[i-2]&&nums[i-2] == nums[i-3]) dp[i] = dp[i]||dp[i-3];
if (nums[i-1] == nums[i-2]+1 && nums[i-2] == nums[i-3]+1) dp[i] = dp[i]||dp[i-3];
|
其中dp[i]代表的是到第i个数前面的数能否被划分。初始条件dp[0]=true;dp[1]=false，然后dp[2]的取值，取决于第一个元素和第二个元素是否相等，从3开始递推。
最后实现代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
bool validPartition(vector<int>& nums) {
int n = nums.size();
if (n < 2) return false;
vector<bool> dp(n+1,false);
dp[0] = true; dp[1] = false;
if (nums[0]==nums[1]) dp[2] = true;
for(int i=3; i<=n; ++i) {
if (nums[i-1] == nums[i-2]) dp[i] = dp[i]||dp[i-2];
if (nums[i-1] == nums[i-2]&&nums[i-2] == nums[i-3]) dp[i] = dp[i]||dp[i-3];
if (nums[i-1] == nums[i-2]+1 && nums[i-2] == nums[i-3]+1) dp[i] = dp[i]||dp[i-3];
}
return dp[n];
}
};
|
2024-03-02
题目传送门：2368. 受限条件下可到达节点的数目 - 力扣（LeetCode）
DFS深搜，对于每个节点返回以当前节点为子树可以访问的节点数量。
实现代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
vector<bool> vis(n, false);
for(auto &node:restricted) vis[node] = true;
vector<vector<int>> es(n);
for(auto &edge:edges){
es[edge[0]].push_back(edge[1]);
es[edge[1]].push_back(edge[0]);
}
function<int(int,int)> dfs = [&](int u, int fa){
int now = 1;
for(auto &v:es[u]){
if (vis[v]||v == fa) continue;
now += dfs(v, u);
}
return now;
};
return dfs(0, -1);
}
};
|
2024-03-09
题目传送门：2386. 找出数组的第 K 大和 - 力扣（LeetCode）
2024-03-10
题目传送门：299. 猜数字游戏 - 力扣（LeetCode）
思路比较简单的一道题，其实我们只需要遍历，对于两个字符串相同位置如果一致不用管，不一样，分别存入对应的10个桶中（分别代表每个字符串中0~9的个数），最后比较对应位置桶的大小即可。
注意：C++字fw符常量使用''，字符串常量使用""
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
string getHint(string secret, string guess) {
vector<int> buk_sec(10,0),buk_gue(10,0);
int a = 0;
for (int i=0;i<secret.size();++i) {
if(secret[i]==guess[i]) a++;
else {
buk_sec[secret[i]-'0']++;
buk_gue[guess[i]-'0']++;
}
}
int b = 0;
for(int i=0;i<10;++i){
b += min(buk_sec[i],buk_gue[i]);
}
return to_string(a)+"A"+to_string(b)+"B";
}
};
|
2024-03-11
题目传送门：2129. 将标题首字母大写 - 力扣（LeetCode）
这道题作为一道基础模拟题，整体思路并不复杂，我将思路分为两个阶段，第一阶段将每个单词第一个字母都大写，然后将所有非首字母的部分都小写。第二阶段判断每个单词的长度，如果长度小于等于2，则将该单词首字母小写。
注意这里转换大写和转换小写可以使用toupper和tolower函数
因此最终代码如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
string capitalizeTitle(string title) {
int n = title.size();
bool flag = true;
for(auto &let:title){
if (let == ' ') {
flag = true;
continue;
}
if(flag == true){
flag = false;
let=toupper(let);
} else {
let=tolower(let);
}
}
int len = title.size();
for(int i=0;i<len;++i){
if (title[i] == ' ') continue;
int tmp = i;
while(tmp<len&&title[tmp]!=' ') tmp++;
if(tmp-i<=2) title[i] = tolower(title[i]);
i = tmp;
}
return title;
}
};
|