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

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

image.png

3 分 - 数组元素积的符号
4 分 - 找出游戏的获胜者
5 分 - 最少侧跳次数
6 分 - 求出 MK 平均值


声明: 本场竞赛不计入 Rating。

7
共 62 个回复

Leetcode 第236场周赛题解

Problem A - 数组元素积的符号

如果有零,显然结果为零;如果没有零,就看负数是奇数个还是偶数个。

  • 时间复杂度O(N)\mathcal{O}(N)
  • 空间复杂度O(1)\mathcal{O}(1)
class Solution {
public:
    int arraySign(vector<int>& nums) {
        bool neg = false;
        for (int num : nums) {
            if (num == 0)
                return 0;
            if (num < 0)
                neg = !neg;
        }
        return neg ? -1 : 1;
    }
};

Problem B - 找出游戏的获胜者

经典约瑟夫问题。数学方法倒推求解。

  • 时间复杂度O(N)\mathcal{O}(N)
  • 空间复杂度O(1)\mathcal{O}(1)
class Solution {
public:
    int findTheWinner(int n, int k) {
        int p = 0;
        for (int i = 2; i <= n; ++i)
            p = (p + k) % i;
        return p + 1;
    }
};

Problem C - 最少侧跳次数

比较简单的动态规划。只需要维护上一列三行的最小侧跳次数即可。

  • 时间复杂度O(C2N)\mathcal{O}(C^2N)
  • 空间复杂度O(C)\mathcal{O}(C)
const int inf = 1e9;

class Solution {
public:
    int minSideJumps(vector<int>& obstacles) {
        int n = obstacles.size() - 1;
        vector<int> dp(4, inf);
        dp[2] = 0;
        dp[1] = dp[3] = 1;
        for (int i = 1; i < n; ++i) {
            vector<int> ndp(4, inf);
            for (int k = 1; k <= 3; ++k) {
                if (dp[k] == -1 || obstacles[i] == k)
                    continue;
                ndp[k] = min(ndp[k], dp[k]);
                for (int j = 1; j <= 3; ++j) {
                    if (obstacles[i] != j)
                        ndp[j] = min(ndp[j], dp[k] + 1);
                }
            }
            dp = move(ndp);
        }
        return *min_element(dp.begin(), dp.end());
    }
};

Problem D - 求出 MK 平均值

方法一:set

  • small存放最小的不超过KK个数,small_candidates存放剩余的未过期的数。
  • large存放最大的不超过KK个数,large_candidates存放剩余的未过期的数。

addElement时:

  • 如果当前元素超过MM个,先进行过期操作,将过期的元素从四个set中删去。
  • 如果当前元素可以放入small中(比small_candidates最小的元素小),将其放入。
  • 如果当前元素可以放入large中(比large_candidates最大的元素大),将其放入。
  • 如果smalllarge元素个数超过了KK个,进行维护。
  • 整个过程中,需要同时维护small_sumlarge_sum

calculateMKAverage时:

  • 如果当前元素不足MM个,返回1-1
  • 否则,先将smalllarge补充至KK个元素,同时维护small_sumlarge_sum
  • 计算平均值。

复杂度:

  • addElement时间复杂度O(logM)\mathcal{O}(\log M)
  • calculateMKAverage的均摊时间复杂度为O(logM)\mathcal{O}(\log M)
  • 空间复杂度O(N)\mathcal{O}(N)

解释:

  • calculateMKAverage中的补充元素操作仅会发生在有元素过期时。因为每个元素最多过期一次,所以补充元素操作的次数上限即为过期元素的数目。
class MKAverage {
    int m, k, cnt;
    vector<int> mem;
    double sum, large_sum, small_sum;
    set<pair<int, int>> small, large, small_candidates, large_candidates;
public:
    MKAverage(int m, int k): m(m), k(k), cnt(0), sum(0), large_sum(0), small_sum(0) {}
    
