链表

链表以节点为单位，每个元素都是一个独立对象，在内存空间的存储是非连续的。链表的节点对象具有两个成员变量：「值 val」，「后继节点引用 next」 。

1
2
3
4
class ListNode:
    def __init__(self, x):
        self.val = x     # 节点值
        self.next = None # 后继节点引用

如下图所示，建立此链表需要实例化每个节点，并构建各节点的引用指向。

1
2
3
4
5
6
7
8
# 实例化节点
n1 = ListNode(4) # 节点 head
n2 = ListNode(5)
n3 = ListNode(1)

# 构建引用指向
n1.next = n2
n2.next = n3

图片

图书整理 I

书店店员有一张链表形式的书单，每个节点代表一本书，节点中的值表示书的编号。为更方便整理书架，店员需要将书单倒过来排列，就可以从最后一本书开始整理，逐一将书放回到书架上。请倒序返回这个书单链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBookList(self, head: Optional[ListNode]) -> List[int]:
        lst = []
        while head:
            lst.append(head.val)
            head = head.next
        lst.reverse()
        return lst
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<int> reverseBookList(ListNode* head) {
        ListNode* tmp = head;
        int len = 0;
        while(tmp!=nullptr){
            ++len;
            tmp = tmp->next;
        }
        
        tmp = head;
        vector<int> arr(len);
        while(tmp!=nullptr){
                arr[--len] = tmp->val;
                tmp = tmp->next;
        }
        
        return arr;
    }
};

删除链表节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if head.val == val:  #链表头节点需要删除，
            return head.next
        lian = head
        while lian and lian.next:
            if lian.next.val == val:
                lian.next = lian.next.next
            lian = lian.next
        return head

训练计划 III

给定一个头节点为 head 的单链表用于记录一系列核心肌群训练编号，请将该系列训练编号 倒序 记录于链表并返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:
        #双指针
        cur, pre = head, None  #定义头节点和空节点
        while cur:
            tmp = cur.next   #暂存cur的下一个节点
            cur.next = pre   #cur指向pre
            pre = cur        #将pre取为cur原节点
            cur = tmp        #将cur取为tmp节点，即为原cur的下一个节点
        return pre   #pre就是反向链表

训练计划 II

给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号，请查找并返回倒数第 cnt 个训练项目编号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def trainingPlan(self, head: Optional[ListNode], cnt: int) -> Optional[ListNode]:
        cur = head #单指针
        i = 1
        while cur.next:   #指针遍历链表，查看有多少个节点
            cur = cur.next
            i += 1
        cur = head   #指针回到头节点
        j = 1
        while j != i+1-cnt:   #指针遍历到目标节点，输出节点
            cur = cur.next
            j += 1
        return cur
1
2
3
4
5
6
7
8
9
#双指针，两指针的间隔为cnt
class Solution:
    def trainingPlan(self, head: ListNode, cnt: int) -> ListNode:
        former, latter = head, head
        for _ in range(cnt):
            former = former.next
        while former:
            former, latter = former.next, latter.next
        return latter

训练计划 IV

给定两个以 有序链表 形式记录的训练计划 l1、l2，分别记录了两套核心肌群训练项目编号，请合并这两个训练计划，按训练项目编号 升序 记录于链表并返回。
注意：新链表是通过拼接给定的两个链表的所有节点组成的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        cur = pre = ListNode(0)  #cur为伪头节点
        while l1 and l2:
            if l1.val<=l2.val:  #比较大小
                pre.next = l1
                l1 = l1.next
            else:
                pre.next = l2
                l2 = l2.next
            pre = pre.next
        pre.next = l1 if l1 else l2 #判断哪个链表下个节点非空
        return cur.next

训练计划 V

某教练同时带教两位学员，分别以链表 l1、l2 记录了两套核心肌群训练计划，节点值为训练项目编号。两套计划仅有前半部分热身项目不同，后续正式训练项目相同。请设计一个程序找出并返回第一个正式训练项目编号。如果两个链表不存在相交节点，返回 null 。

如下面的两个链表：
图片
在节点 c1 开始相交。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        #a,b为headA,heaB两个链表的节点数，c为交叉链表节点数，当没有交叉点时，c=0
        #使curA,curB同时走过a+b-c个节点
        curA, curB = headA, headB
        while curA != curB:
            curA = curA.next if curA else headB
            curB = curB.next if curB else headA        
        return curA

随机链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        #使用哈希表（字典）解题，将原节点和复制后的节点一一对应
        if not head: return None
        cur = head
        d={}
        while cur:   #创造N个新节点，并将其与原节点一一对应
            d[cur] = Node(cur.val)
            cur = cur.next
        cur = head
        while cur:   #根据原节点的next和random，索引新节点
            d[cur].next= d.get(cur.next)
            d[cur].random = d.get(cur.random)
            cur = cur.next
        return d[head]

数组

数组是将相同类型的元素存储于连续内存空间的数据结构，其长度不可变。

如下图所示，构建此数组需要在初始化时给定长度，并对数组每个索引元素赋值，代码如下：

1
2
3
4
5
6
7
8
// 初始化一个长度为 5 的数组 array
int array[5];
// 元素赋值
array[0] = 2;
array[1] = 3;
array[2] = 1;
array[3] = 0;
array[4] = 2;

或者可以使用直接赋值的初始化方式，代码如下：

1
int array[] = {2, 3, 1, 0, 2};

Picture2.png

「可变数组」是经常使用的数据结构，其基于数组和扩容机制实现，相比普通数组更加灵活。常用操作有：访问元素、添加元素、删除元素。

1
2
3
4
5
6
7
8
9
# 初始化可变数组
array = []

# 向尾部添加元素
array.append(2)
array.append(3)
array.append(1)
array.append(0)
array.append(2)

训练计划 I

教练使用整数数组 actions 记录一系列核心肌群训练项目编号。为增强训练趣味性，需要将所有奇数编号训练项目调整至偶数编号训练项目之前。请将调整后的训练项目编号以 数组 形式返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def trainingPlan(self, actions: List[int]) -> List[int]:
        #不需要按顺序
        n=len(actions)
        if not n:
            return actions
        i, j = 0, n-1
        while i != j:
            if actions[i] % 2:
                i = i + 1
                continue
            if actions[j] % 2 ==0 :
                j = j - 1
                continue
            actions[i], actions[j] = actions[j], actions[i]
        return actions

文件组合

待传输文件被切分成多个部分，按照原排列顺序，每部分文件编号均为一个 正整数（至少含有两个文件）。传输要求为：连续文件编号总和为接收方指定数字 target 的所有文件。请返回所有符合该要求的文件传输组合列表。

注意，返回时需遵循以下规则：
每种组合按照文件编号 升序 排列；
不同组合按照第一个文件编号 升序 排列。

1
2
3
4
5
6
7
8
9
class Solution:
	def fileCombination(self, target: int) -> List[List[int]]:
		lst=[]
		max = target // 2
		for n in range(max,1,-1):	  #因为需要升序排列，所以n从大到小遍历
			m = target/n - (n-1)/2    #通过数学求和公式，求出m的值
			if m == int(m) and m>0:   #如果m为整数，符合要求
				lst.append(list(range(int(m),int(m+n))))
		return lst

按规则计算统计结果

为了深入了解这些生物群体的生态特征，你们进行了大量的实地观察和数据采集。数组 arrayA 记录了各个生物群体数量数据，其中 arrayA[i] 表示第 i 个生物群体的数量。请返回一个数组 arrayB，该数组为基于数组 arrayA 中的数据计算得出的结果，其中 arrayB[i] 表示将第 i 个生物群体的数量从总体中排除后的其他数量的乘积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#累乘再除法
class Solution:
    def statisticalResult(self, arrayA: List[int]) -> List[int]:
        total = 1
        arrayB = []
        n = len(arrayA)
        j = 0
        for i in range(n):
            if arrayA[i] == 0:
                m = i    #记录下0的位置，当只有一个0的时候，避免循环
                j += 1
                continue   #跳过0，算出其它位置的total
            total *= arrayA[i]
        if j>1:    #两个及以上0时，全部输出0
            arrayB = [0]*n
        elif j == 1:       #一个零时，零的位置输出total，其它位置输出0      
            arrayB = [0]*n
            arrayB[m] = total             
        else:
            for i in range(n):
                arrayB.append(int(total/arrayA[i]))
        return arrayB
1
2
3
4
5
6
7
8
9
10
#矩阵划分上下三角		
class Solution:
    def statisticalResult(self, arrayA: List[int]) -> List[int]:
        arrayB, tmp = [1] * len(arrayA), 1
        for i in range(1, len(arrayA)):
            arrayB[i] = arrayB[i - 1] * arrayA[i - 1]
        for i in range(len(arrayA) - 2, -1, -1):
            tmp *= arrayA[i + 1]
            arrayB[i] *= tmp
        return arrayB

寻找文件副本

设备中存有 n 个文件，文件 id 记于数组 documents。若文件 id 相同，则定义为该文件存在副本。请返回任一存在副本的文件 id。

1
2
3
4
5
6
7
8
# 哈希表
class Solution:
    def findRepeatDocument(self, documents: List[int]) -> int:
        hmap=set()
        for item in documents:
            if item in hmap: return item
            hmap.add(item)
        return
