周赛笔记239

一、到目标元素的最小距离

给你一个整数数组 nums （下标 从 0 开始 计数）以及两个整数 target 和 start ，请你找出一个下标 i ，满足 nums[i] == target 且 abs(i - start) 最小化 。

class Solution:
    def getMinDistance(self, nums: List[int], target: int, start: int) -> int:
        return min([abs(i-start) for i in range(len(nums)) if nums[i]==target])

二、将字符串拆分为递减的连续值

class Solution:
    def dfs(self, s: str, start: int, last: int):
        if self.ans:
            return
        
        n = len(s)
        if start == n:
            self.ans = True
            return
        
        now = 0
        hi = n if start != 0 else n - 1
        for i in range(start, hi):
            now = now * 10 + ord(s[i]) - ord('0')
            if start == 0 or now == last - 1:
                self.dfs(s, i + 1, now)
            if start != 0 and now >= last:
                return
    
    def splitString(self, s: str) -> bool:
        if len(s) == 1:
            return False
        
        self.ans = False
        self.dfs(s, 0, 0)
        return self.ans

# copy

三、邻位交换的最小次数

# 模拟+贪心

四、包含每个查询的最小区间

#TLE

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        d = {}
        for l, r in intervals:
            a = r-l+1
            for i in range(l, r+1):
                if i in d:
                    d[i] = min(a, d[i])
                else:
                    d[i] = a
        ans = []
        for x in queries:
            if x in d:
                ans.append(d[x])
            else:
                ans.append(-1)
        return ans