讨论/技术交流/🏆 第 237 场力扣周赛/
🏆 第 237 场力扣周赛

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

image.png

3 分 - 判断句子是否为全字母句
4 分 - 雪糕的最大数量
5 分 - 单线程 CPU
6 分 - 所有数对按位与结果的异或和

4
共 90 个回复

终于可以自己写一次周赛题解啦!求点赞~

第一题 判断句子是否为全字母句

遍历字符串加入集合,统计集合大小即可

class Solution {
    public boolean checkIfPangram(String sentence) {
        Set<Character> set = new HashSet<>();
        for(char c:sentence.toCharArray()){
            set.add(c);
        }
        return set.size()==26;
    }
}

时间O(n)O(n),空间O(1)O(1)。

第二题 雪糕的最大数量

对价格排序,贪心取最便宜的雪糕即可

class Solution {
    public int maxIceCream(int[] costs, int coins) {
        Arrays.sort(costs);
        int ret = 0;
        for (int i = 0; i < costs.length; i++) {
            if(costs[i]>coins){
                break;
            }
            coins -= costs[i];
            ret++;
        }
        return ret;
    }
}

时间O(nlog(n))O(nlog(n)),空间O(log(n))O(log(n))(排序使用的额外栈空间)。

第三题 单线程CPU

  1. 创建一个新的二维数组,在保留题目提供的tasks数据的基础上,再把下标存进去;
  2. 把tasks按任务起始时间排序;
  3. 建小顶堆,堆顶元素是时长最小的任务,时长相同的按下标排序;
  4. 初始化当前时间now = 1,遍历tasks中的任务,当堆空或者now>=tasks[i][0](即任务开始时间)时,将任务加入堆中,之后再弹出堆顶元素,根据弹出的新任务需要执行的时间来更新当前时刻now
  5. 重复4直道所有任务都被遍历
  6. 依次弹出堆中所有元素
class Solution {
    public int[] getOrder(int[][] oldTask) {
        int n = oldTask.length;
        int[][] tasks = new int[n][3];
        for (int i = 0; i < oldTask.length; i++) {
            tasks[i][0] = oldTask[i][0];
            tasks[i][1] = oldTask[i][1];
            tasks[i][2] = i;
        }

        Arrays.sort(tasks, (x,y)->x[0]-y[0]);
        PriorityQueue<Integer> heap = new PriorityQueue<>((x,y)->{
            if(tasks[x][1]==tasks[y][1]){
                return tasks[x][2]-tasks[y][2];
            }
            return tasks[x][1]-tasks[y][1];
        });
        int now = 1;
        int[] ret = new int[n];
        int i = 0;
        int j = 0;
        while(i<n){
            while(i<n&&(heap.isEmpty()||now>=tasks[i][0])){
                now = Math.max(now,tasks[i][0]);
                heap.add(i++);
            }
            int[]task = tasks[heap.poll()];
            ret[j++] = task[2];
            now += task[1];
        }
        while(!heap.isEmpty()){
            ret[j++] = tasks[heap.poll()][2];
        }
        return ret;
    }
}

时间O(nlog(n))O(nlog(n)),空间O(n)O(n)。

第四题 所有数对按位与结果的异或和

从arr1中任取元素aa,从arr2中任取元素b1,b2b_1,b_2,则:

(a&b1)⊕(a&b2)=[(¬a∣¬b1)&(a∣b2)]∣[(¬a∣¬b2)&(a∣b1)]=(¬b1&a&b2)∣(¬b2&a&b1)=a&((¬b1&b2)∣(¬b2&b1))=a&(b1⊕b2)\begin{aligned} (a\&b_1)\oplus(a\&b_2) &= [(\lnot a | \lnot b_1) \& (a | b_2)] | [(\lnot a | \lnot b_2) \& (a | b_1)] \\ &= (\lnot b_1 \& a \& b_2)|(\lnot b_2 \& a \& b1) \\ &= a \& ((\lnot b_1 \& b_2) | (\lnot b_2 \& b1)) \\ &= a \& (b_1 \oplus b_2) \end{aligned}

所以有:

(a&b1)⊕(a&b2)⊕...⊕(a&bm)=a&(b1⊕b2⊕...⊕bm)(a \& b_1) \oplus (a \& b_2) \oplus ... \oplus(a \& b_m) = a \& (b_1 \oplus b_2 \oplus ...\oplus b_m)

那么题目所求的异或和为:

