Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
考卷的所有题目的答案用一列T、F组成的字符串表示,可以操作k次,将T改成F或将F改成T,问最多可以制造多少个连续的T或者F
思路参考 -> https://leetcode.com/problems/maximize-the-confusion-of-an-exam/solutions/3729656/video-solution-sliding-window-2-pointers/
维护两个游标i和j,j走在前,当i~j之间T和F之中最少出现的那一个超过k次时,将这一区间的统一改为T或者F


 1 #2024
 2 #Runtime: 298 ms (Beats 84.38%)
 3 #Memory: 13.6 MB (Beats 96.88%)
 4 
 5 class Solution(object):
 6     def maxConsecutiveAnswers(self, answerKey, k):
 7         """
 8         :type answerKey: str
 9         :type k: int
10         :rtype: int
11         """
12         cnt_F, cnt_T = 0, 0
13         i, j = 0, 0
14         ans = 0
15         while j < len(answerKey):
16             if answerKey[j] == 'F':
17                 cnt_F += 1
18             else:
19                 cnt_T += 1
20             while min(cnt_T, cnt_F) > k:
21                 if answerKey[i] == 'F':
22                     cnt_F -= 1
23                 else:
24                     cnt_T -= 1
25                 i += 1
26             ans = max(ans, cnt_F + cnt_T)
27             j += 1
28         return ans

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