第 20 场双周赛

Posted on | In , | |
Words count in article: 420 | Reading time ≈ 2

5323. 根据数字二进制下 1 的数目排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int find(int n){
        int count = 0;
        while(n){
            n = n&(n-1);
            count++;
        }
        return count;
    }
    static bool cmp(vector<int>& a, vector<int>& b){
        if(a[1]==b[1]) return a[0] < b[0];
        return a[1] < b[1];
    }
    vector<int> sortByBits(vector<int>& arr) {
        vector<vector<int>> v(arr.size(), vector<int>(2));
        for(int i=0; i<arr.size(); i++) {
            v[i][0] = arr[i];
            v[i][1] = find(arr[i]);
        }
        sort(v.begin(), v.end(), cmp);
        vector<int> ret;
        for(int i=0; i<arr.size(); i++)
            ret.push_back(v[i][0]);
        return ret;
    }
};

5325. 包含所有三种字符的子字符串数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numberOfSubstrings(string s) {
        int ret = 0;
        int n = s.size();
        int mp[3] = {0,0,0};
        mp[s[0]-'a']++;
        mp[s[1]-'a']++;
        int i =0;
        for(int j=i+2; j<n; j++){
            mp[s[j]-'a']++;
            while(mp[0]&&mp[1]&&mp[2]){
                ret += n-j;
                mp[s[i++]-'a']--;
            }
        }
        return ret;
    }
};

5326. 有效的快递序列数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    const int MOD = 1000000007;

    int countOrders(int N) {
        long long P = 1;
        for (int n = 2; n <= N; n++) {
            long long a = 2 * (n - 1) + 1;
            long long b = a * (a - 1) / 2 + a;
            P = (b * P) % MOD;
        }

        return P;
    }
};

5324. 每隔 n 个顾客打折

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Cashier {
public:
    int discount;
    int n;
    unordered_map<int, int> priceMap;
    int index = 0; 
    
    Cashier(int n, int discount, vector<int>& products, vector<int>& prices) {
        this->n = n;
        this->discount = discount;
        
        for (int i = 0; i < products.size(); i++) {
            priceMap[products[i]] = prices[i];
        }
    }
    
    double getBill(vector<int> product, vector<int> amount) {
        index++;
        double sum = 0;
        for (int i = 0; i < product.size(); i++) {
            sum += priceMap[product[i]] * amount[i];
        }
        if (index % n == 0) {
            sum = sum - (discount * sum) / 100;
        }
        
        return sum;
    }
};
Donate? comment?