LeetCode 每日一题 2024/1/1-2024/1/7

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

---

1/1 1599. 经营摩天轮的最大利润

如果4个人的钱小于运行的钱 则必定亏本
依次遍历每个时间点的游客 wait记录当前等待游客数量
ans记录最大利润时的经营时间 cur记录当前利润 maxv记录最大利润
当没有后续游客时 继续考虑等待的游客 每次上4人使得利润最大化

def minOperationsMaxProfit(customers, boardingCost, runningCost):""":type customers: List[int]:type boardingCost: int:type runningCost: int:rtype: int"""if 4*boardingCost<runningCost:return -1wait = 0ans = -1cur = -999maxv = -999num = 0for cus in customers:wait += custmp = min(4,wait)wait -=tmpcur += tmp*boardingCost-runningCostnum +=1if cur>maxv:maxv = curans = numwhile wait>0:tmp = min(4,wait)wait -=tmpcur += tmp*boardingCost-runningCostnum +=1if cur>maxv:maxv = curans = numreturn ans

---

1/2 466. 统计重复个数

从1个s1开始寻找s2 不停的添加s1 寻找到能够开始循环的地方

def getMaxRepetitions(s1, n1, s2, n2):""":type s1: str:type n1: int:type s2: str:type n2: int:rtype: int"""if n1==0:return 0s1cnt,ind,s2cnt = 0,0,0m = {}while True:s1cnt +=1for c in s1:if c==s2[ind]:ind+=1if ind==len(s2):s2cnt+=1ind=0if s1cnt==n1:return s2cnt//n2if ind in m:s1p,s2p = m[ind]pre = (s1p,s2p)nxt =(s1cnt-s1p,s2cnt-s2p)breakelse:m[ind] = (s1cnt,s2cnt)ans = pre[1]+(n1-pre[0])//(nxt[0])*nxt[1]l = (n1-pre[0])%nxt[0]for i in range(l):for c in s1:if c==s2[ind]:ind+=1if ind==len(s2):ans+=1ind=0return ans//n2

---

1/3 2487. 从链表中移除节点

递归 对右侧进行操作

class ListNode(object):def __init__(self, val=0, next=None):self.val = valself.next = next
def removeNodes(head):""":type head: Optional[ListNode]:rtype: Optional[ListNode]"""def do(node):if node is None:return Nonenode.next = do(node.next)if node.next and node.val<node.next.val:return node.nextelse:return nodereturn do(head)

---

1/4 2397. 被列覆盖的最多行数

枚举每一种情况
cur为选取的状态 1为选择 0位不选
每一行使用二进制表示 mask[i]
与cur相与如果数值不变说明所有1都被覆盖了

def maximumRows(matrix, numSelect):""":type matrix: List[List[int]]:type numSelect: int:rtype: int"""m,n=len(matrix),len(matrix[0])mask = [sum(v<<j for j,v in enumerate(row)) for i,row in enumerate(matrix)]ans,limit = 0,1<<nfor cur in range(1,limit):if cur.bit_count()!=numSelect:continuet = sum((mask[j]&cur)==mask[j] for j in range(m))ans = max(ans,t)return ans

---

1/5 1944. 队列中可以看到的人数

从最右侧开始考虑
对于右侧不高于自己的人 左侧的人必定看不到
维护一个单调栈 递减
忽略不高于自己的人

def canSeePersonsCount(heights):""":type heights: List[int]:rtype: List[int]"""st=[]n = len(heights)ans = [0]*nfor i in range(n-1,-1,-1):cur = heights[i]while st and cur>st[-1]:ans[i]+=1st.pop()if st:ans[i]+=1st.append(cur)return ans

---

1/6 2807. 在链表中插入最大公约数

遍历每一个节点 在节点后插入公约数
下一步跳过最新插入的节点

class ListNode(object):def __init__(self, val=0, next=None):self.val = valself.next = next
def insertGreatestCommonDivisors(head):""":type head: Optional[ListNode]:rtype: Optional[ListNode]"""import mathnode = headwhile node.next is not None:node.next = ListNode(math.gcd(node.val, node.next.val), node.next)node = node.next.nextreturn head

---

1/7 383. 赎金信

记录magazine中的字符个数
遍历ransom检查是否满足

def canConstruct(ransomNote, magazine):""":type ransomNote: str:type magazine: str:rtype: bool"""if len(magazine)<len(ransomNote):return Falsefrom collections import defaultdictm = defaultdict(int)for c in magazine:m[c]+=1for c in ransomNote:m[c]-=1if m[c]<0:return Falsereturn True

---