1
2
3
4
5
6
7
#集合去重法
class Solution:
    def findRepeatDocument(self, documents: List[int]) -> int:
        lst=list(set(documents))
        for item in lst:
            documents.remove(item)
        return documents[0]

螺旋遍历二维数组

给定一个二维数组 array，请返回「螺旋遍历」该数组的结果。
螺旋遍历：从左上角开始，按照 向右、向下、向左、向上 的顺序 依次 提取元素，然后再进入内部一层重复相同的步骤，直到提取完所有元素。

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
#按矩阵外围一圈来循环
class Solution:
    def spiralArray(self, array: List[List[int]]) -> List[int]:
        if not array: return []    #矩阵为空
        m = len(array)     #行
        n = len(array[0])  #列
        def matrix(i):    #定义矩阵函数，输出m-2i * n-2i的矩阵
            lst = []
            for j in range(i,m-i):
                lst.append(array[j][i:n-i])
            return lst
        def bianli(lst):   #定义遍历函数，m-2i * n-2i的矩阵的外围一圈遍历
            m1 = len(lst)   #局部矩阵的行
            n1 = len(lst[0])   #局部矩阵的列
            lst2 = []
            if m1 == 1:    #局部矩阵的行为1，即为行向量时
                return lst[0]
            if n1 == 1:   #局部矩阵的行为1，即为列向量时
                for j in range(m1):
                    lst2 += lst[j]
                return lst2
            lst2 = lst[0]   #局部矩阵的行、列都大于1，即为矩阵时
            for j in range(1,m1-1):
                lst2.append(lst[j][-1])
            lst2 += lst[-1][-1:-n1-1:-1]
            for j in range(m1-2,0,-1):
                lst2.append(lst[j][0])
            return lst2
        output = [] 
        k = min(m,n)   #用行列数中的较小者判断遍历应该循环L次
        l = (k+1)//2 if k % 2 else k//2   
        for i in range(0,l):   
            output += bianli(matrix(i))
        return output
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#按四条边界来循环
class Solution:
    def spiralArray(self, array: List[List[int]]) -> List[int]:
        if not array: return []
        l, r, t, b, res = 0, len(array[0]) - 1, 0, len(array) - 1, []
        while True:
            for i in range(l, r + 1): res.append(array[t][i]) # left to right
            t += 1
            if t > b: break
            for i in range(t, b + 1): res.append(array[i][r]) # top to bottom
            r -= 1
            if l > r: break
            for i in range(r, l - 1, -1): res.append(array[b][i]) # right to left
            b -= 1
            if t > b: break
            for i in range(b, t - 1, -1): res.append(array[i][l]) # bottom to top
            l += 1
            if l > r: break
        return res

字符串

路径加密

假定一段路径记作字符串 path，其中以 “.” 作为分隔符。现需将路径加密，加密方法为将 path 中的分隔符替换为空格 " "，请返回加密后的字符串。

1
2
3
class Solution:
    def pathEncryption(self, path: str) -> str:
        return ' '.join(path.split('.'))

字符串中的单词反转

你在与一位习惯从右往左阅读的朋友发消息，他发出的文字顺序都与正常相反但单词内容正确，为了和他顺利交流你决定写一个转换程序，把他所发的消息 message 转换为正常语序。

注意：输入字符串 message 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格

1
2
3
class Solution:
    def reverseMessage(self, message: str) -> str:
        return ' '.join(message.split()[::-1])   #.split()和.split(' ')有区别，前者会去掉所有空格以及\t\n，后者

动态口令

某公司门禁密码使用动态口令技术。初始密码为字符串 password，密码更新均遵循以下步骤：
设定一个正整数目标值 target
将 password 前 target 个字符按原顺序移动至字符串末尾
请返回更新后的密码字符串

1
2
3
class Solution:
    def dynamicPassword(self, password: str, target: int) -> str:
        return password[target:]+password[:target]   #从第target+1位开始切片至末尾，在末尾加上前target位

不使用库函数的字符串转整数

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 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
class Solution:
    def myAtoi(self, str: str) -> int:
        str = str.lstrip()
        if not str: return 0  #字符串为空返回0
        #定义两个判断函数
        flag1, flag2 = False, False 
        if str[0] == '+': flag1, flag2 = True, False  
        if str[0] == '-': flag1, flag2 = True, True
        #字符串首位不为+-和数字时，或者字符串只有一位+-时，返回0
        if flag1:
            if len(str) == 1 or not str[1].isdigit():
                return 0
        else:
            if not str[0].isdigit():
                return 0
        i = 1
        while i < len(str):
            if not str[i].isdigit():
                break
            i += 1
        num = int(str[0:i]) if not flag1 else int(str[1:i])
        if flag2: num = -num
        if num < -2 ** 31:
            num = -2 ** 31
        elif num >= 2 ** 31:
            num = 2 ** 31 - 1
        return num

有效数字

有效数字（按顺序）可以分成以下几个部分：

若干空格
一个 小数 或者 整数
（可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数
若干空格
小数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（‘+’ 或 ‘-’）
下述格式之一：
至少一位数字，后面跟着一个点 ‘.’
至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
一个点 ‘.’ ，后面跟着至少一位数字
整数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（‘+’ 或 ‘-’）
至少一位数字

部分有效数字列举如下：[“2”, “0089”, “-0.1”, “+3.14”, “4.”, “-.9”, “2e10”, “-90E3”, “3e+7”, “+6e-1”, “53.5e93”, “-123.456e789”]
部分无效数字列举如下：[“abc”, “1a”, “1e”, “e3”, “99e2.5”, “–6”, “-+3”, “95a54e53”]
给你一个字符串 s ，如果 s 是一个 有效数字 ，请返回 true 。

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
class Solution:
    def validNumber(self, s: str) -> bool:
        s = s.strip()
        n = len(s)
        if not s: return False
        if n == 1 and not s[0].isdigit(): return False #如果只有一位，必为数字,方便后续遍历
        sign, index, point = 0, 0, 0
        for i in range(n):
            if s[i].isdigit():
                continue
            if not s[i] in '+-eE.':
                return False
            if s[i] in '+-':
                #+-不能出现在字符串最后一位，+-后一位必须是数字或者.,+-前一位不能是数字
                if not (i+1-n and (s[i+1].isdigit() or s[i+1] == '.')) or (i and s[i-1].isdigit()): return False 
                #如果前面已经出现了+-或.，再出现+-号时前面一位必须为e/E
                elif (sign or point) and s[i-1] not in 'eE': return False  
                else:
                    sign = 1
                    continue
            if s[i] in 'eE':
                #一个字符串中最多一个e或E，e不能出现在首位，eE不能出现在字符串最后一位，eE后一位必须是数字或+-
                if index or i == 0 or not (i+1-n and (s[i+1].isdigit() or s[i+1] in '+-')): return False 
                else:
                    index = 1
                    continue
            else: #如果s[i]为'.'
                if index or point: return False #一个字符串中最多一个.  .不能写在eE的后面
                elif not (i or s[i+1].isdigit()): return False #.在首位时，后一位为数字
                elif not (i+1-n or s[i-1].isdigit()): return False  #在末尾时，前一位为数字
                elif not (s[i-1].isdigit() or s[i+1].isdigit()): return False #点在中间时，前后至少有一个为数字
                else:
                    point =1
                    continue
        return True

图片

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 Solution:
    def validNumber(self, s: str) -> bool:
        states = [
            { ' ': 0, 's': 1, 'd': 2, '.': 4 }, # 0. start with 'blank'
            { 'd': 2, '.': 4 } ,                # 1. 'sign' before 'e'
            { 'd': 2, '.': 3, 'e': 5, ' ': 8 }, # 2. 'digit' before 'dot'
            { 'd': 3, 'e': 5, ' ': 8 },         # 3. 'digit' after 'dot'
            { 'd': 3 },                         # 4. 'digit' after 'dot' (‘blank’ before 'dot')
            { 's': 6, 'd': 7 },                 # 5. 'e'
            { 'd': 7 },                         # 6. 'sign' after 'e'
            { 'd': 7, ' ': 8 },                 # 7. 'digit' after 'e'
            { ' ': 8 }                          # 8. end with 'blank'
        ]
        p = 0                           # start with state 0
        for c in s:
            if '0' <= c <= '9': t = 'd' # digit
            elif c in "+-": t = 's'     # sign
            elif c in "eE": t = 'e'     # e or E
            elif c in ". ": t = c       # dot, blank
            else: t = '?'               # unknown
            if t not in states[p]: return False
            p = states[p][t]
        return p in (2, 3, 7, 8)

栈与队列

栈是一种具有 「先入后出」 特点的抽象数据结构，可使用数组或链表实现。

1
stack = [] # Python 可将列表作为栈使用

如下图所示，通过常用操作「入栈 push()」,「出栈 pop()」，展示了栈的先入后出特性。

1
2
3
4
stack.append(1) # 元素 1 入栈
stack.append(2) # 元素 2 入栈
stack.pop()     # 出栈 -> 元素 2
stack.pop()     # 出栈 -> 元素 1

Picture4.png

注意：通常情况下，不推荐使用 Java 的 Vector 以及其子类 Stack ，而一般将 LinkedList 作为栈来使用。详细说明请见：Stack，ArrayDeque，LinkedList 的区别

1
2
3
4
5
6
LinkedList<Integer> stack = new LinkedList<>();

