算法题目 剑指offer题目

Posted by SunQH Blog on February 13, 2021

按书内容做题

ACM模式练习

输入输出

单行

1
2
3
4
import sys
for line in sys.stdin:
    data = line.split()
    print(int(data[0]) + int(data[1]))
1
2
data = input().split(' ')

个数+多行

1
2
3
4
5
6
7
8
import sys
line = int(input())
res = []
for i in range(line):
    data = [int(e) for e in input().split(' ')]
    res.append(sum(data))
for r in res:
    print(r)
1
2
3
4
5
6
7
8
9
10
11
12
import sys
 
try:
    while True:
        line = sys.stdin.readline()
        x = line.split()
        if len(line.split()) == 1 :
            continue
        else:
            print(int(x[0])+int(x[1]))
except:
    pass

多行+终止条件

1
2
3
4
5
6
7
8
9
10
import sys
res = []
while True:
    data = [int(e) for e in input().split()]
    if data[0] == data[1] == 0:
        break
    res.append(sum(data))
    
for r in res:
    print(r)

多行(无终止条件)

1
2
3
4
5
6
7
8
9
10
import sys

res = []
try:
    while True:
        data = [int(e) for e in input().split()]
        res.append(sum(data))
except:
    for r in res:
        print(r)

有行提示和未知行数的情况

1
2
3
4
5
6
7
8
9
10
11
12
import sys
while True:   # 有while True,则只要没有到最底下就会一直循环进入try,直到到底才会进入except
    nums = set()
    try:
        line_num = int(input())
        for _ in range(line_num):
            nums.add(int(input()))
        for i in sorted(list(nums)):
            print(i)
    except:
        pass
            

有while True,则只要没有到最底下就会一直循环进入try,直到到底才会进入except

HW机试

✅(10m) HJ1 字符串最后一个单词的长度

✅(15m) HJ2 计算某字母出现次数

字符串变大小写

变大写:str.upper()

变小写:str.lower()

🚩(30m) HJ3 明明的随机数

1
2
3
4
5
6
7
8
9
10
11
import sys
while True:   # 有while True,则只要没有到最底下就会一直循环进入try,直到到底才会进入except
    nums = set()
    try:
        line_num = int(input())
        for _ in range(line_num):
            nums.add(int(input()))
        for i in sorted(list(nums)):
            print(i)
    except:
        pass

有行提示和未知行数的情况

有while True,则只要没有到最底下就会一直循环进入try,直到到底才会进入except

✅(5m) HJ4 字符串分隔

🚩(10m)HJ5 进制转换

✅(40m) HJ6 质数因子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
raw = num = int(input())

res = []
zhi = 2
maxval = int(num**(1/2))  # 注意有变量时要考虑能不能放到while上,可能会变
while num>=zhi and zhi <= maxval :
    if num < zhi:
        break
    if num%zhi == 0:
        res.append(zhi)
        num //= zhi
    else:
        zhi += 1
if num != 1:   # 注意要再判断一下是否找完了质因子
    res.append(num)
    
print(" ".join(map(str,res))+" ")

maxval = int(num**(1/2)) # 注意有变量时要考虑能不能放到while上,可能会变

✅(10m) HJ7 取近似值

✅(40m) HJ8 合并表记录

1
2
3
4
5
6
7
8
9
10
11
12
13
import collections
num_lines = int(input())
res_dict = {}
for i in range(num_lines):
    [index,num] = map(int,input().split())
    if index in res_dict.keys():
        res_dict[index] += num
    else:
        res_dict[index] = num

# 先用items属性将字典变为可迭代对象,再进行排序。key 默认安装key值排序。
for (index,num) in sorted(res_dict.items(), key=lambda x:x[0], reverse=False ):
    print(index,num)

先用items属性将字典变为可迭代对象,再进行排序。key 默认安装key值排序。

1
2
for (index,num) in sorted(res_dict.items(), key=lambda x:x[0], reverse=False ):
    print(index,num)

✅(15m) HJ9 提取不重复的整数

✅(3m) HJ10 字符个数统计

✅(2m) HJ11 数字颠倒

✅(1m) HJ12 字符串反转

✅(2m) HJ13 句子逆序

✅(10m) HJ14 字符串排序

✅(2m) HJ15 求int型正整数在内存中存储时1的个数

🚩(20m) HJ16 购物单

✅(40m) HJ17 坐标移动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
data = input().split(';')
direction = {'A':(-1,0),'D':(1,0),'W':(0,1),'S':(0,-1)}
pos_x,pos_y = 0,0
for e in data:
    if e and e[0] in 'ADWS':
        if (len(e)==2 and '0' <= e[1] <= '9') or (len(e)==3 and '0' <= e[1] <= '9' and '0' <= e[2] <= '9'):  # 注意0是最小的 '0'<'00'
                pos_x+=direction[e[0]][0]*int(e[1:])
                pos_y+=direction[e[0]][1]*int(e[1:])
print("{},{}".format(pos_x,pos_y))
        
"""
print( c + " 的ASCII 码为", ord(c))
print( a , " 对应的字符为", chr(a))
"""        

ASCII - 注意数字不能合起来用ascii比较

print( c + “ 的ASCII 码为”, ord(c)) print( a , “ 对应的字符为”, chr(a))

1
2
>>> '0' <= '1A' <= '99'
True

正则表达式

1
res = ``"[ADWS]\\d{1}\\d?"``;

🚩(30m) HJ18 识别有效的IP地址和掩码并进行分类统计

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
import sys
 
#判断子网掩码是否存在非连续的1,(以下是所有连续1的情况)
lll=['254','252','248','240','224','192','128','0']
A, B, C, D, E, err, pri = 0,0,0,0,0,0,0
 
