牛客网刷题笔记231112 最小k位数+二叉树层序遍历+SQL异常邮件概率

算法题牛客网NC119 最小的k个数

题目：

用了一下python列表的便利，不知道在面试时允许用不。当然最简单的方法其实是直接sort()一下取前k位数即可。本次写的思路如下：

用一个最大容量为k的列表存储结果，遍历n个元素，当列表超过k位时，弹出最大值。

代码：

class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        # write code here
        if k == 0:
            return []
        if k >= len(input):
            return input
        ## 直接sort()
        # input.sort()
        # return input[:k]
        
        ## 堆排序
        max_output = input[0]
        output = [max_output]
        for i in input[1:]:
            if len(output) < k:
                output.append(i)
                if i > max_output:
                    max_output = i
            else:
                if i < max_output:
                    output.remove(max_output)
                    output.append(i)
                    max_output = max(output)
        return output
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

算法题牛客网NC15 二叉树层序遍历

题目：

这个题目其实还挺普遍的，简单点说就是要做一次遍历，最直接的想法是用队列的思想。不过自己比较习惯用列表，所以是用列表实现队列的想法。

代码：

class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        # write code here
        if not root:
            return []
        if not root.left and not root.right:
            return [[root.val]]
        
        nodeList = [root] # 作为队列记录节点
        result = []
        while len(nodeList)>0:
            curRow = [] # 记录当前遍历行的结点
            n = len(nodeList)
            for i in range(n):
                cur = nodeList.pop(0) ## 弹出节点
                curRow.append(cur.val)
                ## 加入子节点
                if cur.left:
                    nodeList.append(cur.left)
                if cur.right:
                    nodeList.append(cur.right)
            result.append(curRow)
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

SQL牛客网259 异常的邮件概率

依旧写了两个，题库太少了没什么难度。题目太长放链接

异常的邮件概率

代码：

select date, format(count(case when type = 'no_completed' then 1 else null end)/count(1), 3) as p
from (
    select *
    from email
    where send_id in (select id from user where is_blacklist = 0) 
    and receive_id in (select id from user where is_blacklist = 0)
) a
group by date
order by date asc
1
2
3
4
5
6
7
8
9