leetcode-简单-2021-07-10

今天上来先写了一个对我来说好难的每日一题，之后又遇到一道数据库的题目，确实是不会，sad，可能周六下午就是要献给愉快的游戏吧！周日上午又写了几道题 榨油榨油！！

• 981.基于时间的键值存储 每日一题
• 181.超过经理收入的员工
• 171.Excel表序列号
• 顺时针打印矩阵
• 236. 二叉树的最近公共祖先
• 796.旋转字符串
• 1556.千位分隔数
• 53.最大子序和
• 228.汇总区间
• 283.移动零
• 543.二叉树的直径

981.基于时间的键值存储

class TimeMap:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.dict = defaultdict(list)


    def set(self, key: str, value: str, timestamp: int) -> None:
        self.dict[key].append([value, timestamp])


    def get(self, key: str, timestamp: int) -> str:
        key_val = self.dict[key]
        n = len(key_val)
        if n == 1 and key_val[0][1] <= timestamp:
            return key_val[0][0]
        else:
            for i in range(n-1, -1, -1):
                if  key_val[i][1] <= timestamp:
                    return key_val[i][0]

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

key_val.sort(key=lambda x:x[1], reverse=True)
# 按照key_val里面每个元素的第二个元素降序排列
1
2

171.Excel表序列号

class Solution:
    def titleToNumber(self, columnTitle: str) -> int:
        val = 0
        t=1 
        for i in range(len(columnTitle)-1, -1, -1):
            k = ord(columnTitle[i])-ord("A") +1  
            val += k*t
            t *= 26
        return val
 # 类似26进制，从后往前，最小一位代表个位，倒数第二位要在数字基础上×26，以此类推

1
2
3
4
5
6
7
8
9
10
11

顺时针打印矩阵

旋转矩阵原理

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        while matrix:
            res += matrix.pop(0) # 输出第一行到res
            matrix = list(zip(*matrix))[::-1] #将矩阵旋转90°
        return res
1
2
3
4
5
6
7

元组转表

  in>> print(list(zip(*matrix)))
  out>> [(4, 7), (5, 8), (6, 9)]
  in>> print(list(map(list,zip(*matrix))))
  out>> [(4, 7), (5, 8), (6, 9)]
1
2
3
4

236.二叉树的最近公共祖先

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def dfs(node, target, path): # 深度优先搜索
            if not node: #到底了
                return 
            if node == target: # 找到target了                                                
                path.append(node) # 存入path，节点本身也是自己的父节点
                return node
            val = dfs(node.left, target, path) # 查找左边节点
            if val:
                path.append(node) # 有返回意味着找到了目标节点node.left，将其父节点node存入path
                return node
            val = dfs(node.right, target, path) # 查找右边节点
            if val:
                path.append(node) # 有返回意味着找到了目标节点node.rght，将其父节点node存入path
                return node
        path_p, path_q =[], []
        dfs(root, p, path_p) # 调用dfs查找所有父节点
        dfs(root, q, path_q)

        for i in path_p: # 第一个相同祖先就是最近的公共祖先，因为查找的时候是深度优先的，最近的父节点在前面
            if i in path_q:
                return i
        return -1
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

796.旋转字符串

s+s包含所有s旋转n次的可能组合，因此只要goal在其中有就是true

class Solution:
    def rotateString(self, s: str, goal: str) -> bool:
        if len(goal) == len(s) and goal in s+s:
            return True
        return False 
1
2
3
4
5

class Solution:
    def thousandSeparator(self, n: int) -> str:
        count = 0
        ans = list()
        while True:
            tmp = n % 10 # 取最小一位
            n //= 10 
            ans.append(str(tmp)) # 以字符串形式存起来
            count += 1 # 计数，每三位加入一个"."
            if count % 3 == 0 and n > 0: #保证前面还有数字，要不然就会".123"的情况
                ans.append(".")
            if n == 0:
                break
        return "".join(ans[::-1]) # str.join(element)将element连接到str后面，ans里面是一个一个的str，将他们一个个连接到一起输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14

ans：
['5']
['5', '9']
['5', '9', '8']
['5', '9', '8', '.', '7']
['5', '9', '8', '.', '7', '4']
['5', '9', '8', '.', '7', '4', '7']
['5', '9', '8', '.', '7', '4', '7', '.', '8']
['5', '9', '8', '.', '7', '4', '7', '.', '8', '9']
1
2
3
4
5
6
7
8
9

53.最大子序和

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(1, n):
            if nums[i-1] > 0: #如果前一个元素大于零则留下
                nums[i] += nums[i-1]
        return max(nums)

1
2
3
4
5
6
7
8