Skip to content

Commit 1ad81ad

Browse files
linwtlinwt
authored
Add files via upload
1 parent 12df302 commit 1ad81ad

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

69 files changed

+1083
-0
lines changed

‎2017校招真题编程题汇总/01.合唱团.py

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
# 动态规划
2+
n = int(raw_input())
3+
stu = map(int, raw_input().split())
4+
k, d = map(int, raw_input().split())
5+
res_max = [[0]*k for _ in range(n)]
6+
res_min = [[0]*k for _ in range(n)]
7+
for i in range(n):
8+
res_max[i][0] = stu[i]
9+
res_min[i][0] = stu[i]
10+
for j in range(1, k):
11+
for i in range(n):
12+
for p in range(i+1, min(i+d+1, n)):
13+
res_max[p][j] = max(max(res_min[i][j-1]*stu[p], res_max[i][j-1]*stu[p]), res_max[p][j])
14+
res_min[p][j] = min(min(res_min[i][j-1]*stu[p], res_max[i][j-1]*stu[p]), res_min[p][j])
15+
print(max(res_max[i][k-1] for i in range(n)))

‎2017校招真题编程题汇总/02.地牢逃脱.py

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
'''
2+
题意可以理解为：有没有可以通行的点，但牛牛到不了（输出-1）。如果没有这样的点，牛牛可能花费最多步数是多少。
3+
思路：计算地图里，每个点的最短到达步数。找到到不了的点，或者最短步数里步数最多的点。
4+
1. 创建3个矩阵，size都是n*m的。分别是地图矩阵 mm、步数矩阵 sm、到达矩阵 am。
5+
2. 设置初始点为第一轮的探索点，更新 sm 里初始点的最短步数为0，更新 am 里初始点的到达状态为1。
6+
3. 找到从探索点一步能到达的点，且这些点可以通行并没有到达过。更新这些点的 sm 和 am。并将这些点当作下一轮的探索点。
7+
4. 循环第3步，直到没有新一轮的探索点了。
8+
5. 从 sm 中可以得到正确答案。
9+
'''
10+
11+
#coding=utf-8
12+
n, m = map(int, raw_input().split())
13+
map_matrix = [raw_input() for _ in range(n)] # 地图矩阵，'.' 表示可以通行的位置，'X' 表示不可通行的障碍
14+
x0, y0 = map(int, raw_input().split()) # 开始点的坐标
15+
k = int(raw_input()) # 共有k种行走方式
16+
alternative_steps = [map(int, raw_input().split()) for _ in range(k)] # 可以选择的行走方式
17+
step_matrix = [[-1]*m for _ in range(n)] # 步数矩阵，记录到达该点使用最短步数。初始是-1
18+
arrived_matrix = [[0]*m for _ in range(n)] # 到达矩阵，记录是否已经到达过该点。初始是0，表示没有到达过
19+
arrived_matrix[x0][y0] = 1 # 初始点修改为已到达的点
20+
step_matrix[x0][y0] = 0 # 初始点到达步数为0
21+
current_points = [[x0, y0]] # 第一轮所在的探索点（多个）
22+
while len(current_points) > 0: # 如果当前探索点是0个，结束循环。
23+
next_points = [] # 下一轮的探索点（多个）
24+
for point in current_points:
25+
x, y = point[0], point[1] # 一个探索点
26+
for step in alternative_steps:
27+
x_, y_ = x + step[0], y + step[1] # 该探索点一步能到达的点
28+
# 检查是否越界，该点是否可以通行，或者已经达到过
29+
if x_ < 0 or x_ >= n or y_ < 0 or y_ >= m or map_matrix[x_][y_] != '.' or arrived_matrix[x_][y_] == 1:
30+
continue
31+
step_matrix[x_][y_] = step_matrix[x][y] + 1 # 更新步数矩阵
32+
arrived_matrix[x_][y_] = 1 # 更新到达矩阵
33+
next_points.append([x_, y_]) # 该点添加到下一轮探索点里
34+
current_points = next_points
35+
# 从步数矩阵中找到到不了的点，或者最大的步数，然后输出
36+
try:
37+
max_step = 0
38+
for i in range(n):
39+
for j in range(m):
40+
step = step_matrix[i][j]
41+
if step==-1 and map_matrix[i][j]=='.':
42+
raise Exception
43+
if step > max_step:
44+
max_step = step
45+
print(max_step)
46+
except:
47+
print(-1)

