记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

目录

• • • 3/13 2383. 赢得比赛需要的最少训练时长
    • 3/14 1605. 给定行和列的和求可行矩阵
    • 3/15 1615. 最大网络秩
    • 3/16 2488. 统计中位数为 K 的子数组
    • 3/17 2389. 和有限的最长子序列
    • 3/18 1616. 分割两个字符串得到回文串
    • 3/19

3/13 2383. 赢得比赛需要的最少训练时长

一次遍历 如果无法击败则增加训练时间

def minNumberOfHours(initialEnergy, initialExperience, energy, experience):""":type initialEnergy: int:type initialExperience: int:type energy: List[int]:type experience: List[int]:rtype: int"""ans = 0curen,curex = initialEnergy,initialExperiencefor i in range(len(energy)):print(i,ans,curen,curex)if curex<=experience[i]:ans += experience[i]+1-curexcurex = experience[i]+1curex += experience[i]curen -= energy[i]if curen<=0:ans =ans - curen+1curen=1return ans

3/14 1605. 给定行和列的和求可行矩阵

既然必定存在一个答案 各行和总数=各列和总数
目的是找到分配数值的方案
根据n,m = len(rowSum),len(colSum)
我们可以知道答案是一个n*m的矩阵
1.可以先将列之和分配到第一行的各列之中
例:rowSum = [5,7,10], colSum = [8,6,8]
8,6,8
0,0,0
0,0,0
此后数值的增减操作只在同一列中进行
所以每列之和已经满足条件不需要再考虑
2.依次根据rowSum 通过减去数值来使该行和满足条件
减去的数值增加到该列中的下一行中(列之和不变)
处理第一行
5,0,0
3,6,8
0,0,0
处理第二行
5,0,0
3,4,0
0,2,8
此时第三行自动满足条件

def restoreMatrix(rowSum, colSum):""":type rowSum: List[int]:type colSum: List[int]:rtype: List[List[int]]"""n,m = len(rowSum),len(colSum)ans = [[0]*m for _ in range(n)]ans[0] = colSum[:]for i in range(n-1):target = rowSum[i]for j in range(m):if target>=ans[i][j]:target-=ans[i][j]else:tmp = ans[i][j]ans[i][j] = targetans[i+1][j] = tmp-targettarget = 0return ans

3/15 1615. 最大网络秩

遍历所有路 记录每个节点拥有的道路 以及其连接的其他节点
选取两两节点 计算其拥有的秩

def maximalNetworkRank(n, roads):""":type n: int:type roads: List[List[int]]:rtype: int"""from collections import defaultdictway = defaultdict(int)nxt = defaultdict(set)for i,j in roads:way[i]+=1way[j]+=1nxt[i].add(j)nxt[j].add(i)ans = 0for i in range(n-1):for j in range(i+1,n):tmp = way[i]+way[j]if j in nxt[i]:tmp-=1ans = max(ans,tmp)return ans

3/16 2488. 统计中位数为 K 的子数组

根据题意k是必须选择的
找到k的位置
该位置标签设定为0
分别向左右判断标签 比k大的+1 比k小的-1
记录左右各个位置标签状态
从左右分别选取一个位置标签 使其相加等于0或1 可以满足条件

def countSubarrays(nums, k):""":type nums: List[int]:type k: int:rtype: int"""from collections import defaultdictn = len(nums)ind = 0left,right=defaultdict(int),defaultdict(int)for i in range(n):if nums[i]==k:ind=ibreakcur = 0for i in range(ind+1,n):if nums[i]

def answerQueries(nums, queries):""":type nums: List[int]:type queries: List[int]:rtype: List[int]"""from itertools import accumulateimport bisectnums.sort()s = list(accumulate(nums))return [bisect.bisect_right(s, q) for q in queries]

def checkPalindromeFormation(a, b):""":type a: str:type b: str:rtype: bool"""n = len(a)def check(a,b):i,j=0,n-1while i=j or a[i:j+1]==a[i:j+1][::-1] or b[i:j+1]==b[i:j+1][::-1]return check(a,b) or check(b,a)