On the shoulders of giants.

weekly-contest-182

找出数组中的幸运数

在整数数组中,如果一个整数的出现频次和它的数值大小相等,我们就称这个整数为「幸运数」。

给你一个整数数组 arr,请你从中找出并返回一个幸运数。

  • 如果数组中存在多个幸运数,只需返回 最大 的那个。
  • 如果数组中不含幸运数,则返回 -1

示例 1:

输入:arr = [2,2,3,4]
输出:2
解释:数组中唯一的幸运数是 2 ,因为数值 2 的出现频次也是 2 。

示例 2:

输入:arr = [1,2,2,3,3,3]
输出:3
解释:1、2 以及 3 都是幸运数,只需要返回其中最大的 3 。

示例 3:

输入:arr = [2,2,2,3,3]
输出:-1
解释:数组中不存在幸运数。

示例 4:

输入:arr = [5]
输出:-1

示例 5:

输入:arr = [7,7,7,7,7,7,7]
输出:7

提示:

  • 1 <= arr.length <= 500
  • 1 <= arr[i] <= 500
题解

直接记录次数,返回最大且符合题意的数。

时间复杂度:\(O(\log n + n)\)

class Solution {
public:
    int findLucky(vector<int>& arr) {
        int result = -1;
        map<int, int> h;
        for(auto x : arr) h[x]++;
        for(auto& x : h) {
            if(x.first != x.second) continue;
            result = max(result, (int)x.first);
        }
        return result;
    }
};

统计作战单位数

n 名士兵站成一排。每个士兵都有一个 独一无二 的评分 rating

3 个士兵可以组成一个作战单位,分组规则如下:

  • 从队伍中选出下标分别为 ijk 的 3 名士兵,他们的评分分别为 rating[i]rating[j]rating[k]
  • 作战单位需满足: rating[i] < rating[j] < rating[k] 或者 rating[i] > rating[j] > rating[k] ,其中  0 <= i < j < k < n

请你返回按上述条件可以组建的作战单位数量。每个士兵都可以是多个作战单位的一部分。

示例 1:

输入:rating = [2,5,3,4,1]
输出:3
解释:我们可以组建三个作战单位 (2,3,4)、(5,4,1)、(5,3,1) 。

示例 2:

输入:rating = [2,1,3]
输出:0
解释:根据题目条件,我们无法组建作战单位。

示例 3:

输入:rating = [1,2,3,4]
输出:4

提示:

  • n == rating.length
  • 1 <= n <= 200
  • 1 <= rating[i] <= 10^5
题解

树状数组求前缀和,经典题。

时间复杂度:\(O(n\log m)\)

const int N = 1E5 + 10, M = 2E2 + 10;
class Solution {
public:
    int tree[N], m, great[M], low[M];
    int lowbit(int x) { return x & (-x); }
    void add(int x, int d) {
        while(x <= m) tree[x] += d, x += lowbit(x);
    }
    int ask(int x) {
        int sum = 0;
        while(0 < x) sum += tree[x], x -= lowbit(x);
        return sum;
    }
    int numTeams(vector<int>& rating) {
        int result = 0, n = rating.size();
        for(auto x : rating) m = max(m, x);
        for(int i = 0; i < n; i++) {
            low[i] = ask(rating[i] - 1);
            great[i] = i - ask(rating[i]);
            add(rating[i], 1);
        }
        memset(tree, 0, sizeof(tree));
        for(int i = n - 1; 0 <= i; i--) {
            result += low[i] * (n - 1 - i - ask(rating[i]));
            result += great[i] * ask(rating[i] - 1);
            add(rating[i], 1);
        }
        return result;
    }
};

设计地铁系统

请你实现一个类 UndergroundSystem ,它支持以下 3 种方法:

1. checkIn(int id, string stationName, int t)

  • 编号为 id 的乘客在 t 时刻进入地铁站 stationName 。
  • 一个乘客在同一时间只能在一个地铁站进入或者离开。

2. checkOut(int id, string stationName, int t)

  • 编号为 id 的乘客在 t 时刻离开地铁站 stationName 。

3. getAverageTime(string startStation, string endStation) 

  • 返回从地铁站 startStation 到地铁站 endStation 的平均花费时间。
  • 平均时间计算的行程包括当前为止所有从 startStation 直接到达 endStation 的行程。
  • 调用 getAverageTime 时,询问的路线至少包含一趟行程。

你可以假设所有对 checkIn 和 checkOut 的调用都是符合逻辑的。也就是说,如果一个顾客在 t1 时刻到达某个地铁站,那么他离开的时间 t2 一定满足 t2 > t1 。所有的事件都按时间顺序给出。

示例:

输入:
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]

输出:
[null,null,null,null,null,null,null,14.0,11.0,null,11.0,null,12.0]

