力扣第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

思路1：
思路分析：首先得将题目进行转化，计算出每段时间的空余时间，对于活动，则记空余时间为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
            

参考灵神的思路

思路2：
思路2是对于思路1的优化，在思路1中，我们对于有活动安排的设置为0，这样实际上，让我们的kong数组变长，显得冗余，多余的部分，让我们的滑动窗口的长度变为了2K+1
实际上，我们对于n个活动，总共会产生n+1个空余时间段,对于重新安排的最多的k个会议，实际上就是求解合并其中k+1个连续的时间段，所能够得到的最大的空闲时间

class Solution:
    def maxFreeTime(self, eventTime: int, k: int, startTime: List[int], endTime: List[int]) -> int:
    	# 获得对应的空闲时间
        def get(i: int) -> int:
            if i == 0:
                return startTime[0]
            if i == n:
                return eventTime - endTime[-1]
            return startTime[i] - endTime[i - 1]

        n = len(startTime)
        ans = s = 0
        # 定长滑动窗口的模版
        for i in range(n + 1):
            s += get(i)
            if i < k:
                continue
            ans = max(ans, s)
            s -= get(i - k)
        return ans

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

思路分析：总体来说，还是继续使用上一题：重新安排会议得到最多空余时间I的思路框架相当于上一题的k=1，不同的是，由于上一题不能修改活动的相对顺序，只能在相邻的两个空余时间之间移动,但是这一题可以平移出相邻的空闲时间限制,那么如何考虑这种情况？我们只需记录，空闲时间rest[i]的左边和右边的最大的空闲时间，如果能够容纳下该活动，则转移过去，同时ans要加上目前的活动

from typing import List

class Solution:
    def maxFreeTime(self, eventTime: int, startTime: List[int], endTime: List[int]) -> int:
        """
        计算最大空闲时间
        :param eventTime: 事件的总时间
        :param startTime: 每个事件的开始时间列表
        :param endTime: 每个事件的结束时间列表
        :return: 最大空闲时间
        """
        n = len(startTime)
        if n == 0:
            return 0

        # 计算每个间隔的空闲时间
        rest = [0] * (n + 1)
        for i in range(n + 1):
            if i == 0:
                rest[i] = startTime[0]  # 第一个事件之前的空闲时间
            elif i == n:
                rest[i] = eventTime - endTime[n - 1]  # 最后一个事件之后的空闲时间
            else:
                rest[i] = startTime[i] - endTime[i - 1]  # 事件之间的空闲时间

        # 计算每个间隔左边的最大空闲时间
        left = [0] * (n + 1)
        for i in range(1, n + 1):
            left[i] = max(left[i - 1], rest[i - 1])

        # 计算每个间隔右边的最大空闲时间
        right = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            right[i] = max(right[i + 1], rest[i + 1])

        # 计算最大空闲时间
        ans = 0
        for i in range(n):
            # 当前两个连续的空闲时间
            current_rest = rest[i] + rest[i + 1]
            # 当前活动的时间
            act_time = endTime[i] - startTime[i]
            # 如果左边或右边的最大空闲时间大于当前活动时间，则将其加入
            if left[i] >= act_time or right[i + 1] >= act_time:
                current_rest += act_time
            # 更新最大空闲时间
            ans = max(ans, current_rest)

        return ans