LeetCode 每日一题 2023/4/10-2023/4/16

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

4/10 1019. 链表中的下一个更大节点

从头遍历 在栈中保存节点状态 (节点值,位置)
如果栈顶节点值小于当前节点 则栈顶节点出栈
这个节点的ans就是当前值

class ListNode(object):def __init__(self, val=0, next=None):self.val = valself.next = next
def nextLargerNodes(head):""":type head: ListNode:rtype: List[int]"""ans = []loc = 0l = []while head:while l and l[-1][0]<head.val:node = l[-1]ans[node[1]] = head.vall = l[:-1]ans.append(0)l.append((head.val,loc))loc+=1head = head.nextreturn ans

4/11 1041. 困于环中的机器人

考虑机器人执行完一串指令后的位置与朝向
如果是回到原点 无论方向肯定无法离开 最多四次就回循环
如果最后位置为(x,y)
朝向北 则第二次为(2x,2y) 此种情况逃离 不循环
朝向难 则第二次偏移(-x,-y) 此种回到原点 循环
朝向东或西 执行四次指令 第一次第三次抵消 第二次第四次抵消 回到原点

def isRobotBounded( instructions):""":type instructions: str:rtype: bool"""x,y = 0,0step = [[0,1],[1,0],[0,-1],[-1,0]]loc = 0for ins in instructions:if ins == 'G':x+=step[loc][0]y+=step[loc][1]elif ins=='L':loc = (loc-1)%4else:loc = (loc+1)%4return loc!=0 or (x==0 and y==0)

4/12 1147. 段式回文

为了使得分段最多 匹配到的每段长度越小越好
从1开始遍历长度num 判断当前头尾长度为num的子字符串是否相等
如果相等则增加了两段头尾 将当前字符串减去头尾继续考虑
如果长度超过当前字符串一半 说明找不到 退出总数加一

def longestDecomposition(text):""":type text: str:rtype: int"""ans = 0while text:num = 1while num<=len(text)//2 and text[:num]!=text[-num:]:num+=1if num>len(text)//2:ans+=1breakans+=2text = text[num:-num]return max(1,ans)

4/13 2404. 出现最频繁的偶数元素

排序从头开始统计每个数出现次数 记录次数最高的偶数

def mostFrequentEven(nums):""":type nums: List[int]:rtype: int"""nums.sort()ans = -1maxcnt = 0cnt = 1for i in range(1,len(nums)):if nums[i]!=nums[i-1]:if nums[i-1]%2==0 and cnt>maxcnt:ans = nums[i-1]maxcnt = cntcnt = 1else:cnt+=1if nums[-1]%2==0 and cnt>maxcnt:ans = nums[-1]return ans

4/14 1023. 驼峰式匹配

每个单词与模式串匹配 从头至尾依次比较
判断模式串是否是子序列
同时判断大写字母数量是否一致

def camelMatch(queries, pattern):""":type queries: List[str]:type pattern: str:rtype: List[bool]"""n = len(queries)ans = [False]*nup = 0for c in pattern:if c.isupper():up+=1def check(s):l1,l2 = 0,0while l1<len(s) and l2<len(pattern):if pattern[l2]==s[l1]:l2+=1l1+=1else:l1+=1return l2==len(pattern)def checkUp(s):num = 0for c in s:if c.isupper():num+=1return num==upfor i,s in enumerate(queries):if check(s) and checkUp(s):ans[i]=Truereturn ans

4/15 1042. 不邻接植花

m[i] 记录花园i能够到达的所有其他花园
遍历花园 防止他和连接的其他花园颜色一致
使用二进制v来表示四种颜色是否被使用

def gardenNoAdj(n, paths):""":type n: int:type paths: List[List[int]]:rtype: List[int]"""m=[[] for i in range(n)]for p in paths:m[p[0]-1].append(p[1]-1)m[p[1]-1].append(p[0]-1)ans = [0]*nfor i in range(n):v = 0for g in m[i]:v |= (1<<ans[g])for j in range(1,5):if v & (1<<j)==0:ans[i] = jbreakreturn ans

4/16 1157. 子数组中占绝大多数的元素

在子数组内寻找绝对众数
如果子数组存在绝对众数，那么我随机选择一个数，这个数为绝对众数的概率至少是 1/2
计算出这个数在区间内出现了多少次，如果出现频率大于等于 threshold，那么这个数就是子数组的绝对众数
如果随机选择了20次，都没有找到符合条件的数，可以认为区间内确实不存在绝对众数。

from collections import defaultdict
import random
import bisect
class MajorityChecker(object):def __init__(self, arr):""":type arr: List[int]"""self.arr = arrself.ind = defaultdict(list)for i,num in enumerate(arr):self.ind[num].append(i)def query(self, left, right, threshold):""":type left: int:type right: int:type threshold: int:rtype: int"""for _ in range(20):i = random.randint(left, right)num = self.arr[i]cnt = bisect.bisect_right(self.ind[num], right)-bisect.bisect_left(self.ind[num], left)if cnt>=threshold:return numreturn -1