LeetCode 每日一题 2022/11/28-2022/12/4
admin
2024-03-14 10:05:54
0次

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


目录

      • 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

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,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

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

记录最大和第二大的数字


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

12/4


相关内容

热门资讯

蜻蜓订购APP贵金属订购非法期...   蜻蜓订购APP以"投资平台"名义对外宣传,主打贵金属期货(订购)交易。该平台一方面强调自身"正规...
悟空订购APP非法期货交易欺骗...   近期,有投资者反映,“悟空订购APP”等平台以白银、贵金属订购为名,宣传所谓“高收益”“低门槛”...
小赢淘金APP期货投资骗局,平...   “小赢淘金”之流,最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...
八方淘金APP非法期货交易欺骗...   警惕!八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易!  ...
智易购APP贵金属订购交易骗局...   很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传,很容易把智易购APP当成普...
喜玛银庄APP商品订购投资骗局...   喜玛银庄APP白银、铂金“现货订购”骗局警示:无资质平台涉嫌非法期货交易,投资者爆仓后如何维权?...
吉鑫乐享APP炒贵金属订购交易...   近期,多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损,甚至血本无归。看似正规的“...
易掘金APP虚假期货投资骗局,...   “易掘金”的APP它打着“高收益、灵活投资”的旗号,宣称通过“商品订购”就能轻松赚钱,吸引了不少...
在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...