LeetCode 每日一题 2022/8/1-2022/8/7

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

8/1 1374. 生成每种字符都是奇数个的字符串

n是奇数 则n个a
n是偶数 则n-1个a 1个b

def generateTheString(n):
    """ :type n: int :rtype: str """
    s = "a"*(n-1)
    if n%2==1:
        s+="a"
    else:
        s+="b"
    return s

8/2 622. 设计循环队列

使用队列模拟 head,tail分别记录当前头尾位置
num记录当前队列中有用的个数

class MyCircularQueue(object):

    def __init__(self, k):
        """ :type k: int """
        self.q = [-1]*k
        self.head = 0
        self.tail = 0
        self.num = 0
        self.k = k


    def enQueue(self, value):
        """ :type value: int :rtype: bool """
        if self.num<self.k:
            self.q[self.tail] = value
            self.tail = (self.tail+1)%self.k
            self.num +=1
            return True
        else:
            return False


    def deQueue(self):
        """ :rtype: bool """
        if self.num>0:
            self.num -=1
            self.head = (self.head+1)%self.k
            return True
        else:
            return False


    def Front(self):
        """ :rtype: int """
        if self.num>0:
            return self.q[self.head]
        else:
            return -1


    def Rear(self):
        """ :rtype: int """
        if self.num>0:
            loc = self.tail-1
            if loc<0:
                loc += self.k
            return self.q[loc]
        else:
            return -1


    def isEmpty(self):
        """ :rtype: bool """
        return self.num==0


    def isFull(self):
        """ :rtype: bool """
        return self.num == self.k

8/3 899. 有序队列

当k>1时 可以得到s的升序字符串
当k=1时 需要考虑移动n-1次的每种情况

def orderlyQueue(s, k):
    """ :type s: str :type k: int :rtype: str """
    if k>1:
        return "".join(sorted(s))
    ans = s
    for i in range(1,len(s)):
        tmp = s[i:]+s[:i]
        if tmp<ans:
            ans = tmp
    return ans

8/4 1403. 非递增顺序的最小子序列

先求总和
从大到小排序
依次取出较大的数 直至超过总和的一半

def minSubsequence(nums):
    """ :type nums: List[int] :rtype: List[int] """
    nums.sort(reverse=True)
    total = sum(nums)
    ans = []
    cur = 0
    for num in nums:
        cur += num
        ans.append(num)
        if cur>total/2:
            break
    return ans

8/5 623. 在二叉树中增加一行

dfs找到这一层之前一层 加入
如果depth=1特殊处理

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
def addOneRow(root, val, depth):
    """ :type root: TreeNode :type val: int :type depth: int :rtype: TreeNode """
    def dfs(node,d):
        if not node:
            return 
        if d==depth:
            l = TreeNode(val)
            l.left = node.left
            node.left = l
            r = TreeNode(val)
            r.right = node.right
            node.right = r
            return
        dfs(node.left,d+1)
        dfs(node.right,d+1)
        return
    if depth==1:
        new = TreeNode(val)
        new.left = root
        return new
    dfs(root,1)
    return root

8/6 1408. 数组中的字符串匹配

穷举 两两比较

def stringMatching(words):
    """ :type words: List[str] :rtype: List[str] """
    ans = []
    for i,x in enumerate(words):
        for j,y in enumerate(words):
            if i!=j and x in y:
                ans.append(x)
                break
    return ans

8/7 636. 函数的独占时间

栈 保存[函数标签，起始时间]信息
如果是起始点 判断栈中是否有元素
如果有 说明上一个暂时暂停了 中间间隔为上一个元素的时间
并将上个元素起始点移至当前位置
将当前元素信息保存
如果是终结点 则与上一个起始点配对 将间隔时间加入
此时如果栈中还有元素 将其起始位移至当前位置

def exclusiveTime(n, logs):
    """ :type n: int :type logs: List[str] :rtype: List[int] """
    ans = [0]*n
    st = []
    for log in logs:
        l = log.split(":")
        idx,tg,time = int(l[0]),l[1],int(l[2])
        if tg=="start":
            if st:
                tmpid,tmptime = st[-1]
                ans[tmpid]+=time-tmptime
                st[-1][1] = time            
            st.append([idx,time])
        else:
            i,t = st.pop()
            ans[i]+=time-t+1
            if st:
                st[-1][1] = time+1
    return ans