解释: 
UndergroundSystem undergroundSystem = new UndergroundSystem(); 
undergroundSystem.checkIn(45, "Leyton", 3); 
undergroundSystem.checkIn(32, "Paradise", 8); 
undergroundSystem.checkIn(27, "Leyton", 10); 
undergroundSystem.checkOut(45, "Waterloo", 15); 
undergroundSystem.checkOut(27, "Waterloo", 20); 
undergroundSystem.checkOut(32, "Cambridge", 22);
undergroundSystem.getAverageTime("Paradise", "Cambridge"); // 返回 14.0。从 "Paradise"(时刻 8)到 "Cambridge"(时刻 22)的行程只有一趟 
undergroundSystem.getAverageTime("Leyton", "Waterloo"); // 返回 11.0。总共有 2 躺从 "Leyton" 到 "Waterloo" 的行程,编号为 id=45 的乘客出发于 time=3 到达于 time=15,编号为 id=27 的乘客于 time=10 出发于 time=20 到达。所以平均时间为 ( (15-3) + (20-10) ) / 2 = 11.0 
undergroundSystem.checkIn(10, "Leyton", 24); 
undergroundSystem.getAverageTime("Leyton", "Waterloo"); // 返回 11.0 
undergroundSystem.checkOut(10, "Waterloo", 38); 
undergroundSystem.getAverageTime("Leyton", "Waterloo"); // 返回 12.0

提示:

  • 总共最多有 20000 次操作。
  • 1 <= id, t <= 10^6
  • 所有的字符串包含大写字母,小写字母和数字。
  • 1 <= stationName.length <= 10
  • 与标准答案误差在 10^-5 以内的结果都视为正确结果。
题解

注意所有事件都按时间顺序给出,直接模拟即可。

时间复杂度:\(O(1)\)

class UndergroundSystem {
public:
    unordered_map<int, pair<string, int>> startTime;
    unordered_map<string, unordered_map<string, pair<int, int>>> record;
    UndergroundSystem() { }
    
    void checkIn(int id, string stationName, int t) {
        startTime[id] = make_pair(stationName, t);
    }
    
    void checkOut(int id, string stationName, int t) {
        int sum = t - startTime[id].second;
        string startStation = startTime[id].first;
        record[startStation][stationName].first += sum;
        record[startStation][stationName].second++;
    }
    
    double getAverageTime(string startStation, string endStation) {
        auto inform = record[startStation][endStation];
        return inform.first * 1.0 / inform.second;
    }
};

/**
 * Your UndergroundSystem object will be instantiated and called as such:
 * UndergroundSystem* obj = new UndergroundSystem();
 * obj->checkIn(id,stationName,t);
 * obj->checkOut(id,stationName,t);
 * double param_3 = obj->getAverageTime(startStation,endStation);
 */

找到所有好字符串

给你两个长度为 n 的字符串 s1 和 s2 ,以及一个字符串 evil 。请你返回 好字符串 的数目。

好字符串 的定义为:它的长度为 n ,字典序大于等于 s1 ,字典序小于等于 s2 ,且不包含 evil 为子字符串。

由于答案可能很大,请你返回答案对 10^9 + 7 取余的结果。

示例 1:

输入:n = 2, s1 = "aa", s2 = "da", evil = "b"
输出:51 
解释:总共有 25 个以 'a' 开头的好字符串:"aa","ac","ad",...,"az"。还有 25 个以 'c' 开头的好字符串:"ca","cc","cd",...,"cz"。最后,还有一个以 'd' 开头的好字符串:"da"。

示例 2:

输入:n = 8, s1 = "leetcode", s2 = "leetgoes", evil = "leet"
输出:0 
解释:所有字典序大于等于 s1 且小于等于 s2 的字符串都以 evil 字符串 "leet" 开头。所以没有好字符串。

示例 3:

输入:n = 2, s1 = "gx", s2 = "gz", evil = "x"
输出:2

提示:

  • s1.length == n
  • s2.length == n
  • s1 <= s2
  • 1 <= n <= 500
  • 1 <= evil.length <= 50
  • 所有字符串都只包含小写英文字母。
题解

数位DP,设 \(dp_{x,y}\) 为已确定位置 [0,x) 的合法字符串且该字符串下次与 Evily 位匹配,后面 [x,n) 位置任意填且整体合法的字符串方案数。

(不搞 ACM 的我表示,这题压力有点大,解释不清,请看 WNJXYK 大佬讲解。https://www.bilibili.com/video/BV1r54y1R7bJ?t=627&p=5

时间复杂度:\(O(nm)\)

const int N = 5E2 + 10, M = 50 + 10, MOD = 1E9 + 7;
class Solution {
public:
    int fail[M], f[M][30], m, l, dp[N][M];
    string strEvil, strLim;
    int solve(int x, int y, bool flag) {
        if(l <= y) return 0;
        if(m <= x) return 1;
        if(!flag && dp[x][y] != -1) return dp[x][y];
        char lim = (flag ? strLim[x] : 'z');
        long long result = 0;
        for(char c = 'a'; c <= lim; c++) {
            int j = y;
            while(j && strEvil[j] != c) j = fail[j];
            if(strEvil[j] == c) j++;
            result = (result + solve(x + 1, j, flag & (c == lim))) % MOD;
        }
        if(!flag) dp[x][y] = result;
        return result;
    }
    int findGoodStrings(int n, string s1, string s2, string evil) {
        strEvil = evil, m = n, l = evil.length();
        fail[0] = fail[1] = 0;
        for(int i = 1; i < l; i++) {
            int j = fail[i];
            while(j && evil[i] != evil[j]) j = fail[j];
            fail[i + 1] = (evil[i] != evil[j] ? 0 : j + 1);
        }
        memset(dp, -1, sizeof(dp));
        strLim = s2;
        int result2 = solve(0, 0, true);
        strLim = s1;
        int result1 = solve(0, 0, true) - (s1.find(evil) == string::npos);
        return (result2 - result1 + MOD) % MOD;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注