前言
笔试一共五道编程题(四+一),一为专项编程题,估计不同岗位有题目不一样,使用的是赛码网,允许跳出界面使用自己的IDE。
在此感谢筱羊冰冰提供的部分题目及题解。
题目一:数圈游戏
给定一个整数n,计算该整数含有的圆圈个数。数字0-9对应的圈数如下:
0: 1
1: 0
2: 0
3: 0
4: 0
5: 0
6: 1
7: 0
8: 2
9: 1
输入:
第一行为一个整数n,表示数圈游戏的数字。
输入示例:
60498
输出示例:
5
限制:
80%的测试用例:n<=10000
100%的测试用例:n<=100000000
思路:
该题较为简单,一次遍历累加即可。
题目二:士兵排队
给定一定数量的士兵,将士兵按照身高从小到大排列,身高相同者按照姓名的字典序从小到大排列。
输入:
第一行为一个整数n,表示士兵的数量。
第二行为n个士兵的身高,单位为cm。
第三行为n个士兵的姓名。
输入示例:
4
176 170 176 176
bamma tom alpha beta
输出示例:
tom alpha bamma beta
限制:
士兵身高 hi <= 300
士兵姓名长度 ni <= 20
思路一:
将每一个人的身高和名字按照 (身高,名字) 的格式存储,然后进行两次排序,先按照身高排序,再按照名字排序即可。(利用了python排序算法的稳定性!)
n = int(input())
heights = list(map(str, input().split()))
names = list(map(str, input().split()))
ls = []
for i in range(n):
ls.append((heights[i], names[i]))
ls.sort(key=lambda x:x[1])
ls.sort(key=lambda x:x[0])
for i in range(n):
print(ls[i][1], end=' ')
思路二:
因为身高的限制为 hi <= 300,所以身高最高只能为三位数,那么我们可以把所有身高都通过补前置零的方式化为三位数,然后再与名字拼接成一个字符串,这样只需要一次排序就能够得出结果。
n = int(input())
heights = list(map(str, input().split()))
names = list(map(str, input().split()))
for i in range(n):
heights[i] = heights[i].zfill(3) + names[i]
heights.sort()
for i in range(n):
print(heights[i][3:], end=' ')
题目三:路径搜索
给定一个地图,询问是否存在一条从起点到终点的直接通路。注意,通路是双向的。
输入:
第一行包括两个整数n和m,分别表示地图上点的数量和通路的数量。
第二行包括m个整数,表示地图上通路的一端。
第三行包括m个整数,表示地图上通路的另一端。
第四行包括k个整数,表示询问的次数。
接下来的k行每行包括两个整数,分别表示起点和终点。
输入示例:
4 5
1 2 1 3 1
2 3 3 4 4
4
1 3
2 4
2 1
3 2
输出示例:
Yes
No
Yes
Yes
思路:
筱羊冰冰:上来就看错了,然后花了好久写了类似并查集的东西,然后用不上……
(果然大佬就是不一样,上来直接手撕并查集)
这道题只需要检查有无指定通路就行了,不过要特别注意查询范围,因为通路是双向的而且要求的是直接通路。
n, m = map(int, input().split())
lsu = list(map(int, input().split()))
lsv = list(map(int, input().split()))
k = int(input())
ways = set((lsu[i], lsv[i]) for i in range(m))
out = []
for _ in range(k):
u, v = map(int, input().split())
if (u, v) in ways or (v, u) in ways:
out.append('Yes')
else:
out.append('No')
print('\n'.join(out))
题目四:井字棋
给定一个2x2的棋盘和n中不同的颜色,要求每行每列均不能出现相同的颜色,计算总共有多少种填充方案。
输入:
第一行包括一个整数n,表示颜色的数量。
输出:
输出一个整数,表示有多少种填充方案。
输入示例:
2
输出示例:
2
限制:
颜色的种类n <= 10
思路:
筱羊冰冰:有一说一,感觉就属这个题有意思吧。我当时看完,感觉就有一点像排列组合(业余玩家,不太清楚具体的类型)。
n种颜色,如果颜色足够(指大于四种),我们其实也只能取出四种来操作,所以只需要一个
C
n
4
C_n^4
Cn4
所以我们其实只需要考虑四种以内的情况。
两种颜色:
三种颜色:
我们自然可以想到,拿两种颜色就可以填上面的两种
C
3
2
∗
2
C_3^2 * 2
C32∗2
然后,如果是三种颜色都要,有12种,肯定是有一个重复的,那么对角线重复就有两种情况,剩下的其实就是将三个数字填入三个位置,
A
3
3
A_3^3
A33
就是6 + 6*2 = 18。
到这里其实就应该明白了,我们只需要知道 i 种颜色有多少种即可,因为 i = 2, 3, 4,我们完全可以直接写出来,剩下的就是一个组合问题,再给出一个阶乘列表。
ls = [0, 0, 2, 12, 24]
ls_jc = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]
ret = 0
n = int(input())
if n <= 1:
ret = 0
elif n <= 4:
for i in range(2, n+1):
ret += ls[i] * ls_jc[n] // (ls_jc[i] * ls_jc[n-i])
ret %= 1000000007
else:
for i in range(2, 5):
ret += ls[i] * ls_jc[n] // (ls_jc[i] * ls_jc[n-i])
ret %= 1000000007
print(ret)
小插曲:
当时有一块写错了,然后跑出来只有27%,自己就去看了一下范围是小于等于十,那么案例至少有10个吧。
然后自己因为有边界检测,负数、0、1、2都能正确,那么至少对三个,反推出案例应该是11个,那么就是3往上有问题,所以将矛头对准了ls[3],果然是算少了,改成12,啪的一下,很快就过了……
题目五:堆积木
给定一个已有的字符串和一个目标字符串,可以从右边删除一个字符,也可以往左边插入一个字符,删除和插入操作的次数没有限制,问最少操作多少次可以使已有字符串变成目标字符串。
输入 | 解释 |
---|
5 | 原串长度 |
1 5 3 4 6 | 原串 |
5 | 目标串长度 |
2 1 5 3 4 | 目标串 |
思路:
筱羊冰冰:这个题,其实看明白了就没那么难,其实就是找最长公共子序列。
from collections import deque
l_old = int(input())
old = input().split()
l_new = int(input())
new = input().split()
length = 0
s1, s2 = deque(), deque()
judge = 0
while True:
s1.append(old[length])
s2.appendleft(new[-length-1])
length += 1
if s1 == s2:
judge = 1
break
elif length == min(l_old, l_new):
break
if judge:
print(l_old+l_new - length*2)
else:
print(l_old+l_new)
重大失误:
上面的代码其实没考虑,如果有多对子串相同,要找出最长的……
不过感觉测试案例比较拉,所以显示还是ac了的。
凉梦空间
欢迎你进入我的个人博客网站参观交流:https://www.liangmeng.xyz
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)