stack.addLast(1);   // 元素 1 入栈
stack.addLast(2);   // 元素 2 入栈
stack.removeLast(); // 出栈 -> 元素 2
stack.removeLast(); // 出栈 -> 元素 1

队列是一种具有 「先入先出」 特点的抽象数据结构，可使用链表实现。

1
2
3
4
# Python 通常使用双端队列 collections.deque
from collections import deque

queue = deque()

如下图所示，通过常用操作「入队 push()」,「出队 pop()」，展示了队列的先入先出特性。

1
2
3
4
queue.append(1) # 元素 1 入队
queue.append(2) # 元素 2 入队
queue.popleft() # 出队 -> 元素 1
queue.popleft() # 出队 -> 元素 2

Picture5.png

图书整理 II

读者来到图书馆排队借还书，图书管理员使用两个书车来完成整理借还书的任务。书车中的书从下往上叠加存放，图书管理员每次只能拿取书车顶部的书。排队的读者会有两种操作：

push(bookID)：把借阅的书籍还到图书馆。
pop()：从图书馆中借出书籍。

为了保持图书的顺序，图书管理员每次取出供读者借阅的书籍是 最早 归还到图书馆的书籍。你需要返回 每次读者借出书的值 。
如果没有归还的书可以取出，返回 -1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
class CQueue:
    def __init__(self):
        self.lst1, self.lst2 = [], []
    def appendTail(self, value: int) -> None:
        self.lst1.append(value)
    def deleteHead(self) -> int:
        if self.lst2:   
            return self.lst2.pop()
        if not self.lst1:
                return -1    
        while self.lst1:
            self.lst2.append(self.lst1.pop())
        return self.lst2.pop()

最小栈

请你设计一个 最小栈 。它提供 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class MinStack:
    def __init__(self):
        self.lst = []
        self.lst2 = []  #用来存放最小元素
    def push(self, val: int) -> None:
        self.lst.append(val)
        if not self.lst2 or val <= self.lst2[-1]:  #如果有重复最小元素，也要添加进栈，防止被pop
            self.lst2.append(val) 
    def pop(self) -> None:
        popval = self.lst.pop()
        if self.lst2[-1] == popval:
            self.lst2.pop()
    def top(self) -> int:
        return self.lst[-1]
    def getMin(self) -> int:
        return self.lst2[-1]

验证图书取出顺序

现在图书馆有一堆图书需要放入书架，并且图书馆的书架是一种特殊的数据结构，只能按照 一定 的顺序 放入 和 拿取 书籍。
给定一个表示图书放入顺序的整数序列 putIn，请判断序列 takeOut 是否为按照正确的顺序拿取书籍的操作序列。你可以假设放入书架的所有书籍编号都不相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:  
        dict = {}
        for i in range(len(pushed)):
            dict[pushed[i]] = i
        i = 0
        while i < len(pushed):
            index = dict[popped[i]]   #查看后面的元素是否乱序
            for item in popped[i+1:]:
                if dict[item] < dict[popped[i]]: 
                    if dict[item] < index: 
                        index = dict[item]
                    else:
                        return False
            i += 1
        return True
1
2
3
4
5
6
7
8
9
class Solution:
    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:
        stack, i = [], 0
        for num in putIn:
            stack.append(num) # num 入栈
            while stack and stack[-1] == takeOut[i]: # 循环判断与出栈
                stack.pop()
                i += 1
        return not stack

数据流中的中位数

中位数 是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from heapq import *
#利用最大堆和最小堆
class MedianFinder:

    def __init__(self):
        self.small = []  #储存较小一半的数，大根堆，堆顶为最大值
        self.big = []   #储存较大一半的数，小根堆，堆顶为最小值

    def addNum(self, num: int) -> None:
        if len(self.small) != len(self.big):
            heappush(self.big, num)
            heappush(self.small, -heappop(self.big))
        else:
            heappush(self.small, -num)
            heappush(self.big, -heappop(self.small))

    def findMedian(self) -> float:
        return self.big[0] if len(self.small) != len(self.big) else (self.big[0] - self.small[0]) / 2  #大顶堆存的值为负数

树

树是一种非线性数据结构，根据子节点数量可分为 「二叉树」 和 「多叉树」，最顶层的节点称为「根节点 root」。以二叉树为例，每个节点包含三个成员变量：「值 val」、「左子节点 left」、「右子节点 right」 。

1
2
3
4
5
class TreeNode:
    def __init__(self, x):
        self.val = x      # 节点值
        self.left = None  # 左子节点
        self.right = None # 右子节点

如下图所示，建立此二叉树需要实例化每个节点，并构建各节点的引用指向。

1
2
3
4
5
6
7
8
9
10
11
12
# 初始化节点
n1 = TreeNode(3) # 根节点 root
n2 = TreeNode(4)
n3 = TreeNode(5)
n4 = TreeNode(1)
n5 = TreeNode(2)

# 构建引用指向
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5

Picture6.png

彩灯装饰记录 I

一棵圣诞树记作根节点为 root 的二叉树，节点值为该位置装饰彩灯的颜色编号。请按照从 左 到 右 的顺序返回每一层彩灯编号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 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 decorateRecord(self, root: Optional[TreeNode]) -> List[int]:
        #BFS算法，广度优先
        if not root: return []
        queqe = collections.deque([root])
        res = []
        while queqe:
            tmp = queqe.popleft()
            res.append(tmp.val)
            #如果节点左右树不为空，则将左右树按顺序放进队列中
            if tmp.left: queqe.append(tmp.left)
            if tmp.right: queqe.append(tmp.right)          
        return res

彩灯装饰记录 II

一棵圣诞树记作根节点为 root 的二叉树，节点值为该位置装饰彩灯的颜色编号。请按照从左到右的顺序返回每一层彩灯编号，每一层的结果记录于一行。

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
# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        #BFS算法，并通过1和flag判断该层是否遍历完
        if not root: return []
        queqe = collections.deque([1,root])
        res = []
        flag = False #判断是否为新的一层
        tmp = []
        while queqe:
            if queqe[0] == 1 and not flag: #遇1标志该一层结束
                if tmp:  res.append(tmp) #将该层数据tmp加到res中 
                queqe.popleft()
                tmp = []            #将tmp清空
                flag = True
                continue
            node = queqe.popleft()
            tmp.append(node.val)
            if (node.left or node.right) and flag: 
                queqe.append(1)
                flag = False
            if node.left: queqe.append(node.left)
            if node.right: queqe.append(node.right) 
            if not queqe: res.append(tmp) #队列为空说明循环即将结束，将最后一层数据tmp加到res中
        return res

彩灯装饰记录 III

一棵圣诞树记作根节点为 root 的二叉树，节点值为该位置装饰彩灯的颜色编号。请按照如下规则记录彩灯装饰结果：

第一层按照从左到右的顺序记录
除第一层外每一层的记录顺序均与上一层相反。即第一层为从左到右，第二层为从右到左。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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 decorateRecord(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root: return []
        res, queue = [], collections.deque([root])  #res可以用来判断层数
        while queue:
            tmp = collections.deque()   #使用双向队列
            for _ in range(len(queue)):  #queue的长度变化不会影响循环次数
                node = queue.popleft()
                if  len(res) % 2: tmp.appendleft(node.val) #偶数层从左添加元素
                else: tmp.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            res.append(list(tmp))   #将双向队列改为列表格式添加到res中，满足输出要求
        return res

子结构判断

给定两棵二叉树 tree1 和 tree2，判断 tree2 是否以 tree1 的某个节点为根的子树具有 相同的结构和节点值 。
注意，空树 不会是以 tree1 的某个节点为根的子树具有 相同的结构和节点值 。

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self): #加一个类参数
        self.i = 0
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        if not (A and B): return False #规避空树
        def isSimilarTree(p,q): #定义是否为相似树，即只有最下层的子树可能有不同
            if not q:
                return True
            if not p:
                return False
            if p.val != q.val:
                return False        
            return isSimilarTree(p.left,q.left) and isSimilarTree(p.right,q.right)
        #定义深度搜索算法DFS：
        def dfs(p):
            if not p:
                return
            if p.val == B.val:       #如果遇到和B树根相值同的节点，判断是否是相似的树
                if isSimilarTree(p,B):
                    self.i = 1  #树相同，类属性改为1
                    return
            dfs(p.left)
            dfs(p.right)
        dfs(A)
        return True if self.i else False  #由类属性判断True,Fals
1
2
3
4
5
6
7
8
9
#直接用isSub做递归和遍历，实质也是DFS遍历，将我的版本极度简化了。Krahets定义的recur函数和我定义的isSimilarTree函数相同
class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        def recur(A, B):
            if not B: return True
            if not A or A.val != B.val: return False
            return recur(A.left, B.left) and recur(A.right, B.right)

        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))

翻转二叉树

给定一棵二叉树的根节点 root，请左右翻转这棵二叉树，并返回其根节点。

1
2
3
4
5
6
7
8
#DFS遍历
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root: return  #没有子树的时候，停止翻转
        root.left, root.right = root.right, root.left  #翻转左右树
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root
1
2
3
4
5
6
7
8
9
10
11
12
#DFS遍历，利用栈作交换
class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root: return
        stack = [root]
        while stack:
            node = stack.pop()
            if node.left: stack.append(node.left)
            if node.right: stack.append(node.right)
            node.left, node.right = node.right, node.left
        return root

