LeetCode按类型
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机试
✅(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()
|
Python rjust() 返回一个原字符串右对齐,并使用空格填充至长度 width 的新字符串。如果指定的长度小于字符串的长度则返回原字符串。
语法
rjust()方法语法:
1
| str.rjust(width[, fillchar])
|
参数
- width – 指定填充指定字符后中字符串的总长度.
- fillchar – 填充的字符,默认为空格。
返回值
返回一个原字符串右对齐,并使用空格填充至长度 width 的新字符串。如果指定的长度小于字符串的长度则返回原字符串
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 分别是二进制、十进制、八进制、十六进制。
Alibaba机试
NC78 |
反转链表 |
链表 |
简单 |
AC |
time |
NC140 |
排序 |
排序 |
中等 |
|
5m |
NC93 |
设计LRU缓存结构 |
模拟 |
中等 |
|
|
NC45 |
实现二叉树先序,中序和后序遍历 |
栈树哈希 |
中等 |
|
|
NC119 |
最小的K个数 |
堆排序分治 |
中等 |
|
|
NC15 |
求二叉树的层序遍历 |
树bfs |
中等 |
|
|
NC88 |
寻找第K大 |
堆分治 |
中等 |
|
|
NC61 |
两数之和 |
数组哈希 |
简单 |
|
|
NC33 |
合并有序链表 |
链表 |
简单 |
|
|
NC76 |
用两个栈实现队列 |
栈 |
简单 |
|
|
NC50 |
链表中的节点每k个一组翻转 |
链表 |
中等 |
|
|
NC19 |
子数组的最大累加和问题 |
动态规划分治 |
简单 |
|
|
NC4 |
判断链表中是否有环 |
链表 |
简单 |
|
|
NC3 |
链表中环的入口节点 |
链表双指针 |
中等 |
|
|
NC52 |
括号序列 |
栈字符串 |
简单 |
|
|
NC1 |
大数加法 |
字符串模拟 |
中等 |
|
|
NC14 |
二叉树的之字形层序遍历 |
栈树bfs |
中等 |
|
|
NC127 |
最长公共子串 |
动态规划 |
中等 |
|
|
NC38 |
螺旋矩阵 |
数组 |
入门 |
|
|
NC65 |
斐波那契数列 |
数组 |
入门 |
|
|
NC17 |
最长回文子串 |
字符串动态规划 |
中等 |
|
|
NC54 |
数组中相加和为0的三元组 |
数组双指针 |
中等 |
|
|
NC12 |
重建二叉树 |
树dfs数组 |
中等 |
|
|
NC7 |
股票(一次交易) |
数组动态规划 |
简单 |
|
|
NC128 |
容器盛水问题 |
双指针 |
中等 |
|
|
NC136 |
输出二叉树的右视图 |
树 |
中等 |
|
|
NC13 |
二叉树的最大深度 |
树dfs |
简单 |
|
|
NC141 |
判断回文 |
字符串 |
入门 |
|
|
NC62 |
平衡二叉树 |
树dfs |
简单 |
|
|
NC73 |
数组中出现次数超过一半的数字 |
数组哈希 |
简单 |
|
|
NC59 |
矩阵的最小路径和 |
数组动态规划 |
中等 |
|
|
NC137 |
表达式求值 |
栈递归 |
中等 |
|
|
NC36 |
在两个长度相等的排序数组中找到上中位数 |
数组分治二分 |
较难 |
|
|
NC100 |
将字符串转化为整数 |
字符串 |
较难 |
|
|
NC20 |
数字字符串转化成IP地址 |
字符串回溯 |
中等 |
|
|
NC105 |
二分查找-II |
二分 |
中等 |
|
|
NC123 |
序列化二叉树 |
队列树 |
较难 |
|
|
NC89 |
字符串变形 |
字符串 |
简单 |
|
|
NC95 |
最长连续子序列 |
并查集数组 |
较难 |
|
|
NC10 |
大数乘法 |
字符串 |
中等 |
|
|
NC69 |
链表中倒数第k个结点 |
链表 |
中等 |
|
|
NC122 |
正则表达式匹配 |
字符串 |
较难 |
|
|
NC44 |
通配符匹配 |
字符串贪心动态规划回溯 |
较难 |
|
|
NC144 |
不相邻最大子序列和 |
动态规划 |
中等 |
|
|
NC79 |
丑数 |
数学二分 |
中等 |
|
|
NC145 |
01背包 |
动态规划 |
简单 |
|
|
牛客模考 · 【2021】第1次校招模拟笔试算法
(1h)[编程题]刷墙
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 256M,其他语言512M
最近小明搬到了新家,他正在粉刷墙壁,但是不幸的是他粉刷的墙壁并不理想。他的墙壁是一个长度为n的格子,每个格子用0表示红色,用1表示蓝色。现在墙壁是一个非常混乱的颜色。他想将墙壁涂成左边全是蓝色右边全是红色,可以将墙壁刷成全是红色或者蓝色。请问他至少需要粉刷多少个格子墙壁刷成他想要的样子?
输入描述:
1
2
| 第一行一个整数。
第二行个长度为的01串,0表示红色,1表示蓝色。
|
输出描述:
输入例子1:
输出例子1:
例子说明1:
暴力 - 超时
一定要记得看范围,这样的话可以考虑用多大时间复杂度的算法,像此题有100000长度则不可能用O(n*n)的方法来做,而应该用O(n)的动态规划。
1
2
3
4
5
6
7
8
9
10
| num_words = int(input())
nums = int(input(),2)
res = 1000000
start = int('1'*num_words,2)
for i in range(num_words+1):
tar = start<<i & start
diff = bin(tar^nums).count('1')
res = min(res, diff)
print(res)
|
动态规划
JD机试
🚩 信封套娃问题
Reference
- labuladong的算法小抄pdf
- 九章算法视频