#检测IP是否有效
def check_ip(ip):
    if len(ip)!=4 or " " in ip: return False
    else:
        for i in range(4):
            if int(ip[i])<0 or int(ip[i])>255:
                return False
        return True
     
     
def check_mask(ms):
    if len(ms)!=4:
        return  False
    if ms[0]=='255':
        if ms[1]=='255':
            if ms[2]=='255':
                if ms[3] in lll:
                    return True
                else:
                    return False
            elif ms[2] in lll and ms[3]=='0':
                return True
            else:
                return False
        elif ms[1] in lll and ms[2]==ms[3]=='0':
            return True
        else:
            return False
    elif ms[0] in lll and ms[2]==ms[3]==ms[4]=='0':
        return True
    else:
        return False
 
#主函数
while True:
     
    string=sys.stdin.readline().strip()
    if string=='':
        break
    list1=string.split('~')[0]  #IP地址分割
    list2=string.split('~')[1]  #子网掩码分割
    ip=list1.split('.')
    ms=list2.split('.')
    if check_mask(ms) and check_ip(ip):
        if 1<=int(ip[0])<=126:
            A+=1
        if 128<=int(ip[0])<=191:
            B+=1
        if 192<=int(ip[0])<=223:
            C+=1
        if 224<=int(ip[0])<=239:
            D+=1
        if 240<=int(ip[0])<=255:
            E+=1
        if int(ip[0])==10 or (int(ip[0])==172 and 15<int(ip[1])<32) or (int(ip[0])==192 and int(ip[1])==168):
            pri+=1
    else:
        err+=1
print('%s %s %s %s %s %s %s'%(A,B,C,D,E,err,pri))

🚩(1.0h) HJ19 简单错误记录

✅(30m) HJ20 密码验证合格程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
while True:
    try:
        data = input()
        a = b = c = d = 0
        for e in data:
            if e.isdigit():
                a = 1
            elif e.islower():
                b = 1
            elif e.isupper():
                c = 1
            else:
                d = 1
        flag = True
        for j in range(len(data)-3):
            if data.count(data[j:j+3])>1:
                flag = False
        if len(data)>8 and (a+b+c+d)>=3 and flag:
            print('OK')
        else:
            print('NG')
    except:
        break

判断包含数字大小写的方法

1
2
3
4
5
6
7
8
9
        for e in data:
            if e.isdigit():
                a = 1
            elif e.islower():
                b = 1
            elif e.isupper():
                c = 1
            else:
                d = 1

判断字符串里子串数量方法

1
data.count(data[j:j+3])

✅(20m) HJ21 简单密码破解

T AC 题号 题名
    HJ108 求最小公倍数
    HJ107 求解立方根
    HJ106 字符逆序
    HJ105 记负均正II
    HJ103 Redraiment的走法
    HJ102 字符统计
    HJ101 输入整型数组和排序标识,对其元素按照升序或降序进行排序
    HJ100 等差数列
    HJ99 自守数
    HJ98 自动售货系统
    HJ97 记负均正
    HJ96 表示数字
    HJ95 人民币转换
    HJ94 记票统计
    HJ93 数组分组
    HJ92 在字符串中找出连续最长的数字串
    HJ91 走方格的方案数
    HJ90 合法IP
    HJ89 24点运算
    HJ88 扑克牌大小
    HJ87 密码强度等级
    HJ86 求最大连续bit数
    HJ85 字符串运用-密码截取
    HJ84 统计大写字母个数
    HJ83 二维数组操作
    HJ82 将真分数分解为埃及分数
    HJ81 字符串匹配
    HJ80 整形数组合并
    HJ77 火车进站
    HJ76 尼科彻斯定理
    HJ75 公共字串计算
    HJ74 参数解析
    HJ73 计算日期到天数转换
    HJ72 百钱买百鸡问题
    HJ71 字符串通配符
    HJ70 矩阵乘法计算量估算
    HJ69 矩阵乘法
    HJ68 成绩排序
    HJ67 24点游戏算法
    HJ66 配置文件恢复
    HJ65 查找两个字符串a,b中的最长公共子串
    HJ64 MP3光标位置
    HJ63 DNA序列
    HJ62 查找输入整数二进制中1的个数
    HJ61 放苹果
    HJ60 查找组成一个偶数最接近的两个素数
    HJ59 找出字符串中第一个只出现一次的字符
    HJ58 输入n个整数,输出其中最小的k个
    HJ57 无线OSS-高精度整数加法
    HJ56 iNOC产品部–完全数计算
    HJ55 (练习用)挑7
    HJ54 表达式求值
    HJ53 iNOC产品部-杨辉三角的变形
    HJ52 计算字符串的距离
    HJ51 输出单向链表中倒数第k个结点
    HJ50 四则运算
    HJ49 多线程
    HJ48 从单向链表中删除指定值的节点
    HJ47 线性插值
    HJ46 按字节截取字符串
    HJ45 名字的漂亮度
    HJ44 Sudoku-Java
    HJ43 迷宫问题
    HJ42 学英语
    HJ41 称砝码
    HJ40 输入一行字符,分别统计出包含英文字母、空格、数字和其它字符的个数
    HJ39 判断两个IP是否属于同一子网
    HJ38 求小球落地5次后所经历的路程和第5次反弹的高度
    HJ37 统计每个月兔子的总数
    HJ36 字符串加密
    HJ35 蛇形矩阵
    HJ34 图片整理
    HJ33 整数与IP地址间的转换
    HJ32 【中级】字符串运用-密码截取
    HJ31 【中级】单词倒排
🚩 50m HJ30 字符串合并处理
30m HJ29 字符串加解密
  HJ28 素数伴侣
