LeetCode#362

1.与车相交的点

给你一个下标从 0 开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i，nums[i] = [starti, endi] ，其中 starti 是第 i 辆车的起点，endi 是第 i 辆车的终点。

返回数轴上被车 任意部分 覆盖的整数点的数目。

示例 1：

输入：nums = [[3,6],[1,5],[4,7]]
输出：7
解释：从 1 到 7 的所有点都至少与一辆车相交，因此答案为 7 。

可以使用差分加前缀和达到线性时间复杂度

class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int:

        diff = [0] * 300
        for x, y in nums:
            diff[x] += 1
            diff[y + 1] -= 1
        ans = 0
        for i in range(1, 120):
            diff[i] += diff[i - 1]
            if diff[i] >= 1:
                ans += 1
        return ans

2.判断能否在给定时间到达单元格

给你四个整数 sx、sy、fx、fy 以及一个 非负整数 t 。

在一个无限的二维网格中，你从单元格 (sx, sy) 开始出发。每一秒，你 必须 移动到任一与之前所处单元格相邻的单元格中。

如果你能在 恰好 t 秒 后到达单元格 (fx, fy) ，返回 true ；否则，返回 false 。

单元格的 相邻单元格 是指该单元格周围与其至少共享一个角的 8 个单元格。你可以多次访问同一个单元格。

示例 1：

输入：sx = 2, sy = 4, fx = 7, fy = 7, t = 6
输出：true
解释：从单元格 (2, 4) 开始出发，穿过上图标注的单元格，可以在恰好 6 秒后到达单元格 (7, 7) 。 

当初始点和目标点相同时需特判(t!=1),其他情况只要满足$\max(|sx-fx|,|sy-fy|)$即可

class Solution:
    def isReachableAtTime(self, sx: int, sy: int, fx: int, fy: int, t: int) -> bool:
        if sx == fx and sy == fy and t == 1:
            return False
        mx = max(abs(sx - fx), abs(sy - fy))
        return mx <= t

3.将石头分散到网格图的最少移动次数

给你一个大小为 3 * 3 ，下标从 0 开始的二维整数矩阵 grid ，分别表示每一个格子里石头的数目。网格图中总共恰好有 9 个石头，一个格子里可能会有 多个 石头。

每一次操作中，你可以将一个石头从它当前所在格子移动到一个至少有一条公共边的相邻格子。

请你返回每个格子恰好有一个石头的 最少移动次数 。

暴搜即可，枚举两两匹配最小代价

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        n = 3
        s = []
        e = []
        mp = [[0]*n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                if grid[i][j]>1:
                    s.append((i,j))
                    mp[i][j] = grid[i][j]-1
                elif grid[i][j]<1:
                    e.append((i,j))
        ans = inf
        def dfs(i,cnt):
            if i==len(e):
                nonlocal ans
                ans = min(ans,cnt)
                return
            for x,y in s:
                if mp[x][y]>0:
                    mp[x][y]-=1
                    le = abs(x-e[i][0])+abs(y-e[i][1])
                    dfs(i+1,cnt+le)
                    mp[x][y]+=1
        dfs(0,0)        
        
        return ans

比赛时写了一个非常丑陋且慢的类状压

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:

        s1, s2 = '', ''
        for i in range(3):
            for j in range(3):
                if grid[i][j] == 0:
                    s1 += str(3 * i + j)
                elif grid[i][j] > 1:
                    s2 += str(3 * i + j) + str(grid[i][j])
        k = len(s1)
        res = ''
        for _ in range(k):
            res += '-'

        def get(c: int, c1: int) -> int:
            x1, y1 = c // 3, c % 3
            x2, y2 = c1 // 3, c1 % 3
            return abs(x1 - x2) + abs(y1 - y2)

        def do(s: str, idx: int) -> str:
            lis = list(s)
            lis[idx] = '-'
            return ''.join(c for c in lis)

        def do1(ss: str, idx: int) -> str:
            lis = list(ss)
            lis[idx] = str(int(lis[idx]) - 1)
            return ''.join(c for c in lis)

        @cache
        def dfs(s: str, ss: str) -> int:
            if s == res:
                return 0
            ans = 10 ** 9
            for idx, c in enumerate(s):
                if c == '-':
                    continue
                l = len(ss)
                for t in range(0, l, 2):
                    c1, v = int(ss[t]), int(ss[t + 1])
                    if v == 1:
                        continue
                    ans = min(ans, dfs(do(s, idx), do1(ss, t + 1)) + get(int(c), c1))
            return ans

        return dfs(s1, s2)