(a1&b1)⊕(a1&b2)⊕...⊕(a1&bm)⊕...⊕(an&bm)=[(a1&b1)⊕(a1&b2)⊕...⊕(a1&bm)]⊕...⊕[(an&b1)⊕(an&b2)⊕...⊕(an&bm)]=[a1&(b1⊕...⊕bm)]⊕[a2&(b1⊕...⊕bm)]⊕...⊕[an&(b1⊕...⊕bm)]\begin{aligned} &(a_1\&b_1)\oplus(a_1\&b_2) \oplus...\oplus(a_1\&b_m)\oplus...\oplus(a_n\&b_m) \\ &= [(a_1\&b_1)\oplus(a_1\&b_2)\oplus...\oplus(a_1\&b_m)]\oplus...\oplus[(a_n\&b_1)\oplus(a_n\&b_2)\oplus...\oplus(a_n\&b_m)] \\ &= [a_1 \& (b_1 \oplus ... \oplus b_m)] \oplus [a_2 \& (b_1 \oplus ... \oplus b_m)] \oplus...\oplus [a_n \& (b_1 \oplus ... \oplus b_m)] \end{aligned}

所以,只需要先求出(b1⊕...⊕bm)(b_1 \oplus ... \oplus b_m),再依次计算[ai&(b1⊕...⊕bm)][a_i \& (b_1 \oplus ... \oplus b_m)](1<=i<=n)即可。代码如下:

class Solution {
    public int getXORSum(int[] arr1, int[] arr2) {
        int sum2 = 0;
        int ret = 0;
        for (int i : arr2) {
            sum2^=i;
        }
        for(int i:arr1){
            ret ^= (i&sum2);
        }
        return ret;
    }
}

时间O(n)O(n),空间O(1)O(1)。

32

Leetcode 第237场周赛题解

Problem A - 判断句子是否为全字母句

去重后看个数是否为26即可。

  • 时间复杂度O(N)\mathcal{O}(N)。
  • 空间复杂度O(N)\mathcal{O}(N)。
class Solution:
    def checkIfPangram(self, sentence: str) -> bool:
        return len(set(list(sentence))) == 26

Problem B - 雪糕的最大数量

排序后贪心即可。

  • 时间复杂度O(N)\mathcal{O}(N)。
  • 空间复杂度O(1)\mathcal{O}(1)。
class Solution:
    def maxIceCream(self, costs: List[int], coins: int) -> int:
        costs.sort()
        ans = 0
        for cost in costs:
            if coins < cost:
                return ans
            coins -= cost
            ans += 1
        return ans

Problem C - 单线程 CPU

读清题意后按要求模拟即可。把所有任务按开始时间排序,同时用优先队列维护当前待执行的任务。

  • 如果下一个任务的开始时间的小于当前CPU时间,且队列非空,则逐个执行队列中的任务,直到当前时间超过下一个任务的开始时间或CPU空闲。
  • 此时,或者当前CPU时间已经超过下一个任务的开始时间;或者下一个任务前的所有任务都已执行完毕。无论何种情况,我们都应该将下一个时间点开始的所有任务加入优先队列中。

复杂度:

  • 时间复杂度O(Nlog⁡N)\mathcal{O}(N\log N)。
  • 空间复杂度O(N)\mathcal{O}(N)。
class Solution {
public:
    vector<int> getOrder(vector<vector<int>>& tasks) {
        vector<int> ans;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        map<int, vector<int>> mp;
        int n = tasks.size();
        for (int i = 0; i < n; ++i)
            mp[tasks[i][0]].emplace_back(i);
        int now = 0;
        
        for (auto [t, v] : mp) {
            while (now < t && !pq.empty()) {
                auto [duration, idx] = pq.top();
                pq.pop();
                ans.emplace_back(idx);
                now += duration;
            }
            now = max(now, t);
            for (int i : v) 
                pq.emplace(tasks[i][1], i);
        }
        
        while (!pq.empty()) {
            ans.emplace_back(pq.top().second);
            pq.pop();
        }
        
        return ans;
    }
};

Problem D - 所有数对按位与结果的异或和

方法一:逐位处理

我们可以逐位计算结果,而不会影响最终的答案。因此,我们可以把两个数组都视为0-1数组(就每一位而言)。

显然,这一位在最终结果中为0还是为1,取决于有多少个1-1对。如果1-1对的数目为奇数,结果中为1,否则为0。

  • 时间复杂度O((N+M)W)\mathcal{O}((N+M)W)。
  • 空间复杂度O(1)\mathcal{O}(1)。
class Solution {
public:
    int getXORSum(vector<int>& arr1, vector<int>& arr2) {
        int ans = 0;
        for (int i = 0; i < 31; ++i) {
            int msk = 1 << i, c1 = 0, c2 = 0;
            for (int num : arr1)
                if (num & msk)
                    c1++;
            for (int num : arr2)
                if (num & msk)
                    c2++;
            if (1LL * c1 * c2 % 2 == 1)
                ans ^= msk;
        }
        return ans;
    }
};

方法二:利用分配律

我们可以利用xor和and之间的分配律:

