周赛笔记211

第一题：https://leetcode-cn.com/problems/largest-substring-between-two-equal-characters/
第二题：https://leetcode-cn.com/problems/lexicographically-smallest-string-after-applying-operations/
第三题：https://leetcode-cn.com/problems/best-team-with-no-conflicts/
第四题：https://leetcode-cn.com/problems/graph-connectivity-with-threshold/

一、两个相同字符之间的最长子字符串

给你一个字符串 s，请你返回 两个相同字符之间的最长子字符串的长度 ，计算长度时不含这两个字符。如果不存在这样的子字符串，返回 -1 。

子字符串 是字符串中的一个连续字符序列。

class Solution:
    def maxLengthBetweenEqualCharacters(self, s: str) -> int:
        d=defaultdict(list)
        ans=-1
        for i,x in enumerate(s):
            d[x].append(i)
        for i in d.items():
            nums=i[1]
            if len(nums)>1:
                ans=max(ans,nums[-1]-nums[0]-1)
        return ans

二、执行操作后字典序最小的字符串

#暴力
class Solution:
    def findLexSmallestString(self, s: str, a: int, b: int) -> str:
        b = b%len(s)
        def f1(s):
            tmp=""
            for i in range(len(s)):
                if i%2==0: tmp+=s[i]
                else: tmp+=str((int(s[i])+a)%10)
            return tmp
        def f2(s):
            return s[-b:]+s[:-b]
        ans={s}
        def dfs(s):
            ans.add(s)
            s1,s2=f1(s),f2(s)
            for i in (s1,s2):
                if i not in ans: dfs(i)
        dfs(s)
        return min(ans)

三、无矛盾的最佳球队

假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。

然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。

给你两个列表 scores 和 ages，其中每组 scores[i] 和 ages[i] 表示第 i 名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数 。

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        n = len(scores)
        arr = list(zip(ages, scores))
        arr.sort() # 按年龄递增排序，年龄相同的按分数递增排序
        #print(arr)
        dp = [arr[i][1] for i in range(n)]
        for i in range(n):              #类似最长上升子序列问题
            for j in range(i):
                if arr[i][1] >= arr[j][1]:
                    dp[i] = max(dp[i], dp[j]+arr[i][1])
        return max(dp)

# DPxiu

# 优化版：
class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        import bisect
        d = [(score, age) for age, score in zip(ages, scores)]
        d.sort()
        n = len(d)
        res = 0
        stack = [(0,0)]
        # print(d)
        for i in range(n):
            score, age = d[i]
            idx = bisect.bisect_right(stack, (age,float('inf')))
            s = stack[idx-1][1]
            res = max(res, s+score)
            while idx < len(stack) and stack[idx][1] <= s+score:
                stack.pop(idx)
            stack[idx:idx] = [(age, s+score)]
            while len(stack) >= 2 and stack[-1][1] <= stack[-2][-1]:
                stack.pop()
        # print(stack)
        return res

四、带阈值的图连通性

# 并查集