Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一列字符串,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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理