本文为原创文章，转载注明出处，欢迎关注网站https://hkvision.cn
背景
昨天做了字节的实习生后台开发的题目，4道编程题，2个小时。
题目
用户模型和模型文件之间的对应：
输入：
n
用户模型1 模型文件1
用户模型2 模型文件2
…
用户模型n 模型文件n
输出：
模型文件1 用户模型1 用户模型2 … 用户模型i
…
注：一个模型文件中可能存在多个用户模型
第一题不难，但是我不明白的是为什么我没通过，又没写错误的实例是啥，下面是我写的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| import sys
if __name__ == "__main__":
# 读取n
n = int(sys.stdin.readline().strip())
outDict = {}
# 读取n行的内容，并按照模型文件来组织结构
for i in range(n):
userType, modelFile = sys.stdin.readline().strip().split(' ')
try:
outDict[modelFile].append(userType)
except:
outDict[modelFile] = [userType]
# 打印
for modelFile, userTypes in outDict.items():
print("{modelFile} {userTypes}".format(modelFile=modelFile, userTypes=' '.join(sorted(userTypes))))
|
沙漠旅行者问题
我发现这种问题字节好喜欢考。这题具体是这样的，旅行者穿过沙漠，中间有若干补给站，然后每个补给站的补给量不一样，一公里消耗一单位的水，消耗不随身上的水量变化，每次补给的费用是一样的，因此为了能成功的穿越沙漠，请问最少要补给多少次。
我一开始题目没完全看完，看到旅行者我就头疼，就跳过去了，后来回过头看这题真的不怎么难。
下面是我的代码（这个代码有问题）
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
| import sys
if __name__ == "__main__":
total, init = [int(i) for i in sys.stdin.readline().strip().split(' ')]
positions = [int(i) for i in sys.stdin.readline().strip().split(' ')]
supplys = [int(i) for i in sys.stdin.readline().strip().split(' ')]
positions.append(total)
water = init
distance = positions[0]
fails = False
num = 0
for i in range(len(positions)):
if i == (len(positions) -1):
break
water = water - distance
distance = positions[i+1] - positions[i]
if distance > water:
num += 1
water += supplys[i]
if distance > water:
fails = True
break
if fails:
print(-1)
else:
print(num)
|
这个代码的问题在于，在每一次的补给站的补给策略不正确，正确的策略应该是：假设这次不补给，那么我能走到的最远地方是哪，中间的补给站是否有比这个补给站能补给更多的水（如果有的话，那么我可以一次补给更多的水），我需要选择尽可能的在大的补给站一次补给更多的水。
这个代码居然过了80%的case，我也是跪了，我是后来才发现我的策略有问题的
走迷宫
先输入一个迷宫，然后规定，格子为-2的为起点，-3的为终点，-1为障碍，0是通路，正数成对出现，是传送门
例如输入
4 3
1 0 -1 1
-2 0 -1 -3
2 2 0 0
这个是棋盘，输出则是从起点到终点的最少步数
这题不是特别困难，下面是我的代码
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
66
67
68
69
70
71
72
73
74
75
| import sys
import copy
"""
4 3
1 0 -1 1
-2 0 -1 -3
2 2 0 0
"""
result = []
def getqipan(cols, rows):
qipan = []
for i in range(rows):
row = [int(j) for j in sys.stdin.readline().strip().split(" ")]
qipan.append(row)
return qipan
def getvisited(cols, rows):
visited = []
for i in range(rows):
row = [0]*cols
visited.append(row)
return visited
def isvisited(visited, point):
return visited[point[0]][point[1]] == 1
def getstart(qipan):
for row in range(len(qipan)):
for col in range(len(qipan[0])):
if qipan[row][col] == -2:
return [row, col]
def getResult(qipan, visited, route, point, step=0):
global result
_visited = copy.deepcopy(visited)
_visited[point[0]][point[1]] = 1
_route = copy.deepcopy(route)
_route.append(point)
value = qipan[point[0]][point[1]]
if value == -3:
result.append(step)
return
nextps = [[point[0]-1, point[1]], [point[0]+1, point[1]], [point[0], point[1]-1], [point[0], point[1]+1]]
if value > 0:
c = getchuansong(qipan, value, point)
nextps.append(c)
step += 1
for nextp in nextps:
if nextp[0] >=0 and nextp[0] < len(qipan) and nextp[1] >= 0 and nextp[1] < len(qipan[0]):
if isvisited(_visited, nextp):
continue
if qipan[nextp[0]][nextp[1]] != -1:
getResult(qipan, _visited, _route, nextp, step)
def getchuansong(qipan, value, point):
for row in range(len(qipan)):
for col in range(len(qipan[0])):
if qipan[row][col] == value and (row != point[0] or col != point[1]):
return [row, col]
if __name__ == "__main__":
cols, rows = sys.stdin.readline().strip().split(" ")
cols, rows = int(cols), int(rows)
qipan = getqipan(cols, rows)
visited = getvisited(cols, rows)
start = getstart(qipan)
getResult(qipan, visited, [], start)
if not result:
print(-1)
else:
print(min(result))
|
这题我花了很长时间，重点是要有记录已走过的点的逻辑。后来觉得不应该用这种深度优先遍历的方法，应该用广度优先遍历，这样的话在已经走到终点后，其余路线就不用再走了。
连连看
这题我没时间做了，后来看到这题的时候发现和第三题一脉相承。
输入一个连连看的棋盘，然后后面是输入用户的操作步骤，判断每一步用户的操作是否合法（即不超过三段线段即可连起来）
借用第三题的找路线的方法，然后在每一次的拐点部分记录，要求不超过两个拐点。思路是这样的，具体写起来不一样的就是棋盘需要在输入的棋盘的基础上在外围增加一圈。
教训
首先还是要把四道题一起看一遍，例如其实第二题不难，但是因为我没看完，以为是旅行商背包问题，粗略的看了下就跳过去了，不然第二题肯定能完整的拿下来。
case不能完全通过不要紧，不要死卡在一道题上，这样很亏。