判断对称二叉树

请设计一个函数判断一棵二叉树是否 轴对称 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#BFS遍历
class Solution:
    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:
        if not root or not (root.left or root.right): return True
        elif bool(root.left) ^ bool(root.right): return False  #异或
        queue_left = deque([root.left])
        queue_right = deque([root.right])
        while queue_left and queue_right:
            node_left, node_right = queue_left.popleft(), queue_right.popleft()
            #比较节点值大小,如果有空子树且不对称的话，输出False
            if node_left.val != node_right.val: return False
            if bool(node_left.left) ^ bool(node_right.right ): return False
            if bool(node_left.right) ^ bool(node_right.left): return False
            #root.left从左往右遍历
            if node_left.left: queue_left.append(node_left.left)
            if node_left.right: queue_left.append(node_left.right)
            #root.right从右往左遍历
            if node_right.right: queue_right.append(node_right.right)
            if node_right.left: queue_right.append(node_right.left)
        return False if queue_left or queue_right else True  #queue_left和queue_right有一个不为空则不对称
1
2
3
4
5
6
7
8
9
#递归 DFS遍历
class Solution:
    def checkSymmetricTree(self, root: TreeNode) -> bool:
        def recur(L, R):
            if not L and not R: return True
            if not L or not R or L.val != R.val: return False
            return recur(L.left, R.right) and recur(L.right, R.left)

        return not root or recur(root.left, root.right)

将二叉搜索树转化为排序的双向链表

将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。

对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

特别地，我们希望可以 就地 完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 中序遍历
class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        def dfs(cur):
            if not cur: return
            dfs(cur.left)
            if self.pre:               #建立一个前置节点
                self.pre.right = cur
                cur.left = self.pre
            else: self.head = cur   #建立头节点
            self.pre = cur           #将pre移动到当前节点
            dfs(cur.right)
        
        if not root:return
        self.pre = None
        dfs(root)
        self.pre.right = self.head   #尾节点指向头节点
        self.head.left = self.pre
        return self.head

寻找二叉搜索树中的目标节点

某公司组织架构以二叉搜索树形式记录，节点值为处于该职位的员工编号。请返回第 cnt 大的员工编号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#递归 反向中序遍历 右根左
class Solution:
    def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:
        def dfs(cur):
            if not cur: return
            dfs(cur.right)
            self.cnt -= 1
            if self.cnt == 0:
                self.res = cur.val         
            dfs(cur.left)
        if not root:return
        self.cnt = cnt
        dfs(root)
        return self.res

计算二叉树的深度

某公司架构以二叉树形式记录，请返回该公司的层级数。

1
2
3
4
5
#后序遍历  DFS
class Solution:
    def calculateDepth(self, root: TreeNode) -> int:
        if not root: return 0
        return max(self.calculateDepth(root.left), self.calculateDepth(root.right)) + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#层级遍历 BFS
class Solution:
    def calculateDepth(self, root: TreeNode) -> int:
        if not root: return 0
        queue, res = [root], 0
        while queue:
        #因为我们不需要真的遍历queue，即我们不需要queue的值，所以用tmp刷新队列即可
            tmp = []   
            for node in queue:
                if node.left: tmp.append(node.left)
                if node.right: tmp.append(node.right)
            queue = tmp
            res += 1
        return res

判断是否为平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

1
2
3
4
5
6
7
8
9
10
11
#由下而上遍历
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def recur(root):
            if not root: return 0
            left = recur(root.left)
            if left == -1: return -1
            right = recur(root.right)
            if right == -1: return -1
            return max(left,right) + 1 if abs(left-right) <= 1 else -1
        return recur(root) != -1

235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

1
2
3
4
5
6
7
8
#递归
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left,p,q)
        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right,p,q)
        return root
1
2
3
4
5
6
7
8
9
10
11
#迭代
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if p.val > q.val: p, q = q, p # 保证 p.val < q.val
        while root:
            if root.val < p.val: # p,q 都在 root 的右子树中
                root = root.right # 遍历至右子节点
            elif root.val > q.val: # p,q 都在 root 的左子树中
                root = root.left # 遍历至左子节点
            else: break
        return root

寻找二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root: return   #叶子返回空
        if root == p or root == q: return root   #遇到p\q时返回根
        left = self.lowestCommonAncestor(root.left,p,q)
        right = self.lowestCommonAncestor(root.right,p,q)
        if not (left or right): return   #左右都为空时返回空
        if not left: return right   #左空右不空时返回右
        if not right: return left   #右空左不空时返回左
        return root   #左右都不空时返回根

序列化与反序列化二叉树

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

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
class Codec:

    def serialize(self, root):
        #使用BFS层级遍历将二叉树转化为字符串
        if not root: return ''
        stack, queue = [], deque([root])  #f用来确定层数，在最后一层不添加n
        #BFS
        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()
                if node == 'n':
                    stack.append(node)
                    continue
                stack.append(str(node.val))
                if node.left: queue.append(node.left)
                else: queue.append('n')   #添加n表明空子树
                if node.right: queue.append(node.right)
                else: queue.append('n')   #添加n表明空子树
        while stack[-1] == 'n':   #删除栈顶的无用n
            stack.pop()
        print(stack)
        return '*'.join(stack)   #用*分隔每棵树
        
    def deserialize(self, data):
        #按照层级遍历的模式还原二叉树
        if not data: return
        #将字符串转化为队列
        data = data.split('*')
        lst = deque(data)
        #root定位根节点
        root = TreeNode(int(lst.popleft()))
        queue= deque([root])
        #层级遍历
        while queue:
            node = queue.popleft()

            if not lst:   #已经遍历结束
                node.left = None
            else:
                node_left = lst.popleft()
                if node_left == 'n':   #子树为空
                    node.left = None
                else: node.left = TreeNode(int(node_left))   #左节点指向一个值为node_left的新节点

            if not lst:   #已经遍历结束
                node.right = None
            else:
                node_right = lst.popleft()
                if node_right == 'n':   #子树为空
                    node.right = None
                else: node.right = TreeNode(int(node_right))  #右节点指向一个值为node_right的新节点

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return roo

排序

排序算法简介

排序算法用作实现列表的排序，列表元素可以是整数，也可以是浮点数、字符串等其他数据类型。生活中有许多需要排序算法的场景，例如：

整数排序： 对于一个整数数组，我们希望将所有数字从小到大排序；
字符串排序： 对于一个姓名列表，我们希望将所有单词按照字符先后排序；
自定义排序： 对于任意一个 已定义比较规则 的集合，我们希望将其按规则排序；

Picture1.png

同时，某些算法需要在排序算法的基础上使用（即在排序数组上运行），例如：

二分查找： 根据数组已排序的特性，才能每轮确定排除两部分中的哪一部分；
双指针： 例如合并两个排序链表，根据已排序特性，才能通过双指针移动在线性时间内将其合并为一个排序链表。
接下来，本文将从「常见排序算法」、「分类方法」、「时间与空间复杂度」三方面入手，简要介绍排序算法。「各排序算法详细介绍」请见后续专栏文章。

常见算法

常见排序算法包括「冒泡排序」、「插入排序」、「选择排序」、「快速排序」、「归并排序」、「堆排序」、「基数排序」、「桶排ss序」。如下图所示，为各排序算法的核心特性与时空复杂度总结。

Picture2.png

如下图所示，为在 「随机乱序」、「接近有序」、「完全倒序」、「少数独特」四类输入数据下，各常见排序算法的排序过程。

分类方法

排序算法主要可根据 稳定性 、就地性 、自适应性 分类。理想的排序算法具有以下特性：

具有稳定性，即相等元素的相对位置不变化；
具有就地性，即不使用额外的辅助空间；
具有自适应性，即时间复杂度受元素分布影响；
特别地，任意排序算法都 不同时具有以上所有特性 。因此，排序算法的选型使用取决于具体的列表类型、元素数量、元素分布情况等应用场景特点。

稳定性：

根据 相等元素 在数组中的 相对顺序 是否被改变，排序算法可分为「稳定排序」和「非稳定排序」两类。

  • 「稳定排序」在完成排序后，不改变 相等元素在数组中的相对顺序。例如：冒泡排序、插入排序、归并排序、基数排序、桶排序。
  • 「非稳定排序」在完成排序后，相等素在数组中的相对位置 可能被改变。例如：选择排序、快速排序、堆排序。

何时需考虑排序算法的稳定性？

数组排序中，由于元素皆为数字，因此稳定和非稳定排序皆可输出相同结果，此时无需考虑排序算法的稳定性。

非稳定排序会改变相等元素的相对次序，这在实际应用场景中可能是不能接受的。如以下代码所示，非稳定排序破坏了输入列表 people 按姓名排序的性质。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 人 = (姓名, 年龄) ，按姓名排序

people = [
    ('A', 19),
    ('B', 18),
    ('C', 21),
    ('D', 19),
    ('E', 23)
]

# 非稳定排序（按年龄）

sort_by_age(people)

# 人 = (姓名, 年龄) ，按年龄排序

people = [
    ('B', 18),
    ('D', 19), # ('D', 19) 和 ('A', 19) 的相对位置改变，输入时按姓名排序的性质丢失
    ('A', 19),
    ('C', 21),
    ('E', 23)
]

就地性：

