On the shoulders of giants.

biweekly-contest-20

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

给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。

如果存在多个数字二进制中 1 的数目相同,则必须将它们按照数值大小升序排列。

请你返回排序后的数组。

示例 1:

输入:arr = [0,1,2,3,4,5,6,7,8]
输出:[0,1,2,4,8,3,5,6,7]
解释:[0] 是唯一一个有 0 个 1 的数。
[1,2,4,8] 都有 1 个 1 。
[3,5,6] 有 2 个 1 。
[7] 有 3 个 1 。
按照 1 的个数排序得到的结果数组为 [0,1,2,4,8,3,5,6,7]

示例 2:

输入:arr = [1024,512,256,128,64,32,16,8,4,2,1]
输出:[1,2,4,8,16,32,64,128,256,512,1024]
解释:数组中所有整数二进制下都只有 1 个 1 ,所以你需要按照数值大小将它们排序。

示例 3:

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

示例 4:

输入:arr = [2,3,5,7,11,13,17,19]
输出:[2,3,5,17,7,11,13,19]

示例 5:

输入:arr = [10,100,1000,10000]
输出:[10,100,10000,1000]

提示:

  • 1 <= arr.length <= 500
  • 0 <= arr[i] <= 10^4
题解

通过位运算快速计算出 1 的个数,然后排序输入。

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

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        vector<pair<int, int>> result;
        for(auto x : arr) {
            int total = 0, num = x;
            while(num) {
                total++;
                num -= num & (-num);
            }
            result.push_back(make_pair(total, x));
        }
        sort(result.begin(), result.end());
        vector<int> num;
        for(auto elem : result) {
            num.push_back(elem.second);
        }
        return num;
    }
};

每隔 n 个顾客打折

超市里正在举行打折活动,每隔 n 个顾客会得到 discount 的折扣。

超市里有一些商品,第 i 种商品为 products[i] 且每件单品的价格为 prices[i] 。

结账系统会统计顾客的数目,每隔 n 个顾客结账时,该顾客的账单都会打折,折扣为 discount (也就是如果原本账单为 x ,那么实际金额会变成 x - (discount * x) / 100 ),然后系统会重新开始计数。

顾客会购买一些商品, product[i] 是顾客购买的第 i 种商品, amount[i] 是对应的购买该种商品的数目。

请你实现 Cashier 类:

  • Cashier(int n, int discount, int[] products, int[] prices) 初始化实例对象,参数分别为打折频率 n ,折扣大小 discount ,超市里的商品列表 products 和它们的价格 prices 。
  • double getBill(int[] product, int[] amount) 返回账单的实际金额(如果有打折,请返回打折后的结果)。返回结果与标准答案误差在 10^-5 以内都视为正确结果。

示例 1:

输入
["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"]
[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]]
输出
[null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0] 
解释 
Cashier cashier = new Cashier(3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]); cashier.getBill([1,2],[1,2]);                        // 返回 500.0, 账单金额为 = 1 * 100 + 2 * 200 = 500. 
cashier.getBill([3,7],[10,10]);                      // 返回 4000.0 
cashier.getBill([1,2,3,4,5,6,7],[1,1,1,1,1,1,1]);    // 返回 800.0 ,账单原本为 1600.0 ,但由于该顾客是第三位顾客,他将得到 50% 的折扣,所以实际金额为 1600 - 1600 * (50 / 100) = 800 。 
cashier.getBill([4],[10]);                           // 返回 4000.0 
cashier.getBill([7,3],[10,10]);                      // 返回 4000.0 
cashier.getBill([7,5,3,1,6,4,2],[10,10,10,9,9,9,7]); // 返回 7350.0 ,账单原本为 14700.0 ,但由于系统计数再次达到三,该顾客将得到 50% 的折扣,实际金额为 7350.0 。 
cashier.getBill([2,3,5],[5,3,2]);                    // 返回 2500.0 

提示:

  • 1 <= n <= 10^4
  • 0 <= discount <= 100
  • 1 <= products.length <= 200
  • 1 <= products[i] <= 200
  • products 列表中 不会 有重复的元素。
  • prices.length == products.length
  • 1 <= prices[i] <= 1000
  • 1 <= product.length <= products.length
  • product[i] 在 products 出现过。
  • amount.length == product.length
  • 1 <= amount[i] <= 1000
  • 最多有 1000 次对 getBill 函数的调用。
  • 返回结果与标准答案误差在 10^-5 以内都视为正确结果。
题解

map 存储每个商品的价格,然后模拟计算出结果。

