[leetcode 10-04] 一、考试的最大困扰度（双周赛的第三题）

按照自己的思路

class Solution:
    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
        def get_N(strtest, ans_str):
            cntALL = []
            ls_str = list(strtest)
            if ls_str[0] == ans_str:
                cnt = 1
                cntALL.append(cnt) 
            else:
                cnt = 0
                cntALL.append(cnt)
            for i in range(1,len( ls_str )):
                if ls_str[i] == ans_str and ls_str[i-1] == ans_str:
                    cnt += 1
                    cntALL.append(cnt)
                elif ls_str[i] == ans_str:
                    cnt = 1
                    cntALL.append(cnt)
            return max(cntALL)
        
        from itertools import combinations
        def combine(temp_list, n):
            '''根据n获得列表中的所有可能组合（n个元素为一组）'''
            temp_list2 = []
            for c in combinations(temp_list, n):
                temp_list2.append(c)
            return temp_list2

        ls_ans = list(answerKey)
        Tnum = answerKey.count('T')
        Fnum = answerKey.count('F')
        
        if Tnum <= k or Fnum <= k:  
            return len(ls_ans)
        else:     # 找到所有T F的位置 然后列出所有可能
            numsF = []
            for ix in range(len(ls_ans)):
                if ls_ans[ix] == 'F':
                    numsF.append(ix)   # 找到F的所有位置
            numsFcom = combine(numsF,k)  # 进行排序
            print(numsFcom)  # 此时k 为1 ，有 2,3 2个位置
            
            numsCnt=[]
            for key in numsFcom:
                #anstest = ls_ans  # 这是浅复制，ls_ans 也跟着改变
                anstest = [i for i in ls_ans]
                for ik in range(k):
                    ik_key = key[ik]
                    anstest[ik_key] = 'T'
                    #print(anstest)
                numsCnt.append(get_N(anstest,'T') )
            print(numsCnt)
########################################### 计算T的
            numsT = []
            for ix in range(len(ls_ans)):
                if ls_ans[ix] == 'T':
                    numsT.append(ix)   # 找到T的所有位置
            numsTcom = combine(numsT,k)  # 进行组合
            
            for key in numsTcom:
                anstest = [i for i in ls_ans]
                for ik in range(k):
                    ik_key = key[ik]
                    anstest[ik_key] = 'F'
                numsCnt.append(get_N(anstest,'F') )
                
        return max(numsCnt)
                    

时间复杂度爆表

理解了求1的个数，然后将其改写

class Solution:
    def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
        def camp(v):
            left = cnt = 0
            res = []  # 在这里将right 改为i  其值为j  用枚举的方式
            for i, j in enumerate(answerKey):  
                if j == v:  # 这里的v  比如为T
                    cnt += 1
                while cnt > k:  # 只有left 变化
                    if answerKey[left] == v:
                        cnt -= 1
                    left += 1
                res.append(i - left + 1)
            return max(res)
        return max(camp('T'), camp('F'))

这里与求1的是一样的
针对求1的个数
这个参考链接

根据这个思路写出来的解题思路

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left , right = 0, 0
        cnt = 0
        res = []
        for right in range(len(nums)):
            if nums[right] == 0:
                cnt += 1
            while cnt > k:
                if nums[left] == 0:
                    cnt -= 1
                left += 1
            res.append(right - left + 1 )
        #print(res)
        return max(res)