第75场双周赛

第75场双周赛,第1张

最近的题目貌似有点简单

第一题,直接暴力对比每位是否相等,统计所有不相等位的数量

class Solution {
public:
    int minBitFlips(int start, int goal) {
        int ans = 0;
        while(start || goal)
        {
            int a = start%2;
            int b = goal%2;
            if(a != b)
                ans++;
            start=start>>1;
            goal=goal>>1;
        }
        return ans;
    }
};

 

 第二题同样暴力通过。


(这题貌似和刚学c++入门的时候做杨辉三角一样)

class Solution {
public:
    int triangularSum(vector& nums) {
        int n = nums.size();
        if(n == 1)
            return nums[0];
        for(int i = n-1; i >= 0; i--)
            for(int j = 0; j < i; j++)
                nums[j] = (nums[j]+nums[j+1])%10;
        return nums[0];
    }
};

第三题,有点c动态规划的意思,统计当前0,1,01,10的数量,如果0,1的数量用来更新01,10的数量,01,10用来更新101,010的数量,也就是最终结果。


(忘记看返回的是longlong,直接WA了一次,血亏)

class Solution {
public:
    long long numberOfWays(string s) {
        long long cur_0 = 0, cur_1=0,cur_01=0, cur_10=0;
        long long ans = 0;
        for(auto c:s)
        {
            if(c == '0')
            {
                cur_0+=1;
                ans += cur_01;
                cur_10 += cur_1;
            }
            else
            {
                cur_1+=1;
                ans += cur_10;
                cur_01 += cur_0;
            }
        }
        return ans;
    }
};

 

 第四题最长公共前缀,但是难度增加了,看了大佬们的题解才知道是KMP算法的扩展,叫做Z函数

class Solution {
public:
    vector z_function(string s) {
    int n = (int)s.length();
    vector z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r && z[i - l] < r - i + 1) {
        z[i] = z[i - l];
        } else {
        z[i] = max(0, r - i + 1);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
        }
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
    return z;
    }
    long long sumScores(string s) {
        long long ans = s.length();//注意这里初始化成字符串的长度,因为自身也算,这里被坑了一次
        auto z = z_function(s);
        for(auto k : z)ans += k;
        return ans;
    }
};
//Z函数教程:https://oi-wiki.org/string/z-func/

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/565157.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-06
下一篇 2022-04-06

发表评论

登录后才能评论

评论列表(0条)

保存