LeetCode 第 20 场双周赛（294 / 1541，前19.07%，第1次全部通过）

Michael阿明

发布于 2020-07-13 16:01:13

3890

发布于 2020-07-13 16:01:13

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

1. 比赛结果

第一次全部做出来了，提前6分钟结束战斗，激动啊，今晚睡得着吗？哈哈

全国排名：294/1541，前19.07%；全球排名：885/4347，前20.4%

第4题，忘记取模%，错误一次（有点冤。。。）
第2题有点失误（错了3次），花费时间过长，还用了本地IDE调试了几次做题顺序如下：

2. 题目

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

题目链接给你一个整数数组 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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/sort-integers-by-the-number-of-1-bits 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答：

自定义排序，用的 lambda 表示式

int count(int n)
{
	int c = 0;
	while(n)//计算n的二进制1的个数
	{
		c++;
		n = n&(n-1);
	}
	return c;
}
class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
    	sort(arr.begin(), arr.end(),[](auto& a, auto& b) 
    			{if(count(a) == count(b))
    				return a < b;
    			return count(a) < count(b);});
    	return arr;
    }
};

执行用时：8 ms 内存消耗：12.2 MB

LeetCode 5324. 每隔 n 个顾客打折 medium

题目链接超市里正在举行打折活动，每隔 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 以内都视为正确结果。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/apply-discount-every-n-orders 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题：

注意使用哈希表查找product[i]在products里的下标

class Cashier {
	int num;
	int disc;
	vector<int> pric;
	unordered_map<int,int> idx;
	int people = 0;
    int i;
    double money;
public:
    Cashier(int n, int discount, vector<int>& products, vector<int>& prices) {
    	num = n;
    	disc = discount;
    	pric = prices;
    	for(i = 0; i < products.size();++i)
    	{
    		idx.insert(make_pair(products[i],i));
    	}
    }
    
    double getBill(vector<int> product, vector<int> amount) {
    	money = 0;
    	for(i = 0; i < product.size(); i++)
    	{
    		money += pric[idx[product[i]]]*amount[i];
    	}
    	people++;
    	if(people == num)
    	{
    		people = 0;
    		money = money*(100-disc)/100;
    	}
    	return money;
    }
};

执行用时：228 ms 内存消耗：119.9 MB

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

题目链接

给你一个字符串 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 。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/number-of-substrings-containing-all-three-characters 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题：

先顺序记录下所有的 a,b,c 的位置，存储于 pa，pb，pc
然后遍历 pa，pb，pc 分别以a开头，b开头，c开头查找，开始的下标start是知道的
然后在另外两个数组里二分查找，第一个比start大的下标
如果都存在另外两个下标比start大，那么可有的子串数就是 s.size()-最大的下标

class Solution {
	vector<int> pa;
	vector<int> pb;
	vector<int> pc;
public:
    int numberOfSubstrings(string s) {
    	int i,x,y;
    	for(i = 0; i < s.size(); i++)
    	{	//记录abc的下标
    		if(s[i] == 'a')
    			pa.push_back(i);
    		else if(s[i] == 'b')
    			pb.push_back(i);
    		else
    			pc.push_back(i);
    	}
    	if(pa.empty() || pb.empty() || pc.empty())
    		return 0;
    	int count = 0;
    	for(auto& idxa : pa)
    	{
    		x = bsfirst(idxa,pb);//二分查找第一个大于idxa的下标
    		y = bsfirst(idxa,pc);
    		if(x==-1 || y==-1)
    			continue;//有一个字符没有找到，没有符合的子串
    		count += s.size()-max(pb[x],pc[y]);
    	}
    	for(auto& idxb : pb)
    	{
    		x = bsfirst(idxb,pa);
    		y = bsfirst(idxb,pc);
    		if(x==-1 || y==-1)
    			continue;
    		count += s.size()-max(pa[x],pc[y]);
    	}
    	for(auto& idxc : pc)
    	{
    		x = bsfirst(idxc,pb);
    		y = bsfirst(idxc,pa);
    		if(x==-1 || y==-1)
    			continue;
    		count += s.size()-max(pb[x],pa[y]);
    	}
    	return count;
    }

	int bsfirst(int idx, vector<int>& v)
	{	//二分查找，第一个比idx大的数
		int l = 0, r = v.size()-1, mid;
		while(l <= r)
		{
			mid = l+((r-l)>>1);
			if(v[mid] < idx)
				l = mid+1;
			else if(v[mid] > idx)
			{
				if(mid == 0 || v[mid-1] < idx)
					return mid;
				else
					r = mid-1;
			}
		}
		return -1;
	}
};

执行用时：76 ms 内存消耗：17.3 MB

LeetCode 5326. 有效的快递序列数目 hard

题目链接

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/count-all-valid-pickup-and-delivery-options 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题：

动态规划问题
dp[i] 表示 i 件物品可能的投递次序数
在 dp[i-1] 的基础上，考虑两端，他有一共有 2∗(i−1)+1=2i−12*(i-1)+1 = 2i-12∗(i−1)+1=2i−1 个空位
第 i 个包裹分开投递，那么插空有 C2i−12=(2i−1)(2i−2)/2=(2i−1)(i−1)C_{2i-1}^2 = (2i-1)(2i-2)/2=(2i-1)(i-1)C2i−12=(2i−1)(2i−2)/2=(2i−1)(i−1) 种可能
第 i 个包裹不分开，连续1投1递，那么插空有 2i−12i-12i−1种可能
两种情况相加*乘以之前的种类即可： dp[i]=dp[i−1]∗[(2∗i−1)∗(i−1)+2∗i−1]=dp[i−1]∗(2∗i−1)∗idp[i] = dp[i-1]*[(2*i-1)*(i-1)+2*i-1]=dp[i-1]*(2*i-1)*idp[i]=dp[i−1]∗[(2∗i−1)∗(i−1)+2∗i−1]=dp[i−1]∗(2∗i−1)∗i

class Solution {
public:
    int countOrders(int n) {
        vector<long> dp(n+1,0);
        dp[1] = 1;
        for(int i = 2; i <= n; ++i)
        {
            dp[i] = dp[i-1]*(2*i-1)*i%1000000007;
        }
        return dp[n];
    }
};

执行用时：0 ms 内存消耗：8.6 MB

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-02-23 ，如有侵权请联系 cloudcommunity@tencent.com 删除

https