50m HJ27 查找兄弟单词
40m HJ26 字符串排序
🚩 5m HJ25 数据分类处理
40m HJ24 合唱队
30m HJ23 删除字符串中出现次数最少的字符
30m HJ22 汽水瓶

✅ 30m HJ22 汽水瓶

1
2
3
4
5
6
7
8
9
while True:
    try:
        a=int(input())
        if a!=0:
            print (a//2)
        else:
            pass
    except:
        break

2个空瓶子即可换一瓶汽水喝,而且喝完之后手里也没有空瓶子。

✅ 40m HJ26 字符串排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
while True:   # 注意会有多行
    try:
        data = input()
        res = list(data)
        temp = []

        for i,e in enumerate(data):
            if ord('A')<=ord(e)<=ord('Z') or ord('a')<=ord(e)<=ord('z'):
                temp.append(e)
        #     else:
        #         res[i] = e
        temp.sort(key=lambda x: ord(x) if ord('A')<=ord(x)<=ord('Z') else ord(x)-32)

        ind = 0
        for i in range(len(res)):
            if ord('A')<=ord(res[i])<=ord('Z') or ord('a')<=ord(res[i])<=ord('z'):   # 注意‘A’到‘Z’和‘a’到‘z’是不连续的
                res[i] = temp[ind]
                ind+=1

        print("".join(res))
        
    except:
        break

题解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
while True:   # 注意会有多行
    try:
        data = input()
        res = list(data)
        temp = []

        for i,e in enumerate(data):
            if e.isalpha():
                temp.append(e)
        #     else:
        #         res[i] = e
        temp.sort(key=lambda c:c.lower())

        ind = 0
        for i in range(len(res)):
            if res[i].isalpha():   # 注意‘A’到‘Z’和‘a’到‘z’是不连续的
                res[i] = temp[ind]
                ind+=1

        print("".join(res))
        
    except:
        break

字母改小写— c.lower(),判断是否是字母— ` e.isalpha()`

一定要用while Ture方法防止有多个输入的隐形bug

1
2
3
4
5
while True:   # 注意会有多行
    try:
    	pass
		except:
			pass

注意‘A’到‘Z’和‘a’到‘z’是不连续的,要分开写

1
if ord('A')<=ord(res[i])<=ord('Z') or ord('a')<=ord(res[i])<=ord('z'):   # 注意‘A’到‘Z’和‘a’到‘z’是不连续的

🚩 50m HJ30 字符串合并处理

2进制转16进制

hex(int(‘1101’,2))[2:]

按奇数偶数拆分list

1
2
        res[::2] = sorted(res[::2])
        res[1::2] = sorted(res[1::2])

rjust() — 填充函数

1
2
3
4
5
6
7
8
9
10
11
12
def operatStr(num):
    num = int(num,16)   #转换成16进制整数
    print('num is:',num)
    bc = format(num,'b').rjust(4,'0')
    print('bc is:',bc)
    bc = list(bc)
    bc.reverse()
    print('last bc is:',bc)
    num = int(''.join(bc),2)
    print('last num is:',num)
    hc = format(num,'x')
    return hc.upper()
1
rjust(4,"0")

Python rjust() 返回一个原字符串右对齐,并使用空格填充至长度 width 的新字符串。如果指定的长度小于字符串的长度则返回原字符串。

语法

rjust()方法语法:

1
str.rjust(width[, fillchar])

参数

  • width – 指定填充指定字符后中字符串的总长度.
  • fillchar – 填充的字符,默认为空格。

返回值

返回一个原字符串右对齐,并使用空格填充至长度 width 的新字符串。如果指定的长度小于字符串的长度则返回原字符串

format()— 格式化函数

python format 格式化函数

数字 格式 输出 描述
3.1415926 {:.2f} 3.14 保留小数点后两位
3.1415926 {:+.2f} +3.14 带符号保留小数点后两位
-1 {:+.2f} -1.00 带符号保留小数点后两位
2.71828 {:.0f} 3 不带小数
5 {:0>2d} 05 数字补零 (填充左边, 宽度为2)
5 {:x<4d} 5xxx 数字补x (填充右边, 宽度为4)
10 {:x<4d} 10xx 数字补x (填充右边, 宽度为4)
1000000 {:,} 1,000,000 以逗号分隔的数字格式
0.25 {:.2%} 25.00% 百分比格式
1000000000 {:.2e} 1.00e+09 指数记法
13 {:>10d} 13 右对齐 (默认, 宽度为10)
13 {:<10d} 13 左对齐 (宽度为10)
13 {:^10d} 13 中间对齐 (宽度为10)
11 '{:b}'.format(11) '{:d}'.format(11) '{:o}'.format(11) '{:x}'.format(11) '{:#x}'.format(11) '{:#X}'.format(11) 1011 11 13 b 0xb 0XB 进制

^, <, > 分别是居中、左对齐、右对齐,后面带宽度, : 号后面带填充的字符,只能是一个字符,不指定则默认是用空格填充。

+ 表示在正数前显示 +,负数前显示 -; (空格)表示在正数前加空格

b、d、o、x 分别是二进制、十进制、八进制、十六进制。

LCOF

✅ 03数组中重复的数字

​ 找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

1
2
3
4
5
示例 1:

输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3 

限制:

2 <= n <= 100000

回溯算法(回溯搜索算法)

  1. 深度优先遍历的特有的现象,节约空间
    全排列思路:
    在枚举第一位的时候,有 3 种情况。
    在枚举第二位的时候,前面已经出现过的数字就不能再被选取了;
    在枚举第三位的时候,前面 2 个已经选择过的数字就不能再被选取了。
1
2
3
4
5
6
7
8
9
10
11
12
# 自己做的: 排序后前后对比
# 90% 100%
nums = [2, 3, 1, 0, 2, 5, 3]

def findRepeatNumber(nums) -> int:
    nums_sorted = sorted(nums)
    length = len(nums_sorted)
    for i in range(length-1):
        if nums_sorted[i] == nums_sorted[i+1]:
            return nums_sorted[i]
        
findRepeatNumber(nums)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 法2: 原地替换 不如我的高
nums = [2, 3, 1, 0, 2, 5, 3]

def findRepeatNumber(nums) -> int:
    nums_sorted = sorted(nums)
    length = len(nums_sorted)
    for i in range(length):
        while nums_sorted[i] != i:
            if nums_sorted[i] == nums_sorted[nums_sorted[i]]:
                return nums_sorted[i]
            temp = nums_sorted[i]
            nums_sorted[i] = nums_sorted[temp]
            nums_sorted[temp] = temp
            
findRepeatNumber(nums)
1
2
3
4
5
6
7
8
9
10
11
12
# 法3: hash表
nums = [2, 3, 1, 0, 2, 5, 3]

def findRepeatNumber(nums) -> int:
    hashlist = [False for i in range(len(nums))]
    for i in range(len(nums)):
        if hashlist[nums[i]] == True:
            return nums[i]
        else: 
            hashlist[nums[i]] = True
        
findRepeatNumber(nums)

✅ 04. 二维数组中的查找

在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下:

1
2
3
4
5
6
7
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

给定 target = 5,返回 true。 给定 target = 20,返回 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
25
26
27
28
29
30
matrix = [
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]]

