LEETCODE 第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的个数;次关键词为:数值大小。

代码:

第二题:每隔 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

思路:
  一道面向对象题。

代码:

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

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

思路:

  维护一个窗口, 头和尾分别为head,tail
  记录这个窗口内的a、b、c的数量。
  当abc数量有0时,tail向后移动。
  当abc数量没有0时,此时tail及以后的所有位置都是合法的答案加上len(s)-tailhead向后移动。
  时间复杂度O(n)。

代码:

第四题:有效的快递序列数目

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

思路:
  排列组合,在countOrders(n - 1)的所有排序结果中,按顺序插入P_nD_n的排列数即为countOrders(n)的种数。

代码:

发表评论

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