Posted on 2023-08-29 22:22
Uriel 阅读(11)
评论(0) 编辑 收藏 引用 所属分类:
闲来无事重切Leet Code
给出一列字符串，N表示此刻没有顾客，Y表示此刻有顾客进入，若此刻没有顾客但仍在营业，那么penalty+1，若此刻有顾客到但已经不营业，那么penalty+1，问几点关门penalty最小
对Y和N分别计算suffix和prefix sum，然后扫一遍取最小
1 #2483
2 #Runtime: 194 ms (Beats 34.48%)
3 #Memory: 21.8 MB (Beats 20.69%)
4
5 class Solution(object):
6 def bestClosingTime(self, customers):
7 """
8 :type customers: str
9 :rtype: int
10 """
11 pre_sum1 = [0]
12 pre_sum2 = [0]
13 for ch in customers[::-1]:
14 if ch == 'Y':
15 pre_sum1.append(pre_sum1[-1] + 1)
16 else:
17 pre_sum1.append(pre_sum1[-1])
18 pre_sum1 = pre_sum1[::-1]
19 for ch in customers:
20 if ch == 'N':
21 pre_sum2.append(pre_sum2[-1] + 1)
22 else:
23 pre_sum2.append(pre_sum2[-1])
24 ans = pre_sum1[0] + pre_sum2[0]
25 fg = 0
26 for i in range(1, len(customers) + 1):
27 if pre_sum1[i] + pre_sum2[i] < ans:
28 ans = pre_sum1[i] + pre_sum2[i]
29 fg = i
30 return fg