matrix = [[5]]

def findNumberIn2DArray(matrix, target):
    if len(matrix)==0 or len(matrix[0])==0:
        return False  
    
    row = 0
    col = len(matrix[0])-1
    while True:
        if matrix[row][col]==target:
            return True

        if matrix[row][col]>target:
            if (col==0): 
                return False
            else: 
                col -= 1
        elif matrix[row][col]<target:
            if (row==len(matrix)-1):
                return False
            else: 
                row += 1
findNumberIn2DArray(matrix, 5)

C++

✅ 05. 替换空格

请实现一个函数,把字符串 s 中的每个空格替换成”%20”。

示例 1:

1
2
输入:s = "We are happy."
输出:"We%20are%20happy."
1
s = "We are happy."
1
2
3
4
5
6
7
8
9
# 90 100 
# 注意replace() 不改变原str内容能提高, 
# 在 Python 和 Java 等语言中,字符串都被设计成不可变的类型,
# 即无法直接修改字符串的某一位字符,需要新建一个字符串实现。
class Solution:
    def replaceSpace(s: str) -> str:        
        return s.replace(' ','%20')

Solution.replaceSpace(s)
1
2
3
4
5
6
# 切割拼接法
class Solution:
    def replaceSpace(s: str) -> str:    
        lst = s.split(' ')
        return '%20'.join(lst)
Solution.replaceSpace(s)

✅06. 从尾到头打印链表

自制链表及其函数

输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

1
2
3
4
示例 1:

输入:head = [1,3,2]
输出:[2,3,1]	
1
head = [1,3,2]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def reversePrint(head):
        res = []
        while head:
            res.append(head.val)
            head = head.next
        return res[::-1]

head = l1
Solution.reversePrint(head)

2️⃣

✅ (20m)07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

1
2
3
4
5
6
7
8
9
10
11
例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

2️⃣

细节

在中序遍历中对根节点进行定位时,一种简单的方法是直接扫描整个中序遍历的结果并找出根节点,但这样做的时间复杂度较高。我们可以考虑使用哈希表来帮助我们快速地定位根节点。对于哈希映射中的每个键值对,键表示一个元素(节点的值),值表示其在中序遍历中的出现位置。在构造二叉树的过程之前,我们可以对中序遍历的列表进行一遍扫描,就可以构造出这个哈希映射。在此后构造二叉树的过程中,我们就只需要 O(1) 的时间对根节点进行定位了

1
2
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder:
            return None
        root_val = preorder[0]
        ind = inorder.index(root_val)
        print(ind)
        root = TreeNode(root_val)
        root.left = self.buildTree(preorder[1:ind+1], inorder[:ind])
        root.right = self.buildTree(preorder[ind+1:], inorder[ind+1:])
        return root

官解(使用了set):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> 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(i - left + root + 1, i + 1, right) # 开启右子树递归
            return node                                           # 回溯返回根节点

        dic, preorder = {}, preorder
        for i in range(len(inorder)):
            dic[inorder[i]] = i
        return recur(0, 0, len(inorder) - 1)

✅(20m)09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

1
2
3
4
5
6
7
8
9
10
11
12
示例 1:

输入:
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出:[null,null,3,-1]
示例 2:

