A6056. 字符串中最大的 3 位相同数字
模拟即可
// shiran
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1e9+7;
const int N = 40010, M = 300010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
class Solution {
public:
string largestGoodInteger(string num) {
string ans = "";
for (int i = 0; i + 2 < sz(num); i ++ ) {
if (num[i] == num[i + 1] && num[i + 1] == num[i + 2])
{
if (sz(ans)==0) ans = num.substr(i,3);
else if (num[i] > ans[0])
ans = num.substr(i,3);
}
}
return ans;
}
};
B6057. 统计值等于子树平均值的节点数
深度优先遍历先遍历子树返回权值和和结点数量，每个结点比较计数
// shiran
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define pb push_back
#define mk make_mair
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1e9+7;
const int N = 40010, M = 300010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int res=0;
int averageOfSubtree(TreeNode* root) {
dfs(root);
return res;
}
PII dfs(TreeNode* root) {
if (!root) return {0, 0};
auto l = dfs(root->left), r = dfs(root->right);
int sum = l.x + r.x + root->val, cnt = l.y+r.y+1;
if ((floor)(sum / cnt) == root->val) res ++;
return {sum, cnt};
}
};
C6058. 统计打字方案数
DP，考虑最近的几个字符构成一个字母，f[j]表示前j个字符方案数量，考虑最近的k个字符构成一个字母，显然k最大值应该是3或者是4，答案应该加上除了最近的这k个字母，前面的方案数量f[j]+=f[j-k]，递推得到结果。
// shiran
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
#define mk make_mair
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1e9+7;
const int N = 100010, M = 300010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
class Solution {
public:
int countTexts(string s) {
int n = sz(s);
s = " " + s;
ll f[N];
memset(f, 0, sizeof f);
f[0] = 1;
for (int i = 1; i <= n; i ++ ) {
for (int j = i; j >= max(1, i - 2 - (s[i] == '7' || s[i] == '9')); j -- )
if (s[i] == s[j])
f[i] = (f[i] + f[j - 1]) % mod;
else
break;
}
return f[n];
}
};
D6059. 检查是否有合法括号字符串路径
DP，合法括号序列左括号-右括号数量实时非负，那么DP第三维表示左括号比右括号多的数量。
// shiran
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define sz(x) (int)size(x)
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
#define mk make_mair
typedef long long ll;
typedef pair<int, int> PII;
const int mod = 1e9+7;
const int N = 110, M = 300010;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool f[N][N][2 * N];
class Solution {
public:
int n, m;
bool hasValidPath(vector<vector<char>>& s) {
memset(f, false, sizeof f);
int n = s.size();
int m = s[0].size();
f[1][0][0] = true;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (s[i - 1][j - 1] == '(')
{
for (int k = 1; k < n + m; k++)
{
f[i][j][k] |= f[i - 1][j][k - 1];
f[i][j][k] |= f[i][j - 1][k - 1];
}
}
else // ')'
{
for (int k = 0; k + 1 < n + m; k++)
{
f[i][j][k] |= f[i - 1][j][k + 1];
f[i][j][k] |= f[i][j - 1][k + 1];
}
}
}
}
return f[n][m][0];
}
};
