牛客网刷题笔记三 寻找第K大+两数之和+合并两个排序的链表+用两个栈实现队列

算法题牛客网NC88 寻找第K大

题目：

思路就是做个排序，要求时间复杂度$O(n\log n)$，因此选用快排。代码：

class Solution:
    def quickSort(self, a, start, end):
        if start >= end:
            return
        val = a[start]
        low = start
        high = end
        while low < high:
            while low < high and a[high] >= val:
                high -= 1
            a[low] = a[high]
            while low < high and a[low] < val:
                low += 1
            a[high] = a[low]
        a[low] = val
        self.quickSort(a, start, low-1)
        self.quickSort(a, low+1, end)
        

    def findKth(self , a: List[int], n: int, K: int) -> int:
        # write code here
        self.quickSort(a, 0, n-1)
        return a[-K]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

NC61 两数之和

题目

比较简单，之前也做过，直接用的循环遍历，但本次要求时间复杂度为$O(n\log n)$，循环遍历会超时，参考了下解题思路，用字典做hashmap的方式，代码：

class Solution:
    def twoSum(self , numbers: List[int], target: int) -> List[int]:
        # write code here
        # for i in range(len(numbers)-1):
        #     for j in range(i+1, len(numbers)):
        #         if numbers[i] + numbers[j] == target:
        #             return [i+1, j+1]
        # return []
        hash_map = {}
        for i in range(len(numbers)):
            tmp = target - numbers[i]
            if tmp in hash_map:
                return [hash_map[tmp]+1, i+1]
            elif numbers[i] not in hash_map:
                hash_map[numbers[i]] = i
        return []
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

NC33 合并两个排序的链表

题目：

这个题也是很简单的类型，因为输入就已经排好序了，只要遍历一下链表就可以了。代码：

class Solution:
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # write code here
        if not pHead1 and not pHead2:
            return None
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        newHead = pHead1 if pHead1.val < pHead2.val else pHead2
        newCur = newHead
        cur1 = pHead1.next if pHead1.val < pHead2.val else pHead1
        cur2 = pHead2 if pHead1.val < pHead2.val else pHead2.next
        while cur1 and cur2:
            if cur1.val < cur2.val:
                newCur.next = cur1
                cur1 = cur1.next
            else:
                newCur.next = cur2
                cur2 = cur2.next
            newCur = newCur.next
        if cur1:
            newCur.next = cur1
        if cur2:
            newCur.next = cur2
        return newHead
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

NC76 用两个栈实现队列

题目：

这个题不知道是不是有什么不给用的坑，反正我直接只用了一个栈，过于简单有些怀疑是不是理解有偏差。代码：

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        # write code here
        self.stack1.append(node)
    def pop(self):
        return self.stack1.pop(0)
        # return xx
1
2
3
4
5
6
7
8
9
10