输入:
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出:[null,-1,null,null,5,2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class CQueue:

    def __init__(self):
        self.A, self.B = [], []
        
    def appendTail(self, value: int) -> None:
        self.A.append(value)

    def deleteHead(self) -> int:
        if self.B: return self.B.pop()
        if not self.A: return -1        
        while self.A:
            self.B.append(self.A.pop())
        return self.B.pop()


# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()

2️⃣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class CQueue:
    def __init__(self):
        self.s1 = []
        self.s2 = []

    def appendTail(self, value: int) -> None:
        self.s1.append(value)

    def deleteHead(self) -> int:
        if len(self.s2) == 0:
            if len(self.s1) == 0:
                return -1
            while self.s1:
                self.s2.append(self.s1.pop())
        return self.s2.pop()

✅10- I. 斐波那契数列

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:

F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

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

1
示例 1:输入:n = 2输出:1示例 2:输入:n = 5输出:5

尝试动态规划方法

1
n = 43
1
class Solution:    def fib(self, n: int) -> int:        if n == 0: return 0        if n == 1: return 1        fiblist = [0,1]        for i in range(2,n+1):            fiblist.append((fiblist[i-1]+fiblist[i-2])% 1000000007)        return fiblist.pop()                                
1
# 动态规划方法class Solution:    def fib(self, n: int) -> int:        if n == 0: return 0        if n == 1: return 1        a, b = 0, 1        for _ in range(n):            a, b = b, a+b        return a % 1000000007
1
2
3
solution = Solution()
result = solution.fib(n)
result

2️⃣(32m)

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 fib(self, n: int) -> int:
        if n == 0: return 0
        if n == 1 or n == 2:
            return 1
        # 1
        # dp = [0 for i in range(n+1)]
        # dp[1], dp[2] = 1, 1
        
        # # 2
        # for i in range(3,n+1):
        #     dp[i] = dp[i-1] + dp[i-2]
        
        # return dp[n] % (10**9+7)

        pre, cur = 1, 1
        for i in range(n-2):
            sum = pre + cur 
            pre, cur = cur, sum
        
        return cur % (10**9+7)

✅ 10- II. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

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

1
2
3
4
5
6
7
8
示例 1:

输入:n = 2
输出:2
示例 2:

输入:n = 7
输出:21
1
n = 7
1
2
3
4
5
6
7
8
9
class Solution:
    def numWays(self, n: int) -> int:
        if n == 0: return 0
        if n == 1: return 1
        if n == 2: return 2
        a, b = 1, 2
        for _ in range(n-1):
            a, b = b, a+b
        return a%1000000007
1
2
3
solution = Solution()
result = solution.numWays(n)
result

🚩11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。

1
2
3
4
5
6
7
8
示例 1:

输入:[3,4,5,1,2]
输出:1
示例 2:

输入:[2,2,2,0,1]
输出:0

2️⃣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def minArray(self, numbers: List[int]) -> int:
        l, r = 0, len(numbers)-1
        if numbers[0] < numbers[-1]:
            return numbers[0]
        while l <= r:
            mid = (l+r)//2
            if numbers[mid] > numbers[r]:
                l = mid + 1
            elif numbers[mid] < numbers[r]:
                r = mid  # 不同之处, 要保留右边界
            elif numbers[mid] == numbers[r]:  
                r -= 1  # 不同之处,相同需要一步一步走
        if l > len(numbers) - 1 or numbers[l] > numbers[r]:
            return -1
        return numbers[l]

🚩12. 矩阵中的路径

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。例如,在下面的3×4的矩阵中包含一条字符串“bfce”的路径(路径中的字母用加粗标出)。

[[“a”,”b”,”c”,”e”], [”s”,”f”,”c”,”s”], [“a”,”d”,”e”,”e”]]

但矩阵中不包含字符串“abfb”的路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入这个格子。

1
示例 1:输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"输出:true示例 2:输入:board = [["a","b"],["c","d"]], word = "abcd"输出:false
1
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]word = "ABCCED"

2️⃣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k] or (i,j) in visited: return False
            if k == len(word) - 1: return True
            visited.add((i,j))
            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)
            visited.remove((i,j))
            return res

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

🚩13. 机器人的运动范围

地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。但它不能进入方格 [35, 38],因为3+5+3+8=19。请问该机器人能够到达多少个格子?

1
2
3
4
5
6
7
8
示例 1:

输入:m = 2, n = 3, k = 1
输出:3
示例 2:

输入:m = 3, n = 1, k = 0
输出:1
1
2
3
m = 2
n = 3
k = 1
1
2
3
m = 38
n = 12
k = 9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# copy
def digitsum(n):
    ans = 0
    while n:
        ans += n % 10
        n //= 10
    return ans

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        from queue import Queue
        q = Queue()
        q.put((0, 0))
        s = set()
        while not q.empty():
            x, y = q.get()
            if (x, y) not in s and 0 <= x < m and 0 <= y < n and digitsum(x) + digitsum(y) <= k:
                s.add((x, y))
                for nx, ny in [(x + 1, y), (x, y + 1)]:
                    q.put((nx, ny))
        return len(s)
        
1
2
solution = Solution()
solution.movingCount(m,n,k)

2️⃣

✅(20m)剑指 Offer 14- I. 剪绳子

难度中等265收藏分享切换为英文接收动态反馈

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

示例 1:

1
2
3
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

