Welcome to xpt’s blog! 2021年准备秋招期间整理的一些笔记，分享给大家！

文档分享的初衷是给师弟师妹们作为参考，主要是适合想去大厂+测试开发岗的朋友们。
建议大家自己整理文档，把我的文档作为参考，有些东西自己整理，自己去写出来，才是最适合你自己的！
文章还未精细整理，如存在错误之处，可以邮件or微信反馈给我呀，感激不尽！

想进大厂，要抓住提前批免笔试的机会！（例如京东、字节、百度等报名时间一般为七月，面试时间为报名后的一周内，面试一般为3轮，面试相关经验后续我会单独再写blog分享^_^，也欢迎大家来跟我talk，一定知无不言。）

本人情况：普通211、研究生、有京东、百度、以及字节提前批测开岗offer。7月初开始准备，准备太迟，一边准备一边投简历+面试。

  • 投递简历时间：京东（7.14），字节（7.30），百度（7.30）
  • 三轮面试时间：京东（7.21-7.22-7.26），字节（8.4-8.6-8.9），百度（8.9-8.12-8.16）
  • 意向书时间：京东（8.12），字节（8.16），百度（9.9）

京东提前批开始很早，我投的时候已经是第二批。经过京东几轮面试，熟悉了面试流程，大概掌握了测开岗会问些什么问题。
字节和百度提前批我是在ddl前一天投递，其实已经算很迟了，hc不多了。
投递要趁早，很多岗位有固定hc。
多拿offer，才有谈薪资的底气。

我面试的岗位有以下：
1、测试开发岗（京东、百度、以及字节提前批）
2、银行java开发岗（所以我会整理一点java，银行问的都很简单，所以我这里对java的整理比较少）

整理的内容均来源于历年网络上分享的面经（主要来源于牛客），以及我面试时被问过的问题，list如下：
(1)——计算机网络
(2)——操作系统
(3)——数据库
(4)——数据结构
(5)——python
(6)——java
(7)——linux
(8)——常考编程题
(9)——测试开发相关知识

面试QA整理(8)——常考编程题

大文件 多路归并 排序

分割为小文件+多路归并排序

image-20210816131843573

基本思路：

step1：分割+排序
从头开始将大文件FileFile的一个小部分读入内存中，将这一小部分进行排序，然后将排序后的这一小部分写入到一个独立的小文件file_1file1中。循环前面的步骤，生成了一堆内部有序的小文件file_1file1、file_2file2、file_3file3、… 、file_NfileN。
step2：多路归并
将每一个小文件的第一个数取出，即每一个小文件里的最小数，对这些数进行归并排序，将这些数里的最小数字num_inumi（来自file_ifilei ）写入大文件的第一行，此即整个大文件里的最小数字。
将文件file_ifilei的行数指针+1，取出文件file_ifilei行数指针当前所指的数字，放入内存中，将大文件的行数指针+1。
继续前面的循环，直到所有小文件都遍历完成。

一千万个整数，分布在-1000万到+1000万之间，应该怎么排序

1 兆(mb)=1024 (kb)

1 兆=1048576 字节 （1024*1024）

2000万bit=250万（字节）=2.38 兆(mb)

image-20210808225419928

【全排列】

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

image-20210806210307344

每次交换元素并回溯寻找后，都要将元素交换回来，保持没有交换前的状态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def permute(nums):
    def backtrack(first, n):
        # 所有数都填完了
        if first == n:
            res.append(nums[:])
        for i in range(first, n):
            # 动态维护数组
            nums[first], nums[i] = nums[i], nums[first]
            # 继续递归填下一个数
            backtrack(first + 1, n)
            # 撤销操作
            nums[first], nums[i] = nums[i], nums[first]

    if not nums:
        return []
    res = []
    backtrack(0, len(nums))
    return res

nums = [1, 2, 3]
print(permute(nums))

【LRU】哈希表dict+双向链表

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
62
63
64
65
66
67
68
69
class ListNode:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None
class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hashmap = {} #一个字典存节点
        # 新建两个节点 head 和 tail
        self.head = ListNode()
        self.tail = ListNode()
        # 初始化链表为 head <-> tail #双向链表
        self.head.next = self.tail
        self.tail.prev = self.head

    # 因为get与put操作都可能需要将双向链表中的某个节点移到末尾，所以定义一个方法
    def move_node_to_tail(self, key):
            # 先将哈希表key指向的节点拎出来，为了简洁起名node
            #      hashmap[key]                               hashmap[key]
            #           |                                          |
            #           V              -->                         V
            # prev <-> node <-> next         pre <-> next   ...   node
            node = self.hashmap[key]
            node.prev.next = node.next
            node.next.prev = node.prev
            # 之后将node插入到尾节点前
            #                 hashmap[key]                 hashmap[key]
            #                      |                            |
            #                      V        -->                 V
            # prev <-> tail  ...  node                prev <-> node <-> tail
            node.prev = self.tail.prev
            node.next = self.tail
            self.tail.prev.next = node
            self.tail.prev = node

    def get(self, key: int) -> int:
        if key in self.hashmap:
            # 如果已经在链表中了，把它移到末尾（变成最新访问的）
            self.move_node_to_tail(key)
        res = self.hashmap.get(key, -1)
        if res == -1:
            return res #返回 -1 (未找到)
        else:
            return res.value #返回值

    def put(self, key: int, value: int) -> None:
        if key in self.hashmap:
            # 如果key本身已经在哈希表中了就不需要在链表中加入新的节点
            # 但是需要更新字典该值对应节点的value
            self.hashmap[key].value = value
            # 之后将该节点移到末尾
            self.move_node_to_tail(key)
        else:#插入之前要判断容量够不够
            if len(self.hashmap) == self.capacity: #容量不够了，删！
                # 去掉哈希表对应项
                self.hashmap.pop(self.head.next.key)
                # 去掉最久没有被访问过的节点，即头节点之后的节点
                self.head.next = self.head.next.next
                self.head.next.prev = self.head
            #容量够的情况下：
            # 如果不在的话就插入new节点到尾节点前
            new = ListNode(key, value)
            self.hashmap[key] = new
            new.prev = self.tail.prev
            new.next = self.tail
            self.tail.prev.next = new
            self.tail.prev = new

