现在做网站用什么软件,德阳市建设局官方网站,中医医院网站建设需求,微信头像在线制作免费文章目录 题目总览题目详解找到字符串中合法的相邻数字重新安排会议得到最多空余时间I3440.重新安排会议得到最多空余时间II 第149场双周赛 题目总览
找到字符串中合法的相邻数字
重新安排会议得到最多空余时间I
重新安排会议得到最多空余时间II
变成好标题的最少代价
题目… 文章目录 题目总览题目详解找到字符串中合法的相邻数字重新安排会议得到最多空余时间I3440.重新安排会议得到最多空余时间II 第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 ansreturn ans重新安排会议得到最多空余时间I 思路1 思路分析首先得将题目进行转化计算出每段时间的空余时间对于活动则记空余时间为0对于每一个k,后续使用双指针进行定窗口滑动的时候kk class Solution:def maxFreeTime(self, eventTime: int, k: int, startTime: List[int], endTime: List[int]) - int:# 范围会很长se list(zip(startTime,endTime))# 已经按照开始时间的升序排序se.sort(keylambda 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)kknowsum sum(kong[0:k 1])ans max(0, nowsum)left, right 0, k 1while right n :nowsum nowsum - kong[left] kong[right]left 1right 1ans max(ans, nowsum)# for i in range(n-k):# ans max(ans,sum(kong[i:ik1]))# 感觉上面一直调用这个sum 会超时return ans
参考灵神的思路 思路2 思路2是对于思路1的优化在思路1中我们对于有活动安排的设置为0这样实际上让我们的kong数组变长显得冗余多余的部分让我们的滑动窗口的长度变为了2K1 实际上我们对于n个活动总共会产生n1个空余时间段,对于重新安排的最多的k个会议实际上就是求解合并其中k1个连续的时间段所能够得到的最大的空闲时间 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:continueans max(ans, s)s - get(i - k)return ans
3440.重新安排会议得到最多空余时间II 思路分析总体来说还是继续使用上一题重新安排会议得到最多空余时间I的思路框架相当于上一题的k1不同的是由于上一题不能修改活动的相对顺序只能在相邻的两个空余时间之间移动,但是这一题可以平移出相邻的空闲时间限制,那么如何考虑这种情况我们只需记录空闲时间rest[i]的左边和右边的最大的空闲时间如果能够容纳下该活动则转移过去同时ans要加上目前的活动 from typing import Listclass 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 0for 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
