LeetCode 每日一题 2023/12/11-2023/12/17

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

---

12/11 1631. 最小体力消耗路径

dijstra
最小堆 找到当前最小的路径

import heapq
def minimumEffortPath(heights):
    """
    :type heights: List[List[int]]
    :rtype: int
    """
    m,n = len(heights),len(heights[0])
    dist = [0]+[float("inf")]*(m*n-1)
    q = [(0,0,0)]
    path =set()
    
    while q:
        d,x,y = heapq.heappop(q)
        idx = x*n+y
        if idx in path:
            continue
        if (x,y)==(m-1,n-1):
            break
        path.add(idx)
        for xx,yy in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:
            if 0<=xx<m and 0<=yy<n:
                maxd = max(d,abs(heights[x][y]-heights[xx][yy]))
                if maxd<=dist[xx*n+yy]:
                    dist[xx*n+yy] = maxd
                    heapq.heappush(q,(dist[xx*n+yy],xx,yy))
    return dist[m*n-1]

---

12/12 2454. 下一个更大元素 IV

将数值从大到小排序 并记录其坐标(num,i)
使用一个有序队列s记录已经处理过的坐标
对于当前处理的nums[x] s中所有数值都比其大 只要找到比x大的下下个元素值
即为nums[x]对应的第二大元素坐标

def secondGreaterElement(nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    from sortedcontainers import SortedList
    l = [(x,i) for i,x in enumerate(nums)]
    l.sort(key=lambda x:-x[0])
    s = SortedList()
    n = len(nums)
    ans = [-1]*n
    for _,i in l:
        loc = s.bisect_right(i)
        if loc+1<len(s):
            ans[i] = nums[s[loc+1]]
        s.add(i)
    return ans

---

12/13 2697. 字典序最小回文串

左右指针依次比较 对应的位置需要相同且使用字典序小的字母

def makeSmallestPalindrome(s):
    """
    :type s: str
    :rtype: str
    """
    l,r=0,len(s)-1
    li = [""]*len(s)
    while l<=r:
        c = s[l]
        if s[r]<s[l]:
            c=s[r]
        li[l]=li[r]=c
        l+=1
        r-=1
    return ''.join(li)

---

12/14 2132. 用邮票贴满网格图

二维前缀和判断是否可以贴邮票
二维差分判断是否所有空格子被覆盖

def possibleToStamp(grid, stampHeight, stampWidth):
    """
    :type grid: List[List[int]]
    :type stampHeight: int
    :type stampWidth: int
    :rtype: bool
    """
    m,n=len(grid),len(grid[0])
    psum = [[0]*(n+2) for _ in range(m+2)]
    diff = [[0]*(n+2) for _ in range(m+2)]
    
    for i in range(1,m+1):
        for j in range(1,n+1):
            psum[i][j] = psum[i-1][j]+psum[i][j-1]-psum[i-1][j-1]+grid[i-1][j-1]
            
    for i in range(1,m+2-stampHeight):
        for j in range(1,n+2-stampWidth):
            x = i+stampHeight-1
            y = j+stampWidth-1
            if psum[x][y]-psum[x][j-1]-psum[i-1][y]+psum[i-1][j-1]==0:
                diff[i][j]+=1
                diff[i][y+1]-=1
                diff[x+1][j]-=1
                diff[x+1][y+1]+=1
    for i in range(1,m+1):
        for j in range(1,n+1):
            diff[i][j] += diff[i-1][j]+diff[i][j-1]-diff[i-1][j-1]
            if diff[i][j]==0 and grid[i-1][j-1]==0:
                return False
    return True

---

12/15 2415. 反转二叉树的奇数层

BFS

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
def reverseOddLevels(root):
    """
    :type root: Optional[TreeNode]
    :rtype: Optional[TreeNode]
    """
    li = [root]
    lev = 0
    while len(li)>0:
        if lev%2==1:
            l,r=0,len(li)-1
            while l<r:
                x,y = li[l],li[r]
                x.val,y.val=y.val,x.val
                l+=1
                r-=1
        tmp=[]
        for node in li:
            if not node.left:
                break
            tmp.append(node.left)
            tmp.append(node.right)
        lev+=1
        li = tmp
    return root

---

12/16 2276. 统计区间中的整数数目

线段树
l,r为左右端点 cnt为区间内整数个数
如果当前区间全覆盖 则cnt=r-l+1

class CountIntervals(object):

    def __init__(self,l=1,r=10**9):
        self.left = self.right = None
        self.l,self.r,self.cnt=l,r,0
        


    def add(self, left, right):
        """
        :type left: int
        :type right: int
        :rtype: None
        """
        if self.cnt == self.r-self.l+1:
            return
        if left<=self.l and self.r<=right:
            self.cnt = self.r-self.l+1
            return
        mid = (self.l+self.r)//2
        if self.left is None:
            self.left = CountIntervals(self.l,mid)
        if self.right is None:
            self.right = CountIntervals(mid+1,self.r)
        if left<=mid:
            self.left.add(left,right)
        if mid<right:
            self.right.add(left,right)
        self.cnt = self.left.cnt+self.right.cnt
        


    def count(self):
        """
        :rtype: int
        """
        return self.cnt

---

12/17

---