【反转链表】

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
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


def reverseList(head):
    if head is None or head.next is None:
        return head

    pre = None
    cur = head
    while cur:
        temp = cur.next
        cur.next = pre
        pre = cur
        cur = temp
    return  #!!!!!!!!!return的是pre，头节点！！！！


head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)

p = reverseList(head)
while p:
    print(p.val)
    p = p.next
image-20210729205839131

【判断链表中是否有环】快慢指针，追及问题

力扣141题

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

如果一个链表存在环，那么快慢指针必然会相遇

同时出发，如果没有环，那么快的会扬长而去。。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


def hasCycle(head):
    # 定义快慢指针
    slow = head
    fast = head

    while fast and fast.next:  # 如果无环fast.next会报错
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

#test
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = head.next
print(hasCycle(head))  # True

【合并两个有序链表】

力扣21题——将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的，且合并后新链表依然有序。 

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
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def mergeTwoLists(l1, l2):
    # 终止条件，直到链表都空
    if not l1: return l2
    if not l2: return l1
    if (l1.val <= l2.val):
        l1.next = mergeTwoLists(l1.next, l2)  # 递归调用
        return l1
    else:
        l2.next = mergeTwoLists(l1, l2.next)  # 递归调用
        return l2

# 输入：l1 = [1,2,4], l2 = [1,3,4]
# 输出：[1,1,2,3,4,4]
l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(4)
l2 = ListNode(1)
l2.next = ListNode(3)
l2.next.next = ListNode(4)
p = mergeTwoLists(l1, l2)
while p:
    print(p.val)
    p = p.next

【两个链表生成相加链表(两数相加)】

第一种——力扣445题

第二种——力扣第2题

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。

给定两个这种链表，请生成代表两个整数相加值的结果链表。

第一种：数字最高位位于链表【开始】

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0

（937+63=1000）

方法一：用栈存储每个链表的每一位，出栈的顺序是低位到高位

方法二：反转链表

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
# 方法一：用栈存储每个链表的每一位，出栈的顺序是低位到高位
class ListNode():
    def __init__(self, x):
        self.val = x
        self.next = None

def addTwoNumbers(l1, l2):
    stack1 = []
    stack2 = []

    while l1:
        stack1.append(l1.val)
        l1 = l1.next
    while l2:
        stack2.append(l2.val)
        l2 = l2.next

    ans = 0  # 当前轮结果
    add_num = 0  # 向前进位
    mod_num = 0  # 余数——>存进链表的数字
    head = None  # 初始空链表

    while stack1 or stack2 or add_num:  # 存在两个栈空了，但还有进位没加进链表里
        if stack1:
            a = stack1.pop()
        else:
            a = 0
        if stack2:
            b = stack2.pop()
        else:
            b = 0
        ans = (a + b) + add_num  # 需要加上,上一轮进位
        add_num = ans // 10  # 向前进位
        mod_num = ans % 10  # 余数——>存进链表的数字
        node = ListNode(mod_num)
        node.next = head
        head = node
    return head

# test
l1 = ListNode(7)
l1.next = ListNode(2)
l1.next.next = ListNode(4)
l1.next.next.next = ListNode(3)
l2 = ListNode(5)
l2.next = ListNode(6)
l2.next.next = ListNode(4)
p = addTwoNumbers(l1, l2)
while p:
    print(p.val)
    p = p.next
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
# 方法二：反转链表
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def addTwoNumbers(l1, l2):
    def trans(head):
        # 反转链表
        if head is None or head.next is None:
            return head

        pre = None
        cur = head
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        return pre

    l1 = trans(l1)
    l2 = trans(l2)

    ans = 0  # 当前轮结果
    add_num = 0  # 向前进位
    mod_num = 0  # 余数，需要存进链表里
    head = None  # 初始空链表

    while l1 or l2 or add_num:
        if l1:
            a = l1.val
            l1 = l1.next
        else:
            a = 0
        if l2:
            b = l2.val
            l2 = l2.next
        else:
            b = 0
        ans = (a + b) + add_num
        add_num = ans // 10
        mod_num = ans % 10
        node = ListNode(mod_num)
        node.next = head
        head = node
    return head

# test
l1 = ListNode(7)
l1.next = ListNode(2)
l1.next.next = ListNode(4)
l1.next.next.next = ListNode(3)
l2 = ListNode(5)
l2.next = ListNode(6)
l2.next.next = ListNode(4)
p = addTwoNumbers(l1, l2)
while p:
    print(p.val)
    p = p.next

第二种：数字最高位位于链表【尾部】

1
2
3
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

那就不用反转链表了，直接可以加

从个位数字开始加，也就是链表首部开始加

需要初始一个空的头节点，返回的时候要去掉，新建一个指针指向头节点，用于添加节点

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
class ListNode():
    def __init__(self, x):
        self.val = x
        self.next = None

def addTwoNumbers(l1, l2):
    ans = 0  # 当前轮结果
    add_num = 0  # 进位
    mod_num = 0  # 余数，也是要保存进链表里的数
    head = ListNode(None)
    p = head  # 指针
    while l1 or l2 or add_num:
        if l1:
            a = l1.val
            l1 = l1.next
        else:
            a = 0
        if l2:
            b = l2.val
            l2 = l2.next
        else:
            b = 0
        ans = (a + b) + add_num  # 进位也要加
        add_num = ans // 10
        mod_num = ans % 10
        node = ListNode(mod_num)
        p.next = node
        p = p.next
    head = head.next  # 去除首部None
    return head

# test
l1 = ListNode(2)
l1.next = ListNode(4)
l1.next.next = ListNode(3)
l2 = ListNode(5)
l2.next = ListNode(6)
l2.next.next = ListNode(4)
p = addTwoNumbers(l1, l2)
while p:
    print(p.val)
    p = p.next

【链表中倒数第k个节点】快慢指针，先走k步

1
2
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