‎2017校招真题编程题汇总/03.下厨房.py

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
# 每个字符串加到集合中去重
2+
import sys
3+
s = set()
4+
for line in sys.stdin:
5+
for i in line.split():
6+
s.add(i)
7+
print(len(s))

‎2017校招真题编程题汇总/04.分田地.py

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
n,m=map(int,raw_input().strip().split())
2+
matrix=[map(int,list(raw_input().strip())) for _ in range(n)]
3+
sum_values = [[0]*(m+1) for i in range(n + 1)]
4+
for i in range(1, n + 1):
5+
for j in range(1, m + 1):
6+
sum_values[i][j] += sum_values[i - 1][j] + sum_values[i][j - 1] - sum_values[i - 1][j - 1] + matrix[i-1][j-1]
7+
8+
def calculate_sum(p1,p2):
9+
x1,y1=p1
10+
x2,y2=p2
11+
a1,a2=sum_values[x1 - 1][y1 - 1],sum_values[x1 - 1][y2]
12+
a3,a4=sum_values[x2][y1 - 1],sum_values[x2][y2]
13+
value=a4-a3-a2+a1
14+
return value
15+
16+
def check(mid):
17+
for j1 in range(1, m - 2):
18+
if calculate_sum((1,1),(n,j1)) < mid * 4: continue
19+
for j2 in range(j1 + 1, m - 1):
20+
if calculate_sum((1,j1+1),(n,j2)) < mid * 4: continue
21+
for j3 in range(j2 + 1, m):
22+
if calculate_sum((1,j2+1),(n,j3)) < mid * 4: continue
23+
if calculate_sum((1,j3+1),(n,m)) < mid * 4: continue
24+
pstart,row_count=1,0
25+
for pend in range(1, n + 1):
26+
p1_list=[(pstart,1),(pstart,j1+1),(pstart,j2+1),(pstart,j3+1)]
27+
p2_list=[(pend,j1),(pend,j2),(pend,j3),(pend,m)]
28+
values=[calculate_sum(p1,p2) for p1,p2 in zip(p1_list,p2_list)]
29+
if min(values) >= mid:
30+
pstart=pend+1
31+
row_count+=1
32+
if row_count == 4:return True
33+
return False
34+
35+
l, r = 0, sum_values[n][m]
36+
answer = 0
37+
while l <= r:
38+
mid = (l + r) / 2
39+
if check(mid):
40+
l = mid + 1
41+
answer = mid
42+
else:
43+
r = mid - 1
44+
print(answer)

‎2017校招真题编程题汇总/05.分苹果.py

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
# 可分条件：平均为整数，比平均多的部分可被2整除，且整除结果就是移动次数
2+
n = int(raw_input())
3+
s = [int(i) for i in raw_input().split()]
4+
if sum(s)%len(s)!=0:
5+
print(-1)
6+
else:
7+
count = 0
8+
avg = sum(s)/len(s)
9+
for i in s:
10+
if i > avg:
11+
if (i-avg)%2==0:
12+
count += (i-avg)/2
13+
else:
14+
count = -1
15+
break
16+
print(count)

‎2017校招真题编程题汇总/06.星际穿越.py

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
# 解方程 x*x+x<=h
2+
# 方法一
3+
import math
4+
h = int(raw_input())
5+
x = int(math.sqrt(h))
6+
if h-x*x>=x:
7+
print(x)
8+
else:
9+
print(x-1)
10+
11+
# 方法二
12+
print(int(((1+4*input())**0.5-1)/2))

