LEETCODE 第20场双周赛

Contents

1 第一题：根据数字二进制下 1 的数目排序
2 第二题：每隔 n 个顾客打折
3 第三题：包含所有三种字符的子字符串数目
4 第四题：有效的快递序列数目

第一题：根据数字二进制下 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的个数；次关键词为：数值大小。

代码：

class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        b = [bin(i)[2:].count('1') for i in arr]
        z = list(zip(arr, b))

        s = sorted(z, key=lambda kv: (kv[1], kv[0]))

        return [i[0] for i in s]

class Solution:

def sortByBits(self, arr: List[int]) -> List[int]:

b = [bin(i)[2:].count('1') for i in arr]

z = list(zip(arr, b))

s = sorted(z, key=lambda kv: (kv[1], kv[0]))

return [i[0] for i in s]

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

思路：
　　一道面向对象题。

代码：

class Cashier(object):

    def __init__(self, n, discount, products, prices):
        """
        :type n: int
        :type discount: int
        :type products: List[int]
        :type prices: List[int]
        """
        self.n = n
        self.values = {}
        for i in range(len(products)):
            pro = products[i]
            price = prices[i]
            self.values[pro] = price
        self.discount = discount
        self.i = 0

    def getBill(self, product, amount):
        """
        :type product: List[int]
        :type amount: List[int]
        :rtype: float
        """
        sum = 0.
        self.i += 1
        discount = False
        if self.i % self.n == 0:
            discount = True
        for i in range(len(product)):
            pro = product[i]
            v = self.values[pro]
            a = amount[i]
            sum += v * a

        if discount:
            sum = sum - (self.discount * sum) / 100. 
        return sum

class Cashier(object):

def __init__(self, n, discount, products, prices):

"""

:type n: int

:type discount: int

:type products: List[int]

:type prices: List[int]

"""

self.n = n

self.values = {}

for i in range(len(products)):

pro = products[i]

price = prices[i]

self.values[pro] = price

self.discount = discount

self.i = 0

def getBill(self, product, amount):

"""

:type product: List[int]

:type amount: List[int]

:rtype: float

"""

sum = 0.

self.i += 1

discount = False

if self.i % self.n == 0:

discount = True

for i in range(len(product)):

pro = product[i]

v = self.values[pro]

a = amount[i]

sum += v * a

if discount:

sum = sum - (self.discount * sum) / 100.

return sum

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

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

代码：

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        if len(s) == 0:
            return 0
        a, b, c = 0, 0, 0
        head, tail = 0, 1  # s[head: tail]

        def add_count(char, count=1):
            nonlocal a, b, c
            if char == 'a':
                a += count
            elif char == 'b':
                b += count
            elif char == 'c':
                c += count

        add_count(s[0])
        l = len(s)
        ans = 0
        while head < l:
            if a == 0 or b == 0 or c == 0:
                tail += 1
                if tail > l:
                    return ans
                add_count(s[tail-1])
            else:
                ans += l - tail + 1
                head += 1
                add_count(s[head - 1], -1)

        return ans

class Solution:

def numberOfSubstrings(self, s: str) -> int:

if len(s) == 0:

return 0

a, b, c = 0, 0, 0

head, tail = 0, 1 # s[head: tail]

def add_count(char, count=1):

nonlocal a, b, c

if char == 'a':

a += count

elif char == 'b':

b += count

elif char == 'c':

c += count

add_count(s[0])

l = len(s)

ans = 0

while head < l:

if a == 0 or b == 0 or c == 0:

tail += 1

if tail > l:

return ans

add_count(s[tail-1])

else:

ans += l - tail + 1

head += 1

add_count(s[head - 1], -1)

return ans

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

　　给你 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_n$ 和 $D_n$ 的排列数即为countOrders(n)的种数。

代码：

class Solution:
    def countOrders(self, n: int) -> int:
        if n == 1:
            return 1
        return self.countOrders(n-1) * (2 * n -1 ) * n % 1000000007

class Solution:

def countOrders(self, n: int) -> int:

if n == 1:

return 1

return self.countOrders(n-1) * (2 * n -1 ) * n % 1000000007