根据排序过程中 是否使用额外内存（辅助数组），排序算法可分为「原地排序」和「异地排序」两类。一般地，由于不使用外部内存，原地排序相比非原地排序的执行效率更高。

  • 「原地排序」不使用额外辅助数组，例如：冒泡排序、插入排序、选择排序、快速排序、堆排序。
  • 「非原地排序」使用额外辅助数组，例如：归并排序、基数排序、桶排序。

自适应性：
根据算法 时间复杂度 是否 受待排序数组的元素分布影响 ，排序算法可分为「自适应排序」和「非自适应排序」两类。

  • 「自适应排序」的时间复杂度受元素分布影响；例如：冒泡排序、插入排序、快速排序、桶排序。
  • 「非自适应排序」的时间复杂度恒定；例如：选择排序、归并排序、堆排序、基数排序。

是否基于比较：
比较类排序基于元素之间的 比较算子（小于、相等、大于）来决定元素的相对顺序；相对的，非比较排序则不基于比较算子实现。

  • 「基于比较排序」基于元素之间的比较完成排序，例如：冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序。

  • 「非基于比较排序」不基于元素之间的比较完成排序，例如：基数排序、桶排序。

基于比较的排序算法的平均时间复杂度最优为 O(NlogN) ，而非比较排序算法可以达到线性级别的时间复杂度。

时空复杂度
总体上看，排序算法追求时间与空间复杂度最低。而即使某些排序算法的时间复杂度相等，但实际性能还受 输入列表性质、元素数量、元素分布等 等因素影响。

设输入列表元素数量为 N ，常见排序算法的「时间复杂度」和「空间复杂度」如下图所示。

image-20240311191547346

对于上表，需要特别注意：

  • 「基数排序」适用于正整数、字符串、特定格式的浮点数排序，k 为最大数字的位数；「桶排序」中 k 为桶的数量。
  • 普通「冒泡排序」的最佳时间复杂度为 O(N2N^2) ，通过增加标志位实现 提前返回 ，可以将最佳时间复杂度降低至 O(N) 。
  • 在输入列表完全倒序下，普通「快速排序」的空间复杂度劣化至 O(N) ，通过代码优化尾递归优化 保持算法递归较短子数组，可以将最差递归深度降低至 logN 。
  • 普通「快速排序」总以最左或最右元素为基准数，因此在输入列表有序或倒序下，时间复杂度劣化至 O($N^2 $)；通过 随机选择基准数 ，可极大减少此类最差情况发生，尽可能地保持 O(NlogN) 的时间复杂度。
  • 若输入列表是数组，则归并排序的空间复杂度为 O(N) ；而若排序 链表 ，则「归并排序」不需要借助额外辅助空间，空间复杂度可以降低至 O(1) 。

冒泡排序

冒泡排序是最基础的排序算法，由于其直观性，经常作为首个介绍的排序算法。其原理为：

内循环： 使用相邻双指针 j , j + 1 从左至右遍历，依次比较相邻元素大小，若左元素大于右元素则将它们交换；遍历完成时，最大元素会被交换至数组最右边 。
外循环： 不断重复「内循环」，每轮将当前最大元素交换至 剩余未排序数组最右边 ，直至所有元素都被交换至正确位置时结束。

如下图所示，冒泡排序的「外循环」共 N−1 轮，每轮「内循环」都将当前最大元素交换至数组最右边，从而完成对整个数组的排序。

Picture1.png

1
2
3
4
5
6
7
def bubble_sort(nums):
    N = len(nums)
    for i in range(N - 1):           # 外循环
        for j in range(N - i - 1):   # 内循环
            if nums[j] > nums[j + 1]:
                # 交换 nums[j], nums[j + 1]
                nums[j], nums[j + 1] = nums[j + 1], nums[j]

通过增加一个标志位 flag ，若在某轮「内循环」中未执行任何交换操作，则说明数组已经完成排序，直接返回结果即可。

优化后的冒泡排序的最差和平均时间复杂度仍为 O(N2N^2) ；在输入数组 已排序 时，达到 最佳时间复杂度 Ω(N) 。

1
2
3
4
5
6
7
8
9
def bubble_sort(nums):
    N = len(nums)
    for i in range(N - 1):
        flag = False         #  初始化标志位
        for j in range(N - i - 1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                flag = True  # 记录交换元素
        if not flag: break   # 内循环未交换任何元素，则跳出

快速排序

快速排序算法有两个核心点，分别为 哨兵划分 和 递归 。

哨兵划分：以数组某个元素（一般选取首元素）为 基准数 ，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。

递归：对 左子数组 和 右子数组 分别递归执行 哨兵划分，直至子数组长度为 1 时终止递归，即可完成对整个数组的排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def quick_sort(nums, l, r):
    # 子数组长度为 1 时终止递归
    if l >= r: return
    # 哨兵划分操作
    i = partition(nums, l, r)
    # 递归左（右）子数组执行哨兵划分
    quick_sort(nums, l, i - 1)
    quick_sort(nums, i + 1, r)
    
def partition(nums, l, r):
    # 以 nums[l] 作为基准数
    i, j = l, r
    while i < j:
        while i < j and nums[j] >= nums[l]: j -= 1
        while i < j and nums[i] <= nums[l]: i += 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[l], nums[i] = nums[i], nums[l]
    return i

# 调用
nums = [3, 4, 1, 5, 2]
quick_sort(nums, 0, len(nums) - 1)

尾递归

1
2
3
4
5
6
7
8
9
10
11
12
def quick_sort(nums, l, r):
    # 子数组长度为 1 时终止递归
    while l < r:  #迭代代替递归
        # 哨兵划分操作
        i = partition(nums, l, r)
        # 仅递归至较短子数组，控制递归深度
        if i - l < r - i:
            quick_sort(nums, l, i - 1)
            l = i + 1
        else:
            quick_sort(nums, i + 1, r)
            r = i - 1

随机基准数

1
2
3
4
5
6
7
8
9
10
11
12
def partition(nums, l, r):
    # 在闭区间 [l, r] 随机选取任意索引，并与 nums[l] 交换
    ra = random.randrange(l, r + 1)
    nums[l], nums[ra] = nums[ra], nums[l]
    # 以 nums[l] 作为基准数
    i, j = l, r
    while i < j:
        while i < j and nums[j] >= nums[l]: j -= 1
        while i < j and nums[i] <= nums[l]: i += 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[l], nums[i] = nums[i], nums[l]
    return i

归并排序

归并排序体现了 “分而治之” 的算法思想，具体为：

「分」： 不断将数组从 中点位置 划分开，将原数组的排序问题转化为子数组的排序问题；
「治」： 划分到子数组长度为 1 时，开始向上合并，不断将 左右两个较短排序数组 合并为 一个较长排序数组，直至合并至原数组时完成排序；

Picture1.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def merge_sort(nums, l, r):
    # 终止条件
    if l >= r: return
    # 递归划分数组
    m = (l + r) // 2
    merge_sort(nums, l, m)
    merge_sort(nums, m + 1, r)
    # 合并子数组
    tmp = nums[l:r + 1]       # 暂存需合并区间元素
    i, j = 0, m - l + 1       # 两指针分别指向左/右子数组的首个元素
    for k in range(l, r + 1): # 遍历合并左/右子数组
        if i == m - l + 1:
            nums[k] = tmp[j]
            j += 1
        elif j == r - l + 1 or tmp[i] <= tmp[j]:
            nums[k] = tmp[i]
            i += 1
        else:
            nums[k] = tmp[j]
            j += 1

# 调用
nums = [3, 4, 1, 5, 2, 1]
merge_sort(0, len(nums) - 1)

查找

招式拆解 II

某套连招动作记作仅由小写字母组成的序列 arr，其中 arr[i] 第 i 个招式的名字。请返回第一个只出现一次的招式名称，如不存在请返回空格。

1
2
3
4
5
6
7
8
#Counter函数
class Solution:
    def dismantlingAction(self, arr: str) -> str:
        dict = Counter(arr)
        for key in dict:
            if dict[key] == 1:
                return key
        return ' '
1
2
3
4
5
6
7
8
9
#哈希表
class Solution:
    def dismantlingAction(self, arr: str) -> str:
        hmap = collections.OrderedDict()
        for c in arr:
            hmap[c] = not c in hmap
        for k, v in hmap.items():
            if v: return k
        return ' '

统计目标成绩的出现次数

某班级考试成绩按非严格递增顺序记录于整数数组 scores，请返回目标成绩 target 的出现次数。

1
2
3
4
5
6
#二分法 bisect函数
class Solution:
    def countTarget(self, scores: List[int], target: int) -> int:
        a = bisect_left(scores,target)
        b = bisect_right(scores,target)
        return b-a
1
2
3
4
5
6
7
8
9
10
11
#直接二分法
class Solution:
    def countTarget(self, scores: List[int], target: int) -> int:
        def helper(tar):
            i, j = 0, len(scores) - 1
            while i <= j:
                m = (i + j) // 2
                if scores[m] <= tar: i = m + 1
                else: j = m - 1
            return i
        return helper(target) - helper(target - 1)

点名

某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。

1
2
3
4
5
6
7
8
class Solution:
    def takeAttendance(self, records: List[int]) -> int:
        i, j = 0, len(records) - 1
        while i <= j:
            m = (i + j) // 2
            if records[m] == m: i = m + 1
            else: j = m-1
        return i

寻找目标值 - 二维数组

m*n 的二维数组 plants 记录了园林景观的植物排布情况，具有以下特性：

每行中，每棵植物的右侧相邻植物不矮于该植物；
每列中，每棵植物的下侧相邻植物不矮于该植物。

请判断 plants 中是否存在目标高度值 target。

1
2
3
4
5
6
7
8
9
10
# 贪心算法，把matrix改成plants即可
class Solution:
    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:
        matrix = plants
        i, j = len(matrix) - 1, 0   #要确保相邻格子的元素性质不一样，所以选左下或者右上
        while 0 <= i < len(matrix) and 0 <= j < len(matrix[0]):
            if matrix[i][j] > target: i -= 1
            elif matrix[i][j] < target: j += 1
            else: return True
        return False

库存管理 I

仓库管理员以数组 stock 形式记录商品库存表。stock[i] 表示商品 id，可能存在重复。原库存表按商品 id 升序排列。现因突发情况需要进行商品紧急调拨，管理员将这批商品 id 提前依次整理至库存表最后。请你找到并返回库存表中编号的 最小的元素 以便及时记录本次调拨。

1
2
3
4
5
6
7
8
9
10
11
12
13
#二分法一定要滤清思路再写代码
class Solution:
    def stockManagement(self, stock: List[int]) -> int:
        nums = stock
        i, j = 0, len(nums) - 1
        while i < j:
            m = (i + j) // 2
            #m 一定在左排序数组中，即旋转点 xxx 一定在[m+1,j] 闭区间内，因此执行i=m+1。
            if nums[m] > nums[j]: i = m + 1  
            #m一定在右排序数组中，即旋转点 xxx 一定在[i,m]闭区间内，因此执行j=m。
            elif nums[m] < nums[j]: j = m 
            else: j -= 1  #无法判断 mmm 在哪个排序数组中,执行j=j-1缩小范围
        return nums[i]

回溯

设计机械累加器

请设计一个机械累加器，计算从 1、2… 一直累加到目标数值 target 的总和。注意这是一个只能进行加法操作的程序，不具备乘除、if-else、switch-case、for 循环、while 循环，及条件判断语句等高级功能。

1
2
3
4
5
6
7
8
class Solution:
    def __init__(self):
        self.res = 0
    def mechanicalAccumulator(self, target: int) -> int:
        #and左边为True时，右边才会执行
        target > 1 and self.mechanicalAccumulator(target - 1)
        self.res += target
        return self.res

字母迷宫

字母迷宫游戏初始界面记作 m x n 二维字符串数组 grid，请判断玩家是否能在 grid 中找到目标单词 target。
注意：寻找单词时 必须 按照字母顺序，通过水平或垂直方向相邻的单元格内的字母构成，同时，同一个单元格内的字母 不允许被重复使用 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
	def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i,j,k):
            #i,j越界或者board[i][j]和目标值不符时，返回False
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]: return False
            if k == len(word) - 1: return True #word在board中，返回True
            #当board[i][j]等于word[k]时，将该处值改为空，避免重复遍历
            board[i][j] = ''
            #以下、上、右、左的顺序递归，查看临近格是否存在word[k+1]
            res = dfs(i+1,j,k+1) or dfs(i-1,j,k+1) or dfs(i,j+1,k+1) or dfs(i,j-1,k+1)
            #递归回溯后，将值还原
            board[i][j] = word[k]
            return res

        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i,j,0): return True
        return False

