编程能力 算法及刷题 Lcof+牛客

Posted by Sun on February 1, 2021

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机试

✅(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 分别是二进制、十进制、八进制、十六进制。

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
2
3
001
输出例子1:
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

  1. labuladong的算法小抄pdf
  2. 九章算法视频