1
2
3
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
1
2
3
4
5
6
7
8
class Solution:
    def cuttingRope(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[2] = 1
        for i in range(3, n + 1):
            for j in range(2, i):
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
        return dp[n]

✅(20m)剑指 Offer 14- 2 剪绳子

✅(10m)15 二进制中1的个数

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

🚩(30m)16 数值的整数次方

实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。不得使用库函数,同时不需要考虑大数问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
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
            x *= x
            n >>= 1
        return res

2️⃣

✅(5m)17 打印1到最大的n位数

✅(10m)18. 删除链表的节点

难度简单97

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

返回删除后的链表的头节点。

注意:此题对比原题有改动

示例 1:

1
输入: head = [4,5,1,9], val = 5输出: [4,1,9]解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.

示例 2:

1
输入: head = [4,5,1,9], val = 1输出: [4,5,9]解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.

🚩(30m)19 正则表达式匹配

1
2
3
4
5
6
7
8
9
10
# 请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(含0次)。在本题中,匹配
# 是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但与"aa.a"和"ab*a"均不匹配。 
# 
#  示例 1: 
# 
#  输入:
# s = "aa"
# p = "a"
# 输出: false
# 解释: "a" 无法匹配 "aa" 整个字符串。
  1. 初始化: 行是s,列是匹配符p

    1
    2
    3
    4
    5
    
            m, n = len(s) + 1, len(p) + 1
            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 - 1] == '*'
    
  2. 状态转移方程:

    1. 展开来看,假设 s[:i]s[:i] 与 p[:j]p[:j] 可以匹配,那么下一状态有两种:

      1
      2
      
      添加一个字符 s_{i+1}后是否能匹配?
      添加字符 p_{j+1}后是否能匹配?
      
    2. p[j - 1] == ‘*’

    1
    2
    3
    4
    
                       if p[j - 1] == '*':
                           if dp[i][j - 2]: dp[i][j] = True                              # 1.0个
                           elif dp[i - 1][j] and s[i - 1] == p[j - 2]: dp[i][j] = True   # 2.多1次
                           elif dp[i - 1][j] and p[j - 2] == '.': dp[i][j] = True        # 3.
    
    1. p[j - 1] != ‘*’
    1
    2
    3
    
                       else:
                           if dp[i - 1][j - 1] and s[i - 1] == p[j - 1]: dp[i][j] = True # 1.
                           elif dp[i - 1][j - 1] and p[j - 1] == '.': dp[i][j] = True    # 2.
    

2️⃣

🚩20. 表示数值的字符串

难度中等154

请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串”+100”、”5e2”、”-123”、”3.1416”、”-1E-16”、”0123”都表示数值,但”12e”、”1a3.14”、”1.2.3”、”+-5”及”12e+5.4”都不是。

2️⃣

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def isNumber(self, s: str) -> bool:
        import re
        pattern = '\s*[+-]?((\d*\.?\d+)|(\d+\.))([Ee][+-]?\d+)?\s*'
        # pattern = "\\s*[+-]?((\\d*\\.?\\d+)|(\\d+\\.?))([eE][+-]?\\d+)?\\s*"
        # pattern = "\\s*[+-]?((\\d+)|(\\d*\\.\\d+)|(\\d+\\.\\d*))([eE][+-]?\\d+)?\\s*"
        sm = re.fullmatch(pattern, s)
        print(sm)
        if sm:
            return True
        else:
            return False

注意:

要用全匹配 fullmatch()

✅(20m) 21. 调整数组顺序使奇数位于偶数前面

✅(15m) 22. 链表中倒数第k个节点

✅(10m) 24. 反转链表

✅(15m) 25. 合并两个排序的链表

核心代码:

1
        while l1 and l2:            if l1.val <= l2.val:                cur.next = ListNode(l1.val)                l1 = l1.next            else:                cur.next = ListNode(l2.val)                l2 = l2.next            cur = cur.next  # 注意要往下走了!

🚩(30m)剑指 Offer 26. 树的子结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        def compare(nodeA,nodeB):
            # B 被遍历空,返回True
            if not nodeB:
                return True
            # 防止 A.val 报错, 值不同,返回False
            if not nodeA or nodeA.val != nodeB.val:
                return False
            # 继续递归遍历后续子树是否相同
            return compare(nodeA.left, nodeB.left) or compare(nodeA.right, nodeB.right)
        if not A or not B:
            return False
        # 通过递归将A的结点分别和B进行比较,这里的 or 具有阻断效应,后面的递归调用不执行,直接向上返回
        return compare(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right, B) 

2️⃣ 注意:

这里的 or 具有阻断效应,后面的递归调用不执行,直接向上返回

✅(10m) 剑指 Offer 27. 二叉树的镜像

✅(20m)剑指 Offer 28. 对称的二叉树

请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def isSym(left,right):
            if not left and not right:
                return True
            if not left or not right or left.val != right.val:
                return False
            return isSym(left.left, right.right) and isSym(left.right, right.left)
        if not root:
            return True
        return isSym(root.left,root.right)

2️⃣

🚩(60m) 剑指 Offer 29. 顺时针打印矩阵

2️⃣

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 spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        l,r,t,b,res = 0, len(matrix[0])-1, 0, len(matrix)-1, []  # 注意减1啊
        while True :
            print(l,r,t,b,res)
            for i in range(l, r+1):
                res.append(matrix[t][i])
            t += 1
            if t > b: break
            for i in range(t, b+1):
                res.append(matrix[i][r])
            r -= 1
            if r < l: break
            for i in range(r, l-1, -1):
                res.append(matrix[b][i])
            b -= 1  
            if b < t: break          
            for i in range(b, t-1, -1):
                res.append(matrix[i][l])
            l += 1  
            if l > r: break          
        return res
1
2
3
4
5
6
7
8
9
10
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        while matrix:
            res += matrix.pop(0)
            # print(matrix)
            # 逆时针旋转(这里通过转置+倒序实现)
            matrix = list(zip(*matrix))[::-1]
            # print(matrix)
        return res

注意: 矩阵逆时针旋转

1
2
        # 逆时针旋转(这里通过转置+倒序实现)
        matrix = list(zip(*matrix))[::-1]

✅(30m) 剑指 Offer 30. 包含min函数的栈

难度简单102

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

提示:

  1. 各函数的调用总次数不超过 20000 次

🚩(40m) 剑指 Offer 31. 栈的压入、弹出序列

2️⃣

1
2
3
4
5
6
7
8
9
10
class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []
        i = 0
        for num in pushed:
            stack.append(num)
            while stack and stack[-1] == popped[i]:
                stack.pop()
                i += 1
        return not stack

✅(10m) 剑指 Offer 32 - I. 从上到下打印二叉树

✅(10m) 剑指 Offer 32 - II. 从上到下打印二叉树 II

✅(10m) 剑指 Offer 32 - III. 从上到下打印二叉树 III

