leetcode 2243.计算字符串的数字和:力扣
c++实现:
class Solution {
public:
string digitSum(string s, int k) {
if(s.size()<=k) return s;
unordered_maph;
h['0']=0;h['1']=1;h['2']=2;h['3']=3;h['4']=4;h['5']=5;h['6']=6;h['7']=7;h['8']=8;h['9']=9;
string res="";
while(s.size()>k){
//合并
for(int i=0;i
leetcode 2244.完成所有任务需要的最少轮数:力扣
c++实现:
class Solution {
public:
int minimumRounds(vector& tasks) {
int res=0;
unordered_maph;
sort(tasks.begin(),tasks.end());
for(int i=0;i
leetcode2245.转角路径的乘积中最多能有几个尾随零:力扣
c++实现:
思路: 我们先来找下尾随零的规律.如果两个数相乘可以多出一个尾随零,那说明这两个数肯定可以至少包含一个2和5的组合.比如15*4=60，有一个尾随零,是因为15=5*3包含一个5，而4=2*2包含2个2.取二者之间的最小值也就是5的个数，所以两个数相乘的结果包含一个尾随零.
需要注意的是尾随零的个数随着乘积的因数不断增加只有可能增加或不变而不可能+减少，并且一条路径至多一个拐点.所以我们选择循环遍历grid中的每一个数字作为一个"拐点".把经过这个"拐点"的最长路径，也就是从一个边界到另一个边界的路径全部计算一个尾随零个数取最大值,因此我们需要预处理出一个分解后的 2 5 个数的前缀和数组.
1.分解后的每一个格子的2 5个数:num_2[N][N] num_5[N][N]
2.行的2 5 个数的前缀和:row_2[N][N] row_5[N][N]
3.列的2 5个数的前缀和:column_2[N[N] column_5[N][N]
class Solution {
public:
int maxTrailingZeros(vector>& grid) {
int m=grid.size();
int n=grid[0].size();
int res=0;
int num_2[m][n];
int num_5[m][n];
int row_2[n][m];
int row_5[n][m];
int column_2[m][n];
int column_5[m][n];
//对每一个框格的2 5进行存储
for(int i=0;i
leetcode 2246.相邻字符不同的最长路径:力扣
c++实现:
class Solution {
public:
vector>h;
int res=-1e+9;
string s;
int dp[100010][2]; //1表示以这个点为拐点可以形成的最长路径 0表示这个节点的最高高度
void dfs(int root){
int a,b;
int flag=0;
//如果这只是唯一的点，那么经过他的最长路径就是它自身一个节点就是1，它能拓展的树的高度就是它自身的高度1
dp[root][1]=dp[root][0]=1;
//遍历所有的子节点
for(int j:h[root]){
//如果发生断点.则不更新当前节点的所有信息,并仍以当前为根进行新一轮遍历
if(s[j]==s[root]){
dfs(j);
}
//如果没有发生断点，则更新当前的所有信息,并以当前节点为根进行新一轮遍历
else{
dfs(j);
//更新dp[root][0]
dp[root][0]=max(dp[root][0],dp[j][0]+1);
//记录经过这个拐点的两条路径中可以相加得到的最长路径
if(flag<2){
dp[root][1]+=dp[j][0];
if(flag==0) a=dp[j][0];
if(flag==1) b=dp[j][0];
flag++;
}
else{
if(dp[j][0]>a&&dp[j][0]a&&dp[j][0]>b){
if(a<=b) { dp[root][1]=dp[root][1]-a+dp[j][0];a=dp[j][0]; }
else{ dp[root][1]=dp[root][1]-b+dp[j][0];b=dp[j][0]; }
}
//还有dp可能等于a/b的情况!!别漏了
else if(dp[j][0]==a){
if(a>b){
dp[root][1]=dp[root][1]-b+dp[j][0];
b=dp[j][0];
}
}
else if(dp[j][0]==b){
if(a& parent, string s) {
h=vector>(parent.size());
this->s=s;
for(int i=1;i
总结:这次周赛更多的是思维题和一些经典题变式，具体实现起来虽然有思路但是完整的通过所有案例还是有一定难度.
