LeetCode 每日一题 2023/8/28-2023/9/3

def minimumJumps(forbidden, a, b, x):
    """
    :type forbidden: List[int]
    :type a: int
    :type b: int
    :type x: int
    :rtype: int
    """
    s = set(forbidden)
    ans = 0
    l = [(0,1)]
    mem={(0,1)}
    while l:
        tmp = []
        for loc,k in l:
            if loc==x:
                return ans
            nxt = [(loc+a,1)]
            if k==1:
                nxt.append((loc-b,-1))
            for i,k in nxt:
                if i not in s and 0<=i<6000 and (i,k) not in mem:
                    tmp.append((i,k))
                    mem.add((i,k))
        ans+=1
        l=tmp
    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

8/31 1761. 一个图中连通三元组的最小度数

m[i][j]记录i,j的连通情况
deg[i] 记录i的出度

def minTrioDegree(n, edges):
    """
    :type n: int
    :type edges: List[List[int]]
    :rtype: int
    """
    deg = [0]*n
    m = [[0]*n for i in range(n)]
    for x,y in edges:
        x,y = x-1,y-1
        m[x][y] = m[y][x] = 1
        deg[x]+=1
        deg[y]+=1
        
    ans = float("inf")
    for i in range(n):
        for j in range(i+1,n):
            if m[i][j]==1:
                for k in range(j+1,n):
                    if m[i][k]==m[j][k]==1:
                        ans = min(ans,deg[i]+deg[j]+deg[k]-6)
    return -1 if ans==float("inf") else ans



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

9/1 2240. 买钢笔和铅笔的方案数

遍历可以买钢笔的个数 累加各个情况下可以买铅笔的个数

def waysToBuyPensPencils(total, cost1, cost2):
    """
    :type total: int
    :type cost1: int
    :type cost2: int
    :rtype: int
    """
    ans = 0
    for i in range(total//cost1):
        ans += (total -i*cost1)//cost2+1
    return ans



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

9/2 2511. 最多可以摧毁的敌人城堡数目

从头遍历记录前一个自己城堡位置x 和 空位置y

def captureForts(forts):
    """
    :type forts: List[int]
    :rtype: int
    """
    x,y=-1,-1
    ans = 0
    for i,v in enumerate(forts):
        if v==-1:
            if x>-1:
                ans = max(i-1-x,ans)
            x,y=-1,i
        elif v==1:
            if y>-1:
                ans = max(i-1-y,ans)
            x,y=i,-1
    return ans



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

9/3 1921. 消灭怪物的最大数量

计算每个怪物到城市的时间 从小到大排序
遍历每个怪物是否能在其到达前被消灭

def eliminateMaximum(dist, speed):
    """
    :type dist: List[int]
    :type speed: List[int]
    :rtype: int
    """
    n = len(dist)
    t=[0]*n
    for i in range(n):
        t[i] = dist[i]*1.0/speed[i]
    t.sort()
    ans = 0
    for i,v in enumerate(t):
        if i<v:
            ans+=1
        else:
            break
    return ans


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