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

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

---

9/11 630. 课程表 III

将期限日期从小到大排序
将耗时放入大顶堆中 如果当前耗时无法满足 但是比堆中最大值小时 进行替换

def scheduleCourse(courses):
    """
    :type courses: List[List[int]]
    :rtype: int
    """
    import heapq
    l=[]
    heapq.heapify(l)
    courses.sort(key = lambda x:x[1])
    now = 0
    for d,last in courses:
        if now+d<=last:
            now +=d
            heapq.heappush(l,-d)
        elif l and -l[0]>d:
            now = now+l[0]+d
            heapq.heappop(l)
            heapq.heappush(l,-d)
    return len(l)


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

---

9/12 1462. 课程表 IV

m[i][j]记录i是否依赖j
dg[i]记录当前i是否还有依赖未考虑
g[i]记录i依赖的课程
bfs l中存放当前无课程依赖可以考虑的课程

def checkIfPrerequisite(numCourses, prerequisites, queries):
    """
    :type numCourses: int
    :type prerequisites: List[List[int]]
    :type queries: List[List[int]]
    :rtype: List[bool]
    """
    m = [[False]*numCourses for _ in range(numCourses)]
    dg = [0]*numCourses
    g = [[] for _ in range(numCourses)]
    for p in prerequisites:
        dg[p[1]] +=1
        g[p[0]].append(p[1])
        
    l = []
    for i in range(numCourses):
        if dg[i]==0:
            l.append(i)
        
    while l:
        tmp = []
        for cur in l:
            for nx in g[cur]:
                m[cur][nx] = True
                for i in range(numCourses):
                    m[i][nx] = m[i][cur] or m[i][nx]
                dg[nx]-=1
                if dg[nx]==0:
                    tmp.append(nx)
        l= tmp
    ans = []
    for q in queries:
        ans.append(m[q[0]][q[1]])
    return 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
26
27
28
29
30
31
32
33
34
35
36

---

9/13 2596. 检查骑士巡视方案

规定从左上角出发 判断grid[0][0]是否为0
从当前位置向八个方向遍历是否能够到达下一个点

def checkValidGrid(grid):
    """
    :type grid: List[List[int]]
    :rtype: bool
    """
    x,y=0,0
    n = len(grid)
    if grid[0][0]!=0:
        return False
    steps=[(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]
    
    cur = 0
    while cur<n*n-1:
        tag = True
        for i,j in steps:
            nx,ny = x+i,y+j
            if 0<=nx<n and 0<=ny<n and grid[nx][ny]==cur+1:
                cur +=1
                x,y=nx,ny
                tag = False
                break
        if tag:
            return False
    return True



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

---

9/14 1222. 可以攻击国王的皇后

mem记录八个方向皇后可以攻击到国王的最近距离

def queensAttacktheKing(queens, king):
    """
    :type queens: List[List[int]]
    :type king: List[int]
    :rtype: List[List[int]]
    """
    mem = {}    
    for x,y in queens:
        i,j=0,0
        v = 0
        if x==king[0]:
            v = abs(y-king[1])
            j = (y-king[1])//v
        elif y==king[1]:
            v = abs(x-king[0])
            i = (x-king[0])//v
        else:
            v = abs(x-king[0])
            if v!=abs(y-king[1]):
                continue
            i = (x-king[0])//v
            j = (y-king[1])//v
        if (i,j) not in mem:
            mem[(i,j)] = v
        else:
            if v<mem[(i,j)]:
                mem[(i,j)] = v
    ans = []
    for (i,j),v in mem.items():
        ans.append([king[0]+i*v,king[1]+j*v])
    return 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
26
27
28
29
30
31
32
33
34

---

9/15 LCP 50. 宝石补给

按照规则依次赠送

def giveGem(gem, operations):
    """
    :type gem: List[int]
    :type operations: List[List[int]]
    :rtype: int
    """
    for x,y in operations:
        v = gem[x]//2
        gem[x]-=v
        gem[y]+=v
    return max(gem)-min(gem)



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

---

9/16 198. 打家劫舍

使用一个maxlist记录 进入当前x位置的房间能够得到的最大价值
可知前一个位置无法获取 所以在x时
可以通过[0,x-2]之间的最大值加上x的值获得该位置最大值
而在maxlist中最大的值必定是在最后两个位置 n,n-1
因为位置n的值必定大于n-2的值 所以我们只要比较maxlist中x-3,x-2这两个位置的值
就可以得到[0,x-2]之间的最大值

def rob(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    maxlist=[]
    res = 0
    for i in range(len(nums)):
        if i>2:
            tmp = max(maxlist[i-3],maxlist[i-2])+nums[i]
            maxlist.append(tmp)
        elif i==2:
            tmp = maxlist[0]+nums[i]
            maxlist.append(tmp)
        else:
            tmp = nums[i]
            maxlist.append(nums[i])
        res = max(res,tmp)
    return res


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

---

9/17 213. 打家劫舍 II

第一个和最后一个不能同时选择
分两种情况 选最后一个 和不选最后一个
记录前一家最大值pre1 和前前一家最大值pre2
可以得到当前i最大值 max(pre1,pre2+nums[i])

def rob(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    def func(start,end):
        now,pre1,pre2 = 0,0,0
        for i in range(end,start-1,-1):
            now = max(pre1,nums[i]+pre2)
            pre2=pre1
            pre1=now
        return now
    
    n =len(nums)
    if n==0:
        return 0
    elif n==1:
        return nums[0]
    return max(func(0,n-2),func(1,n-1))


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

---