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

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

image.png

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

展开讨论
力扣 (LeetCode)发起于 2020-03-29

题解
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
展开全部 31 讨论