衣橱整理

家居整理师将待整理衣橱划分为 m x n 的二维矩阵 grid，其中 grid[i][j] 代表一个需要整理的格子。整理师自 grid[0][0] 开始 逐行逐列 地整理每个格子。

整理规则为：在整理过程中，可以选择 向右移动一格 或 向下移动一格，但不能移动到衣柜之外。同时，不需要整理 digit(i) + digit(j) > cnt 的格子，其中 digit(x) 表示数字 x 的各数位之和。

请返回整理师 总共需要整理多少个格子。

1
2
3
4
5
6
7
8
9
10
#该题题意不明，没有仔细研究，该处直接复制答案
class Solution:
    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:
        def dfs(i, j, si, sj):
            if i >= m or j >= n or cnt < si + sj or (i, j) in visited: return 0
            visited.add((i,j))
            return 1 + dfs(i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj) + dfs(i, j + 1, si, sj + 1 if (j + 1) % 10 else sj - 8)

        visited = set()
        return dfs(0, 0, 0, 0)

二叉树中和为目标值的路径

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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 pathTarget(self, root: Optional[TreeNode], target: int) -> List[List[int]]:
        path, res = [], []
        def dfs(root,target): 
            if not root: return  #终止递归
            path.append(root.val)
            target -= root.val
            if target == 0 and not root.left and not root.right: #符合累加值且为叶节点时，记录路径
                res.append(list(path))  #不能直接把对象path加到res中，否则res结果会随path改变
            dfs(root.left,target)
            dfs(root.right,target)
            path.pop()  #回溯时删除该路径
        dfs(root,target)
        return res

套餐内商品的排列顺序

某店铺将用于组成套餐的商品记作字符串 goods，其中 goods[i] 表示对应商品。请返回该套餐内所含商品的 全部排列方式 。

返回结果 无顺序要求，但不能含有重复的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def goodsOrder(self, goods: str) -> List[str]:
        #递归的核心思想不是返回结果，而是递归参数和终止条件
        #通过换位的想法，来减少重复操作次数
        #通过递归位数，而不是递归字符串，来减少递归次数,实际上这就转化成了树的递归，位数就是节点
        #如果要重复使用初始值，对初始值进行删改操作后要还原（回溯）
        arr, res = list(goods), []  #字符串不可变，所以将其转化为列表操作
        def dfs(x):
            if x == len(arr) - 1:
                res.append(''.join(arr))  ## 添加排列方案
                return
            rep = set()
            for i in range(x,len(arr)):
                if arr[i] in rep: continue  #重复，剪枝
                rep.add(arr[i])
                arr[x], arr[i] = arr[i], arr[x]  # 交换，将 arr[i] 固定在第 x 位
                dfs(x+1)                         # 开启固定第 x + 1 位字符
                arr[x], arr[i] = arr[i], arr[x]  # 恢复交换
        dfs(0)
        return res

分治

分治，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

推理二叉树

某二叉树的先序遍历结果记录于整数数组 preorder，它的中序遍历结果记录于整数数组 inorder。请根据 preorder 和 inorder 的提示构造出这棵二叉树并返回其根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        #将二叉树分为左子树、根、右子树，再去考虑左右子树，即将大问题拆解为小问题，分治思想。
        def recur(root,left,right):
            if left > right: return
            node = TreeNode(preorder[root])
            i = dic[preorder[root]]
            node.left = recur(root+1, left, i-1)
            node.right = recur(root+1+i-left, i+1, right)
            return node

        dic = {}
        for i in range(len(inorder)):
            dic[inorder[i]] = i  #哈希表映射，将值映射为对应索引
        return recur(0, 0, len(inorder)-1)

验证二叉搜索树的后序遍历序列

请实现一个函数来判断整数数组 postorder 是否为二叉搜索树的后序遍历结果。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def verifyTreeOrder(self, postorder: List[int]) -> bool:
        def recur(i,j):
            if i >= j :return True #说明只有一个节点，即为叶节点，无需判断
            p = i
            while postorder[p] < postorder[j]: p += 1 #遍历小于根节点的值，即为左子树
            m = p  #m用来确定右子树范围
            while postorder[p] > postorder[j]: p += 1 #遍历大于根节点的值，即为右子树
            #检验j根点的树是否符合预期（p=j）,检验左子树和右子树是否为搜索树
            return p == j and recur(i,m-1) and recur(m,j-1)       
        return recur(0,len(postorder)-1)

Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n）。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0: return 0  
        if n < 0: x, n = 1/x, -n #转化为正幂讨论
        res = 1
        while n:
            if n & 1: res *= x #如果n二进制位为1,乘上x
            x *= x  #x=x^2
            n >>= 1  #n右移一位
        return res

报数

实现一个十进制数字报数程序，请按照数字从小到大的顺序返回一个整数数列，该数列从数字 1 开始，到最大的正整数 cnt 位数字结束。

1
2
3
4
#应该考虑大数问题，但题目没有限制，这里暂且不考虑
class Solution:
    def countNumbers(self, cnt: int) -> List[int]:
        return [i for i in range(1,10**cnt)]

库存管理 III

仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。

1
2
3
4
class Solution:
    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:
        stock.sort()
        return stock[0:cnt]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#基于快速排序的快速选择
#快速排序的本质就是一种分治算法
class Solution:
    def inventoryManagement(self, stock: List[int], cnt: int) -> List[int]:
        if cnt >= len(stock): return stock
        def quicksort(nums,l,r):
            #以i为哨兵节点，nums[l]为基准数
            i, j = l, r
            while i < j:
                #外循环终止条件无法影响内循环，所以内循环也要加i<j
                while i < j and nums[j] >= nums[l]: j -= 1
                while i < j and nums[i] <= nums[l]: i += 1
                nums[i], nums[j] = nums[j], nums[i] #i,j都停住时交换i,j的值
            nums[i], nums[l] = nums[l], nums[i] #i,j重合时交换i,l的值
            if i > cnt: quicksort(nums,l,i-1)  #在cnt左边时，递归右子数组
            if i < cnt: quicksort(nums,i+1,r)  #在cnt右边时，递归左子数组
            return nums[:cnt] #i=cnt时，输出较小的cnt个数
        return quicksort(stock, 0, len(stock)-1)