n 为这次购买的商品种数,m 为商店商品总数。

每次结算,时间复杂度:\(O(n \log m)\)

class Cashier {
public:
    map<int, int> h_prices;
    int count, n, discount;

    Cashier(int n, int discount, vector<int>& products, vector<int>& prices) {
        for(int i = 0; i < prices.size(); i++) {
            h_prices[products[i]] = prices[i];
        }
        count = 0;
        this->n = n;
        this->discount = discount;
    }
    
    double getBill(vector<int> product, vector<int> amount) {
        double money = 0;
        count++;
        for(int i = 0; i < product.size(); i++) {
            money += h_prices[product[i]] * amount[i];
        }
        if(count % n != 0) return money;
        return money - (discount * money) / 100;
    }
};

/**
 * Your Cashier object will be instantiated and called as such:
 * Cashier* obj = new Cashier(n, discount, products, prices);
 * double param_1 = obj->getBill(product,amount);
 */

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

给你一个字符串 s ,它只包含三种字符 a, b 和 c 。

请你返回 a,b 和 c 都 至少 出现过一次的子字符串数目。

示例 1:

输入:s = "abcabc"
输出:10
解释:包含 a,b 和 c 各至少一次的子字符串为 "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc"  "abc" (相同字符串算多次)

示例 2:

输入:s = "aaacb"
输出:3
解释:包含 a,b 和 c 各至少一次的子字符串为 "aaacb", "aacb"  "acb" 。

示例 3:

输入:s = "abc"
输出:1

提示:

  • 3 <= s.length <= 5 x 10^4
  • s 只包含字符 a,b 和 c 。
题解

首先从左到右记录每个字符出现的位置,然后枚举位置 x 作为目标字符串的开头。

接下来就是找到三个字符出现位置大于等于 x 的最小位置 p,求出它们的最大值 \(y=\max p_i\)。

显然,在 xy 构成的字符串满足题意,并可将其延申至原串末尾。

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

class Solution {
public:
    vector<int> pos[3];
    int numberOfSubstrings(string s) {
        int result = 0;
        for(int i = 0; i < s.length(); i++) {
            pos[s[i] - 'a'].push_back(i);
        }
        for(int i = 0; i < s.length(); i++) {
            int lim = i, flag = 0;
            for(int j = 0; j < 3; j++) {
                auto x = lower_bound(pos[j].begin(), pos[j].end(), i);
                if(x == pos[j].end()) break;
                lim = max(lim, *x);
                flag++;
            }
            if(flag == 3) result += s.length() - lim;
        }
        return result;
    }
};

有效的快递序列数目

给你 n 笔订单,每笔订单都需要快递服务。

请你统计所有有效的 收件/配送 序列的数目,确保第 i 个物品的配送服务 delivery(i) 总是在其收件服务 pickup(i) 之后。

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

示例 1:

输入:n = 1
输出:1
解释:只有一种序列 (P1, D1),物品 1 的配送服务(D1)在物品 1 的收件服务(P1)后。

示例 2:

输入:n = 2
输出:6
解释:所有可能的序列包括:
(P1,P2,D1,D2),(P1,P2,D2,D1),(P1,D1,P2,D2),(P2,P1,D1,D2),(P2,P1,D2,D1) 和 (P2,D2,P1,D1)。
(P1,D2,P2,D1) 是一个无效的序列,因为物品 2 的收件服务(P2)不应在物品 2 的配送服务(D2)之后。

示例 3:

输入:n = 3
输出:90

提示:

  • 1 <= n <= 500
题解

递推,假设 \(f_x\) 为 x 笔订单的有效序列,已知 \(f_i, i\in [1, n)\),现在构建 \(f_n\) 。

方法一:

将新来的一笔接连处理 \((P_n,D_n)\) 将其放入之前合法序列的空隙中(共有 \(2(n-1)+1\) 个) ,

共有 \(2n-1\) 种放法。

方法二:

在之前合法序列中,找出两个空隙,然后先放入 \(P_n\) 再放入 \(D_n\),

共有 \(C^2_{2n-1}=(2n-1)(n-1)\) 种放法。

综上,根据乘法加法计数原理可得:\(f_n=(2n-1)n\cdot f_{n-1}\)

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

class Solution {
public:
    int MOD = 1E9 + 7;
    int countOrders(int n) {
        if(n == 1) return 1;
        long long result = 1;
        for(int i = 2; i <= n; i++) {
            result = (2 * i - 1) * i * result % MOD;
        }
        return result;
    }
};
Share

You may also like...

发表评论

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