第二题 每隔 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 以内都视为正确结果。

链接：https://leetcode-cn.com/problems/apply-discount-every-n-orders

解题思路

读懂题目就行。略

from blog.

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

给你一个字符串 s ，它只包含三种字符 a, b 和 c 。

请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。

链接：https://leetcode-cn.com/problems/number-of-substrings-containing-all-three-characters

解题思路

hash表 + 双指针

1. hash表用于记录目前窗口内 a b c 分别的个数
2. 当每一个字母个数都大于等于1时，为计算总数加 right 指针剩余位数
3. 左指针右移，入仍符合条件，继续叠加
4. 如此类推，最后返回总数

以示例 1 为例
当第一次满足 abc 个数都大于 0，即left指针为0，right指针为2时 => 'abc', 'abca', 'abcab', 'abcabc' 均成立，由此可以统计 count += s.length - right
满足 abc 个数都大于 0，后左节点像右移动，对应移除字母再hash表上减 1 => hash = {a: 0, b:1, c:1} 'bc'
（如果依然成立，即可统计 count += s.length - right, 如示例2中 aaacb(这时候count+= 1) => aacb(再次count+= 1)）
当条件不成立时，右节点向右移动，如此循环，直至right到达最右，且 hash 表永远不满足条件

右指针最多走 n 次，左指针最多走 n - 2次，所以 时间复杂度为 O(n)

代码

/**
 * @param {string} s
 * @return {number}
 */
// 滑动窗口
var numberOfSubstrings = function(s) {
    let hash = {
        a: 0,
        b: 0,
        c: 0
    }
    let arr = s.split('')
    let count = 0
    let left = 0
    let right = 0
    while(right <= s.length - 1) {
        hash[arr[right]] ++

        while(hash['a'] >= 1 && hash['b'] >= 1 && hash['c'] >= 1) {
            count += s.length - right 
            hash[arr[left]] --
            left ++
        }
        right ++
    }
    return count
    
};

from blog.

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

给你 n 笔订单，每笔订单都需要快递服务。

请你统计所有有效的 收件/配送 序列的数目，确保第 i 个物品的配送服务 delivery(i) 总是在其收件服务 pickup(i) 之后。

由于答案可能很大，请返回答案对 10^9 + 7 取余的结果。

链接：https://leetcode-cn.com/problems/count-all-valid-pickup-and-delivery-options

解题思路

找规律递推...

代码

/**
 * @param {number} n
 * @return {number}
 */
var countOrders = function(n) {
    let mod = 1e9 + 7
    let last=1;
    for(let i=1;i<=n;i++){
        //组合 C(2,2*i)
        let c=i*(2*i-1);
        last=(last*c) % mod;
    }
    return last;

};

from blog.