交易逆序对的总数

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#归并排序，考虑倒数对
class Solution:
    def reversePairs(self, record: List[int]) -> int:
        def mergesort(l,r):
            if l >= r: return 0  #长度为1，返回0
            m = (l + r) // 2
            res = mergesort(l, m) + mergesort(m+1, r)
            i ,j = 0, m - l + 1
            tmp = record[l:r+1]
            for k in range(l, r+1):
                if i == m - l + 1:   #左子数组已经遍历完
                    record[k] = tmp[j]
                    j += 1
                elif j == r - l + 1 or tmp[i] <= tmp[j]:#右子数组遍历完或左边数字小
                    record[k] = tmp[i]
                    i += 1
                else: #左边数字大，即为倒数对
                    record[k] = tmp[j]
                    j += 1
                    res += m-l - i + 1 #左子树组中i右边的数都比i大，都为倒数对
            return res
        return mergesort(0, len(record)-1)

动态规划

动态规划解题框架

若确定给定问题具有重叠子问题和最优子结构，那么就可以使用动态规划求解。总体上看，求解可分为四步：

状态定义： 构建问题最优解模型，包括问题最优解的定义、有哪些计算解的自变量；
初始状态： 确定基础子问题的解（即已知解），原问题和子问题的解都是以基础子问题的解为起始点，在迭代计算中得到的；
转移方程： 确定原问题的解与子问题的解之间的关系是什么，以及使用何种选择规则从子问题最优解组合中选出原问题最优解；
返回值： 确定应返回的问题的解是什么，即动态规划在何处停止迭代；
完成以上步骤后，便容易写出对应的解题代码。

image-20240320164121181

斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。

答案需要取模 1e9+7(1000000007) ，如计算初始结果为：1000000008，请返回 1。

1
2
3
4
5
6
7
class Solution:
    def fib(self, n: int) -> int:
        if n <= 1: return n
        a, b = 0, 1
        for _ in range(n-1): #在计算的时候就取余，避免数值过大
            a, b = b, (a+b) % int(1e9+7)
        return b

跳跃训练

今天的有氧运动训练内容是在一个长条形的平台上跳跃。平台有 num 个小格子，每次可以选择跳 一个格子 或者 两个格子。请返回在训练过程中，学员们共有多少种不同的跳跃方式。

结果可能过大，因此结果需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

1
2
3
4
5
6
7
class Solution:
    def trainWays(self, num: int) -> int:
        if num == 1: return num
        a, b = 1, 1
        for _ in range(num-1):
            a, b = b, (a+b) % 1000000007
        return b

连续天数的最高销售额

某公司每日销售额记于整数数组 sales，请返回所有 连续 一或多天销售额总和的最大值。

要求实现时间复杂度为 O(n) 的算法。

1
2
3
4
5
class Solution:
    def maxSales(self, sales: List[int]) -> int:
        for i in range(1,len(sales)):
            if sales[i-1] > 0: sales[i] += sales[i-1]
        return max(sales)

买卖芯片的最佳时机

数组 prices 记录了某芯片近期的交易价格，其中 prices[i] 表示的 i 天该芯片的价格。你只能选择 某一天 买入芯片，并选择在 未来的某一个不同的日子 卖出该芯片。请设计一个算法计算并返回你从这笔交易中能获取的最大利润。

如果你不能获取任何利润，返回 0。

1
2
3
4
5
6
7
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        cost, profit = float('+inf'), 0
        for price in prices:
            cost = min(cost, price)
            profit = max(profit, price - cost)
        return profit
1
2
3
4
5
6
7
8
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        f = [0] * n
        for i in range(1,n): 
            f[i] = prices[i] - prices[i-1] + max(0,f[i-1])
        #f[i]代表第i天卖出的最大利润，如果f[i-1]小于等于0，说明price[i-1]是最低价，若大于0，说明有比price[i-1]更低的价格
        return max(f)

珠宝的最高价值

现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：

只能从架子的左上角开始拿珠宝
每次可以移动到右侧或下侧的相邻位置
到达珠宝架子的右下角时，停止拿取
注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def jewelleryValue(self, frame: List[List[int]]) -> int:
        m, n = len(frame), len(frame[0])
        for j in range(1,n):
            frame[0][j] += frame[0][j-1] #第一行只能往右走得到
        for i in range(1,m):
            frame[i][0] += frame[i-1][0] #第一列只能往下走得到 
            for j in range(1,n):
                frame[i][j] += max(frame[i-1][j],frame[i][j-1]) #比较从上往下走和从左往右走谁大
        return frame[-1][-1]

解密数字

现有一串神秘的密文 ciphertext，经调查，密文的特点和规则如下：

密文由非负整数组成
数字 0-25 分别对应字母 a-z
请根据上述规则将密文 ciphertext 解密为字母，并返回共有多少种解密结果。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def crackNumber(self, ciphertext: int) -> int:
        s = str(ciphertext)
        a, b = 1, 1
        y = ciphertext % 10
        while ciphertext > 9: #用进制考虑，额外空间复杂度为O(1)
            ciphertext //= 10
            x = ciphertext % 10
            c, a = a, b
            if 10 <= 10*x+y <= 25: b += c
            y = x        
        return b
1
2
3
4
5
6
7
8
class Solution:
    def crackNumber(self, ciphertext: int) -> int:
        s = str(ciphertext) #额外空间复杂度为O(n)
        a, b = 1, 1
        for i in range(1,len(s)):
            c, a = a, b
            if 10<= int(s[i-1:i+1]) <= 25: b = c + b          
        return b

招式拆解 I

某套连招动作记作序列 arr，其中 arr[i] 为第 i 个招式的名字。请返回 arr 中最多可以出连续不重复的多少个招式。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        #动态规划
        if not s: return 0
        dp, res = '', 0
        for item in s:
            if item not in dp: dp += item
            else:
                if dp[-1] == item: dp = item
                else: dp = dp[dp.find(item)+1:] + item
            res = max(res, len(dp))
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        #双指针,滑动窗口
        if not s: return 0
        res, dic = 1, {}
        i, j = -1, 0
        while j < len(s):
            if s[j] in dic:
                i = max(i,dic[s[j]])
            dic[s[j]] = j
            res = max(j-i, res)
            j += 1
        return res

统计结果概率

你选择掷出 num 个色子，请返回所有点数总和的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 num 个骰子所能掷出的点数集合中第 i 小的那个的概率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def statisticsProbability(self, num: int) -> List[float]:
        f = [1/6] * 6
        if num == 1: return f
        for i in range(2,num+1):
            g = f + [0]*5
            for j in range(5*i+1): #反向推导，有越界问题，需分类讨论
                if j < 6: #前段取j个概率和
                    g[j] = sum(f[:j+1]) * 1/6
                elif j < 5*num-4: #中段取6个概率和
                    g[j] = sum(f[j-5:j+1]) * 1/6
                else:  #后段取5*i+1-j个概率和
                    g[j] = sum(f[j-5:]) * 1/6
            f = g
        return f
1
2
3
4
5
6
7
8
9
10
11
#思路相同，但是极大地简化了代码
class Solution:
    def statisticsProbability(self, n: int) -> List[float]:
        dp = [1 / 6] * 6
        for i in range(2, n + 1):
            tmp = [0] * (5 * i + 1)
            for j in range(len(dp)): #正向推导，由旧骰子推到新骰子
                for k in range(6):
                    tmp[j + k] += dp[j] / 6
            dp = tmp
        return dp

模糊搜索验证

请设计一个程序来支持用户在文本编辑器中的模糊搜索功能。用户输入内容中可能使用到如下两种通配符：

‘.’ 匹配任意单个字符。
‘*’ 匹配零个或多个前面的那一个元素。

请返回用户输入内容 input 所有字符是否可以匹配原文字符串 article。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def articleMatch(self, s: str, p: str) -> bool:
        s, p = '0'+s, '0'+p   #用'0'来代替''，使得题解更清晰
        m, n = len(s), len(p)
        #dp[i][j]表明s[:i+1]是否与p[:j+1]匹配，因为我们前面加上了'0'，所以这里dp[i][j]与s[i],p[j]关联
        dp = [[False ] * n for _ in range(m)]  
        dp[0][0] = True
        for j in range(2, n, 2):  #初始化首行
            dp[0][j] = dp[0][j-2] and p[j] == '*'  # 'x*'可视为''
        for i in range(1,m):
            for j in range(n):
                if p[j] == '*':
                    if dp[i][j-2] or (dp[i-1][j] and p[j-1] in [s[i],'.']):
                        dp[i][j] = True
                else:
                    if dp[i-1][j-1] and p[j] in [s[i],'.']:
                        dp[i][j] = True
        return dp[-1][-1]

贪心

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。

贪心算法不是对所有问题都能得到体最优解，关键是整贪心策略的选择

贪心算法一般按如下步骤进行：

①建立数学模型来描述问题

②把求解的问题分成若干个子问题

③对每个子问题求解，得到子问题的局部最优解

④把子问题的解局部最优解合成原来解问题的一个解

文物朝代判断

