LC-6250. 商店的最少代价(枚举+前缀和)【双周赛92】
admin
2024-02-21 19:51:09
0次

6250. 商店的最少代价

难度中等0

给你一个顾客访问商店的日志,用一个下标从 0 开始且只包含字符 'N' 和 'Y' 的字符串 customers 表示:

  • 如果第 i 个字符是 'Y' ,它表示第 i 小时有顾客到达。
  • 如果第 i 个字符是 'N' ,它表示第 i 小时没有顾客到达。

如果商店在第 j 小时关门(0 <= j <= n),代价按如下方式计算:

  • 在开门期间,如果某一个小时没有顾客到达,代价增加 1 。
  • 在关门期间,如果某一个小时有顾客到达,代价增加 1 。

请你返回在确保代价 最小 的前提下,商店的 最早 关门时间。

注意,商店在第 j 小时关门表示在第 j 小时以及之后商店处于关门状态。

示例 1:

输入:customers = "YYNY"
输出:2
解释:
- 第 0 小时关门,总共 1+1+0+1 = 3 代价。
- 第 1 小时关门,总共 0+1+0+1 = 2 代价。
- 第 2 小时关门,总共 0+0+0+1 = 1 代价。
- 第 3 小时关门,总共 0+0+1+1 = 2 代价。
- 第 4 小时关门,总共 0+0+1+0 = 1 代价。
在第 2 或第 4 小时关门代价都最小。由于第 2 小时更早,所以最优关门时间是 2 。

示例 2:

输入:customers = "NNNNN"
输出:0
解释:最优关门时间是 0 ,因为自始至终没有顾客到达。

示例 3:

输入:customers = "YYYY"
输出:4
解释:最优关门时间是 4 ,因为每一小时均有顾客到达。

提示:

  • 1 <= customers.length <= 105
  • customers 只包含字符 'Y' 和 'N' 。

枚举+前缀和

题解来自TsReaper:https://leetcode.cn/circle/discuss/YBhcDT/

为了方便计算前(后)缀和,我们认为 customers 的下标是从 1 开始的,最后答案减 1 即可。

维护 f(i)f(i)f(i) 表示第 111 到第 $i $个字符有几个 N(初值 f(0)=0f(0) = 0f(0)=0),g(i)g(i)g(i) 表示第 iii 到第 nnn 个字符有 几个 Y(初值 g(n+1)=0g(n + 1) = 0g(n+1)=0),那么第 hhh 小时关店的代价即为 f(h−1)+g(h)f(h - 1) + g(h)f(h−1)+g(h)。

从 111 到 (n+1)(n + 1)(n+1) 枚举所有 hhh 并选出代价最小的即可。复杂度 O(n)\mathcal{O}(n)O(n)。

Java

class Solution {public int bestClosingTime(String customers) {int n = customers.length();int[] f = new int[n+2];int[] g = new int[n+2];//计算前缀有几个Nf[0] = 0; // 认为下标从1开始,最后答案减1for(int i = 1; i <= n; i++){f[i] = f[i-1] + (customers.charAt(i-1) == 'N' ? 1 : 0); }//计算后缀有几个Yg[n+1] = 0;for(int i = n; i > 0; i--){g[i] = g[i+1] + (customers.charAt(i-1) == 'Y' ? 1 : 0);}//依次遍历找最少代价int ans = 0,best = (int)1e9;for(int i = 1; i <= n + 1; i++){int tmp = f[i-1] + g[i];if(tmp < best){ans = i;best = tmp;}}return ans-1;}
}

c++

class Solution {
public:int bestClosingTime(string customers) {int n = customers.size();int f[n + 2], g[n + 2];// 计算前缀有几个 Nf[0] = 0;for (int i = 1; i <= n; i++) f[i] = f[i - 1] + (customers[i - 1] == 'N' ? 1 : 0);// 计算后缀有几个 Yg[n + 1] = 0;for (int i = n; i > 0; i--) g[i] = g[i + 1] + (customers[i - 1] == 'Y' ? 1 : 0);// 枚举答案int ans = 0, best = 1e9;for (int i = 1; i <= n + 1; i++) {int tmp = f[i - 1] + g[i];if (tmp < best) ans = i, best = tmp;}return ans - 1;}
};

自己的不优雅解法(找规律)

观察到第 i 小时关门时0-i-1 的代价 与 第 i-1小时关门的代价是相同的,那么通过预先计算有多少Y,然后依次遍历找最小代价

class Solution {public int bestClosingTime(String customers) {int n = customers.length();char[] arr = customers.toCharArray();int from = 0,to = 0;for(int i = 0; i < n; i++){if(arr[i] == 'Y') from++;}to = n - from; // from 起始Y的个数,to 起始N的个数int cost = from;int ans = 0;for(int i = 1; i <= n; i++){ // 第i小时关门if(arr[i-1] == 'Y'){from--;}else{from++;}if(from < cost){ans = i;cost = from;}}return ans;
}
}

暴力(超时)


class Solution {public int bestClosingTime(String customers) {int cost = Integer.MAX_VALUE;int ans = 0;int n = customers.length();char[] arr = customers.toCharArray();for(int i = 0; i <= n; i++){ // 第i小时关门int tmp = 0;for(int j = 0; j < i; j++){ // 未关门if(arr[j] == 'Y'){continue;}else{tmp++;}}for(int j = i; j < n; j++){ // 已关门if(arr[j] == 'Y'){tmp++;}else continue;}if(tmp < cost){cost = tmp;ans = i;}}return ans;
}
}

相关内容

热门资讯

AI做攻略、“双向奔赴”……国... 本文转自:人民网人民网记者 许维娜今年国庆假期,AI(人工智能)成了不少年轻人的“旅行搭子”。行前做...
合肥的这个“梗”, 翻篇了 社交平台的评论区,曾长期流传一句专属于合肥的黑色幽默。有人问合肥哪里好玩,本地网友半开玩笑地回复:合...
7万+旅游中高层都在的群,今天... 做旅游这行,资源卡位、渠道互通、项目落地——往往就差一个“对的机会”。我们的行业社群已聚集70,00...
一场帐篷音乐节,如何让井研从“... 帐篷音乐节现场封面新闻记者 周洪攀10月的研溪湿地,晚风里裹着柑橘的清甜与民谣的回响。夜幕降临,10...
白鹤翩翩落星愿,上海迪士尼度假... 10月9日,世界候鸟日前夕,上海迪士尼度假区星愿公园的湖风里多了一分白鹤的灵动。三座白鹤雕塑正式揭幕...
成都锦江边赏初秋枫叶飘飘 目前,成都锦江边国华街枫叶树红了。近年来,国华街附近的几条街都栽种了红枫树,是城区较集中看枫叶的点位...
GBTA:商务旅行正在复苏,但... 亚太正在成为全球商务旅行增长的重要引擎。在经历疫情后的快速反弹之后,全球商务旅行正在进入一个新的增长...
从景区焕新到节赛引流 邹城双节... 齐鲁网·闪电新闻10月9日讯 中秋、国庆“双节”假期,邹城市文化和旅游局提前谋划、周密部署,立足自身...
江山如此多娇 且看石楼今朝 金秋十月,黄河岸畔秋意盎然,丰收盛会喜迎国庆。本次石楼国庆文旅活动以“江山如此多娇,且看石楼今朝”为...
海南国庆假期接待游客475.4... 2026年国庆假期,海南接待游客475.40万人次,较2025年增长13.1%,较2024年增长15...