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

目录

• • • 11/28 882. 细分图中的可到达节点
    • 11/29 1758. 生成交替二进制字符串的最少操作数
    • 11/30 895. 最大频率栈
    • 12/1 1779. 找到最近的有相同 X 或 Y 坐标的点
    • 12/2 1769. 移动所有球到每个盒子所需的最小操作数
    • 12/3 1796. 字符串中第二大的数字
    • 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 heapqfrom collections import defaultdictl = defaultdict(list)for u,v,n in edges:l[u].append([v,n])l[v].append([u,n])used = {}visited = set()ans = 0pq = [(0,0)]heapq.heapify(pq)while pq and pq[0][0]<=maxMoves:step,u = heapq.heappop(pq)if u in visited:continuevisited.add(u)ans +=1for 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

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]+=1else:ans[1]+=1else:if c=="0":ans[0]+=1else:ans[1]+=1return min(ans)

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 = 0def push(self, val):""":type val: int:rtype: None"""self.m[val]+=1self.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]-=1if len(self.fre[self.maxfre])==0:self.maxfre-=1return v

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 = 20000ans = -1for ind,p in enumerate(points):i,j=p[0],p[1]if i==x or j==y:tmp = dis(i,j)if tmp

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

def secondHighest(s):""":type s: str:rtype: int"""a,b=-1,-1for c in s:if c.isdigit():v = int(c)if v>a:a,b=v,aelif vb:b =vreturn b