292 场周赛
第一题
class Solution {
public:
string largestGoodInteger(string num) {
string ret = "";
for (int i = 0; i < num.size(); ++ i) {
string t = num.substr(i, 3);
if (t[0] == t[1] && t[0] == t[2] && t > ret) {
ret = t;
}
}
return ret;
}
};
第二题
/**
* 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 ret = 0;
pair<int, int> dfs(TreeNode* root) {
pair<int, int> l = {0, 0}, r = {0, 0};
if (root->left) {
l = dfs(root->left);
}
if (root->right) {
r = dfs(root->right);
}
int v = root->val;
if (v == (l.first + r.first + v) / (l.second + r.second + 1) ) ++ ret;
return {v + l.first + r.first, l.second + r.second + 1};
}
int averageOfSubtree(TreeNode* root) {
dfs(root);
return ret;
}
};
第三题
class Solution {
public:
static const int N = 1E5 + 5;
int f[N], g[N];
int countTexts(string ps) {
f[0] = 1;
g[0] = 1;
int p = 1e9 + 7;
for (int i = 1; i < N; ++ i) {
for (int j = 1; j <= 3; ++ j) {
if (i >= j) f[i] = (f[i] + f[i - j]) % p;
}
for (int j = 1; j <= 4; ++ j) {
if (i >= j) g[i] = (g[i] + g[i - j]) % p;
}
}
long long ret = 1;
for (int i = 0; i < ps.size(); ++ i) {
int j = i;
while (j < ps.size() && ps[j] == ps[i]) {
++ j;
}
if (ps[i] == '7' || ps[i] == '9') ret *= g[j - i];
else ret *= f[j - i];
ret %= p;
i = j - 1;
}
return ret;
}
};
第四题
** 动态规划的本质就是有剪枝的暴力枚举**
一般学习方法：写出暴力枚举 --> 剪枝暴力枚举 --> 写成循环的方式
剪枝推荐题解
循环推荐题解
// 超时
class Solution {
public:
vector<vector<char> > g;
bool dfs(int x, int y, int cnt) {
if (x >= g.size() || y >= g[0].size()) return false;
if (g[x][y] == '(') {
++ cnt;
}else -- cnt;
if (cnt < 0) return false;
if (x == g.size() - 1 && y == g[0].size() - 1) {
return cnt == 0;
}
return dfs(x + 1, y, cnt) || dfs(x, y + 1, cnt);
}
bool hasValidPath(vector<vector<char>>& grid) {
this->g = grid;
return dfs(0, 0, 0);
}
};
// 剪枝
class Solution {
public:
vector<vector<char> > g;
unordered_map<int, int> mp;
bool dfs(int x, int y, int cnt) {
int n = g.size(), m = g[0].size();
if (x >= g.size() || y >= g[0].size()) return false;
int k = (x * m + y) * m + cnt;
if (mp[(x * m + y) * m + cnt]) return mp[k] == 1;
if (g[x][y] == '(') {
++ cnt;
}else -- cnt;
if (cnt < 0) return false;
if (x == g.size() - 1 && y == g[0].size() - 1) {
return cnt == 0;
}
bool t = dfs(x + 1, y, cnt) || dfs(x, y + 1, cnt);
if (t) {
mp[k] = 1;
}else mp[k] = 2;
return mp[k] == 1;
}
bool hasValidPath(vector<vector<char>>& grid) {
this->g = grid;
return dfs(0, 0, 0);
}
};
// 循环
class Solution {
public:
static const int N = 2e2 + 5;
int dp[N][N][N];
bool hasValidPath(vector<vector<char>>& grid) {
if (grid[0][0] == ')') return false;
int n = grid.size(), m = grid[0].size();
dp[0][0][1] = 1;
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < m; ++ j) {
if (i || j) {
int t = grid[i][j] == '('? 1 : -1;
for (int k = 0; k < n + m; ++ k) {
if (k - t < 0) continue;
if (i)
dp[i][j][k] |= dp[i - 1][j][k - t];
if (j)
dp[i][j][k] |= dp[i][j - 1][k - t];
}
}
}
}
return dp[n - 1][m - 1][0];
}
};
