01串修改
题意:给定一个字符串,每次操作可以将一个子串变"00"或者"11",问所有字母相同的最小操作次数。
知识点:枚举
显然最终要么变成全0,要么变成全1。
如果变成全0,那么每个"0连续段"长度为时,操作次数为。
例如,00111000,第一个0连续段长度为2,操作1次。第二个0连续段长度为3,操作2次。
可以利用字符运算巧妙减少代码长度。
class Solution { public: int minOperations(string str) { int i,n=str.length(),mi=1e9; for(char c='0';c<='1';c++){ int res=0,ans=0; //res维护连续段长度,ans维护操作次数。 for(i=0;i<n;i++){ if(str[i]==c)res++; else res=0; if(res&1)ans++; //等价于向上取整。当连续段长度为奇数时计数。 } mi=min(mi,ans); //维护最小值。 } return mi; } };
另一种更容易懂的写法:
class Solution { public: int minOperations(string str) { int i,n=str.length(),mi=1e9; for(char c='0';c<='1';c++){ int res=0,ans=0; //res维护连续段长度,ans维护操作次数。 for(i=0;i<n;i++){ if(str[i]==c)res++; else ans+=res/2+res%2,res=0; //向上取整。 } ans+=res/2+res%2; //处理结尾未被处理的连续段。 mi=min(mi,ans); //维护最小值。 } return mi; } };
连续子数组数量
题意:求乘积尾零数量大于的连续子数组数量。
知识点:双指针/二分
本题本质是维护的区间数量。由于满足单调性,所以可以双指针/二分解决。
双指针;遍历右指针,当不合法时左指针右移,复杂度。(也可以遍历左指针,不过更推荐遍历右指针的写法,代码更好写)
双指针做法参考代码:
class Solution { public: int f(int x,int p){ //计算x中有多少个因子p。 int cnt=0; while(x%p==0)x/=p,cnt++; return cnt; } int getSubarrayNum(vector<int>& a, int x) { int i,n=a.size(),j,cnt2=0,cnt5=0,res=0,mod=1e9+7; for(i=0,j=0;i<n;i++){ cnt2+=f(a[i],2); cnt5+=f(a[i],5); while(min(cnt2,cnt5)>=x){ //找到第一个不合法的区间左端点,该左端点的左边全部合法。 cnt2-=f(a[j],2); cnt5-=f(a[j],5); j++; } res=(res+j)%mod; } return res; } };
二分:首先用前缀和可以求出前项的2因子和5因子数量,这样就可以查询区间的因子数量了。
二分的时候,枚举左端点,在前缀和数组上找到第一处合法的右端点即可。复杂度 。
本题在笔试中不建议用二分写法,复杂度比双指针大,并且写起来也比双指针麻烦。不过二分算法还是建议大家掌握的,用处非常多。
二分参考代码:
class Solution { public: int f(int x,int p){ //计算x种有多少个因子p。 int cnt=0; while(x%p==0)x/=p,cnt++; return cnt; } int sum2[101010]={},sum5[101010]={}; int check(int idx,int mid,int x){ //判断[idx,mid]区间的乘积尾零是否大于x int cnt2=sum2[mid],cnt5=sum5[mid]; if(idx)cnt2-=sum2[idx-1],cnt5-=sum5[idx-1]; //这里前缀和需要判0。可以前缀和数组下标从1开始来规避这个问题。 return min(cnt2,cnt5)>=x; } int bs(int idx,int l,int r,int x){ //在a数组中,固定左端点为idx,二分找最小合法右端点的位置。 if(!check(idx,r,x))return r+1; //右端点不合法需要特判。 if(l==r)return l; int mid=l+r>>1;//等价于(l+r)/2。 if(check(idx,mid,x))return bs(idx,l,mid,x); //合法二分递归向左找。 return bs(idx,mid+1,r,x); //不合法则向右找。 } int getSubarrayNum(vector<int>& a, int x) { int i,n=a.size(),j,cnt2=0,cnt5=0,res=0,mod=1e9+7; for(i=0;i<n;i++){ sum2[i]=cnt2+=f(a[i],2); //习惯了可以这样写前缀和,也可以把sum2[i]=cnt2放到下面。 sum5[i]=cnt5+=f(a[i],5); } for(i=0;i<n;i++){ res+=n-bs(i,i,n-1,x); //找到第一个合法的右端点,其右边均为合法区间。 res%=mod; } return res; } };
好矩阵
题意:求的矩阵,每个元素都在区间,满足任意2*2子矩阵之和为偶数的矩阵数量。
知识点:组合数学
我们可以先确定第一行和第一列,每个格子上有种不同的取法,共有个格子。因此这些格子的取法总数为。
当第一行和第一***定了以后,其余的格子的奇偶性也就确定下来了。无论是奇数还是偶数,每个格子的取法都是种,因此取法为
把这两个答案乘起来就是最终的答案。
由于指数很大,所以要用快速幂:即利用快速计算乘方。
class Solution { public: int mod=1e9+7; int power(int a,long long b){ int res=1; while(b){ if(b&1)res=1LL*res*a%mod; //注意这里会爆int,所以要先转long long。 b>>=1; a=1LL*a*a%mod; } return res; } int numsOfGoodMatrix(int n, int m, int x) { return 1LL*power(x,n+m-1)*power(x/2,1LL*(n-1)*(m-1))%mod; } };
当然python已经将快速幂封装好了,所以如果用python的话本题只有一行代码(滑稽):
class Solution: def numsOfGoodMatrix(self , n: int, m: int, x: int) -> int: return pow(x,n+m-1,10**9+7)*pow(x//2,(n-1)*(m-1),10**9+7)%(10**9+7)
全部评论
(1) 回帖