Leetcode 第 292 场周赛
6056. 字符串中最大的 3 位相同数字
顺序3个3个找
class Solution {
public:
string largestGoodInteger(string num) {
string ans="";
for(int i=0;i<num.size()-2;i++){
if(num[i]==num[i+1]&&num[i]==num[i+2]){
if(ans=="") ans=num.substr(i,3);
else {
if(num.substr(i,3)>ans) ans=num.substr(i,3);
}
i+=2;
}
}
return ans;
}
};
6057. 统计值等于子树平均值的节点数
递归得到 节点下树的值和val和节点数目cnt
class Solution {
public:
int ans = 0;
struct node {int val,cnt;};
node dfs(TreeNode* root) {
if(root==nullptr) return {0,0};
auto [lv,lc] = dfs(root->left);
auto [rv,rc] = dfs(root->right);
if((lv+rv+root->val)/(lc+rc+1)==root->val) ans++;
return {lv+rv+root->val,lc+rc+1};
}
int averageOfSubtree(TreeNode* root) {
auto [v,c] = dfs(root);
return ans;
}
};
6058. 统计打字方案数
重点要解决 连续按钮 的方案数目。然后就是每个”连续数字“间的方案数乘积就是答案啦。
用lx3 表示3为数的连续 ，下面用1表示连按（虽然题目中没得1）
lx(1)：1 [1个方案]
lx3(11)：（1，1），11 [2个方案]
lx3(111)：1（（1，1），11），11（1），111 [4个方案]
lx3(1111)：1（lx3(111)），11（lx3(11)），111（lx3(1)） [7个方案]
所以就得到递推式了
class Solution {
public:
int countTexts(string pressedKeys) {
int mod = 1e9+7;
long long ans = 0;
vector<long long> lx3(1e5+1),lx4(1e5+1);
lx3[1]=1;lx3[2]=2;lx3[3]=4;lx3[4]=7;
lx4[1]=1;lx4[2]=2;lx4[3]=4;lx4[4]=8;
for(int i=5;i<1e5+1;i++) {
lx3[i] = ((lx3[i-1]+lx3[i-2])%mod+lx3[i-3])%mod;
lx4[i] = ((lx4[i-1]+lx4[i-2])%mod+(lx4[i-3]+lx4[i-4])%mod)%mod;
}
int x = 0;
while(x<pressedKeys.size()) {
int y = x;
while(y<pressedKeys.size()&&pressedKeys[x]==pressedKeys[y]) y++;
long long num = y-x;
if(ans==0) {
if(pressedKeys[x]!='9'&&pressedKeys[x]!='7') ans=lx3[num];
else ans = lx4[num];
}
else {
if(pressedKeys[x]!='9'&&pressedKeys[x]!='7') ans = (ans * lx3[num]) % mod;
else ans = (ans * lx4[num]) % mod;
}
x=y;
}
return (int)ans;
}
};
6059. 检查是否有合法括号字符串路径
没写出来，一直超时,一直想着记忆化搜索，操作半天还是失败了。看大佬们思路去了（菜狗哭泣）
思路：n，m<100，dfs(c,x,y,grid)： c表示搜索状态（遇到"(" c+1,")"c-1），遇到c<0 肯定是不合法，所以状态中c>=0. 在最后一个坐标是 应该是c=0。
记忆：vis[x][y][c] 表示坐标xy下c状态已经访问过了
class Solution {
public:
int n,m;
vector<vector<vector<bool>>> vist;
bool dfs(int c,int x,int y,vector<vector<char>>& grid){
if(x==n-1&&y==m-1) return c==1;//最后一个为')' -1 c==0
if(vist[x][y][c]) return false;//访问过了
vist[x][y][c] = true;
c += grid[x][y]=='('? 1:-1;
return c>=0 && ((x+1<n&&dfs(c,x+1,y,grid)) || (y+1<m&&dfs(c,x,y+1,grid)));
}
bool hasValidPath(vector<vector<char>>& grid) {
n = grid.size(), m = grid[0].size();
vist.resize(n,vector<vector<bool>>(m,vector<bool>(n+m)));
if((n+m)%2==0||grid[0][0]==')'||grid[n-1][m-1]=='(') return false;
return dfs(0,0,0,grid);
}
};