注意:

  1. ​ temp = collections.deque()

​ res.append(list(temp)) # 注意要先转化为list

  1. 双端队列

    1. if len(res)%2==0: temp.appendleft(node.val)

    ​ else: temp.append(node.val)

    1. ​ node = deque.popleft(0) # 注意

🚩(30m)剑指 Offer 33. 二叉搜索树的后序遍历序列

难度中等320收藏分享切换为英文接收动态反馈

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树:

1
2
3
4
5
     5
    / \
   2   6
  / \
 1   3

示例 1:

1
2
输入: [1,6,3,2,5]
输出: false

2️⃣

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def verifyPostorder(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
            while postorder[p] > postorder[j]:
                p += 1
            return p == j and recur(i, m-1) and recur(m, j-1)
        return recur(0, len(postorder)-1)

🚩(20m)剑指 Offer 34. 二叉树中和为某一值的路径

输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例: 给定如下二叉树,以及目标和 target = 22

1
2
3
4
5
6
7
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

返回:

1
2
3
4
[
   [5,4,11,2],
   [5,8,4,5]
]

2️⃣

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 pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
        def dfs(root, target):
            if not root:
                return

            path.append(root.val)
            target -= root.val

            if not root.left and not root.right and target == 0:
                res.append(path[:])

            dfs(root.left, target)
            dfs(root.right, target)

            target += root.val
            path.pop()

        res = []
        path = []
        dfs(root, target)
        return res

🚩剑指 Offer 35. 复杂链表的复制

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

示例 1:

img

1
2
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]	

2️⃣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
        dict = {}
        cur = head
        while cur:
            dict[cur] = TreeNode(cur.val)  # 注意要新建!!!!!
            cur = cur.next
        cur = head
        while cur:
            dict[cur].next = dict.get(cur.next)  # 与直接dict[cur.next]不同是其有默认返回值为None
            dict[cur].random = dict.get(cur.random)
            cur = cur.next
        return dict[head]
    
  1. dict[cur].next = dict.get(cur.next) # 与直接dict[cur.next]不同是其有默认返回值为None
  2. 这种复制的题目,dict[cur] = TreeNode(cur.val) # 注意要新建!!!!!

🚩(30m)剑指 Offer 36. 二叉搜索树与双向链表

难度中等285收藏分享切换为英文接收动态反馈

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。

为了让您更好地理解问题,以下面的二叉搜索树为例:

img

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

img

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

注意:本题与主站 426 题相同:https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/

2️⃣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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.left = cur, self.pre
            else: # 记录头节点
                self.head = cur
            self.pre = cur # 保存 cur
            dfs(cur.right) # 递归右子树
        
        if not root: return
        self.pre = None
        dfs(root)
        self.head.left, self.pre.right = self.pre, self.head
        return self.head

🚩(50m)剑指 Offer 37. 序列化二叉树

难度困难227

请实现两个函数,分别用来序列化和反序列化二叉树。

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

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

示例:

img

1
2
输入:root = [1,2,3,null,null,4,5]
输出:[1,2,3,null,null,4,5]

2️⃣

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections


class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root: return '[]'
        queue = [root]
        res = []
        while queue:
            cur = queue.pop(0)
            if not cur:
                res.append('null')
            else:
                res.append(str(cur.val))  # 注意,只有不是none的cur才放入queue里
                queue.append(cur.left)
                queue.append(cur.right)
        return '[' + ','.join(res) + ']'
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if data == '[]':
            return None
        vals, i = data[1:-1].split(','), 1
        root = TreeNode(int(vals[0]))
        queue = collections.deque()
        queue.append(root)
        while queue:
            cur = queue.popleft()
            if vals[i] != 'null':
                cur.left = TreeNode(int(vals[i]))
                queue.append(cur.left)
            i += 1
            if vals[i] != 'null':
                cur.right = TreeNode(int(vals[i]))
                queue.append(cur.right)
            i += 1
        return root

✅(30m)剑指 Offer 38. 字符串的排列

难度中等402

输入一个字符串,打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。

示例:

1
2
输入:s = "abc"
输出:["abc","acb","bac","bca","cab","cba"]

2️⃣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def permutation(self, s: str) -> List[str]:
        def dfs(s, path):
            if len(path) == len(s):
                res.append(''.join(path))
                return 
            for i in range(len(s)):
                if i not in visited:
                    path.append(s[i])
                    visited.add(i)
                    dfs(s, path)
                    path.pop()
                    visited.remove(i)
        
        res = []
        path = []
        visited = set()
        dfs(s, path)
        return list(set(res))

✅(10m)剑指 Offer 39. 数组中出现次数超过一半的数字

难度简单189

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例 1:

1
2
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cur = nums[0]
        count = 1
        for i in range(1, len(nums)):
            if nums[i] == cur:
                count += 1
            else:
                if count == 0:
                    cur = nums[i]
                    count = 1
                else:
                    count -= 1  
        return cur

2️⃣

🚩(30m)剑指 Offer 40. 最小的k个数

难度简单282

输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。

示例 1:

1
2
输入:arr = [3,2,1], k = 2
输出:[1,2] 或者 [2,1]

示例 2:

1
2
输入:arr = [0,1,2,1], k = 1
输出:[0]

2️⃣

1
2
3
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        return  heapq.nsmallest(k, arr)

复杂度分析

时间复杂度:O(nlogk),其中 n 是数组 arr 的长度。由于大根堆实时维护前 k 小值,所以插入删除都是 O(logk) 的时间复杂度,最坏情况下数组里 nn 个数都会插入,所以一共需要 O(nlogk) 的时间复杂度。

空间复杂度:O(k),因为大根堆里最多 k个数。

