【LeetCode】第20场夜喵双周赛
【摘要】
一.第一题
（1）题目：根据数字二进制下 1 的数目排序
给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。 如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。 请你返回排序后的数组。
示例1：
输入：a...
一.第一题
（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 <= 5000 <= arr[i] <= 10^4
（2）算法思想
统计数的二进制中1的个数用位运算a&=(a-1)，每次位运算实现去掉距离最右边最近的一个1，如a=10，则a&(a-1)=10&9=1010 & 1001=1000=8，就实现10的二进制1010的最右边的一个1去掉了。
直接调用库函数sort，可以三个参数也可以两个参数，如果是在pat中则必须上头文件#include < algorithm>和using namespace std。
（3）代码
-
class Solution {
-
public:
-
vector<int> sortByBits(vector<int>& arr) {
-
//int n=arr.size();
-
sort(arr.begin(),arr.end(),cmp);//自定义排序
-
return arr;
-
}
-
static int getOneCount(int a) {//二进制中1的个数（正负数都适用）
-
int cnt=0;
-
while(a!=0){
-
cnt++;
-
a&=(a-1);//去掉最右边的1
-
}
-
return cnt;
-
}
-
static bool cmp(int a,int b){//按二进制中1的个数降序，相同时按值升序
-
int one_a=getOneCount(a),one_b=getOneCount(b);
-
return (one_a==one_b)?(a<b):(one_a<one_b);
-
}
-
};
二.第二题
（1）题目：每隔 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以内都视为正确结果
-
输入
-
["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^40 <= discount <= 1001 <= products.length <= 2001 <= products[i] <= 200products列表中 不会 有重复的元素。prices.length == products.length1 <= prices[i] <= 10001 <= product.length <= products.lengthproduct[i]在products出现过。amount.length == product.length1 <= amount[i] <= 1000- 最多有
1000次对getBill函数的调用。 - 返回结果与标准答案误差在
10^-5以内都视为正确结果。
（2）算法思想
快乐模拟题，用map存储产品号和对应的价格，每次getBill将cnt加1，如果最后cnt为n的倍数则幸运用户打折。
（3）代码
-
class Cashier {
-
public:
-
int n, d;
-
map <int, int> p;
-
int cnt;
-
Cashier(int _n, int discount, vector<int>& products, vector<int>& prices) {
-
n = _n;
-
d = discount;
-
for (int i = 0; i < products.size(); i++) p[products[i]] = prices[i];
-
cnt = 0;
-
}
-
-
double getBill(vector<int> product, vector<int> amount) {
-
double ans = 0;
-
for (int i = 0; i < product.size(); i++) ans += amount[i] * p[product[i]];
-
cnt++;
-
if (cnt == n) {
-
cnt = 0;
-
ans = ans - (d * ans) / 100;
-
}
-
return ans;
-
}
-
};
三.第三题
（1）题目：包含所有三种字符的子字符串数目
lc题号【5325】
给你一个字符串 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^4s只包含字符 a，b 和 c 。
（2）算法思想
滑动窗口
滑动窗口解决子串问题：https://mp.weixin.qq.com/s/nJHIxQ2BbqhDv5jZ9NgXrQ
（3）代码
-
class Solution {
-
public:
-
int numberOfSubstrings(string s) {
-
int n = s.size();
-
int cnt[5];
-
cnt[0] = cnt[1] = cnt[2] = 0;
-
int r = -1;
-
int ans = 0;
-
for (int l = 0; l < n; l++) {
-
while ((cnt[0] == 0 || cnt[1] == 0 || cnt[2] == 0) && r < n - 1) {
-
r++;
-
cnt[s[r] - 'a']++;
-
}
-
//printf("%d %d\n", l, r);
-
if (cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0) {
-
ans += (n - 1 - r + 1);
-
}
-
cnt[s[l] - 'a']--;
-
}
-
return ans;
-
}
-
};
四.第四题
（1）题目：有效的快递序列数目
给你 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
（2）算法思想
组合数学题，此处填坑，现在不想看。。
（3）代码
-
class Solution {
-
public:
-
int countOrders(int n) {
-
int mo = 1000000007;
-
int ans = 1, sur = n * 2;
-
for (int i = 1; i <= n; i++) {
-
int now = (long long)sur * (sur - 1) / 2 % mo;
-
ans = (long long)ans * now % mo;
-
sur -= 2;
-
}
-
return ans;
-
}
-
};
文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。
原文链接：andyguo.blog.csdn.net/article/details/104454934
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）