题目列表

2843. 统计对称整数的数目

2844. 生成特殊数字的最少操作

2845. 统计趣味子数组的数目

2846. 边权重均等查询

一、统计对称整数的数目

 这题看一眼数据范围，直接就可以开始暴力求解了，按照题目要求模拟就行，代码如下

class Solution {
public:int countSymmetricIntegers(int low, int high) {int ans=0;for(int i=low;i<=high;i++){string s=to_string(i);if(s.size()%2)continue;int m=s.size()/2;int diff=0;for(int j=0;j<m;j++)diff+=(s[j]-s[j+m]);if(diff==0)ans++;}return ans;}
};

二、生成特殊数字的最小操作数

这题其实也不难，只要知道25的倍数的特点就行，即末尾两位为00，25 ，50，75的数字，题目要求最小操作数，就是在这四种情况中找到操作数最小的，当然还要注意0也能被25的整除，所以当不满足前面四种情况时， 还要考虑数字中是否包含0，如果有返回n-1，如果没有返回n。

代码如下

class Solution {
public:int minimumOperations(string num) {int n=num.size();function<int(string)>f=[&](string s)->int{size_t pos=num.rfind(s[1]);if(pos==-1||pos==0)return n;pos=num.rfind(s[0],pos-1);if(pos==-1)return n;return n-pos-2;};int ret1=min(min(f("00"),f("25")),min(f("75"),f("50")));int ret2=n-(num.find('0')!=-1);return min(ret1,ret2);}
};

三、统计趣味子数组的数目

求满足条件的子数组的数量，一般都是用前缀和+哈希表，这题前缀和是求满足nums[i]%modulo=k的子数组的数量，这里有一些求余运算的数学知识，如下

假设s[ ]为前缀和数组，i<j，且(s[j]-s[i])%m=k，

那么s[j]%m-s[i]%m=k，即s[i]%m=s[j]%m-k，这里有一个细节要注意，s[j]%m-s[i]%m可能小于0，这样就需要+m之后再%m，才能得到正确的取模值，即s[j]%m-s[i]%m+m=k，s[i]%m=s[j]%m-k+m

综上所诉：无论s[j]%m-s[i]%m结果是正是负，s[i]%m=(s[j]%m-k+m)%m

 所以，哈希表只用记录s%m之后的值的数量即可

 代码如下

class Solution {
public:long long countInterestingSubarrays(vector<int>& nums, int m, int k) {long long ans=0;int s=0;unordered_map<int,int>hash;hash[0]=1;//这里要注意！！！，代表没有元素时，余数为0的情况for(auto x:nums){s+=(x%m==k);s%=m;ans+=hash[(s-k+m)%m];hash[s%m]++;}return ans;}
};

四、边权重均等查询

 思路如下：

代码如下 

class Solution {
public:vector<int> minOperationsQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {//创建矩阵--记录每个点所连接的点和权值vector<vector<pair<int,int>>>g(n);for(auto& e:edges){int x=e[0],y=e[1],w=e[2]-1;g[x].push_back({y,w});g[y].push_back({x,w});}int m=32-__builtin_clz(n);//得到前导0的个数int cnt[n][m][26];memset(cnt,0,sizeof(cnt));int pa[n][m];memset(pa,-1,sizeof(pa));vector<int>depth(n);//记录每个点的深度function<void(int,int)> dfs=[&](int x,int father){pa[x][0]=father;for(auto [y,w]: g[x]){if(y!=father){cnt[y][0][w]=1;depth[y]=depth[x]+1;dfs(y,x);}}};dfs(0,-1);//倍增for(int i=1;i<m;i++){for(int j=0;j<n;j++){int p=pa[j][i-1];if(p!=-1){pa[j][i]=pa[p][i-1];for(int k=0;k<26;k++){cnt[j][i][k]=cnt[j][i-1][k]+cnt[p][i-1][k];}}}}vector<int> ans;for(auto&e:queries){int a=e[0],b=e[1];int len=depth[a]+depth[b];if(depth[a]>depth[b])swap(a,b);int cw[26]{};//让x和y在同一高度for(int k=depth[b]-depth[a];k;k&=k-1){int idx=__builtin_ctz(k);int p=pa[b][idx];for(int j=0;j<26;j++)cw[j]+=cnt[b][idx][j];b=p;}//同时向上跳if(a!=b){for(int i=m-1;i>=0;i--){int A=pa[a][i],B=pa[b][i];if(A!=B){for(int k=0;k<26;k++){cw[k]+=cnt[a][i][k]+cnt[b][i][k];}a=A,b=B;}}//跳完之后，还在LAC下面一层for(int k=0;k<26;k++){cw[k]+=cnt[a][0][k]+cnt[b][0][k];}a=pa[a][0];}int lca=a;len-=depth[lca]*2;ans.push_back(len-*max_element(cw,cw+26));}return ans;}
};