专栏首页Michael阿明学习之路LeetCode 第 20 场双周赛(294 / 1541,前19.07%,第1次全部通过)

LeetCode 第 20 场双周赛(294 / 1541,前19.07%,第1次全部通过)

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 806. 写字符串需要的行数

    我们要把给定的字符串 S 从左到右写到每一行上,每一行的最大宽度为100个单位,如果我们在写某个字母的时候会使这行超过了100 个单位,那么我们应该把这个字母写...

    Michael阿明
  • 程序员面试金典 - 面试题 05.01. 插入(位运算)

    编写一种方法,将 M 插入 N,使得 M 从 N 的第 j 位开始,到第 i 位结束。 假定从 j 位到 i 位足以容纳 M,也即若 M = 10 011,那...

    Michael阿明
  • LeetCode 1015. 可被 K 整除的最小整数(数学)

    Michael阿明
  • 【LeetCode第20场夜猫赛】5324. 每隔 n 个顾客打折

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

    韩旭051
  • leetcode 7 Reverse Integer

    Example1: x = 123, return 321 Example2: x = -123, return -321

    用户1539362
  • 为新兴物联网公司提供五项免费营销技巧

    原文地址:https://internetofthingsagenda.techtarget.com/blog/IoT-Agenda/Five-free-mar...

    双愚
  • java中的lastIndexOf( )函数是什么意思

    String中的lastIndexOf方法,是获取要搜索的字符、字符串最后次出现的位置。

    黑泽君
  • 51Nod--1004 n^n的末位数字

    题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1004

    指点
  • 再爬 Boss 直聘,探究哪种岗位更好就业

    不知不觉,十月份已经过去了,传说中的金九银十招聘季也应该随之结束了,不知道有换工作打算的朋友有没有找到理想的下家,反正我没有

    周萝卜
  • 1年多,近100次的版本更新,终于有所积累

    前年的时候,买了吉日嘎拉的4998元的开发平台个人版本,去年公司里面采购了9998的企业版,一路上用下来,多是欣喜。公司里面的积累自然不用说,应对用户的需求,处...

    崔文远TroyCui

扫码关注云+社区

领取腾讯云代金券