【LeetCode第 80 场双周赛】

简介: 笔记

10.png

感谢又给一次AK的机会,AK传送门


强密码检验器 II


题目

11.png


思路

  • 根据题意模拟即可

代码

class Solution {
public:
    bool strongPasswordCheckerII(string p) {
        int n = p.size();
        if(n < 8) return false;
        string s = "!@#$%^&*()-+";
        bool o1 = true, o2 = true, o3 = true, o4 = true, o5 = true;
        for (int i = 0; i < n; i++) {
            if(p[i] <= 'z' && p[i] >= 'a') o1 = false;
            if(p[i] <= 'Z' && p[i] >= 'A') o2 = false;
            if(p[i] <= '9' && p[i] >= '0') o3 = false;
            for (int j = 0; j < s.size(); j++) if(s[j] == p[i]) o4 = false;
            if(i && p[i] == p[i - 1]) o5 = false;
        }
        return !o1 && !o2 && !o3 && !o4 && o5;
    }
};

咒语和药水的成功对数


题目

12.png

思路

13.png

代码

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        vector<int> res;
        vector<long long> a;
        for (int i = 0; i < potions.size(); i++) {
            a.push_back(1ll * (success - 1) / potions[i] + 1);
        }
        sort(a.begin(), a.end());
        for (int i = 0; i < spells.size(); i++) {
            int id = upper_bound(a.begin(), a.end(), spells[i]) - a.begin();
            res.push_back(id);
        }
        return res;
    }
};

替换字符后匹配


题目


14.png

思路

15.png

代码

class Solution {
public:
    map<char, map<char, bool>> mp;
    bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {
        int n = s.size(), m = sub.size();
        if(m > n) return false;
        for (int i = 0; i < mappings.size(); i++) {
            char a = mappings[i][0], b = mappings[i][1];
            mp[a][b] = true;
        }
        for (int i = 0; i < n - m + 1; i++) {
            string pre = s.substr(i, m);
            bool o = true;
            for (int j = 0; j < m; j++) {
                if(!mp[sub[j]][pre[j]] && sub[j] != pre[j]) o = false;
                if(!o) break;
            }
            if(o) return true;
        }
        return false;
    }
};

补题学到的妙解

s u f  数组存储最终每个字符所有能转移到的状态


最终结果就是取 s u b中每个字符状态的并集


参考这位大佬

16.png


位运算加速,代码如下:

class Solution {
public:
    static const int N = 5010;
    bitset<N> res, pre[128], suf[128]; 
    bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {
        for (int i = 0; i < 128; i++) pre[i].reset();
        for (int i = 0; i < s.size(); i++) pre[s[i]].set(i);
        for (int i = 0; i < 128; i++) suf[i] = pre[i];
        for (auto &mp: mappings) suf[mp[0]] |= pre[mp[1]];
        res.set();
        for (int i = 0; i < sub.size(); i++) res &= suf[sub[i]] >> i;
        return res.count();
    }
};

统计得分小于 K 的子数组数目


题目

17.png


思路


比较容易能发现一个性质,单调性, 即子数组越长,那么分数越高。

由此我们可以想到有双指针来解决,(应该可以吧hhhh

l , r 维护区间左右,当前区间表示一定满足分数

那么如何计算上每个状态的贡献呢?


我们可以定义,当前状态 ll,r ,贡献值为:以 r 结尾的区间个数,并且区间起始是从 l 开始,形式化为 r − l + 1这样在r 每次移动时,都对其计算贡献,显然每个状态都是不重的,并且对于答案这样是不会遗漏的。(r 会从起始移动到末尾)

误:一开始我对贡献计算是区间l,r 之间所有区间数,显然这样会有大量的重复区间的计算,读者可自行思考。


代码

class Solution {
public:
    #define ll long long
    long long countSubarrays(vector<int>& nums, long long k) {
        int r = 0, n = nums.size();
        ll now = 0, len = 0, res = 0;
        for (int i = 0; i < n; i++) {
            while(r < n && ((now + nums[r])) * (len + 1) < k) {
                now += nums[r];
                len ++;
                res += (r - i + 1);
                r++;
            }
            now -= nums[i];
            len--;
        }
        return res;
    }
};



相关文章
|
6月前
Leetcode第123场双周赛
在LeetCode的第123场双周赛中,参赛者需解决三个问题。第一题涉及根据给定数组构建三角形并判断其类型,如等边、等腰或不等边,代码实现通过排序简化条件判断。第二题要求找出满足差值为k的好子数组的最大和,解决方案利用前缀和与哈希表提高效率。第三题则需要计算点集中满足特定条件的点对数量,解题策略是对点按坐标排序并检查点对是否满足要求。
26 1
|
6月前
力扣双周赛 -- 117(容斥原理专场)
力扣双周赛 -- 117(容斥原理专场)
【Leetcode】- 第 29 场双周赛
【Leetcode】- 第 29 场双周赛
|
机器人
LeetCode 双周赛 106(2023/06/10)两道思维题
往期回顾:[LeetCode 单周赛第 348 场 · 数位 DP 模版学会了吗?](https://mp.weixin.qq.com/s/4aLHpyaLOUEHSaX2X8e5FQ)
87 0
LeetCode 双周赛 106(2023/06/10)两道思维题
|
算法 索引
LeetCode 双周赛 107(2023/06/24)滑动窗口与离散化
> **本文已收录到 [AndroidFamily](https://github.com/pengxurui/AndroidFamily),技术和职场问题,请关注公众号 \[彭旭锐] 和 \[BaguTree Pro] 知识星球提问。**
74 0
LeetCode 双周赛 107(2023/06/24)滑动窗口与离散化
|
边缘计算 缓存 算法
LeetCode 双周赛 102,模拟 / BFS / Dijkstra / Floyd
昨晚是 LeetCode 双周赛第 102 场,你参加了吗?这场比赛比较简单,拼的是板子手速,继上周掉大分后算是回了一口血 😁。
111 0
|
人工智能 算法 测试技术
LeetCode 双周赛 101,DP / 中位数贪心 / 裴蜀定理 / Dijkstra / 最小环
这周比较忙,上周末的双周赛题解现在才更新,虽迟但到哈。上周末这场是 LeetCode 第 101 场双周赛,整体有点难度,第 3 题似乎比第 4 题还难一些。
99 0
|
人工智能 算法 测试技术
LeetCode 双周赛 103(2023/04/29)区间求和的树状数组经典应用
这场周赛是 LeetCode 双周赛第 103 场,难得在五一假期第一天打周赛的人数也没有少太多。这场比赛前 3 题比较简单,我们把篇幅留给最后一题。
80 0