‎2017校招真题编程题汇总/07.藏宝图.py

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
# 方法一：索引递增
2+
s, t = raw_input(), raw_input()
3+
j = flag = 0
4+
for i in s:
5+
if i == t[j]:
6+
j += 1
7+
if j == len(t):
8+
flag = 1
9+
break
10+
print('Yes' if flag else 'No')
11+
12+
# 方法二：字符串截取
13+
s, t = raw_input(), raw_input()
14+
for i in s:
15+
if t and i == t[0]:
16+
t = t[1:]
17+
print('No' if t else 'Yes')

‎2017校招真题编程题汇总/08.数列还原.py

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
import itertools
2+
n, k = map(int, raw_input().split())
3+
A = map(int, raw_input().split())
4+
miss_num = []
5+
miss_index = []
6+
res = 0
7+
# 计算序列顺序对个数
8+
def findCount():
9+
count = 0
10+
for i in range(len(A)-1):
11+
j = i+1
12+
while j<len(A):
13+
if A[i]<A[j]:
14+
count += 1
15+
j += 1
16+
return count
17+
# 找出缺失数
18+
for i in range(1,n+1):
19+
if i not in A:
20+
miss_num.append(i)
21+
# 找出缺失数的索引
22+
for i,v in enumerate(A):
23+
if v == 0:
24+
miss_index.append(i)
25+
# 将缺失数进行排列组合
26+
items = itertools.permutations(miss_num,len(miss_num))
27+
for item in items:
28+
for i,v in enumerate(item):
29+
A[miss_index[i]] = v
30+
if findCount() == k:
31+
res += 1
32+
print(res)

‎2017校招真题编程题汇总/09.混合颜料.py

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
# 进行行与行之间的xor，其中1^1=0; 0^0=0; 1^0=1; 0^1=1;
2+
3+
# 矩阵的秩定义：是其行向量或列向量的极大无关组中包含向量的个数。
4+
# 矩阵的秩求法：用初等行变换化成梯矩阵, 梯矩阵中非零行数就是矩阵的秩
5+
6+
# 问题理解：输入n个数，将这些数之间进行多次xor（异或操作），其中一个数可能被xor多次，看最后能剩余多少不重复的数，输出数量即可。
7+
# 思路：类似矩阵求秩，首先将各数从大到小排序,对位数与该行相同的进行异或操作
8+
9+
# 具体过程如下：
10+
# 排序 i=0 异或 排序 i=1 异或 排序 i=2
11+
# 101010 --> 111010 --> 111010 --> 111010 --> 111010 --> 111010
12+
# 111010 --> 110110 --> 001100 --> 010111 --> 010111 --> 010111
13+
# 101101 --> 101101 --> 010111 --> 010000 --> 000111 --> 001100
14+
# 110110 --> 101010 --> 010000 --> 001100 --> 001100 --> 000111
15+
16+
n = int(raw_input())
17+
X = map(int, raw_input().split())
18+
for i in range(n-1,0,-1):
19+
X.sort()
20+
for j in range(i-1,-1,-1):
21+
if X[i]^X[j] < X[j]:
22+
X[j] ^= X[i]
23+
for i in range(n):
24+
if X[i]!=0:
25+
print (n-i)
26+
break

‎2017校招真题编程题汇总/10.幸运的袋子.py

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
# 递归
2+
n = int(raw_input())
3+
x = map(int, raw_input().split())
4+
x.sort()
5+
def lucky(x, lsum, lmul):
6+
res = 0
7+
for i in range(len(x)):
8+
if i>0 and x[i]==x[i-1]:
9+
continue
10+
lsum += x[i]
11+
lmul *= x[i]
12+
if lsum > lmul:
13+
# 符合条件则继续往下扩展一位
14+
res = res+1+lucky(x[i+1:], lsum, lmul)
15+
elif x[i] == 1:
16+
res = res+lucky(x[i+1:], lsum, lmul)
17+
else:
18+
break
19+
# 回溯一位，继续扩展
20+
lsum -= x[i]
21+
lmul /= x[i]
22+
return res
23+
print(lucky(x, 0, 1))

0 commit comments

Comments
 (0)