LeetCode 每日一题 2024/3/25-2024/3/31

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

---

3/25 518. 零钱兑换 II

完全背包问题
1.动态规划
前i个面额可以凑出j的方法
dp[i][j] = dp[i-1][j]+dp[i][j-coins[i-1]]
2.压缩 二维变一维
因为可以无限次数使用 所以j无需逆序考虑

def change(amount, coins):
    """
    :type amount: int
    :type coins: List[int]
    :rtype: int
    """
    n = len(coins)
    dp = [[0]*(amount+1) for _ in range(n+1)]
    for i in range(1,n+1):
        dp[i][0] = 1
    for i in range(1,n+1):
        for j in range(1,amount+1):
            if j - coins[i-1]>=0:
                dp[i][j] = dp[i-1][j]+dp[i][j-coins[i-1]]
            else:
                dp[i][j] = dp[i-1][j]
    return dp[n][amount]

def change2(amount, coins):
    """
    :type amount: int
    :type coins: List[int]
    :rtype: int
    """
    n = len(coins)
    dp = [0]*(amount+1)
    dp[0]=1
    for i in range(1,n+1):
        for j in range(coins[i-1],amount+1):
            dp[j] += dp[j-coins[i-1]]
    return dp[amount]


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

---

3/26 2642. 设计可以求最短路径的图类

m为邻接表 m[x]=(y,v)表示节点x能到达y并且长度为v
dijkstra
dis[x]用来存放开始节点到当前x节点最短距离
堆用来保存当前可达的所有节点 距离短的优先处理

class Graph(object):

    def __init__(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        """
        self.m = [[] for _ in range(n)]
        for x,y,v in edges:
            self.m[x].append((y,v))


    def addEdge(self, edge):
        """
        :type edge: List[int]
        :rtype: None
        """
        self.m[edge[0]].append((edge[1],edge[2]))


    def shortestPath(self, node1, node2):
        """
        :type node1: int
        :type node2: int
        :rtype: int
        """
        import heapq
        dis = [float("inf")]*len(self.m)
        dis[node1] = 0
        h = [(0,node1)]
        while h:
            d,nxt = heapq.heappop(h)
            if nxt==node2:
                return d
            if d > dis[nxt]:
                continue
            for y,v in self.m[nxt]:
                if d+v < dis[y]:
                    dis[y] = d+v
                    heapq.heappush(h,(dis[y],y))
        return -1


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

---

3/27 2580. 统计将重叠区间合并成组的方案数

按起始位置从小到大排序
记录有多少个单独的区间 num
每个单独区间都可以选择第一组或第二组
所以有2^num种方案

def countWays(ranges):
    """
    :type ranges: List[List[int]]
    :rtype: int
    """
    ranges.sort(key=lambda x:x[0])
    num = 0
    prer = -1
    for l,r in ranges:
        if l>prer:
            num +=1
        prer = max(prer,r)
    MOD=10**9+7
    return pow(2,num,MOD)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

3/28 1997. 访问完所有房间的第一天

第一次访问i 为奇数必定要返回左侧的nextVisit
只有第二次访问i 才能继续下一步i+1
此时i+1左侧必定都访问了偶数次
定义dp[i]为第一次访问i的时间
dp[i-1]为第一次访问i-1的时间
此时从i-1花一天时间回退到nextVisit[i-1]
nextVisit[i-1]出为奇数次访问 nextVisit[i-1]+1~i-2为偶数次访问
此时相当于nextVisit[i-1]被第一次访问
所以再次到i-1步数为dp[i-1]-dp[nextVisit[i-1]]
再花一天可以到达i
所以dp[i]=dp[i-1]+1+(dp[i-1]-dp[nextVisit[i-1]])+1
dp[i]=2*dp[i-1]-dp[nextVisit[i-1]]+2

def firstDayBeenInAllRooms(nextVisit):
    """
    :type nextVisit: List[int]
    :rtype: int
    """
    n = len(nextVisit)
    MOD = 10**9+7
    dp = [0]*n
    for i in range(1,n):
        dp[i] = (2*dp[i-1]-dp[nextVisit[i-1]]+2)%MOD
    return dp[-1]


1
2
3
4
5
6
7
8
9
10
11
12
13

---

3/29 2908. 元素和最小的山形三元组 I

先从左到右 l[i]记录位置i左侧比它小的最小值
同理从右到左 r[i]记录位置i右侧比它小的最小值
寻找最小和l[i]+r[i]+nums[i]

def minimumSum(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    n = len(nums)
    l = [float("inf")]*n
    r = [float("inf")]*n
    cur = nums[0]
    for i in range(1,n):
        if cur<nums[i]:
            l[i]=cur
        else:
            cur = nums[i]
    cur = nums[-1]
    for i in range(n-2,-1,-1):
        if cur<nums[i]:
            r[i]=cur
        else:
            cur = nums[i]
    ans = min([l[i]+r[i]+nums[i] for i in range(n)])
    return ans if ans!=float("inf") else -1


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

3/30 2952. 需要添加的硬币的最小数量

从小到大排序
假设当前位置为i 目标总和为s 已得到[0,s-1]的情况
如果x=coins[i] <=s
那么可以继续得到区间s~s+x-1之间的情况
如果x>s
那么我们无法得到[s,x-1]之间的数
所以必须添加s进入数组中 得到[s,2s-1] 下一个将考虑2*s的情况

def minimumAddedCoins(coins, target):
    """
    :type coins: List[int]
    :type target: int
    :rtype: int
    """
    coins.sort()
    ans = 0
    s = 1
    i = 0
    while s<=target:
        if i<len(coins) and coins[i]<=s:
            s += coins[i]
            i+=1
        else:
            s*=2
            ans+=1
    return ans


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

3/31 331. 验证二叉树的前序序列化

1.计算叶节点个数 添加一个数值必定有两个叶节点（包括#）+2,每一个值也必定是一个叶节点(-1) 最终叶节点剩余值为0
2.将节点压入栈中，根据根左右顺序如果压入的是叶节点必定左右为# 及后面两个为# 则可以将这个叶节点取出用#代替 最终stack中只剩一个#

def isValidSerialization(preorder):
    """
    :type preorder: str
    :rtype: bool
    """
    l = preorder.split(",")
    leaf = 1
    for i in l:
        leaf -=1
        if leaf<0:
            return False
        if i!="#":
            leaf+=2
    return leaf==0
              

def isValidSerialization2(preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        l = preorder.split(",")
        if len(l)>1 and (l[-1]!="#" or l[-2]!="#"):
          return False
        stack =[]
        for i in l:

            stack.append(i)
            if len(stack)<2:
                continue
            while stack[-1]=="#" and stack[-2]=="#":
                if len(stack)==2 or stack[-3]=="#":
                    return False
                stack.pop()
                stack.pop()
                stack.pop()
                stack.append("#")
                if len(stack)==1:
                    break

        if len(stack)==1 and stack[0]=="#":
            return True
        else:
            return False


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

---