首页 > 0926腾讯音乐笔试题解
头像
神崎兰子
发布于 2022-09-27 11:43 香港
+ 关注

0926腾讯音乐笔试题解

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) 回帖
加载中...
话题 回帖