LeetCode Daily Question 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,tailRecord the current head and tail positions respectively
numRecord the number of useful ones in the current queue

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时 need to consider movingn-1each case

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. 非递增顺序的最小子序列

先求总和
从大到小排序
Take the larger numbers in order until more than half of the total

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. 在二叉树中增加一行

dfsFind the layer before this layer 加入
如果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. 函数的独占时间

栈 保存[函数标签,起始时间]信息
如果是起始点 判断栈中是否有元素
如果有 The previous one is temporarily suspended The intermediate interval is the time of the previous element
and move the previous element start point to the current position
Save the current element information
If it is an endpoint is paired with the previous starting point Add the interval time
At this point, if there are still elements in the stack Move its starting position to the current position

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