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

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

image.png

3 分 - 找出数组中的幸运数
4 分 - 统计作战单位数
5 分 - 设计地铁系统
8 分 - 找到所有好字符串

展开讨论
共 31 个讨论

题解
T1、T2都没啥好说的,暴力就行了
T1

class Solution(object):
    def findLucky(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        d = dict()
        for v in arr:
            d[v] = 0
        for v in arr:
            d[v] += 1
        ans = -1
        for v in arr:
            if d[v] == v and v > ans:
                ans = v
        return ans

T2

class Solution {
public:
    int numTeams(vector<int>& rating) {
        int n = rating.size();
        int ans = 0;
        for (int i = 0; i < n; ++i)
            for (int j = i+1; j < n; ++j)
                for (int k = j+1; k < n; ++k) {
                    if (rating[i] < rating[j] && rating[j] < rating[k])
                        ans += 1;
                    if (rating[i] > rating[j] && rating[j] > rating[k])
                        ans += 1;
                }
        return ans;
    }
};

不过T2如果数据量大,就变成白书上一道题了,那个时候就是枚举中间的数,然后树状数组/线段树/balabala统计左边比它大的和右边比它小的数的个数,然后把这个个数相乘,最后所有结果求和就是最终答案,复杂度是O(nlogn)。这个题200^3=800w很多小伙伴以为会超时,这里我大概给大家一个超时的感觉。
其实超时有两方面因素,一个是算法本身的复杂度,另一个是算法的常数,比如一个复杂度O(n^2)的算法,n=10,但每次都要通过各种if枚举各种情况,一次运算数有100,总的运算数就是100100=10000,而同样的O(n^3)的算法,情况很简单,每次运算数只有3,总的运算数就是10003=3000,这时候小数据反而O(n^3)比较快。
对于1s的时限,可以接受的计算次数大概在2~3千万左右,当然由于常数问题,所以一般认为1kw以下的运算是肯定能完成的,也就是说200^3=800w肯定没有压力,而300^3=2700w,如果每次只有一两个加法和乘法,那么理论上暴力也有过的可能。

以上的分析针对c++,对于python,由于它for循环的机制不同,因此速度比c++慢得多,所以大家如果要用for循环暴力,千万不要用python来写!!!

T3题我直接用dict来记录,对于这种字符串作为下标的,python的dict用起来还是很方便的,当然c++的map应该也能升任

class UndergroundSystem(object):

    def __init__(self):
        self.passenger = dict()
        self.dist = dict()
        self.cnt = dict()

    def checkIn(self, id, stationName, t):
        """
        :type id: int
        :type stationName: str
        :type t: int
        :rtype: None
        """
        self.passenger[id] = [stationName, t]


    def checkOut(self, id, stationName, t):
        """
        :type id: int
        :type stationName: str
        :type t: int
        :rtype: None
        """
        preName, st = self.passenger[id]
        if not (preName, stationName) in self.dist:
            self.dist[(preName, stationName)] = 0
            self.cnt[(preName, stationName)] = 0
        
        self.dist[(preName, stationName)] += t - st
        self.cnt[(preName, stationName)] += 1

    def getAverageTime(self, startStation, endStation):
        """
        :type startStation: str
        :type endStation: str
        :rtype: float
        """
        return 1.0 * self.dist[(startStation, endStation)] / self.cnt[(startStation, endStation)]

今天的T4想必难到了很多coder,因为这是一道比较综合的题,需要用到kmp和数位dp的知识,特别是数位dp,还要分情况讨论。但如果把情况整合得比较好一点,写起来思路还是挺清晰的。

定义状态为f[i][j][lb][ub]
i: 字符串选到第i位
j: evil匹配到第j位
lb: lowerbound, 表示选第i位字符时,前面的字符是否都和s1选得一样,取值0/1
ub:upperbound,表示选第i位字符时,前面的字符是否都和s2选得一样,取值0/1

举例来说,对于下面的例子
s1 = 'leet'
s2 = 'lgkt'

对于第一位,显然只能取到l,这时候上下界都顶到,lb=1,ub=1
对于第二位,由于前一位的lb=1,所以这一位最小只能取'e',由于前一位ub=1,这一位最大只能取'g'
当第二位取e时,lb=1,ub=0
当第二位取f时,lb=0,ub=0
当第二位取g时,lb=0,ub=1
从而,对于第三位
如果第二位是lb=1,ub=0,则可取的范围是s1[i]/'e'..'z'
如果第二位是lb=0,ub=0,则可取的范围是'a'..'z'
如果第二位是lb=0,ub=1,则可取范围是是'a'..s2[i]/'k'

而kmp则可以帮助压缩存储,因为j对应的值就隐含了之前的字符的情况,不用单独把所有的结果记下来。
详细看代码吧

class Solution {
public:
    int findGoodStrings(int n, string s1, string s2, string evil) {
        int m = evil.length();
        int nxt[m];
        memset(nxt, 0, sizeof(nxt));
        int idx = 0, i = 1;
        //kmp得到evil的nxt数组
        while (i < m) {
            if (evil[i] == evil[idx]) {
                nxt[i] = idx+1;
                idx += 1;
                i += 1;
            }
            else if (idx != 0) {
                idx = nxt[idx-1];
            }
            else {
                nxt[i] = 0;
                i += 1;
            }
        }
        
        int f[n+1][m][2][2];
        memset(f, 0, sizeof(f));
        
        f[0][0][1][1] = 1;
        
        int mo = 1000000007;
        
        //i表示主字符串枚举到第i位,j表示evil匹配到第j位,lb,ub分别表示s在之前是否紧贴了s1/s2
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                for (int lb = 0; lb <= 1; ++lb)
                    for (int ub = 0; ub <= 1; ++ub)
                        if (f[i][j][lb][ub] != 0) {
                            //如果之前都紧贴,那么主字符串第i位可以的取值范围是s1[i] .. s2[i]
                            if (lb != 0 and ub != 0) {
                                for (char ch = s1[i]; ch <= s2[i]; ++ch) {
                                    int nlb = 0, nub = 0;
                                    if (ch == s1[i]) //是否贴了下界
                                        nlb = 1;
                                    if (ch == s2[i]) //是否贴了上界
                                        nub = 1;
                                    int k = j; //看新字符串对应与k能匹配到哪一位
                                    while (k != 0 and ch != evil[k])
                                        k = nxt[k-1];
                                    if (ch == evil[k])
                                        k = k + 1;
                                    if (k == m) //如果与evil完全匹配上了,则不能放进最终答案
                                        continue;
                                    f[i+1][k][nlb][nub] = (f[i+1][k][nlb][nub] + f[i][j][lb][ub]) % mo;
                                }
                            }
                            //如果两边都没有紧贴,那么这一位的范围就是'a' .. 'z'
                            else if (lb == 0 and ub == 0) {
                                for (char ch = 'a'; ch <= 'z'; ++ch) {
                                    int nlb = 0, nub = 0; //之前没有紧贴,后面的一定也不会紧贴
                                    int k = j;
                                    while (k != 0 and ch != evil[k])
                                        k = nxt[k-1];
                                    if (ch == evil[k])
                                        k = k + 1;
                                    if (k == m)
                                        continue;
                                    f[i+1][k][nlb][nub] = (f[i+1][k][nlb][nub] + f[i][j][lb][ub]) % mo;
                                }
                            }
                            // 紧贴s1
                            else if (lb == 1) {
                                for (char ch = s1[i]; ch <= 'z'; ++ch) {
                                    int nlb = 0, nub = 0;
                                    if (s1[i] == ch)
                                        nlb = 1;
                                    int k = j;
                                    while (k != 0 and ch != evil[k])
                                        k = nxt[k-1];
                                    if (ch == evil[k])
                                        k = k + 1;
                                    if (k == m)
                                        continue;
                                    f[i+1][k][nlb][nub] = (f[i+1][k][nlb][nub] + f[i][j][lb][ub]) % mo;
                                }
                            }
                            // 紧贴s2
                            else if (ub == 1) {
                                for (char ch = 'a'; ch <= s2[i]; ++ch) {
                                    int nlb = 0, nub = 0;
                                    if (s2[i] == ch)
                                        nub = 1;
                                    int k = j;
                                    while (k != 0 and ch != evil[k])
                                        k = nxt[k-1];
                                    if (ch == evil[k])
                                        k = k + 1;
                                    if (k == m)
                                        continue;
                                    f[i+1][k][nlb][nub] = (f[i+1][k][nlb][nub] + f[i][j][lb][ub]) % mo;
                                }
                            }
                        }
        //最终答案统计
        int ans = 0;
        for (int j = 0; j < m; ++j)
            for (int lb = 0; lb <= 1; ++lb)
                for (int ub = 0; ub <= 1; ++ub)
                    ans = (ans + f[n][j][lb][ub]) % mo;
        
        return ans;
    }
};

其实细心的话可以看到,我代码中在讨论不同情况时,唯一的差别只有for循环的范围,以及nlb和nub情况的讨论,状态转移的代码都是一样的,可以直接copy

int k = j;
while (k != 0 and ch != evil[k])
    k = nxt[k-1];
if (ch == evil[k])
    k = k + 1;
if (k == m)
    continue;
f[i+1][k][nlb][nub] = (f[i+1][k][nlb][nub] + f[i][j][lb][ub]) % mo;

刚看了一眼前几名大佬的写法,是数位dp更常用的写法,需要讨论的情况要少一些。大致就是定义f(s),表示所有字典序小于等于s的字符串中,不包含evil的有多少个,最终的答案就是f(s2)-f(s1-1)(-1指s1的前一个),这样的话就只用讨论一个上界,不用像我一样要讨论两个界,而且大佬们的代码也简洁得多(还差好远qaq)

21

看到半小时后的现在第四题排行榜上都没人做出来,我就知道这不是我能做的了

10

第三题不返回一位小数就是错的吗?

4

连续几周了,
都是稳定前3选手........
对,就是只做出前3题的选手..........

第4题,感觉就像以前数学卷的最后一题一般........有思路,写不完......如果在早上刚起床的时候做,可能可以..

3

第四题想了半个多小时。。。一点思路都没, 看下排名, 只有 18 个人做出来了。。 我选择等题解。。。

2

很郁闷,答案都对了,就是小数点不对,哪位大佬解释一下?double的返回值是五个小数点,但是答案只有一个,怎么解决啊。

class UndergroundSystem {
public:
    UndergroundSystem() {
        
    }
    map<string, vector<int>> mp;
    map<int, int> startt;
    map<int, int> endt;
    void checkIn(int id, string stationName, int t) {
        mp[stationName].push_back(id);
        startt[id] = t;
    }
    
    void checkOut(int id, string stationName, int t) {
        mp[stationName].push_back(id);
        endt[id] = t;
    }
    
    double getAverageTime(string startStation, string endStation) {
        vector<int> mem;
        for(int i = 0; i < mp[startStation].size(); i++){
            for(int j = 0; j < mp[endStation].size(); j++){
                if(mp[startStation][i] == mp[endStation][j]) mem.push_back(mp[startStation][i]);
            }
        }
        int tot = 0;
        for(int i = 0; i < mem.size(); i++){
            tot += endt[mem[i]] - startt[mem[i]];
        }
        int ans = tot/mem.size();
        return ans;
    }
};

T2,有点排列组合的感觉,代码还是不够简洁。

class Solution {
public:
    int numTeams(vector<int>& rating) {
        int n = rating.size();
        int kase = 0;
        for(int j = 1; j < n-1; j++){
            int lower = 0, upper = 0;
            for(int i = j-1; i >=0; i--){
                if(rating[i] < rating[j]) lower++;
            }
            for(int k = j+1; k < n; k++){
                if(rating[j] < rating[k]) upper++;
            }
            int s = lower * upper;
            kase += s;
        }
        for(int j = 1; j < n-1; j++){
            int lower = 0, upper = 0;
            for(int i = j-1; i >=0; i--){
                if(rating[i] > rating[j]) lower++;
            }
            for(int k = j+1; k < n; k++){
                if(rating[j] > rating[k]) upper++;
            }
            int s = lower * upper;
            kase += s;
        }
        return kase;
    }
};
2

三四题超时不会做。。等题解。。

1

第三次参赛,还是做出了前三道,,,第四道暴力求解超时了

1

T4 数位dp

代码写的有点乱……

class Solution {
    int n = 0, m = 0;
    string evil;
    using ll = long long;
    const ll mod = 1e9 + 7;
public:
    ll dp[505][30][56];

    void kmp_init(int n, vector<int>&pi, const string&a)
    {
        pi = vector<int>(a.size(), 0);
        for (int i = 1; i < n; ++i)
        {
            int j = pi[i - 1];
            while (j > 0 && a[i] != a[j])
            {
                j = pi[j - 1];
            }
            if (a[i] == a[j]) j++;
            pi[i] = j;
        }
    }
    vector<int> p;
    ll dfs(int cur, int st, int front, bool op, const string&s)
    {
        if (front == m)return 0;
        if (cur >= n) return 1;
        if (!op && ~dp[cur][st][front]) return dp[cur][st][front];
        int mx = op ? s[cur] - 'a' : 25;
        ll res = 0;
        for (int i = 0; i <= mx; ++i)
        {
            if (i == evil[front] - 'a')
            {
                res += dfs(cur + 1, i, front + 1, op&& i == mx, s);
            }
            else
            {
                int tf = 0;
                if (front > 0)
                {
                    int j = p[front - 1];
                    while (j > 0 && evil[j] - 'a' != i)
                    {
                        j = p[j - 1];
                    }
                    if (evil[j] - 'a' == i) j++;
                    tf = j;
                }
                else
                {
                    tf = i == evil[0] - 'a';
                }
                res += dfs(cur + 1, i, tf, op&& i == mx, s);
            }
            res %= mod;
        }
        res %= mod;
        if (!op) dp[cur][st][front] = res;
        return res;
    }
    int findGoodStrings(int n, string s1, string s2, string evil) {
        if (s1 > s2) return 0;
        this->evil = evil;
        this->n = n;
        m = evil.size();
        kmp_init(m, p, evil);
        memset(dp, -1, sizeof(dp));
        ll res = dfs(0, 26, 0, 1, s1);
        memset(dp, -1, sizeof(dp));
        res = dfs(0, 26, 0, 1, s2) - res;
        int flag = 1;
        for (int i = 0; i + m <= n; ++i)
        {
            if (s1[i] == evil[0] && s1.substr(i, m) == evil)
            {
                flag = 0; break;
            }
        }
        return (res + mod + flag) % mod;
    }
};
1

第三道题看了好久没看明白啊,,,