2023-04-05:做甜点需要购买配料,目前共有n种基料和m种配料可供选购。 制作甜点需要遵循以下几条规则

2023-04-05:做甜点需要购买配料,目前共有n种基料和m种配料可供选购。
制作甜点需要遵循以下几条规则:
必须选择1种基料;可以添加0种、1种或多种配料,每种类型的配料最多添加2份,
给定长度为n的数组base, base[i]表示第i种基料的价格,
给定长度为m的数组topping, topping[j]表示第j种配料的价格,
给定一个正数target,表示你做的甜点最终的价格要尽量接近这个数值。
返回最接近这个数值的价格是多少。
如果有多个方案,都最接近target,返回价格最小的那个答案。
1 <= n,m <= 10,
1 <= base[i], topping[j] <= 10 ^ 4,
1 <= target <= 10 ^ 4。
来自华为。

答案2023-04-05:

方法1:有序表

1.首先创建一个空的有序表 set。

2.然后使用递归方式枚举所有辅料的组合方式,并将每种组合方式所能产生的价格放入有序表里。

3.接着遍历主料的价格数组,对于每个价格,从有序表中找到其中最接近且小于等于 target - num 的价格 floor 和最接近且大于等于 target - num 的价格 ceiling,然后计算出与主料价格相加最接近目标价格 target 的套餐价格 cur,分别跟当前的最优解 ans 比较,选取更优的一种。

4.对于每种辅料的组合方式和每个主料的价格,都要进行以上操作来更新最优解。

时间复杂度:

对于辅料的组合方式,每个辅料有三种选择(选或不选、加一份或两份),因此总共有 3^m 种组合方式。
对于主料的价格,需要在有序表中查找最接近且小于等于 target - num 的价格和最接近且大于等于 target - num 的价格。由于使用了红黑树实现的有序表,所以平均查找复杂度为 O(logn),其中 n <= 3^m 是有序表中元素的个数。
因此,该算法的时间复杂度为 O(n *log n + m 3 ^ m *log (3^m))。

空间复杂度:

由于需要存储所有辅料组合方式所能产生的价格,因此需要用到一个 BTreeSet 来存储这些价格,其空间复杂度为 O(m 3^m)。
因此,该算法的空间复杂度为 O(m 3^m)。

方法2:数组排序+二分

1.首先创建一个静态数组 COLLECT 和一个静态变量 SIZE。

2.然后使用递归方式枚举所有辅料的组合方式,并将每种组合方式所能产生的价格存入 COLLECT 数组中,并更新 SIZE 的值。

3.接着将 COLLECT 数组中存储的所有价格以非降序排列。

4.对于每个主料的价格,从 COLLECT 数组中找到其中最接近且小于等于 target - num 的价格 floor 和最接近且大于等于 target - num 的价格 ceiling,然后计算出与主料价格相加最接近目标价格 target 的套餐价格 cur,分别跟当前的最优解 ans 比较,选取更优的一种。

5.对于每种辅料的组合方式和每个主料的价格,都要进行以上操作来更新最优解。

6.注意,在二分查找 COLLECT 数组时需要使用 unsafe 代码块,因为 Rust 的 borrow checker 无法保证并发访问 COLLECT 数组的安全性。

时间复杂度:

对于辅料的组合方式,每个辅料有三种选择(选或不选、加一份或两份),因此总共有 3^m 种组合方式。
先对数组进行组合生成和排序,其中生成的元素个数是 3 ^ m,而排序的时间复杂度为 O(3 ^ m log 3^m)。
对于主料的价格,需要在排序后的数组中进行二分查找。由于数组是有序的,因此每次查找的时间复杂度为 O(log 3^m) =O(m)。
因此,该算法的时间复杂度为 O(m(3^m
log(3 ^ m)+n*logm))。

空间复杂度:

由于需要存储所有辅料组合方式所能产生的价格,因此需要用到一个静态数组来存储这些价格,其空间复杂度为 O(3^m)。
因此,该算法的空间复杂度为 O(3^m)。

测试

最后,为了验证代码实现的正确性,进行了功能测试和性能测试。在功能测试中,随机生成了多组数据对两种算法进行了比较,并检验它们的输出结果是否一致。在性能测试中,随机生成了一个较大的数据集,对两种算法的运行时间进行了比较。

rust完整代码如下:

use std::cmp::Ordering;
use std::collections::BTreeSet;

// 方法1,用有序表的方法
fn closed_target1(base: &[i32], topping: &[i32], target: i32) -> i32 {
    // 辅料所能产生的所有价格!
    // 0 5 15 23
    let mut set = BTreeSet::new();
    // 暴力展开!收集所有能产生的价格!放入辅料表里去!
    process1(topping, 0, 0, &mut set);
    let mut ans = i32::MAX;
    for &num in base.iter() {
        // 枚举每一种主料的价格!
        // 最终能搭配出来的最接近的价格
        let mut cur = num;
        // 20   100
        // 110  100
        if num < target {
            // cur < 要求
            // 60  100
            // 40
            let rest = target - num;
            // <= rest 最接近的!
            let floor = set.range(..=rest).next_back();
            // >= rest 最接近的!
            let ceiling = set.range(rest..).next();
            cur += match (floor, ceiling) {
                (Some(f), Some(c)) => {
                    if rest - f <= c - rest {
                        *f
                    } else {
                        *c
                    }
                }
                (Some(f), None) => *f,
                (None, Some(c)) => *c,
                (None, None) => 0, // 处理边界情况
            };
            // cur会选择floor,或ceiling,谁加上最接近target选谁!
        }
        if (cur - target).abs() < (ans - target).abs()
            || (cur - target).abs() == (ans - target).abs() && cur < ans
        {
            ans = cur;
        }
    }
    ans
}

