8.1 ~ 8.7 尽量坚持刷力扣的每日一题，锻炼大脑思维。更新中~~

1374. 生成每种字符都是奇数个的字符串【签到题】

题目描述

思路

如果n是奇数则输出n个a，反之如果是偶数则输出n1个a，n-1个b。

AC代码

class Solution:
    def generateTheString(self, n: int) -> str:
        ans = "a"
        if n % 2 == 1:
            ans += "a" * (n - 1)
        else:
            ans += "b" * (n - 1)
        return ans

1
2
3
4
5
6
7
8
9

622. 设计循环队列【模拟循环队列】

题目描述

思路

模拟循环队列即可，具体看代码注释

AC代码

class MyCircularQueue:
    q = [0]
    num = 0 # 当前队列元素个数
    st = 0 # 队头， 队尾st + num - 1
    len = 0 # 队列总大小
    
    # 初始化循环队列大小
    def __init__(self, k: int):
        self.len = k
        self.q = [0] * k # 初始化数组
        
	# 入队
    def enQueue(self, value: int) -> bool:
        if self.isFull(): # 队满
            return False
        self.num += 1 # 队列元素个数+1
        self.q[(self.st + self.num - 1) % self.len] = value # 将元素加入到队尾
        return True
	
	# 出队
    def deQueue(self) -> bool:
        if self.isEmpty(): # 队空
            return False
        self.num -= 1 # 队列元素个数-1
        self.st = (self.st + 1) % self.len # 删除队首元素
        return True

	# 返回队首元素
    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.q[self.st]

	# 返回队尾元素
    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.q[(self.st + self.num - 1) % self.len]

	# 判断队列是否为空
    def isEmpty(self) -> bool:
        if self.num == 0:
            return True
        return False

	# 判断是否队满
    def isFull(self) -> bool:
        if self.num == self.len:
            return True
        return False


# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

899. 有序队列【思维题】

题目描述

思路

当k = 1时，轮转字符串，得到一个字典树最小的字符串；
当k = 2时，可以想象成一个环，将s[0]单拿出来，让字符串转动，可以放到任意位置，s[1],s[2]…都是如此，这样就能使得将整个字符串的每一位调整到任意位置。所以将该字符串排为升序即可。

AC代码

class Solution:
    def orderlyQueue(self, s: str, k: int) -> str:
        if k == 1:
            ans = s
            for i in range(len(s) - 1):
                s = s[1:] + s[0]
                ans = min(ans, s)
            return ans
        return  ''.join(sorted(s)) # 注sorted返回的时list，要将其转化为str

1
2
3
4
5
6
7
8
9
10

1403. 非递增顺序的最小子序列【贪心】

题目描述

思路

将nums排序，从最大数开始选取，直到选到大于总数和的那些数即可。

AC代码

class Solution:
    def minSubsequence(self, nums: List[int]) -> List[int]:
        nums.sort(reverse = True)
        tot, cur = sum(nums), 0
        for i in range(len(nums)):
            cur += nums[i]
            if cur > tot /2 :
                return nums[: i+1]

1
2
3
4
5
6
7
8
9

623. 在二叉树中增加一行【DFS or BFS】

题目描述

思路

根据题目描述，有两种情况：

• 第一，当depth = 1时，返回连接到左子节点的root。
• 第二，当depth> 1时，找到第depth - 1层的所有节点，然后让这些节点的左节点连接到新节点的左子树上面，右节点连接到新节点的右子树上面。

AC代码【DFS】

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
        if depth == 1:
            return TreeNode(val, root, None)
            
        def dfs(node, curLevel): # 内嵌函数
            if node == None:
                return
            if curLevel == depth - 1: # 找到第depth - 1层的所有节点，并将找到的这些节点，都按题目要求加入新节点
                node.left = TreeNode(val, node.left, None)
                node.right = TreeNode(val, None, node.right)
            dfs(node.left, curLevel + 1)
            dfs(node.right, curLevel + 1)
        dfs(root, 1)
        return root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

AC代码【BFS】

class Solution:
    def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
        if depth == 1:
            return TreeNode(val, root, None)
        # 找到第depth - 1层的所有节点
        curLevel = [root]
        for i in range(1, depth - 1) : 
            tmp = []
            for node in curLevel:
                if node.left:
                    tmp.append(node.left)
                if node.right:
                    tmp.append(node.right)
            curLevel = tmp
        # 将找到的这些节点，都按题目要求加入新节点
        for node in curLevel:
            node.left = TreeNode(val, node.left, None)
            node.right = TreeNode(val, None, node.right)
        return root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1408. 数组中的字符串匹配【暴力枚举】

题目描述

思路

题目数据量小，可以暴力枚举。

AC代码

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        ans = []
        n = len(words)
        for i in range(n):
            for j in range(n):
                if i != j and words[i] in words[j]:
                    ans.append(words[i])
                    break
        return ans
       '''
       # 也可用内置函数enumerate，此函数即可得到下标，又可得到值
       for i, x in enumerate(words):
            for j, y in enumerate(words):
                if i != j and x in y :
                    ans.append(x)
                    break
       '''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

636. 函数的独占时间【模拟栈】

题目描述

思路

遇到start将其函数标识和时间戳入栈，如果栈里本来有start将栈顶函数暂停运行，并且计算执行时间。如果遇到end，将栈顶元素出栈，并且一定是对应函数，并且计算运行时间。

AC代码

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:    
        ans = [0] * n
        st = []
        for log in logs:
            pos, tmp, time = log.split(':')
            pos, time = int(pos), int(time)
            # 正在调用开始时，如果又函数正在运行，就抢占运行函数，记录执行时间，然后将调用函数入栈
            if tmp == "start":
                if st: # 栈不为空
                    ans[st[-1][0]] += time - st[-1][1]
                    st[-1][1] = time # 被强制的函数调用开始时间随之变化
                st.append([pos, time])
            # 正在调用结束时，弹出栈顶调用函数，计算运行时间，如果此函数被暂停则开始运行该函数。
            else:
                p, t = st.pop()
                ans[p] += time - t + 1
                if st:
                    st[-1][1] = time + 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20