双周赛 – 20

1. 根据数字二进制下 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的个数,然后排序就好啦。

viv丑陋版

struct Num {
    int x;
    int cnt;
} num[550];

bool cmp(const Num& a, const Num& b) {
    if(a.cnt != b.cnt) return a.cnt < b.cnt;
    return a.x < b.x;
}

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        int n = arr.size();
        for(int i=0; i<n; i++) {
            num[i].x = arr[i];
            int now = 0;
            while(arr[i]) {
                if(arr[i] & 1) now++;
                arr[i] >>= 1;
            }
            num[i].cnt = now;
        }
        sort(num, num+n, cmp);
        
        vector<int> ans;
        for(int i=0; i<n; i++) ans.push_back(num[i].x);
        return ans;
    }
};

zz美丽版

我是对计算完1的个数的结构体排序的,zz是对vector直接排序的,排序时计算1的个数。

int bcount(int x) {
    int ret = 0;
    while(x) {
        if(x & 1) ret++;
        x /= 2;
    }
    return ret;
}
bool cmp(int a, int b) {
    int ba = bcount(a), bb = bcount(b);
    if(ba != bb) return ba < bb;
    return a < b;
}
class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), cmp);
        return arr;
    }
};

2. 每隔 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 以内都视为正确结果。

代码

viv丑陋版

感觉这道题属于这种类型题里最简单的了呀,一点也没有绕弯。
构造一个map用来方便的访问每种商品的价格,然后用一个变量now来记录当前是第几个顾客,如果符合要求即打折。

class Cashier {
private:
    int n;
    int now;
    int discount;
    map<int, int> mp;
public:
    Cashier(int n, int discount, vector<int>& products, vector<int>& prices) {
        this->n = n;
        this->discount = discount;
        this->now = 0;
        
        mp.clear();
        int siz = products.size();
        for(int i=0; i<siz; i++) mp[products[i]] = prices[i];
    }
    
    double getBill(vector<int> product, vector<int> amount) {
        int siz = product.size();
        double ans = 0;
        for(int i=0; i<siz; i++) ans += (amount[i] * mp[product[i]]);    
        if((++now) % n == 0) ans = ans - (1.0 * discount * ans) / 100;
        return ans;
    }
};

/**
 * 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);
 */

zz美丽版

好像唯一的区别就是zz把now及时清零了,不过这个也不会爆int,所以当时就顺手那么写了。

class Cashier {
public:
    map<int, int> pric;
    int cur, tot;
    int discount;
    Cashier(int n, int discount, vector<int>& products, vector<int>& prices) {
        this->cur = 0; this->tot = n;
        this->discount = discount;
        
        this->pric.clear();
        int m = products.size();
        for (int i = 0; i < m; i++)
            this->pric[products[i]] = prices[i];
    }
    
    double getBill(vector<int> product, vector<int> amount) {
        double ans = 0;
        
        int m = product.size();
        for (int i = 0; i < m; i++){
            ans += 1.0 * amount[i] * this->pric[product[i]];
        }
        
        ++cur;
        if (cur == tot){
            ans = ans - 1.0 * this->discount * ans / 100.0;
            cur = 0;
        }
        
        return ans;
    }
};

/**
 * 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);
 */

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

给你一个字符串 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 * 10^4
  • s 只包含字符 a,b 和 c 。

题解

viv丑陋版

思路乱糟糟的,代码也乱糟糟的,然后居然过了。
双指针。如果当前指针包含的范围满足a、b、c都有的条件,更新答案,左指针向右移一位,如果移完仍然满足条件,则右指针也向右移一位;否则,右指针向右移一位。
最后再更新左指针至最后位置,每次移动指针,满足条件则答案加一。

class Solution {
public:
    int numberOfSubstrings(string s) {
        int n = s.size();
        int left = 0, right = 0, ans = 0;
        int cnt[3]; memset(cnt, 0, sizeof(cnt));
        cnt[s[0]-'a']++;
        while(left <= right && right < n) {
            if(cnt[0] >= 1 && cnt[1] >= 1 && cnt[2] >= 1) {
                ans += n - right;
                cnt[s[left]-'a']--;
                left++;
                if(cnt[0] < 1 || cnt[1] < 1 || cnt[2] < 1) {
                    right++;
                    if(right < n) cnt[s[right]-'a']++;
                }
            }
            else {
                right++;
                if(right < n) cnt[s[right]-'a']++;
            }
        }
        while(left < n) {
            if(cnt[0] >= 1 && cnt[1] >= 1 && cnt[2] >= 1) {
                ans++;
                cnt[s[left]-'a']--;
            }
            left++;
        }
        return ans;
    }
};

zz美丽版

啊哈哈哈哈,我感觉zz的做法没我机智,复杂度比我高啊。
zz是对于每一个左端点,都遍历枚举符合条件且最靠近左边的右端点计算。
代码简单但复杂度高!骄傲!

class Solution {
public:
    int numberOfSubstrings(string s) {
        int n = s.length(), app = 0, ans = 0;
        map<char, int> cnt; cnt.clear();
        
        for (int i = 0, j = 0; i < n; i++){
            if (i > 0){
                if (cnt[s[i - 1]] == 1) --app;
                --cnt[s[i - 1]];
            }
            
            while(app < 3 && j < n){
                if (cnt[s[j]] == 0) ++app;
                ++cnt[s[j]];
                ++j;
            }
            
            if (app == 3) {
                ans += n - j + 1;
                // printf("%d %d\n", i, j);
            }
        }
        
        return ans;
    }
};

4. 有效的快递序列数目

给你 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

代码

viv丑陋版

组合数学94分的viv也许是太困了。她居然不会做。

zz美丽版

组合数学82分的zz觉得这题是弱智题。好的。
$n=1$时,很明显只有P1D1一种解法。
$n=2$时,考虑把P2和D2放入P1D1中。如果P2D2连续,那么有$n*2-1=3$种;如果不连续,那么有$C_{n*2-1}^2=C_3^2$种。以此类推。
不要忘记取模。

const long long MOD = 1e9 + 7;
class Solution {
public:
    int countOrders(int n) {
        long long ans = 1;
        
        for (int i = 2; i <= n; i++){
            int c = 2 * i - 1;
            ans = ans * (c * (c - 1) / 2 + c) % MOD; 
        }
        
        return ans;
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