LeetCode 每日一题 2022/3/7-2022/3/13

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

3/7 504. 七进制数

7进制 用7取余

def convertToBase7(num):
    """ :type num: int :rtype: str """
    if num==0:
        return "0"
    minus =False
    if num<0:
        minus = True
        num = -num
    ans = ""
    while num>0:
        ans = str(num%7)+ans
        num //=7
    if minus:
        ans = "-"+ans
    return ans
        

3/8 2055. 蜡烛之间的盘子

left,right记录往左往右最近的蜡烛位置
plate记录从左往右 当前位置有多少盘子
根据查询条件[l,r]找到l右边最近的蜡烛 r左边最近的蜡烛
如果存在这个区间 plate[r]-plate[l]就是区间内的盘子

def platesBetweenCandles(s, queries):
    """ :type s: str :type queries: List[List[int]] :rtype: List[int] """
    n = len(s)
    left,right = [0]*n,[0]*n
    plate = [0]*n
    l,r=-1,-1
    for loc,c in enumerate(s):
        if c=="*":
            if loc==0:
                plate[loc]=1
            else:
                plate[loc]=plate[loc-1]+1     
        else:
            l = loc
            plate[loc]=plate[loc-1]
        left[loc]=l
    for i in range(n-1,-1,-1):
        c = s[i]
        if c=="|":
            r = i
        right[i] = r
    ans = []
    for l,r in queries:
        num = 0
        if s[l]!="|":
            l = right[l]
        if s[r]!="|":
            r = left[r]
        if l<r and l>=0 and r>=0:
            num = plate[r]-plate[l]
        ans.append(num)
    return ans

3/9 798. 得分最高的最小轮调

nums有n个数
对于nums[loc]=v进行了k的轮调
0<=k<n
如果k<=loc:
轮调后的位置为loc-k 需要v<=loc-k
得到 0<=k<=min(loc,loc-v)
如果k>loc:
轮调后位置为n-k+loc 需要v<=n-k+loc
得到 loc<k<=n+loc-v
对于loc位置的数 有这两个区间的k可以满足条件
对这些区间内的k加1
区间内整体改动 使用差分数组
差分数组li长度为n+1 记录k的状态
如果区间[x,y]+1 只需要将li[x]+=1 li[y+1]-=1
最后从头累加到每个位置的数 即为这个位置的个数

def bestRotation(nums):
    """ :type nums: List[int] :rtype: int """
    n = len(nums)
    li = [0]*(n+1)
    for loc,v in enumerate(nums):
        nl = min(loc,loc-v)
        if nl>=0:
            li[0]+=1
            li[nl+1]-=1
        nl = min(n-1,n+loc-v)
        if nl<n and loc<n:
            li[loc+1]+=1
            li[nl+1]-=1
            
    cur = 0
    maxnum = 0
    ans = 0
    for k,v in enumerate(li):
        cur+=v
        if maxnum<cur:
            maxnum = cur
            ans = k
    return ans

3/10 589. N 叉树的前序遍历

1.递归
2.迭代 存入栈中每次取栈顶元素 并将子节点倒序压入栈中

class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

def preorder(root):
    """ :type root: Node :rtype: List[int] """
    ans =  []
    def dfs(node):
        if not node:
            return 
        ans.append(node.val)
        for c in node.children:
            dfs(c)
    dfs(root)
    return ans

def preorder2(root):
    """ :type root: Node :rtype: List[int] """
    stack = [root]
    ans = []
    while stack:
        node = stack.pop()
        if node :
            ans.append(node.val)
            for c in node.children[::-1]:
                stack.append(c)
    return ans

3/11 2049. 统计最高分的节点数目

使用child[p]用来记录节点p的子节点
深搜 对于节点node 初始size = n-1 除去自身后个数
在搜索完叶子树后减去叶子树个数sz
此时size个数为node子树以外的节点个数
将子树sz与size相乘可以得到当前node得分
如果与最大值相同则将cnt+1
如果大于最大值 则更新最大值cnt=1

def countHighestScoreNodes(parents):
    """ :type parents: List[int] :rtype: int """
    n = len(parents)
    from collections import defaultdict
    child = defaultdict(list)
    for node,p in enumerate(parents):
        if p!=-1:
            child[p].append(node)
          
    maxnum,cnt = 0,0
    def dfs(node):
        global maxnum,cnt
        num = 1
        size = n-1
        for c in child[node]:
            sz = dfs(c)
            num *= sz
            size -=sz
        if node!=0:
            num *= size
        if num==maxnum:
            cnt+=1
        elif num>maxnum:
            maxnum = num
            cnt = 1
        return n-size
    dfs(0)
    return cnt
    

3/12 590. N 叉树的后序遍历

1.递归 先子后根
2.迭代 栈stack 如果节点包含子节点将子节点倒序压入栈中
如果节点无子节点或者子节点已经被处理 即该节点在mem中 则将结果加入

class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

def postorder(root):
    """ :type root: Node :rtype: List[int] """
    ans = []
    def dfs(node):
        if not node:
            return
        for c in node.children:
            dfs(c)
        ans.append(node.val)
    dfs(root)
    return ans

def postorder2(root):
    """ :type root: Node :rtype: List[int] """
    if not root:
        return []
    ans = []
    stack = [root]
    mem=set()
    while stack:
        node = stack[-1]
        if len(node.children)==0 or node in mem:
            ans.append(node.val)
            stack.pop()
            continue
        stack.extend(reversed(node.children))
        mem.add(node)
    return ans
                
    

3/13 393. UTF-8 编码验证

check通过位运算来得到数值第一个0前包含有几个1
最多四个如果超过四个则说明该数值不符合条件返回-1
依次从头校验 need表示当前需要几个10开头的值
need==0时 不能出现check为1的数值
need>0时 只能接check为1的数值

def validUtf8(data):
    """ :type data: List[int] :rtype: bool """
    def check(v):
        if v>>7==0:
            return 0
        off = 7
        ans = 0
        while off >0:
            if ans >4:
                return -1
            if (v>>off)&1==1:
                ans +=1
                off-=1
            else:
                break
        return ans
    need = 0
    for v in data:
        num = check(v)
        if num<0:
            return False
        if need==0 and num==1:
            return False
        if need>0 and num!=1:
            return False
        if need==0 and num==0:
            continue
        if need==0:
            need= num-1
        else:
            need-=1
    return need==0