采用快慢指针，定义一个计数器，fast指针先开始移动，当计数器走过K个数后，slow指针开始移动。

当fast指针结束，slow指针指向的即是倒数第k个数

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
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def getKthFromEnd(head, k):
    slow = fast = head
    i = 0
    while fast:
        if i >= k:
            slow = slow.next
        fast = fast.next
        i += 1
    return slow

# test
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
k=2
p = getKthFromEnd(head,k)
while p:
    print(p.val)
    p = p.next

☆【删除链表的倒数第n个节点】

给定一个链表，删除链表的倒数第 个节点并返回链表的头指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def removeNthFromEnd(self , head , n ):
        # write code here
        #快慢指针找到倒数第n个
        fast=head
        slow=head
        
        for i in range(n):#快指针先走n步
            fast=fast.next
        #特殊情况，要删除的是头节点，则此时fast已经指向尾部的下一个：None
        if not fast:
            return head.next
        while fast.next: #使得slow刚好为倒数第n个之前的数字
            fast=fast.next
            slow=slow.next
        slow.next=slow.next.next #删除倒数第n个
        return head

——测试用例

正确的测试用例

空链表，抛异常

n是不是有效的

{1},1，{1,2},2 特殊情况，要删除的是头节点

{1,2},1

【链表中的节点每k个一组翻转】

将给出的链表中的节点每k个一组翻转，返回翻转后的链表
如果链表中的节点数不是k的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
要求空间复杂度O(1)
image-20210730203808003
用栈，我们把 k 个数压入栈中，然后弹出来的顺序就是翻转的！
这里要注意几个问题：
第一，剩下的链表个数够不够 k 个（因为不够 k 个不用翻转）；
第二，已经翻转的部分要与剩下链表连接起来。

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
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def reverseKGroup(head, k):
    root = ListNode(None)
    p = root
    while True:
        count = k
        stack = []
        temp = head
        while count and temp:
            stack.append(temp)
            temp = temp.next
            count -= 1
        # 如果count没能减完，temp就空了，说明不够k个，就不翻转了跳出去
        if count:
            p.next = head
            break
        # 如果够k个，这时候temp已经指向第k+1个节点
        # 翻转
        while stack:
            p.next = stack.pop()
            p = p.next
        p.next = temp  # 跟剩下的链表temp连接起来
        head = temp  # 把剩下的链表temp给head,继续下一轮翻转
    return root.next  # 因为首个是None,所以返回root.next
#test
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
p = reverseKGroup(head, 2)
while p:
    print(p.val)
    p = p.next

二叉树转双向链表

二叉搜索树将 二叉搜索树 转换成一个 “排序的循环双向链表” ，其中包含三个要素：

  • 排序链表： 节点应从小到大排序，因此应使用 中序遍历 “从小到大”访问树的节点。
  • 双向链表： 在构建相邻节点的引用关系时，设前驱节点 pre 和当前节点 cur ，不仅应构建 pre.right = cur ，也应构建 cur.left = pre 。
  • 循环链表： 设链表头节点 head 和尾节点 tail ，则应构建 head.left = tail 和 tail.right = head 。
image-20210814203228602

使用中序遍历访问树的各节点 cur ；并在访问每个节点时构建 cur 和前驱节点 pre 的引用指向；中序遍历完成后，最后构建头节点和尾节点的引用指向即可。

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
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

pre = None
head = None
def treeToDoublyList(node):
    def dfs(cur):
        global pre, head
        if not cur:
            return
        dfs(cur.left)  # 递归左子树
        if pre:
            # 当pre不为空时:修改双向节点引用，即 pre.right = cur ,cur.left = pre
            pre.right, cur.left = cur, pre
        else:
            head = cur  # 当pre为空时:代表正在访问链表头节点，记为 head
        # 保存cur:更新 pre = cur ,即节点 cur 是后继节点的 pre
        pre = cur
        dfs(cur.right)

    if not root:
        return
    dfs(node)
    # 头尾连接
    head.left = pre
    pre.right = head
    return head

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
p = treeToDoublyList(root)
# print是停不下来的
# print("双向链表正序:")
# while p:
#     print(p.val)
#     p = p.right
print("双向链表倒序:")
while p:
    p = p.left
    print(p.val)

☆【无重复字符的最长子串】（不含有重复字符的 最长子串 的长度）(滑动窗口)

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

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
def lengthOfLongestSubsting(s):
    n = len(s)
    if n == 0:
        return 0

    max_len = 0  # 记录最大长度
    dict = {}  # 键值对

    # 定义窗口的首尾端 (start, end)， 然后滑动窗口
    start = 0
    for end in range(n):
        # 把窗口末端元素加入哈希表，使其出现次数+1
        dict[s[end]] = dict.get(s[end], 0) + 1  # dict.get(字典中要查找的键,如果指定键的值不存在时返回该默认值)
        # 如果dict的长度，和end-start+1相同，则说明还没有重复字符
        if len(dict) == end - start + 1:
            max_len = max(max_len, end - start + 1)  # 更新最大长度

        # 当窗口长度大于哈希表长度时候 (说明存在重复元素)，窗口不合法
        # 所以需要不断移动窗口左指针直到窗口再次合法, 同时提前更新需要维护的变量 (dict)
        while end - start + 1 > len(dict):
            head = s[start]
            dict[head] -= 1
            if dict[head] == 0:
                del dict[head]
            start += 1
    return max_len

if __name__ == '__main__':
    s = "abcabcbb"
    maxlen=lengthOfLongestSubsting(s)
    print(maxlen)

——测试用例

要求是

0 <= s.length <= 5 * 104``s

由英文字母、数字、符号和空格组成

可以这么测：

  • 首先是一些边界值和特殊值 如“”（返回0），“ ”（空格，返回1），“abcdef”（无重复的），“bbb”（全部重复的）这种；
  • 正确的测试用例
  • 输入的不是字符串，抛异常
  • 输入中文字符串，抛异常
  • （等价类划分法将测试数据中具有某种共同特征的数据集合，进行划分）
  • 考虑数据类型范围，抛异常
    • 考虑代码内存限制，或者是电脑性能
    • stackoverflow上有一个测试结果：在使用了116G内存后报内存错误。
      • 结论：python本身对string长度无强制性限制。使用过程中主要需要考虑电脑性能和程序效率。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#滑动窗口类题目模板