    void addElement(int num) {
        if (cnt >= m) {
            pair<int, int> p = {mem[cnt - m], cnt - m};
            if (small.count(p))
                small.erase({mem[cnt - m], cnt - m}), small_sum -= p.first;
            small_candidates.erase({mem[cnt - m], cnt - m});
            if (large.count(p))
                large.erase({mem[cnt - m], cnt - m}), large_sum -= p.first;
            large_candidates.erase({mem[cnt - m], cnt - m});
            sum -= p.first;
        }
        sum += num;
        mem.emplace_back(num);
        if (small_candidates.empty() || num <= small_candidates.begin()->first) {
            small.emplace(num, cnt);
            small_sum += num;
        } else {
            small_candidates.emplace(num, cnt);
        }
        if (small.size() > k) {
            auto p = *small.rbegin();
            small.erase(p);
            small_sum -= p.first;
            small_candidates.insert(p);
        }
        
        if (large_candidates.empty() || num >= large_candidates.rbegin()->first) {
            large.emplace(num, cnt);
            large_sum += num;
        } else {
            large_candidates.emplace(num, cnt);
        }
        if (large.size() > k) {
            auto p = *large.begin();
            large.erase(p);
            large_sum -= p.first;
            large_candidates.insert(p);
        }
        cnt++;
    }
    
    int calculateMKAverage() {
        if (cnt < m)
            return -1;
        
        while (small.size() < k) {
            auto p = *small_candidates.begin();
            small_sum += p.first;
            small.insert(p);
            small_candidates.erase(p);
        }
        
        while (large.size() < k) {
            auto p = *large_candidates.rbegin();
            large_sum += p.first;
            large.insert(p);
            large_candidates.erase(p);
        }
        
        double ans = (sum - small_sum - large_sum) / (m - k * 2);
        
        return int(ans);
    }
};

方法二:自行实现平衡二叉树

我们可以自己实现任意一种平衡二叉树(Splay、AVL、红黑树……),同时在节点中额外存储:

  • 子树元素和
  • 子树元素个数

从而可以在平衡二叉树基本操作的基础上扩展出O(logN)\mathcal{O}(\log N)的求前KK大/小元素和的操作。

具体实现略。

25

记录第一次做完4道题

12

yysy,这次T4的暴力还是挺难卡的,感觉python的bisect的实现里面有优化,目前最好也只能卡到6s+。

不过用sort的就没有那么幸运了,随便构造一个极限数据就能卡掉。

bisect我猜想应该是对连续的插入操作有额外优化(类似lazy),需要每次插入后进行询问才能达到最坏复杂度,但是总共只能进行10^5个操作,所以如果每个插入都进行询问只能插入50000个数,同时询问只有当当前序列长度不小于m才有效,所以m不能设置太大,此时O(m)的插入卡着极限时间过了(大概6秒)。比较可能的方案大概是构造一个几次插入后进行一次询问的数据,来确保插入的数据足够多,但询问太少的话又容易被lazy掉。

目前还没找到合适的hack数据……卡到9s了但是还是不超时,不知道python时限究竟有多宽……

更新:搞定了,思路是把m设在50000,首先插入49999个数(随机)。
然后做25000次如下操作:先插入一个随机数,随后做一次询问。
这个测试数据能卡掉第二和第四名的代码,后面的懒得试了。sort实现的一样能卡掉,只要没有针对这个进行优化。

想实验的可以用下面的代码自行构造数据,去测试排行榜上别人的代码@LeetCode
@chen-hao-jing-7你的题解也会被卡掉,建议修改。

import json
import random
m = 50000
m0 = 99999
k = 1000

kk = 25000

opt = []
para = []

random.seed(0)

opt.append("MKAverage")
para.append([m, k])
for i in range(m - 1):
    opt.append('addElement')
    para.append([random.randint(1, m0)])
