讨论/题目交流/🏆 第 168 场力扣周赛/
🏆 第 168 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 统计位数为偶数的数字
4 分 - 划分数组为连续数字的集合
6 分 - 子串的最大出现次数
7 分 - 你能从盒子里获得的最大糖果数

展开讨论

题解 (LeetCode 竞赛题真是越来越难了,今天居然翻车了)

第一题:统计位数为偶数的数字

数数位。可以转字符串做,也可以直接做。

class Solution {
public:
    int findNumbers(vector<int>& nums) {
        int ret=0;
        for (auto&i:nums){
            int tmp=0;
            while (i){
                ++tmp;
                i/=10;
            }
            if (tmp%2==0)++ret;
        }
        return ret;
    }
};

第二题:划分数组为连续数字的集合

贪心。假设当前还有数字序列 [y,x1,x2,x3,x4,...,xn][y,x_1,x_2,x_3,x_4,...,x_n] ,其中 yy 是序列中最小的数字,那么如果真的有解,就必须出现序列 [y,y+1,y+2,...,y+k1][y,y+1,y+2,...,y+k-1] ,否则 yy 就无法匹配了。所以每次贪心选择最小的数字序列减掉就行。
用map维护或者哈希表维护一下即可。

class Solution {
public:
    bool isPossibleDivide(vector<int>& nums, int k) {
        map<int,int> mmp;
        int cur=0x3f3f3f3f;
        for (auto&i:nums){
            mmp[i]++;
            cur=min(cur,i);
        }
        if (nums.size()%k!=0) return false;
        int rua=nums.size()/k;
        for (int i=0;i<rua;++i){
            for (int j=0;j<k;++j){
                if (mmp[cur+j]<=0) return false;
                --mmp[cur+j];
            }
            cur=0x3f3f3f3f;
            for (auto &i:mmp){
                if (i.second>0) cur=min(cur,i.first);
            }
        }
        return true;
    }
};

第三题:子串的最大出现次数

贪心,因为只要返回任意一个符合要求的字串。我们知道,如果一个长度为 xx ( xminSizex \ge minSize )的子串符合要求,那么这个子串的长度为 minSizeminSize 的子串也全部符合要求,并且这样的子串出现次数只可能更多不可能更少。因此, maxSizemaxSize 除了用来判断 minSizemaxSizeminSize \leq maxSize 以外没有任何作用。
然后就剩下暴力了, O(n)O\left(n\right) 扫一下整个字符串长度为 minSizeminSize 的子串,同时维护当前26个字符出现的次数即可。需要一点实现技巧。

class Solution {
public:
    int maxFreq(string s, int x, int len, int maxSize) {
        if (len>maxSize) return 0;
        int n=s.length();
        map<string,int> mmp;
        map<char,int> cur;
        for (int i=0;i<len;++i){
            cur[s[i]]++;
        }
        if (cur.size()<=x){
            mmp[s.substr(0,len)]++;
        }
        for (int i=0;i+len<n;++i){
            if (cur[s[i]]==1) cur.erase(s[i]);
            else --cur[s[i]];
            ++cur[s[i+len]];
            if (cur.size()<=x) ++mmp[s.substr(i+1,len)];
        }
        int ans=0;
        for (auto &i:mmp){
            ans=max(ans,i.second);
        }
        return ans;
    }
};

第四题:你能从盒子里获得的最大糖果数

模拟。首先需要想明白的是,由于所有的状态都是给定的(比如不存在需要决策钥匙开哪个盒子因为钥匙只能开对应的盒子,也不存在箱子中糖果个数为负的的情况),答案其实是唯一的。

开一些数据结构:

  • 开一个数组(vector)记录箱子是否被拥有;
  • 开一个数组(vector)记录箱子是否已经被使用了;
  • 开一个队列(queue)记录当前待检查的箱子(检查其中新的箱子,糖果和钥匙)

然后每次取一个检查队列中的箱子进行检查:

  • 拿到箱子就立刻标记箱子被拥有
  • 拿到钥匙就立刻把对应锁着的箱子解锁
  • 将拥有的,解锁的,未被使用的箱子加入队列准备新一轮的检查

以此往复将将所有能打开的箱子全部打开,得到的糖果必然是最多的。

class Solution {
public:
    int maxCandies(vector<int>& open, vector<int>& x, vector<vector<int>>& keys,
                   vector<vector<int>>& boxes, vector<int>& initBoxes) {
        queue<int> que;
        bool vis[1010];
        bool has[1010];
        memset(vis,false,sizeof(vis));
        memset(has,false,sizeof(has));
        for (auto&i:initBoxes){
            if (open[i]==1){
                vis[i]=true;
                que.push(i);
            }
            else{
                has[i]=true;
            }
        }
        int ans=0;
        while (!que.empty()){
            int cur=que.front();que.pop();
            ans+=x[cur];
            for (auto&i:boxes[cur]){
                has[i]=true;
                if (has[i]&&open[i]&&!vis[i]){
                    vis[i]=true;
                    que.push(i);
                }
            }
            for (auto&i:keys[cur]){
                open[i]=1;
                if (open[i]&&has[i]&&!vis[i]){
                    vis[i]=true;
                    que.push(i);
                }
            }
        }
        return ans;
    }
};

题外话:
题目给的样例都是这样的,简直反人类好不好!!比如第四题

输入:status = [1,1,1], candies = [2,3,2], keys = [[],[],[]], containedBoxes = [[],[],[]], initialBoxes = [2,1,0]
输出:7

既然有这么长的样例,为什么不直接给可以复制使用的格式

[1,1,1]
[2,3,2]
[[],[],[]]
[[],[],[]]
[2,1,0]

要是C++玩家能得到{}而非[]就更好了,这样就可以直接初始化vector了

{1,1,1}
{2,3,2}
{{},{},{}}
{{},{},{}}
{2,1,0}

或者自定义输入的时候能选择题目样例也很棒啊……(逃

填入样例1
填入样例2
填入样例3

翻车了,这次前五十都没进……丢人

7
展开全部 16 讨论