LeetCode 每日一题 2022/11/28-2022/12/4

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

---

11/28 882. 细分图中的可到达节点

原始节点间的细分节点数可看做节点间的距离
使用dijkstra 可以算出起点到个点的最短路径
哈希表used[(u,v)]记录节点u到v可达的细分节点 (v,u)记录v到u可达的细分节点
最后统计时相加 并不大于u,v间的细分节点总数

def reachableNodes(edges, maxMoves, n):
    """
    :type edges: List[List[int]]
    :type maxMoves: int
    :type n: int
    :rtype: int
    """
    import heapq
    from collections import defaultdict
    l = defaultdict(list)
    for u,v,n in edges:
        l[u].append([v,n])
        l[v].append([u,n])
    used = {}
    visited = set()
    ans = 0
    pq = [(0,0)]
    heapq.heapify(pq)
    while pq and pq[0][0]<=maxMoves:
        step,u = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)
        ans +=1
        for v,nodes in l[u]:
            if nodes+step+1<=maxMoves and v not in visited:
                heapq.heappush(pq,[nodes+step+1,v])
            used[(u,v)] = min(nodes,maxMoves-step)
    for u,v,n in edges:
        ans += min(n,used.get((u,v),0)+used.get((v,u),0))
    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

---

11/29 1758. 生成交替二进制字符串的最少操作数

遍历一遍 分别记录两种情况的操作次数

def minOperations(s):
    """
    :type s: str
    :rtype: int
    """
    ans = [0,0]
    for i,c in enumerate(s):
        if i%2==0:
            if c=="1":
                ans[0]+=1
            else:
                ans[1]+=1
        else:
            if c=="0":
                ans[0]+=1
            else:
                ans[1]+=1
    return min(ans)
                


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

---

11/30 895. 最大频率栈

m[val]记录val的频率
fre[num] 记录出现num次的元素

from collections import defaultdict
class FreqStack(object):

    def __init__(self):
        self.m = defaultdict(int)
        self.fre = defaultdict(list)
        self.maxfre = 0


    def push(self, val):
        """
        :type val: int
        :rtype: None
        """
        self.m[val]+=1
        self.fre[self.m[val]].append(val)
        self.maxfre = max(self.maxfre,self.m[val])


    def pop(self):
        """
        :rtype: int
        """
        v = self.fre[self.maxfre].pop()
        self.m[v]-=1
        if len(self.fre[self.maxfre])==0:
            self.maxfre-=1
        return v


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

---

12/1 1779. 找到最近的有相同 X 或 Y 坐标的点

遍历依次寻找

def nearestValidPoint(x, y, points):
    """
    :type x: int
    :type y: int
    :type points: List[List[int]]
    :rtype: int
    """
    def dis(i,j):
        return abs(x-i)+abs(y-j)
    d = 20000
    ans = -1
    for ind,p in enumerate(points):
        i,j=p[0],p[1]
        if i==x or j==y:
            tmp = dis(i,j)
            if tmp<d:
                d = tmp
                ans = ind
    return ans


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

---

12/2 1769. 移动所有球到每个盒子所需的最小操作数

若已知转移到i位置需要ans[i]=x次 i及左侧[0~i]间有a个球 右侧i+1到最后有b个球
那么对于i+1的位置而言 所有[0~i]需要多走1步 所有[i+1~n]可以少走一步
所以ans[i+1]=ans[i]+a-b

def minOperations(boxes):
    """
    :type boxes: str
    :rtype: List[int]
    """
    l,r,cur = int(boxes[0]),0,0
    n = len(boxes)
    for i in range(1,n):
        if boxes[i]=='1':
            r+=1
            cur +=i
    ans = [cur]
    for i in range(1,n):
        cur += l-r
        if boxes[i]=='1':
            l+=1
            r-=1
        ans.append(cur)
    return ans


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

---

12/3 1796. 字符串中第二大的数字

记录最大和第二大的数字

def secondHighest(s):
    """
    :type s: str
    :rtype: int
    """
    a,b=-1,-1
    for c in s:
        if c.isdigit():
            v = int(c)
            if v>a:
                a,b=v,a
            elif v<a and v>b:
                b =v
    return b


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

---

12/4 1774. 最接近目标价格的甜点成本

配料价格从小到大排序 ans记录当前最小价格差的成本
遍历每一种基料
对于每一种配料可以有不加，加一份，加两份三种情况
如果当前成本已经大于target并且大于已有ans与target的价格差
则后续配料无需考虑 只会是价格差越来越大

def closestCost(baseCosts, toppingCosts, target):
    """
    :type baseCosts: List[int]
    :type toppingCosts: List[int]
    :type target: int
    :rtype: int
    """
    toppingCosts.sort()
    global ans 
    ans = min(baseCosts)
    def func(ind,cur):
        global ans
        if cur-target>abs(ans-target):
            return
        if abs(cur-target)<=abs(ans-target):
            if abs(cur-target)<abs(ans-target):
                ans = cur
            else:
                ans = min(ans,cur)
        if ind==len(toppingCosts):
            return
        func(ind+1,cur)
        func(ind+1,cur+toppingCosts[ind])
        func(ind+1,cur+2*toppingCosts[ind])
        
    for c in baseCosts:
        func(0,c)
        
    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

---