难度中等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 <= 105customers 只包含字符 '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;
}
}