讨论/题目交流/🐱 第 20 场夜喵双周赛/
🐱 第 20 场夜喵双周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 根据数字二进制下 1 的数目排序
4 分 - 每隔 n 个顾客打折
5 分 - 包含所有三种字符的子字符串数目
6 分 - 有效的快递序列数目

展开讨论

第二题,Rust的代码一直过不了,换成Golang就过了…我觉得应该是精度的问题。麻烦官方看看什么情况

use std::collections::HashMap;

struct Cashier {
    product_price: HashMap<i32, i32>,
    n: i32,
    discount: i32,
    count: i32,
}

impl Cashier {

    fn new(n: i32, discount: i32, products: Vec<i32>, prices: Vec<i32>) -> Self {
        let mut hash = HashMap::new();
        for (&pid, &price) in products.iter().zip(prices.iter()) {
            hash.insert(pid, price);
        }
        Self{
            n,
            discount,
            product_price: hash,
            count: 0,
        }
    }

    fn get_bill(&mut self, product: Vec<i32>, amount: Vec<i32>) -> f64 {
        self.count += 1;
        let mut total_price: i64 = 0;
        for (pid, &total) in product.iter().zip(amount.iter()) {
            total_price += *self.product_price.get(pid).unwrap() as i64 * total as i64;
        }
        if self.count == self.n {
            self.count = 0;
            (1f64 - self.discount as f64 / 100f64) * total_price as f64
        } else {
            total_price as f64
        }
    }
}

第四题
我一开始想复杂了,直接硬推排列组合公式,各种组合数求和,然后求组合数由于有除法,取模还得费马小定理+快速幂…
最后发现,根本没那么复杂,很简单。

f(n) = n * (n-1)*2 * f(n-1),O(n)的递推就完事儿,O(1)的空间

展开全部 22 讨论