LeetCode 每日一题 2022/3/21-2022/3/27

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

3/21 653. 两数之和 IV - 输入 BST

bst前序遍历为从小到大排列
双指针寻找

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findTarget(root, k):
    """ :type root: TreeNode :type k: int :rtype: bool """
    l = []
    def find(node):
        if not node:
            return
        find(node.left)
        l.append(node.val)
        find(node.right) 
    find(root)
    if l[left]==k:
        return True
    while left<right:
        v = l[left]+l[right]
        if v==k:
            return True
        elif v<k:
            left +=1
        else:
            right-=1
    return False

3/22 2038. 如果相邻两个颜色均相同则删除当前颜色

统计符合条件的A和符合条件的B哪一个较多

def winnerOfGame(colors):
    """ :type colors: str :rtype: bool """
    m = {
    "A":0,"B":0}
    ct = False
    for i,c in enumerate(colors):
        if i==0:
            continue
        if colors[i]==colors[i-1]:
            ct = True
            m[colors[i]]+=1
        else:
            if ct:
                m[colors[i-1]]-=1
            ct = False
    if ct:
        m[colors[-1]]-=1
    
    if m["A"]>m["B"]:
        return True
    else:
        return False

3/23 440. 字典序的第K小数字

字典树思路
从小到大考虑
每个节点最多拥有10个子节点
例如节点1
在小于n的情况下
可以有第一层子节点10,11…19 最小值为110 最大值为110+9
可以有第二层子节点100,101,…199 最小值为1010 最大值为1910+9
记录每一层子节点最大最小值minv maxv
next_minv=10minv next_maxv = 10maxv+9
每一层节点个数为 min(maxv,n)-minv+1 最大值不能超过n
从最小前缀cur=1开始找起 统计1开头的所有数量num
如果需要的k大于等于num 则减去个数num 继续寻找下一个前缀2 cur = cur+1
如果k小于num 说明需要的数以1开头
进入1的第一层子节点继续寻找cur = cur*10 此时经过了节点1 所以k需要减去1
此时节点为10继续上述步骤 直至找到第k个

def findKthNumber(n, k):
    """ :type n: int :type k: int :rtype: int """
    def find(prefix,n):
        count,minv,maxv=0,prefix,prefix
        while minv<=n:
            count += min(maxv,n)-minv+1
            minv *=10
            maxv = maxv*10+9
        return count
    
    cur = 1
    k -=1
    while k>0:
        num = find(cur,n)
        if num<=k:
            k-=num
            cur+=1
        else:
            cur*=10
            k-=1
    return cur

3/24 661. 图片平滑器

遍历每一个点 统计九个位置是否满足

def imageSmoother(img):
    """ :type img: List[List[int]] :rtype: List[List[int]] """
    pos = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(0,0),(1,-1),(1,0),(1,1)]
    m,n = len(img),len(img[0])
    ret = [[0]*n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            num = 0
            v = 0
            for x,y in pos:
                newi,newj = i+x,j+y
                if 0<=newi<m and 0<=newj<n:
                    num+=1
                    v += img[newi][newj]
            ret[i][j] = v//num
    return ret

3/25 172. 阶乘后的零

尾随零由5*2得到 阶乘中2的数量足够
所以只要考虑出现过多少次5 则有多少个0
除以5可以得到包含因子5的数有多少个 及因子5出现了一次的个数
若商大于0 说明存在一个数包含多个因子5 继续除

def trailingZeroes(n):
    """ :type n: int :rtype: int """
    num = 0
    while n>0:
        n //=5
        num += n
    return num

3/26 682. 棒球比赛

模拟

def calPoints(ops):
    """ :type ops: List[str] :rtype: int """
    l = []
    for c in ops:
        if c=="+":
            l.append(l[-1]+l[-2])
        elif c=="D":
            l.append(2*l[-1])
        elif c=="C":
            l = l[:-1]
        else:
            l.append(int(c))
    return sum(l)

3/27 2028. 找出缺失的观测数据

得到所有观测次数num
平均值num得到总和
总和减去rolls内已知数据的和 得到n次为止数据的和total
每次观测数据[1,6] 如果total<n1 或者total>6*n则说明不存在
将total平均分配到n次观测中 得到x=total//n
如果无法平均分配剩余m = total%n m必定小于n
将剩余的m分配到m次观测中每次为1 及x+1
所以最后可以有m个x+1 和(n-m)个x

def missingRolls(rolls, mean, n):
    """ :type rolls: List[int] :type mean: int :type n: int :rtype: List[int] """
    num = len(rolls)+n
    total = mean*num-sum(rolls)
    if total<n or total>6*n:
        return []
    x = total//n
    m = total%n
    ans = [x+1]*m
    ans.extend([x]*(n-m))
    return ans