// 暴力展开!收集所有能产生的价格!放入辅料表里去!
// topping[index....]
// topping[0...index-1]  sum
fn process1(topping: &[i32], index: usize, sum: i32, set: &mut BTreeSet<i32>) {
    if index == topping.len() {
        set.insert(sum);
    } else {
        process1(topping, index + 1, sum, set);
        process1(topping, index + 1, sum + topping[index], set);
        process1(topping, index + 1, sum + (topping[index] << 1), set);
    }
}

// 方法2,用数组排序+二分的方法

static mut COLLECT: [i32; 14348907] = [0; 14348907];
static mut SIZE: usize = 0;

fn closed_target2(base: &[i32], topping: &[i32], target: i32) -> i32 {
    unsafe {
        SIZE = 0;
        process2(topping, 0, 0);
        let size = SIZE;
        COLLECT[..size].sort_unstable();
        let mut ans = i32::MAX;
        for &num in base.iter() {
            let mut cur = num;
            if num < target {
                let rest = target - num;
                let floor = floor(rest);
                let ceiling = ceiling(rest);
                if floor == None || ceiling == None {
                    cur += if floor == None {
                        ceiling.unwrap()
                    } else {
                        floor.unwrap()
                    };
                } else {
                    cur += if rest - floor.unwrap() <= ceiling.unwrap() - rest {
                        floor.unwrap()
                    } else {
                        ceiling.unwrap()
                    };
                }
            }
            if (cur - target).abs() < (ans - target).abs()
                || (cur - target).abs() == (ans - target).abs() && cur < ans
            {
                ans = cur;
            }
        }
        ans
    }
}

fn process2(topping: &[i32], index: usize, sum: i32) {
    unsafe {
        if index == topping.len() {
            COLLECT[SIZE] = sum;
            SIZE += 1;
        } else {
            process2(topping, index + 1, sum);
            process2(topping, index + 1, sum + topping[index]);
            process2(topping, index + 1, sum + (topping[index] << 1));
        }
    }
}

fn floor(num: i32) -> Option<i32> {
    unsafe {
        let mut l = 0;
        let mut r = SIZE - 1;
        let mut ans = None;
        while l <= r {
            let m = (l + r) / 2;
            match COLLECT[m].cmp(&num) {
                Ordering::Less => {
                    ans = Some(COLLECT[m]);
                    l = m + 1;
                }
                Ordering::Greater => r = m - 1,
                Ordering::Equal => {
                    ans = Some(COLLECT[m]);
                    break;
                }
            }
        }
        ans
    }
}

fn ceiling(num: i32) -> Option<i32> {
    unsafe {
        let mut l = 0;
        let mut r = SIZE - 1;
        let mut ans = None;
        while l <= r {
            let m = (l + r) / 2;
            match COLLECT[m].cmp(&num) {
                Ordering::Less => l = m + 1,
                Ordering::Greater => {
                    ans = Some(COLLECT[m]);
                    r = m - 1;
                }
                Ordering::Equal => {
                    ans = Some(COLLECT[m]);
                    break;
                }
            }
        }
        ans
    }
}

// 为了验证
fn random_array(n: usize, v: i32) -> Vec<i32> {
    let mut arr = vec![0; n];
    for i in 0..n {
        arr[i] = (rand::random::<i32>() % v).abs() + 1;
    }
    arr
}

// 为了验证
fn main() {
    let N: usize = 8;
    let V: i32 = 10000;
    let test_time = 5000;
    println!("功能测试开始");
    for _ in 0..test_time {
        let n = (rand::random::<usize>() % N) + 1;
        let m = (rand::random::<usize>() % N) + 1;
        let base = random_array(n, V);
        let topping = random_array(m, V);
        let target = (rand::random::<i32>() % V).abs() + 1;
        let ans1 = closed_target1(&base, &topping, target);
        let ans2 = closed_target2(&base, &topping, target);
        assert_eq!(ans1, ans2);
    }
    println!("功能测试结束");

    println!("性能测试开始");
    let N: usize = 15;
    let V: i32 = 10000;
    let base = random_array(N, V);
    let topping = random_array(N, V);
    let target = (rand::random::<i32>() % V).abs() + 1;
    println!("base数组长度 : {}", N);
    println!("topping数组长度 : {}", N);
    println!("数值范围 : {}", V);
    let start = std::time::Instant::now();
    closed_target2(&base, &topping, target);
    let duration = start.elapsed();
    println!("运行时间 : {} 毫秒", duration.as_millis());
    println!("性能测试结束");
}

在这里插入图片描述

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 1

我以为是真的制作甜点来着 :joy:

1年前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
482
粉丝
23
喜欢
37
收藏
22
排名:456
访问:2.0 万
私信
所有博文
社区赞助商