展览馆展出来自 13 个朝代的文物，每排展柜展出 5 个文物。某排文物的摆放情况记录于数组 places，其中 places[i] 表示处于第 i 位文物的所属朝代编号。其中，编号为 0 的朝代表示未知朝代。请判断并返回这排文物的所属朝代编号是否连续（如遇未知朝代可算作连续情况）。

1
2
3
4
5
6
7
8
9
class Solution:
    def checkDynasty(self, places: List[int]) -> bool:
        s, ma, mi = [], 0, 14
        for item in places: #提出非0元素，并记录最大最小值
            if item:
                ma = max(ma,item)
                mi = min(mi,item)
                s.append(item)
        return False if len(set(s)) < len(s) else (ma - mi) <= 4

破解闯关密码

闯关游戏需要破解一组密码，闯关组给出的有关密码的线索是：

一个拥有密码所有元素的非负整数数组 password
密码是 password 中所有元素拼接后得到的最小的一个数
请编写一个程序返回这个密码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#快速排序
class Solution:
    def crackPassword(self, password: List[int]) -> str:
        n= len(password)
        for i in range(n):
            password[i] = str(password[i])
        for i in range(n):
            stop = True
            for j in range(n-i-1):
                if int(password[j]+password[j+1]) > int(password[j+1]+password[j]):
                    password[j], password[j+1] = password[j+1], password[j]
                    stop = False
            if stop: break
        return ''.join(password)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#快速排序
class Solution:
    def crackPassword(self, password: List[int]) -> str:
        n= len(password)
        for i in range(n):
            password[i] = str(password[i])
        def quick_sort(l,r):
            if l >= r: return
            i, j = l, r
            while i < j:
                while i<j and int(password[l]+password[j]) <= int(password[j]+password[l]): j-=1
                while i<j and int(password[l]+password[i]) >= int(password[i]+password[l]): i+=1
                password[i], password[j] = password[j], password[i]
            password[l], password[i] = password[i], password[l]
            quick_sort(l,i-1)
            quick_sort(i+1,r)
        quick_sort(0,n-1)
        return ''.join(password)
1
2
3
4
5
6
7
8
9
10
11
12
#定义排序规则，使用sort的key
class Solution:
    def crackPassword(self, password: List[int]) -> str:
        def sort_rule(x, y):
            a, b = x + y, y + x
            if a > b: return 1
            elif a < b: return -1
            else: return 0
        
        strs = [str(num) for num in password]
        strs.sort(key = functools.cmp_to_key(sort_rule))
        return ''.join(strs)

砍竹子

现需要将一根长为正整数 bamboo_len 的竹子砍为若干段，每段长度均为正整数。请返回每段竹子长度的最大乘积是多少。

1
2
3
4
5
6
7
8
9
10
#不考虑大数
class Solution:
    def cuttingBamboo(self, bamboo_len: int) -> int:
        n = bamboo_len
        if n < 4: return n-1
        x = n // 3
        y = n % 3
        if y == 0: return 3**x
        elif y == 1: return 3**(x-1)*4
        else: return 3**x*2
1
2
3
4
5
6
7
8
9
10
#考虑大数
class Solution:
    def cuttingBamboo(self, bamboo_len: int) -> int:
        n, mod = bamboo_len, 1000000007
        if n < 4: return n-1
        x = n // 3
        y = n % 3
        if y == 0: return pow(3,x,mod)
        elif y == 1: return pow(3,x-1,mod)*4 % mod
        else: return pow(3,x,mod)*2 % mod

位运算

位 1 的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。

1
2
3
4
5
6
7
8
#逐位判断
class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            if n & 1: res += 1
            n >>= 1
        return res
1
2
3
4
5
6
7
8
#巧用n & n-1 消去最右侧的1
class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            res += 1
            n &= n - 1
        return res

加密运算

计算机安全专家正在开发一款高度安全的加密通信软件，需要在进行数据传输时对数据进行加密和解密操作。假定 dataA 和 dataB 分别为随机抽样的两次通信的数据量：

正数为发送量
负数为接受量
0 为数据遗失
请不使用四则运算符的情况下实现一个函数计算两次通信的数据量之和（三种情况均需被统计），以确保在数据传输过程中的高安全性和保密性。

1
2
3
4
5
6
7
8
9
class Solution:
    def encryptionCalculate(self, dataA: int, dataB: int) -> int:
        #python的符号位有无数位（内存无限）
        x =0xffffffff #32位的1
        dataA, dataB = dataA & x, dataB & x #只保留32位，相当于提取出负数不带符号的补码
        while dataB != 0:
            dataA, dataB = (dataA ^ dataB), (dataA & dataB) << 1 & x
        #最大的正数只可能是 2 的 31次-1 即 0x7ffffffff，如果是负数，要将其还原。
        return dataA if dataA <= 0x7fffffff else ~(dataA ^ x)

撞色搭配

整数数组 sockets 记录了一个袜子礼盒的颜色分布情况，其中 sockets[i] 表示该袜子的颜色编号。礼盒中除了一款撞色搭配的袜子，每种颜色的袜子均有两只。请设计一个程序，在时间复杂度 O(n)，空间复杂度O(1) 内找到这双撞色搭配袜子的两个颜色编号。

1
2
3
4
5
6
7
8
9
class Solution:
    def sockCollocation(self, sockets: List[int]) -> List[int]:
        x, y ,n, m = 0, 0, 0, 1
        for num in sockets: n ^= num #求出目标值x^y
        while m & n == 0: m <<= 1 #找出x^y中为1的位（x与y不同的位）,通过m记录
        for num in sockets: #靠不同位将数组分为两类
            if num & m: x ^= num #找出不重复的x
            else: y ^= num #找出不重复的y
        return x,y

训练计划 VI

教学过程中，教练示范一次，学员跟做三次。该过程被混乱剪辑后，记录于数组 actions，其中 actions[i] 表示做出该动作的人员编号。请返回教练的编号。

1
2
3
4
5
6
7
8
#位运算，有限状态机
class Solution:
    def trainingPlan(self, actions: List[int]) -> int:
        ones, twos = 0, 0
        for action in actions:
            ones = ones ^ action & ~twos
            twos = twos ^ action & ~ones
        return ones
1
2
3
4
5
6
7
#Counter函数
class Solution:
    def trainingPlan(self, actions: List[int]) -> int:
        dic = Counter(actions)
        for x,y in dic.items():
            if y == 1:
                return x

数学

库存管理 II

仓库管理员以数组 stock 形式记录商品库存表。stock[i] 表示商品 id，可能存在重复。请返回库存表中数量大于 stock.length / 2 的商品 id

1
2
3
4
5
#哈希表法
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums = Counter(nums)
        return nums.most_common(1)[0][0]
1
2
3
4
5
6
7
8
9
10
11
12
#摩尔投票法
#抵消掉不同的树，剩下的一定是众数
class Solution:
    def inventoryManagement(self, stock: List[int]) -> int:
        votes, count = 0, 0
        for num in stock:
            if votes == 0: x = num
            votes += 1 if num == x else -1
        # 验证 x 是否为众数
        for num in stock:
            if num == x: count += 1
        return x if count > len(stock) // 2 else 0 # 当无众数时返回 0

查找总价格为目标值的两个商品

购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。

1
2
3
4
5
6
7
class Solution:
    def twoSum(self, price: List[int], target: int) -> List[int]:
        i, j = 0, len(price)-1
        while i < j:
            if price[i]+price[j] == target: return [price[i],price[j]]
            while i<j and price[i]+price[j] > target: j -= 1
            while i<j and price[i]+price[j] < target: i += 1

数字 1 的个数

给定一个整数 num，计算所有小于等于 num 的非负整数中数字 1 出现的个数。

k神题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def digitOneInNumber(self, num: int) -> int:
        n = num
        digit, res = 1, 0
        high, cur, low = n // 10, n % 10, 0 #高位，当前位，低位
        while high != 0 or cur != 0: #高位和当前位同时为0说明溢出
            if cur == 0: res += high * digit
            elif cur == 1: res += high * digit + low + 1
            else: res += (high + 1) * digit
            low += cur * digit
            cur = high % 10
            high //= 10
            digit *= 10
        return res

找到第 k 位数字

某班级学号记录系统发生错乱，原整数学号序列 [0,1,2,3,4,…] 分隔符丢失后变为 01234… 的字符序列。请实现一个函数返回该字符序列中的第 k 位数字。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def findKthNumber(self, k: int) -> int:
        res, n, nine = 0, 0, 0.9
        while res < k: #找出k是在n位数中
            nine *= 10
            n += 1
            res += nine * n
        x, y = (int(res) - k) // n, (int(res) - k) % n #第n位数最大者中反推k
        pur = 10**n - 1 - x
        return int(str(pur)[-1-y])

破冰游戏

社团共有 num 位成员参与破冰游戏，编号为 0 ~ num-1。成员们按照编号顺序围绕圆桌而坐。社长抽取一个数字 target，从 0 号成员起开始计数，排在第 target 位的成员离开圆桌，且成员离开后从下一个成员开始计数。请返回游戏结束时最后一位成员的编号。

1
2
3
4
5
6
7
#约瑟夫环，x→(x+t) mod n
class Solution:
    def iceBreakingGame(self, num: int, target: int) -> int:
        x = 0
        for i in range(2, num + 1):
            x = (x + target) % i
        return x