(a xor b) and c = (a and c) xor (b and c)

来简化求解。

原式最终可以被化简为:

(a_1 xor a_2 xor … xor a_n) and (b_1 xor b_2 xor … xor b_m)

从而容易求得。

  • 时间复杂度O(N+M)\mathcal{O}(N+M)。
  • 空间复杂度O(1)\mathcal{O}(1)。
class Solution {
public:
    int getXORSum(vector<int>& arr1, vector<int>& arr2) {
        int a1 = 0, a2 = 0;
        for (int num : arr1)
            a1 ^= num;
        for (int num : arr2)
            a2 ^= num;
        return a1 & a2;
    }
};
20
该内容已被删除

温饭斩周赛!

10

绝了,第四题看那么多人做出来,就一直在那推。没学过异或的我半天推不出来,最后不管了,直接找规律,没想到AC了。。。纪念我的第一次AK!!!

5

为何两周直接取消rated?每场比赛如果unrated怎么不提前说一声呢?(对我这个分奴太不友好了。

5

练了这么久的金山打字通终于派上用场了。

4

虽然不会第4题,但我看很多人完成了,于是断定第4题的逻辑很简单,通过蒙和凑的方式过了……
image.png

4

手:第4题我就先秒了。
脑子:等等我!

4

实况录像:Bilibili

3

第 237 场周赛

题目1:判断句子是否为全字母句

思路:模拟

  • 哈希表记录每个字母出现次数,然后26个字母判断一遍即可

代码:

class Solution {
public:
    bool checkIfPangram(string s) {
        map<int, int> mp;
        for(char c : s) mp[c - 'a']++;
        for(int i = 0; i < 26; i++) {
            if(!mp[i]) return false;
        }
        return true;
    }
};

复杂度分析:

  • 时间复杂度为 O(n)O(n),遍历了整个字符串
  • 空间复杂度为 O(n)O(n),利用了哈希表

题目2:雪糕的最大数量

思路:贪心

  • 排序数组,贪心购买

代码:

public:
    int maxIceCream(vector<int>& a, int c) {
        sort(a.begin(), a.end());
        int ret = 0;
        for(int x : a) {
            if(c < x) break;
            c -= x;
            ret++;
        }
        return ret;
    }
};

复杂度分析:

  • 时间复杂度为 O(nlgn)O(nlgn),对数组进行了排序。之后的遍历只需要最大 O(n)O(n) 的复杂度
  • 空间复杂度为 O(1)O(1)。

题目3:单线程 CPU

思路:模拟

  • 由于总时长可能达到 10910^9,所以需要按任务进行遍历。
  • 维护两个优先队列,第一个队列优先按任务开始时间排序,第二个队列优先按执行时间排序。每次将第一个队列中,满足开始时间早于或等于当前时间 curcur 的任务全部放入第二个队列。然后从第二个队列中选出执行时间最优的执行,更新当前时间即可。
  • 特别地,如果所有任务的开始时间都晚于当前时间,则需要挑出最早开始的任务执行。

代码:

class Solution {
    using ll = long long;
public:
    vector<int> getOrder(vector<vector<int>>& t) {
        int n = t.size();
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        for(int i = 0; i < n; i++) {
            q.push({t[i][0], t[i][1], i});
        }
        ll cur = 0;
        vector<int> ret;
        while(n--) {
            while(!q.empty()) {
                auto [begin, time, index] = q.top();
                if(begin <= cur) {
                    q.pop();
                    pq.push({time, index});
                } else {
                    break;
                }
            }
            if(pq.empty()) {
                auto [begin, time, index] = q.top();
                q.pop();
                pq.push({time, index});
                cur += begin;
            }
            auto [time, index] = pq.top();
            pq.pop();
            ret.push_back(index);
            cur += time;
        }
        return ret;
    }
};

复杂度分析:

  • 时间复杂度为 O(nlgn)O(nlgn),优先队列维护全部任务,每次挑出一个任务执行均摊复杂度为 O(1)O(1)
  • 空间复杂度为 O(n)O(n),维护了优先队列。

题目4:所有数对按位与结果的异或和

思路:模拟

  • 两个位运算满足分配率

代码:

class Solution {
    using ll = long long;
public:
    int getXORSum(vector<int>& a, vector<int>& b) {
        ll r1 = 0, r2 = 0;
        for(int x : a) r1 ^= x;
        for(int x : b) r2 ^= x;
        return r1 & r2;
    }
};

复杂度分析:

  • 时间复杂度为 O(n)O(n)
  • 空间复杂度为 O(1)O(1)

关注GTAlgorithm,专注周赛、面经题解分享,陪大家一起攻克算法难关~

算法干货汇总

腾讯客户端一面面经(附答案)

第 234 场周赛 题解

4