Posted on 2023-08-29 22:22
Uriel 閱讀(27)
評論(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