9.超市里的货物架调整

刷题前请喊一遍我们的口号：

• 方法不对，刷题白费。
• 节省时间，精准刷题。

本题难度系数：⭐⭐⭐中等

问题描述

在一个超市里，有一个包含 n 个格子的货物架，每个格子中放有一种商品，商品用小写字母 a 到 z 表示。当顾客进入超市时，他们会依次从第一个格子查找到第 n 个格子，寻找自己想要购买的商品。如果在某个格子中找到该商品，顾客就会购买它并离开；如果中途遇到一个空格子，或查找完所有格子还没有找到想要的商品，顾客也会离开。

作为超市管理员，你可以在顾客到来之前重新调整商品的顺序，以便尽可能多地出售商品。当第一个顾客进入后，商品位置不能再调整。你需要计算在最优调整下，最多可以卖出多少件商品。输入变量说明：

• n：货物架的格子数
• m：顾客想要购买的商品种类数
• s：货物架上商品的初始顺序
• c：顾客想要购买的商品种类

测试样例

样例 1：

输入：n = 3 ,m = 4 ,s = "abc" ,c = "abcd"
输出：3

样例 2：

输入：n = 4 ,m = 2 ,s = "abbc" ,c = "bb"
输出：2

样例 3：

输入：n = 5 ,m = 4 ,s = "bcdea" ,c = "abcd"
输出：4

解题思路

这个问题可以转化为：如何重新排列货物架上的商品顺序，使得顾客按顺序查找时能购买最多的商品。关键在于让尽可能多的顾客在查找过程中尽早找到他们想要的商品。

1. 问题分析：
   • 每个顾客会从第一个格子开始查找，直到找到自己想要的商品或遇到空格子/查找完所有格子。
   • 我们需要重新排列商品顺序，使得顾客按顺序查找时能尽可能多地找到商品。
2. 关键观察：
   • 商品在货物架上的顺序决定了顾客是否能找到商品。
   • 为了让更多顾客找到商品，应该将顾客想要的商品尽量放在前面。
   • 重复的商品可以满足多个顾客的需求（如样例 2 中的"bb"）。
3. 算法选择：
   • 统计顾客想要的每种商品的数量。
   • 统计货物架上每种商品的数量。
   • 对于每种商品，取顾客想要的数量和货物架上数量的较小值，累加得到最多能卖出的商品数量。

代码实现

function solution(n, m, s, c) {
    // PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE
    // write code here
    const shelfCount = {};
    const customerCount = {};
    
    // Count the frequency of each character in s
    for (const char of s) {
        shelfCount[char] = (shelfCount[char] || 0) + 1;
    }
    
    // Count the frequency of each character in c
    for (const char of c) {
        customerCount[char] = (customerCount[char] || 0) + 1;
    }
    
    let maxSold = 0;
    
    // For each character in customer's list, take the minimum of shelf count and customer count
    for (const char in customerCount) {
        maxSold += Math.min(shelfCount[char] || 0, customerCount[char]);
    }
    
    return maxSold;
}

function main() {
    console.log(solution(3, 4, "abc", "abcd") === 3);
    console.log(solution(4, 2, "abbc", "bb") === 2);
    console.log(solution(5, 4, "bcdea", "abcd") === 4);
}

main();

代码解释

1. 统计频率：
   • shelfCount统计货物架上每种商品的数量。
   • customerCount统计顾客想要的每种商品的数量。
2. 计算最大售出数量：
   • 对于顾客想要的每种商品，取货物架上该商品的数量和顾客想要数量的较小值，累加到maxSold中。
3. 返回结果：
   • maxSold即为最多能卖出的商品数量。

这种方法的时间复杂度是 O(n + m)，空间复杂度是 O(1)（因为字符种类有限，最多 26 种）。

以上关于9.超市里的货物架调整的文章就介绍到这了，更多相关内容请搜索码云笔记以前的文章或继续浏览下面的相关文章，希望大家以后多多支持码云笔记。