def problemName(str):
    # Step 1: 定义需要维护的变量们 (对于滑动窗口类题目，这些变量通常是最小长度，最大长度，或者哈希表)


    # Step 2: 定义窗口的首尾端 (start, end)， 然后滑动窗口
    start=0
    for end in range(len(str)):
        # Step 3: 更新需要维护的变量, 有的变量需要一个if语句来维护 (比如最大最小长度)
        ...       
        # Step 4 - 情况2
        # 如果题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
        # 如果当前窗口不合法时, 用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
        # 在左指针移动之前更新Step 1定义的(部分或所有)维护变量 
        while 不合法:
        # 更新 (部分或所有) 维护变量 
        # 不断移动窗口左指针直到窗口再次合法

    # Step 5: 返回答案
    return ...

☆【最大数】（给非负整数数组，数字拼接，使得最后结果最大）

给定一个数组由一些非负整数组成，现需要将他们进行排列并拼接，使得最后的结果最大，返回值需要是string类型 否则可能会溢出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import functools

def largestNumber(nums):
    # 先把 nums 中的所有数字转字符串，形成字符串数组 nums_str
    # 用map函数
    nums_str = map(str, nums)
    # 自定义比较
    cmp = lambda x, y: -1 if x + y > y + x else 1
    nums_str = sorted(nums_str, key=functools.cmp_to_key(cmp))
    res = "".join(nums_str)
    if res[0] == "0":
        res = "0"
    return res

if __name__ == '__main__':
    nums = [3, 30, 34, 5, 9]
    print(largestNumber(nums)) #9534330

——测试用例

  • 首先是一些边界值和特殊值 如[0,0]（输出应该为“0”）；

  • 正确的测试用例；

  • 输入为空，抛异常

  • 输入的不是非负整数，抛异常

  • 输入的数字超过了数据类型范围，抛异常

    • 考虑代码内存限制，或者是电脑性能
    • stackoverflow上有一个测试结果：在使用了116G内存后报内存错误。
      • 结论：python本身对string长度无强制性限制。使用过程中主要需要考虑电脑性能和程序效率。

利用Python3自定义cmp_to_key函数，传入两个参数(x,y)对应于(self,other),也就是(当前数,前面比较过的数)，或者说y为数组前面的数，x为数组后面的数。

sorted()函数默认升序

默认的时候compare(x,y)会在当前x<y时返回-1，说明当前x比前面数小，应该放到前面去；

在当前x>y时返回1，说明当前x比前面数字大。

我现在想要：x与y拼接>y与x拼接时，把x放到前面去，用[x,y]的顺序，也就是我想要它返回-1

1
cmp = lambda x, y: -1 if x + y > y + x else 1

要使得构造的数更大，需要满足条件：前面的数+后面的数>后面的数+前面的数，即y+x>x+y返回1成立

【长度最小的子数组】（找出该数组中满足其和 ≥ target 的长度最小的 连续子数组)（滑动窗口）

力扣209题

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl+1, …, numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0 。

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
def minSubArrayLen(target, nums):
    # 满足其和 ≥ target 的长度最小的 连续子数组
    # 并返回其长度。如果不存在符合条件的子数组，返回 0。
    n = len(nums)

    inf = int(1e9)

    min_len = inf
    sum_ans = 0

    start = 0
    for end in range(n):
        sum_ans += nums[end]
        if sum_ans >= target:
            min_len = min(min_len, end - start + 1)

        # 当sum_的值大于target时候，窗口不合法
        # 所以需要不断移动窗口左指针直到窗口再次合法, 同时提前更新需要维护的变量 (min_len， sum_ans)
        while sum_ans >= target:
            # 需要再判断一下，不然end=n-1结束的时候会出问题
            min_len = min(min_len, end - start + 1)

            sum_ans -= nums[start]
            start += 1
            
    if min_len == inf:
        return 0
    return min_len


target = 7
nums = [2, 3, 1, 2, 4, 3]
print(minSubArrayLen(target, nums))

inf也可以用math.inf

import math就行

连续子数组最大和

【合并两个有序数组】

力扣第88题

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

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
# 从后向前数组遍历
# 两个指针指向A,B末尾，比较两个数组末尾元素
# 哪个大哪个存到A数组最后，并把指针前移
def merge(A, m, B, n):
    p1 = m - 1
    p2 = n - 1
    p = m + n - 1
    while p1 >= 0 and p2 >= 0:  # 两个指针都要>=0
        if A[p1] >= B[p2]:
            A[p] = A[p1]
            p1 -= 1
        else:
            A[p] = B[p2]
            p2 -= 1
        p -= 1
    # 如果A遍历完了，B里还有数，就把B的前面复制到A前面
    # 没有数了，也可以复制，就是p2=-1了，啥也复制不进去
    A[:p2 + 1] = B[:p2 + 1]
    return A

# test
A = [1]
m = 1
B = []
n = 0
print(merge(A, m, B, n))

——测试用例

正确用例：[1,2,3,0,0,0]，3；[2,5,6]，3

[1]，1；[]，0 ——B空

[0]，0，[1]，1——A空，B不空

m,n范围限制

数组里数字，数字类型范围限制

【买卖股票的最佳时机】

力扣121题

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def maxProfit(prices):
    # 记录一个历史最低价格 minprice
    # 一般场合下的数据都是小于10^9的，所以它可以作为无穷大使用而不致出现数据大于无穷大的情形。
    inf = int(1e9)
    minprice = inf

    maxprofit = 0

    for price in prices:
        maxprofit = max(maxprofit, price - minprice)
        minprice = min(minprice, price)
    return maxprofit


prices = [7, 1, 5, 3, 6, 4]
print(maxProfit(prices))

【只出现一次的数字】（其余每个元素均出现两次，找出那个只出现了一次的元素）