for i in range((m0 - m) // 2):
    for j in range(1):
        opt.append('addElement')
        para.append([random.randint(1, m0)])
    opt.append("calculateMKAverage")
    para.append([])

opt.append("calculateMKAverage")
para.append([])

print(json.dumps(opt))
print(json.dumps(para))

又及,感@lucifer1004的建议,增加random.seed(0)来固定seed为0。

4.16更新:我之前在github上给英文站提交了issue,也看到了类似的issue,现在英文站已经重新评测(比如原先的英文站第1名已经被判为不通过),但是似乎中国区的用户代码并没有rejudge,请问两边的rejudge是各自独立的吗@LeetCode

6

第三题贪心可以过。
下一个是障碍物的时候换跑道,分两种情况

  1. 换的两个跑道有一个此时有障碍物,只能换没有障碍物的跑道
  2. 两个跑道都没有障碍物。这时候换未来第一个障碍物最远的那个跑道,也就是尽可能拉长这次换道带来的距离
6

就我第三题还没做出来是吧(^▽^)

5

第一次全做完!!!!!
哈哈哈哈哈哈哈哈
必须记录一下

5726. 数组元素积的符号

思路:莽!

class Solution:
    def arraySign(self, nums: List[int]) -> int:
        ans = 1
        for i in nums:
            if i<0:
                ans *= -1
            elif i>0:
                ans *= 1
            else:
                return 0
        return ans

5727. 找出游戏的获胜者

思路:莽!模拟游戏过程即可。

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        A = [i+1 for i in range(n)]
        cur = 0
        while len(A)>1:
            n = len(A)
            cur = (cur+k-1)%n
            pick = A[cur]
            A.remove(pick)
        return A[0]

5728. 最少侧跳次数

思路:动态规划

  1. dp[i][j]:青蛙在第i点第j个赛道时,花费的最小侧跳数。最终答案便是min([dp[n-1][0], dp[n-1][1], dp[n-1][2]])
  2. 初始化一波:
    2.1. 起始位置:dp[0][1]=0, 一开始就侧跳:dp[0][0]=dp[0][2]=1
    2.2. 初始障碍物,dp[i][obstacles[i]-1] = n, 在这里用n表示无限大
  3. 递推关系:
    obstacles[i]-1==j时,表示当前位置是有障碍物的,则令当前位置侧跳数为无穷

dp[i][j]=ndp[i][j]=n

obstacles[i]-1==j时,当前位置要么从上一点的同赛道过来(不需要侧跳)、要么从上一点的其他赛道过来(需要一个侧跳,但从上一点的其他赛道侧跳到当前位置时,可能碰到障碍物,这时就要多跳一下,所以加入一个指示函数II来判断是不是需要多跳一下)。

dp[i][j]=mint(dp[i1][j],dp[i1][t]+1+I(dp[i][t]))dp[i][j] = \min_t(dp[i-1][j], dp[i-1][t]+1+I(dp[i][t]))

class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        n = len(obstacles)
        dp = [[0 for _ in range(3)] for _ in range(n)]
        dp[0][0], dp[0][2] = 1,1
        for i in range(n):
            if obstacles[i]!=0:
                dp[i][obstacles[i]-1] = n
        
        for i in range(1, n):
            for j in range(3):
                if obstacles[i]-1==j:
                    dp[i][j] = n
                else:
                    dp[i][j] = min([dp[i-1][j],dp[i-1][j-1]+1+(dp[i][j-1]>=n),dp[i-1][j-2]+1+(dp[i][j-2]>=n)])
        #print(dp)
        return min([dp[n-1][0], dp[n-1][1], dp[n-1][2]])

5729. 求出 MK 平均值

思路:维护两个数据结构:1.队列que 2. 有序数组 A

addElement函数

  1. 每次元素numnum过来,进队,若队列A长度超过M,则出队一次,记出队元素为ee
  2. 移除数组A中的元素ee
  3. 二分查找有序数组A中num的插入位置,然后插入

calculateMKAverage函数

  1. 当前元素小于M,return -1
  2. 如果 k*2 >= M, return 0
  3. 否则返回掐头去尾的中间数组和平均值:sum(self.A[self.K:-self.K]) // (self.M-self.K*2)
  4. 注意向下取整!
import bisect
from collections import deque
class MKAverage:

    def __init__(self, m: int, k: int):
        self.A = []
        self.que = deque()
        self.count = 0
        self.M,self.K=m,k

    def addElement(self, num: int) -> None:
        self.count+=1
        self.que.append(num)
        if self.count<=self.M:
            bisect.insort(self.A,num)
        else:
            rm_e = self.que.popleft()
            self.A.remove(rm_e)
            bisect.insort(self.A,num)
        

    def calculateMKAverage(self) -> int:
        if self.count<self.M:
            return -1
        if self.K*2>=self.M:
            return 0
        ans = sum(self.A[self.K:-self.K]) // (self.M-self.K*2)
        return ans
5

第四题,实在想不出来什么好办法,谁知道居然一个对列+排序(两分钟的事情)就通过了,白白浪费我大半个小时

4

它的测试用例没做好,正常来说应该O(logM)才能通过的。

3

写了半天第四题最大堆最小堆然后发现居然还有滑窗。。(理解错题意救不了)
最吐血的是赛后看别人答案,直接暴力bisect insort都能过,我真的是疯了。我看数据量就直接放弃了暴力的办法,结果数据尼玛这么水。学会了,以后周赛先暴力做一遍,超时再拉倒。
以及第三题想问下,贪心是不是应该是不能过的?感觉不行,但是没想到反例。

3

踩坑+1

2