第149场双周赛

题目总览

找到字符串中合法的相邻数字

重新安排会议得到最多空余时间I

重新安排会议得到最多空余时间II

变成好标题的最少代价

题目详解

找到字符串中合法的相邻数字

思路分析：签到题，但是可以借助这个Counter来计数，然后正常遍历即可

from collections import Counter
class Solution:
    def findValidPair(self, s: str) -> str:
        st = list(s)
        co = Counter(st)
        n = len(st)
        ans = ""
        for i in range(1,n):
            if st[i] != st[i-1] and co[st[i]] == int(st[i]) and co[st[i-1]] == int(st[i-1]):
                ans = st[i-1] + st[i]
                break
                #return ans
        return ans

重新安排会议得到最多空余时间I

思路分析：首先得将题目进行转化，计算出每段时间的空余时间，对于活动，则记空余时间为0，对于每一个k,后续使用双指针进行，定窗口滑动的时候，k+=k

class Solution:
    def maxFreeTime(self, eventTime: int, k: int, startTime: List[int], endTime: List[int]) -> int:
        # 范围会很长
        se = list(zip(startTime,endTime))
        # 已经按照开始时间的升序排序
        se.sort(key=lambda x: x[0])

        # 可以先计算出空余时间段的一个情况
        # 要是能够统计对于一个空余时间段的左边和右边距离下一个空余时间段的数目就好了
        kong = []
        for i,(s,e) in enumerate(se):
            if i == 0:
                kong.append(s-0)
                kong.append(0)
                continue
            # 计算现在的活动与上一个活动之间的空余时间
            kong.append(se[i][0] - se[i-1][1])
            kong.append(0)
        kong.append(eventTime - se[-1][1])
        # 使用双指针进行计算
        n = len(kong)
        k+=k
        nowsum = sum(kong[0:k + 1])
        ans = max(0, nowsum)
        left, right = 0, k + 1
        while right < n :
            nowsum = nowsum - kong[left] + kong[right]
            left += 1
            right += 1
            ans = max(ans, nowsum)
        # for i in range(n-k):
        #     ans = max(ans,sum(kong[i:i+k+1]))
        # 感觉上面一直调用这个sum 会超时
        return ans