力扣136题

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

按位异或运算符：当两对应的二进位相异时，结果为1，否则为0。

a ^ a = 0
0 ^ a = a

1
2
3
4
5
6
7
def singleNumber(nums):
    for i in range(1,len(nums)):
        nums[0]=nums[0]^nums[i]
    return nums[0]

nums=[2,2,1]
print(singleNumber(nums))

【32位有符号整数进行反转】（java写）

力扣第7题

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）

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
public class DemoMain {
    public static int reverse(int x) {
        int ans = 0;
        while (x != 0) {
            int pop = x % 10;
            if (ans>Integer.MAX_VALUE/10 || (ans==Integer.MAX_VALUE/10 && pop>7)){
                return 0;
            }
            if (ans<Integer.MIN_VALUE/10 || (ans==Integer.MIN_VALUE/10 && pop<-8)){
                return 0;
            }
            ans = ans * 10 + pop;
            x /= 10;
        }
        return ans;
    }

    public static void main(String[] args) {
        int x = -120;
        System.out.println(reverse(x));//-21
    }
}
/*
通过循环将数字x的每一位拆开，在计算新值时每一步都判断是否溢出。
溢出条件有两个，一个是大于整数最大值MAX_VALUE，另一个是小于整数最小值MIN_VALUE
设当前计算结果为ans，下一位为pop。
    从ans * 10 + pop > MAX_VALUE这个溢出条件来看
        当出现 ans > MAX_VALUE / 10 时，则一定溢出
        当出现 ans == MAX_VALUE / 10 且 pop > 7 时，则一定溢出，7是2^31 - 1的个位数
    从ans * 10 + pop < MIN_VALUE这个溢出条件来看
        当出现 ans < MIN_VALUE / 10 时，则一定溢出
        当出现 ans == MIN_VALUE / 10 且 pop < -8 时，则一定溢出，8是-2^31的个位数
 315%10=5     315/10=31
 31%10=1      31/10=3
 3%10=3       3/10=0
 */

image-20210728093557741

【字符串变形】（字符串中由空格隔开的单词反序，同时反转每个字符的大小写

对于一个给定的字符串，我们需要在线性(也就是O(n))的时间里对它做一些变形。首先这个字符串中包含着一些空格，就像”Hello World”一样，然后我们要做的是把着个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。比如”Hello World”变形后就变成了”wORLD hELLO”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# str.swapcase()方法用于对字符串的大小写字母进行转换。
# 字符串分割str.split(),输出的是一个列表list
# s[::-1]步长为1，反向输出

# 给定一个字符串s以及它的长度n
def trans(s, n):
    a = s.swapcase().split(" ")
    b = a[::-1]  # 步长为1，反向输出
    return " ".join(b)


test_str = "This is a sample"
n = 16
print(trans(test_str, n))

如果不让用swapcase()函数的话，用ASCII判断如下：

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
# ACSII码 ：A(65)-Z(90)，a(97)-z(122),空格32
# 字符转ASCII：ord()
# ASCII转字符：chr()
def trans(s, n):
    # 大小写转换
    str_list = list(s)
    for i in range(n):
        asc = ord(str_list[i])
        if asc == 32:
            continue
        if asc >= 65 and asc <= 90:
            asc += 32
        else:  # asc >= 97 and asc <= 122
            asc -= 32
        str_list[i] = chr(asc)  # 字符串不可更改，所以转为list改
        s = "".join(str_list)  # 转回字符串

    # 单词反序
    s2 = s.split(" ")
    s3 = s2[::-1]
    ans = " ".join(s3)

    return ans


# test
test_str = "This is a sample"
n = 16
print(trans(test_str, n))

【将字符串转化为整数】

实现函数 atoi 。函数的功能为将字符串转化为整数

提示：仔细思考所有可能的输入情况。这个问题没有给出输入的限制，你需要自己考虑所有可能的情况。

1
2
3
4
5
代码要解决三个主要问题：
    字符串前有空白字符；
    ‘+’，‘-’ 处理问题；
    浮点数问题
    数据类型范围
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
# 数字字符转数字: “此数字的 ASCII 码” 与 “ 00 的 ASCII 码” 相减即可
# 字符转ASCII：ord()
# ASCII转字符：chr()
# str.strip()移除字符串头尾指定的字符（默认为空格或换行符）或字符序列
def strToInt(str):
    str = str.strip()  # 删除首尾空格
    if not str: #！！！！！！！！！！记得判空
        return 0
    int_max = 2 ** 31 - 1
    int_min = -2 ** 31

    i = 1  # 数字读取初始索引设为1
    sign = 1  # 符号位初始化为正
    res = 0  # 存结果

    if str[0] == '-':
        sign = -1
    elif str[0] != '+': #elif！！！！！！
        i = 0  # 若没有符号位，则数字读取从0开始
    # 数字拼接边界bndry
    # 如果sign=1时，res>bndry 或者 res==bndry时,等待拼接的数字x>7，则越界
    # 如果sign=-1时，（res不带符号位）res>bndry 或者 res==bndry时，等待拼接的数字x>8
    bndry = int_max // 10
    for c in str[i:]: #！！！！！！不能写错，[]里还有冒号呢！！
        if not '0' <= c <= '9': break  # 遇到非数字则跳出！！！！！！！！！！！！
        # 如果读数字，需要判断是否越界，每拼接一位都要考虑是否越界
        if sign == 1 and (res > bndry or (res == bndry and c > '7')):
            return int_max
        if sign == -1 and (res > bndry or (res == bndry and c > '8')):
            return int_min
        res = res * 10 + ord(c) - ord('0')  # 数字拼接

    return sign * res  # 不要忘记乘上符号
image-20210728195148668

【字符串反转】

写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）

解法一:开辟一个和str长度大小相同的一个字符串ans，把传入的str倒序赋值到ans字符串上

解法二:原地交换