剑指 Offer 41. 数据流中的中位数

难度困难169

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

例如,

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构:

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

示例 1:

1
2
3
4
输入:
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出:[null,null,null,1.50000,null,2.00000]

示例 2:

1
2
3
4
输入:
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出:[null,null,2.00000,null,2.50000]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# leetcode submit region begin(Prohibit modification and deletion)
class MedianFinder:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.lnums = []  # 小顶,保存大的
        self.rnums = []  # 大顶,保存小的, heappush(heap, -num) 和 -heappop(heap) 都要取反。(内部存的是负数)
    def addNum(self, num: int) -> None:
        if len(self.lnums) == len(self.rnums):
            heappush(self.rnums, -num)
            heappush(self.lnums, -heappop(self.rnums)) # 插入取反
        if len(self.lnums) != len(self.rnums):
            heappush(self.lnums, num) # 插入取反
            heappush(self.rnums, -heappop(self.lnums)) # 弹出取反
    def findMedian(self) -> float:
        return self.lnums[0] if len(self.lnums) != len(self.rnums) else (self.lnums[0] + (-self.rnums[0]))/2


注意:

1
2
    self.lnums = []  # 小顶,保存大的
    self.rnums = []  # 大顶,保存小的, heappush(heap, -num) 和 -heappop(heap) 都要取反。(内部存的是负数)

✅(20m) 剑指 Offer 42. 连续子数组的最大和

剑指 Offer 43. 1~n 整数中 1 出现的次数

输入一个整数 n ,求1~n这n个整数的十进制表示中1出现的次数。

例如,输入12,1~12这些整数中包含1 的数字有1、10、11和12,1一共出现了5次。

示例 1:

1
2
输入:n = 12
输出:5

示例 2:

1
2
输入:n = 13
输出:6

2️⃣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def countDigitOne(self, n: int) -> int:
        digit, res = 1, 0
        high, cur, low = n//10, n%10, 0
        while high != 0 or cur != 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

剑指 Offer 44. 数字序列中某一位的数字

难度中等161

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第5位(从下标0开始计数)是5,第13位是1,第19位是4,等等。

请写一个函数,求任意第n位对应的数字。

示例 1:

1
2
输入:n = 3
输出:3

示例 2:

1
2
输入:n = 11
输出:0

✅(20m) 剑指 Offer 46. 把数字翻译成字符串

✅(15m) 剑指 Offer 47. 礼物的最大价值

✅(15m) 剑指 Offer 50. 第一个只出现一次的字符

字典有序且效率高

为什么Python 3.6以后字典有序并且效率更高?

1
2
3
4
5
for key in 字典

for value in 字典.values()

for key, value in 字典.items()

✅(30m) 剑指 Offer 52. 两个链表的第一个公共节点

✅(15m) 剑指 Offer 53 - I. 在排序数组中查找数字 I

🚩(30m) 剑指 Offer 53 - II. 0~n-1中缺失的数字

🚩(30m) 剑指 Offer 54. 二叉搜索树的第k大节点

✅(40m) 剑指 Offer 55 - I. 二叉树的深度

C++ queue

初始化: queue<TreeNode*> q;

判断为空:while(!q.empty())

取第一个元素:

1
2
                TreeNode* node = q.front;
                q.pop();

C++ 二叉树

初始化: queue<TreeNode*> q;

左右节点:

1
2
                if(node->left)   q.push(node->left);
                if(node->right)  q.push(node->right);

🚩(60m) 剑指 Offer 55 - II. 平衡二叉树

🚩(30m) 剑指 Offer 56 - I. 数组中数字出现的次数

🚩(20m) 剑指 Offer 57. 和为s的两个数字

排序数组 —》 想

双指针法

常数空间复杂度 想—》

1、想原地inplace操作

2、想用异或操作

🚩(20m) 剑指 Offer 57 - II. 和为s的连续正数序列

解方程法

✅(10m) 剑指 Offer 58 - I. 翻转单词顺序

✅(10m) 剑指 Offer 58 - II. 左旋转字符串

🚩(10m) 剑指 Offer 59 - I. 滑动窗口的最大值

🚩(20m) 剑指 Offer 62. 圆圈中最后剩下的数字

✅(20m) 剑指 Offer 63. 股票的最大利润

C++ for循环时,记得初始化

1
2
3
        for(int i=0; i<prices.size(); i++){
        // do sth;
        }

🚩(20m) 剑指 Offer 64. 求1+2+…+n

利用逻辑运算符的短路效应模拟条件表达式

逻辑运算符的短路效应: 常见的逻辑运算符有三种,即 “与 \&\& ”,“或 || ”,“非 ! ” ;而其有重要的短路效应,如下所示:

1
2
3
4
5
6
if(A && B)  // 若 A 为 false ,则 B 的判断不会执行(即短路),直接判定 A && B 为 false

if(A || B) // 若 A 为 true ,则 B 的判断不会执行(即短路),直接判定 A || B 为 true
本题需要实现 “当 n = 1n=1 时终止递归” 的需求,可通过短路效应实现。

n > 1 && sumNums(n - 1) // 当 n = 1 时 n > 1 不成立 ,此时 “短路” ,终止后续递归
1
2
3
4
5
6
7
8
class Solution {
public:
    int sumNums(int n) {
        // return n==0 ? 0 : n + sumNums(n-1);
        n && (n += sumNums(n-1));
        return n;
    }
};

🚩(30m) 剑指 Offer 65. 不用加减乘除做加法

🚩(40m) 剑指 Offer 66. 构建乘积数组

🚩(10m) 剑指 Offer 67. 把字符串转换成整数

🚩 剑指 Offer 68 - II. 二叉树的最近公共祖先

##