周赛笔记265

一、值相等的最小索引

给你一个下标从 0 开始的整数数组 nums ，返回 nums 中满足 i mod 10 == nums[i] 的最小下标 i ；如果不存在这样的下标，返回 -1 。

x mod y 表示 x 除以 y 的 余数 。

class Solution:
    def smallestEqual(self, nums: List[int]) -> int:
        for i, num in enumerate(nums):
            if i%10 == num:
                return i
        return -1

二、找出临界点之间的最小和最大距离

class Solution:
    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:
        tmp = []
        while head:
            tmp.append(head.val)
            head = head.next
        
        n = len(tmp)
        if n<3: return [-1, -1]
        res = []
        for i in range(1,n-1):
            if (tmp[i]-tmp[i-1])*(tmp[i]-tmp[i+1])>0:
                res.append(i)
        if len(res)<2: return [-1, -1]
        a = min([res[i]-res[i-1] for i in range(1,len(res))])
        b = res[-1]-res[0]
        return [a, b]

#可以优化

三、转化数字的最小运算数⭐

给你一个下标从 0 开始的整数数组 nums ，该数组由 互不相同 的数字组成。另给你两个整数 start 和 goal 。

整数 x 的值最开始设为 start ，你打算执行一些运算使 x 转化为 goal 。你可以对数字 x 重复执行下述运算：

如果 0 <= x <= 1000 ，那么，对于数组中的任一下标 i（0 <= i < nums.length），可以将 x 设为下述任一值：

• x + nums[i]
• x - nums[i]
• x ^ nums[i]（按位异或 XOR）

注意，你可以按任意顺序使用每个 nums[i] 任意次。使 x 越过 0 <= x <= 1000 范围的运算同样可以生效，但该该运算执行后将不能执行其他运算。

返回将 x = start 转化为 goal 的最小操作数；如果无法完成转化，则返回 -1 。

# bfs
# 用集合作为优化，因为总共1001个数

class Solution:
    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:
        q = deque([(start, 0)])
        d = set(range(1001))
        vis = set([start])

        while q:
            x, res = q.popleft()
            for i, num in enumerate(nums):
                a, b, c = x+num, x-num, x^num
                for nex in [a, b, c]:
                    if nex == goal: return res+1
                    if nex in d and nex not in vis:
                        vis.add(nex)
                        q.append((nex,res+1))
                
        return -1

四、同源字符串检测

# 字符串通配的问题，类似编辑距离之类的动态规划