1
2
3
4
5
6
7
8
9
10
class Solution:
    def solve(self , str ):
        # write code here
        if not str:
            return
        str_list=list(str)
        n=len(str)
        for i in range(n//2):#注意这里！！！！！！！
            str_list[i],str_list[n-i-1]=str_list[n-i-1],str_list[i]#交换
        return ''.join(str_list)#转为字符串

【字符串匹配，实现 strStr()】

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -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
32
33
34
35
36
37
38
39
40
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle not in haystack:
            return -1
        elif needle == '':
            return 0
        else:
            for i in range(len(haystack)):
                if haystack[i:len(needle)+i] == needle[:]:
                    return i
详细写法：
// 方法一
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        a=len(needle)
        b=len(haystack)
        if a==0:
            return 0
        next=self.getnext(a,needle)
        p=-1
        for j in range(b):
            while p>=0 and needle[p+1]!=haystack[j]:
                p=next[p]
            if needle[p+1]==haystack[j]:
                p+=1
            if p==a-1:
                return j-a+1
        return -1

    def getnext(self,a,needle):
        next=['' for i in range(a)]
        k=-1
        next[0]=k
        for i in range(1,len(needle)):
            while (k>-1 and needle[k+1]!=needle[i]):
                k=next[k]
            if needle[k+1]==needle[i]:
                k+=1
            next[i]=k
        return next

【栈push pop top getMin】

力扣面试题 03.02. 栈的最小值

请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。

  • push(x) – 压一个数到栈顶
  • pop() – 移除栈顶的元素，不返回任何对象
  • top() – 返回栈顶端的元素
  • getMin() – 检索栈中的最小值
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
class MinStack(object):

    def __init__(self):
        self.stack = []  # 存放所有元素
        self.minStack = []  # 引入minStack列表存放最小值

    def push(self, x):
        self.stack.append(x)
        if not self.minStack:  # 判断minStack是否空
            self.minStack.append(x)
        else:
            self.minStack.append(min(x, self.minStack[-1]))

    def pop(self):
        self.stack.pop()
        self.minStack.pop()

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.minStack[-1]

#test
obj = MinStack()
obj.push(6)
obj.push(1)
obj.push(7)
print(obj.getMin())
obj.pop()
print(obj.top())

【用两个栈实现队列】

用两个栈来实现一个队列，分别完成在队列尾部插入整数(push)和在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 只使用一个栈 stack1 当作队列，另一个栈 stack2 用来辅助操作。
# 想要先进先出，就要将新加入的元素放在栈底
# 需要先将stack1的元素转移到stack2将元素入栈stack1最后将stack2的元素全部回到stack1
class CQueue(object):

    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def appendTail(self, value):
        while self.stack1:  # stack1不为空，就不能新加元素，需要转移到stack2
            self.stack2.append(self.stack1.pop())
        # 转移完了，添加新元素
        self.stack1.append(value)
        while self.stack2:  # 再把所有元素转移回stack1
            self.stack1.append(self.stack2.pop())
        return self.stack1

    def deleteHead(self):
        if not self.stack1:#保证pop操作时队列内已有元素，就不会出现这个。
            return -1 
        return self.stack1.pop()

【单调递增的数字】

力扣第738题

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）

1
2
3
输入: N = 332
输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 从左遍历，找到第一个：左数>右数，的位置，
# 把左数-1，并且把右边及后都变为9
# 42432
# 42429
# 一直往前遍历
# 42399
# 39999


def increasingDigits(n):
    digits_str = list(str(n)) #整数整形int转list,要先转成str
    lens = len(digits_str)
    for i in range(lens - 2, -1, -1):
        if digits_str[i] > digits_str[i + 1]:  # 左数>右数
            digits_str[i] = str(int(digits_str[i]) - 1)
            digits_str[i + 1:] = '9' * (lens - i - 1)
    return int(''.join(digits_str))


# test
print(increasingDigits(42432))

【两数之和】找出两个加起来等于目标值的数

给出一个整数数组，请在数组中找出两个加起来等于目标值的数，

你给出的函数twoSum 需要返回这两个数字的下标（index1，index2），需要满足 index1 小于index2。注意：下标是从1开始的。假设给出的数组中只存在唯一解

1
2
给出的数组为 {20, 70, 110, 150},目标值为90
输出 index1=1, index2=2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def twoSum(nums, target):
    # dict存(num值，索引)
    dict = {}
    for i, num in enumerate(nums):
        dict[num] = i  # 给字典增加项
    # 在整个numdict中去查找num2
    for i, num1 in enumerate(nums):
        # i是num1索引
        num2 = target - num1
        if num2 in dict and dict[num2] != i:  # 不能用本身
            # 注意输出的是第几个，而不是索引，且要求左index<右index
            return [i + 1, dict[num2] + 1] if i < dict[num2] else [dict[num2] + 1, i + 1]

nums = [3, 2, 4]
target = 6
print(twoSum(nums, target))  # [2, 3]

【三数之和】找出三个加起来等于目标值的数

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

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
def threeSum(nums):
    lens = len(nums)
    if lens <= 2:
        return []
    nums.sort()  # 排序
    if nums[0] > 0:
        return []

    res = []
    for i in range(lens):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        l = i + 1
        r = lens - 1
        target = 0 - nums[i]
        while l < r:
            if nums[l] + nums[r] == target:
                res.append([nums[i], nums[l], nums[r]])
                # 还要往继续往中间找
                while (l < r and nums[l] == nums[l + 1]):
                    l += 1
                while (l < r and nums[r] == nums[r - 1]):
                    r -= 1
                l += 1
                r -= 1
            elif nums[l] + nums[r] < target:
                l += 1
            else:
                r -= 1
    return res

nums = [-1, 0, 1, 2, -1, -4]
print(threeSum(nums))

【找出数组中重复的数字】

剑指 Offer 03. 数组中重复的数字

1
2
3
4
5
6
7
8
class Solution(object):
    def findRepeatNumber(self, nums):
        num_dict=set()
        for num in nums:
            if num in num_dict:
                return num
            num_dict.add(num)
        return -1

☆【TopK问题，数组中第K大的数】快排partition思想

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。(包括重复的元素，不用去重)

借助快排的 partition 操作定位到最终排定以后索引为 len - k 的那个元素

partition总能排定一个元素，还能够知道这个元素它最终所在的位置，这样每经过一次partition就能缩小搜索的范围

第一种：目标是第k大，但由于是升序找partition,所以目标是倒数第K个
第二种：降序找partition，目标是k-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
# 第一种：目标是第k大，但由于是升序找partition,所以目标是倒数第K个
def findKth(nums, k):
    l = 0
    r = len(nums) - 1
    target = len(nums) - k

    while True:
        p = partition(nums, l, r)
        if p == target:
            return nums[p]
        elif p < target:
            l = p + 1
        else:  # p > target:
            r = p - 1

def partition(nums, l, r):
    pivot = nums[l]
    while l < r:
        while l < r and nums[r] >= pivot:
            r -= 1
        nums[l] = nums[r]
        while l < r and nums[l] <= pivot:
            l += 1
        nums[r] = nums[l]
    nums[l] = pivot
    return l

#test
nums = [3, 2, 1, 5, 6, 4]
k = 2
print(findKth(nums, k))
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
# 第二种：降序找partition，目标是k-1
def findKth(nums, k):
    lens = len(nums)
    l = 0
    r = lens - 1
    target = k - 1
    while True:
        p = partition(nums, l, r)
        if p == target:
            return nums[p]
        elif p < target:
            l = p + 1
        else:
            r = p - 1

def partition(nums, l, r):  # 降序排partition
    pivot = nums[l]
    while l < r:
        while l < r and nums[r] <= pivot:  # 注意这里
            r -= 1
        nums[l] = nums[r]  # 大的换到左边
        while l < r and nums[l] >= pivot:  # 注意这里
            l += 1
        nums[r] = nums[l]  # 小的换到右边
    nums[l] = pivot
    return l

#test
nums = [3, 2, 1, 5, 6, 4]
k = 2
print(findKth(nums, k))

【最小的K个数】快排partition 或 大顶堆

求给定数组的topK小问题。找出数组中最小的k个数。以任意顺序返回这k个数均可

法一：直接排序，然后取前k小数据。

法二：借助快排partition，找第K，则返回左边序列即可

法三：借助大顶堆，仅维护K个长度的堆，遍历数组，当新元素小于堆顶元素时，更新堆顶元素,调整堆

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
# 法二：借助快排partition，找第K，则返回左边序列即可
def smallestK(arr, k):
    l = 0
    r = len(arr) - 1
    target = k - 1
    while True:
        p = partition(arr, l, r)
        if p == target:
            return arr[0:k]
        elif p < target:
            l = p + 1
        else:
            r = p - 1

def partition(nums, l, r):
    pivot = nums[l]
    while l < r:
        while l < r and nums[r] >= pivot:
            r -= 1
        nums[l] = nums[r]
        while l < r and nums[l] <= pivot:
            l += 1
        nums[r] = nums[l]
    nums[l] = pivot
    return l

#test
s = [4, 5, 1, 6, 2, 7, 3, 8]
k = 4
print(smallestK(s, k)
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
# 法三：借助大顶堆，仅维护K个长度的堆，遍历数组，当新元素小于堆顶元素时，更新堆顶元素,调整堆
def HeadAdjust(arr, i, n):  # 以i为根节点进行堆调整
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[l] > arr[largest]:
        largest = l
    if r < n and arr[r] > arr[largest]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        HeadAdjust(arr, largest, n)

def smallestK(arr, k):
    if k == 0:
        return []
    # 构建一个只有k个数的大顶堆
    hp = arr[:k]
    for i in range((k) // 2 - 1, -1, -1):  # 从有子节点的节点开始判断就行
        HeadAdjust(hp, i, k)
    # 遍历数组，当新元素小于堆顶元素时，更新堆顶元素,调整堆
    for num in arr[k:]:
        if num < hp[0]:
            hp[0] = num
            HeadAdjust(hp, 0, k)
    return hp

# test
s = [4, 5, 1, 6, 2, 7, 3, 8]
k = 0
print(smallestK(s, k))

【二叉搜索树的第k大节点】求此树中序遍历倒序的第k个节点

二叉搜索树，二叉查找树，二叉排序树，

左子树小于根结点； 右子树大于根结点，中序遍历，会有序输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def kthLargest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        def InOrderReverse(node):
            if not node:
                return
            InOrderReverse(node.right)
            if self.k==0:
                return
            self.k=self.k-1
            if self.k==0:self.res=node.val
            InOrderReverse(node.left)

        self.k=k
        InOrderReverse(root)
        return self.res

【二叉树的最近公共祖先】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#牛客上，o1,o2都是int,且要求返回也是int
class Solution:
    def lowestCommonAncestor(self , root , o1 , o2 ):
        # write code here
        # 超过叶子节点，或者root为o1、o2中的一个直接返回
        if not root:
            return None
        if root.val == o1 or root.val == o2: return root.val
        left = self.lowestCommonAncestor(root.left, o1, o2) #返回左侧的o1/o1节点
        right = self.lowestCommonAncestor(root.right, o1, o2)#返回右侧的o1/o1节点
        if not left: return right #都在右侧
        if not right: return left #都在左侧
        return root.val #在左右两侧
---------------------------------------------
#力扣上，o1,o1都是TreeNode，返回也是TreeNode
class Solution:
    def lowestCommonAncestor(self , root , o1 , o2 ):
        if not root or root == o1 or root == o2: return root
        left = self.lowestCommonAncestor(root.left, o1, o2)
        right = self.lowestCommonAncestor(root.right, o1, o2)
        if not left: return right
        if not right: return left
        return root

https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/solution/mian-shi-ti-68-ii-er-cha-shu-de-zui-jin-gong-gon-7/

【最长公共前缀】多个字符串

力扣14题

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 先判空
# 令最长公共前缀 ans 的值为第一个字符串，进行初始化
# 遍历后面的字符串，依次与ans比较，找出公共前缀
# 如果不为空则返回，为空则return ""
def longestCommonPrefix(strs):
    if not strs:
        return ""
    ans = strs[0]
    for s in strs[1:]:
        if len(s) < len(ans):
            ans = ans[:len(s)]  # 会有字符串比初始小的情况
        for i in range(len(s)):
            if i < len(ans) and s[i] != ans[i]:  # 注意这里i可能会超出ans索引
                ans = ans[:i]  # 和公共前缀字符不匹配,截断ans
    return ans

#test
strs = ["flower", "flow", "flight"]
print(longestCommonPrefix(strs))

【最长公共子串】牛客

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。

1
2
3
输入："1AB2345CD","12345EF"
返回值："2345"
注意这题求的是最长公共子串，不是最长公共子序列，子序列可以是不连续的，但子串一定是连续的。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def LCS(self , str1 , str2 ):
        # write code here
        l1, l2 = len(str1), len(str2)
        dp = [['' for _ in range(l2 + 1)] for _ in range(l1 + 1)]
        ans = ''
        for i in range(l1):
            for j in range(l2):
                if str1[i] == str2[j]:
                    dp[i+1][j+1] = dp[i][j] + str1[i]
                    if len(dp[i+1][j+1]) > len(ans):
                        ans = dp[i+1][j+1]
        return ans

最长公共子序列&最长公共子串，题解：https://blog.csdn.net/weixin_42462804/article/details/104813182

image-20210730142509564

【字符串前缀和后缀搜索】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class WordFilter(object):
    def __init__(self, words):
        """
        :type words: List[str]
        """
        self.a={}
        for ind,i in enumerate(words):
            for j in range(len(i)+1):
                for k in range(len(i)+1):
                    now=i[:j]+'$'+i[k:]
                    self.a[now]=ind

    def f(self, prefix, suffix):
        """
        :type prefix: str
        :type suffix: str
        :rtype: int
        """
        k=prefix+'$'+suffix
        return self.a.get(k,-1)

# Your WordFilter object will be instantiated and called as such:
# obj = WordFilter(words)
# param_1 = obj.f(prefix,suffix)

【模拟键盘，只有a-z 26个英文字母的输入键,有两个按键坏了】

题目：有一个键盘，只有a-z 26个英文字母的输入键， 现在发现有两个按键坏了，按下会发生特定的结果
按下i键=退格，会消除掉上一个输入字母
按下o键=撤回，会撤销掉上一步的操作
要求实现一个方法，模拟键盘的输出逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def words(str):
    result = []  # 存最终输入
    temp_copy = []  # 拷贝一份数据，防止要撤回操作

    for ch in enumerate(str):
        if ch[1] == 'i':  # 按下i键=退格，会消除掉上一个输入字母
            temp_copy = result.copy()  # 拷贝数组
            result.pop()
        elif ch[1] == 'o':  # 按下o键=撤回，会撤销掉上一步的操作
            result, temp_copy = temp_copy, result
        else:
            temp_copy = result.copy()
            result.append(ch[1])
    return ''.join(result)

print(words('asddiio'))
# (0, 'a')——ch[0]指的是0，ch[1]指的是'a'
# (1, 's')
# (2, 'd')
# (3, 'd')
# (4, 'i')
# (5, 'i')
# (6, 'o')

飞书-【下一个排列】输出给定数字下一个比它大的数字排列

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须 原地 修改，只允许使用额外常数空间。

比如数字：1234， 输出 1243；比如 1243，则输出 1324

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
# 从右向左遍历，第一次出现左数<右数的情况，说明包含右数在内后面是降序排列，把这个降序里的比左数大的最小数字和左数交换
# 特例：找不到左数<右数的情况，如4321，即倒序排一下变成1234
def nextPermutation(nums):
    n = len(nums)
    if n == 1:  # 注意特殊情况
        return nums
    temp = -1  # 记录能不能找到左数<右数的情况
    for i in range(n - 2, -1, -1):  # 从倒数第二个数开始判断（一是特例已经判断过，二是防止i+1越界
        if nums[i] < nums[i + 1]:  # 第一次出现左数<右数的情况
            temp = i
            # 包含右数在内后面是降序排列，把这个降序里的比左数大的最小数字和左数交换
            for k in range(n - 1, i, -1):  # 从最后往前找第一个比nums[i]大的数
                if nums[k] > nums[i]:
                    nums[k], nums[i] = nums[i], nums[k]  # 交换
                    break  # 找到了！立即跳出
            break

    # temp还是=-1，特例,找不到左数<右数的情况,倒序排；也就是从temp+1开始倒序排
    # temp=i，交换之后，需要把索引从i+1开始逆序；也就是从temp+1开始倒序排
    # 合二为一，都是从索引：temp+1开始倒序排
    reverse_nums(nums, temp + 1, n - 1)
    return nums

def reverse_nums(nums, l, r):#力扣里写的时候要把函数写在def函数体里，并且先写在上方
    while l < r:
        nums[l], nums[r] = nums[r], nums[l]
        l += 1
        r -= 1
    return nums

#       i i+1 k                     temp+1
nums = [2, 4, 3, 2, 1]  # 交换之后为[3, 4, 2, 2, 1] 然后需要把索引从i+1开始逆序
print(nextPermutation(nums))  # [3, 1, 2, 2, 4]

【有效的括号】，括号匹配

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

栈先入后出特点恰好与本题括号排序特点一致，即若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，则遍历完所有括号后 stack 仍然为空；
建立哈希表 dic 构建左右括号对应关系：key左括号，value右括号；这样查询 22 个括号是否对应只需O(1) 时间复杂度；建立栈 stack，遍历字符串 s 并按照算法流程一一判断。

  • 如果 c 是左括号，则入栈append；
  • 否则通过哈希表判断括号对应关系，若 stack 栈顶出栈括号 stack.pop() 与当前遍历括号 c 不对应，则提前返回 false。
1
2
3
4
5
6
7
8
class Solution:
    def isValid(self, s: str) -> bool:
        dic = {'{': '}',  '[': ']', '(': ')', '?': '?'}
        stack = ['?']
        for c in s:
            if c in dic: stack.append(c)
            elif dic[stack.pop()] != c: return False 
        return len(stack) == 1
image-20210804131739836