周赛笔记212

第一题：https://leetcode-cn.com/problems/slowest-key/
第二题：https://leetcode-cn.com/problems/arithmetic-subarrays/
第三题：https://leetcode-cn.com/problems/path-with-minimum-effort/
第四题：https://leetcode-cn.com/problems/rank-transform-of-a-matrix/

一、按键持续时间最长的键

class Solution:
    def slowestKey(self, releaseTimes: List[int], keysPressed: str) -> str:
        ans,t=0,0
        tmp=[releaseTimes[0]]
        for i in range(len(releaseTimes)-1):
            tmp.append(releaseTimes[i+1]-releaseTimes[i])
        #print(tmp)
        for i,time in enumerate(tmp):
            if time>t: 
                ans,t=keysPressed[i],time
            elif time==t: 
                ans=max(keysPressed[i],ans)
            #print(ans,t)
        return ans

二、等差子数组

class Solution:
    def checkArithmeticSubarrays(self, nums: List[int], l: List[int], r: List[int]) -> List[bool]:
        def check(arr):
            tmp=arr[1]-arr[0]
            for i in range(len(arr)-2):
                if arr[i+2]-arr[i+1]!=tmp:
                    return False
            return True
        ans=[]
        for i in range(len(r)):
            t=nums[l[i]:r[i]+1]
            t.sort()
            #print(i,t)
            ans.append(check(t))
        return ans

三、 最小体力消耗路径

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。

请你返回从左上角走到右下角的最小 体力消耗值 。

# dfs回溯超时
# 目的性不强，hhh
class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        
        self.ans=float('inf')
        rows,cols=len(heights),len(heights[0])
        
        def dfs(x,y,travel,hp):
            if x==rows-1 and y==cols-1: 
                self.ans=min(self.ans,hp)
                return 
            for nx,ny in [(x,y-1),(x,y+1),(x-1,y),(x+1,y)]:
                if 0<=nx<rows and 0<=ny<cols:
                    if (nx,ny) not in travel:
                        travel.append((nx,ny))
                        dfs(nx,ny,travel,max(hp,abs(heights[nx][ny]-heights[x][y])))
                        travel.pop()
        dfs(0,0,[(0,0)],0)
        return self.ans

# copy的bfs+二分:
class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        m, n = len(heights), len(heights[0])

        mat = [[0]*n for _ in range(m)]

        l, r = 0, 999999
        while l < r:
            mid = (l + r)//2
            mat = [[0]*n for _ in range(m)]
            mat[0][0] = 1
            queue = deque([(0, 0)])
            while queue:
                i, j = queue.popleft()
                for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
                    if 0<=x<m and 0<=y<n and mat[x][y]==0 and abs(heights[i][j] - heights[x][y]) <= mid:
                        queue.append((x, y))
                        mat[x][y] = 1
            if mat[-1][-1] == 1:
                r = mid
            else:
                l = mid + 1
        return l

四、矩阵转换后的秩

# copy: 全排序+并查集
class Solution: 
    def matrixRankTransform(self, matrix: List[List[int]]) -> List[List[int]]: 
        R, C = len(matrix), len(matrix[0])
        res = [[0]*C for _ in range(R)]
        countR, countC = [0]*R, [0]*C
        
        # 按元素大小分别存储元素坐标
        ls = collections.defaultdict(list)
        for r, row in enumerate(matrix): 
            for c, val in enumerate(row): 
                ls[val].append((r, c))
                
        # 并查集用于合并行或列相同的元素
        union = list(range(LIM*2))
        def find(i): 
            if union[i] == i: return i
            union[i] = find(union[i])
            return union[i]
        
        # 按val从小到大遍历
        pool = collections.defaultdict(list)
        for val in sorted(ls.keys()): 

            # 用并查集合并行和列相同的元素并分组
            for r, c in ls[val]: 
                union[find(r)] = find(c+LIM)
            pool.clear()
            for r, c in ls[val]: 
                pool[find(r)].append((r, c))

                
            # 行和列相同的元素，共享相同的rank
            for group in pool.values(): 
                rank = max(max((countR[r], countC[c])) for r, c in group) + 1
                for r, c in group: 
                    countR[r] = countC[c] = res[r][c] = rank

                    # 重置并查集
                    union[r] = r
                    union[c+LIM] = c+LIM
        return res