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))

‎2017校招真题编程题汇总/11.不要二.py

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
# ＊＊ ＊＊ ＊＊
2+
# ＊＊ ＊＊ ＊＊
3+
# ＊＊ ＊＊ ＊＊
4+
# ＊＊ ＊＊ ＊＊
5+
# ＊＊ ＊＊ ＊＊
6+
# ＊＊ ＊＊ ＊＊
7+
# 由数据规律分三种情况讨论
8+
n, m = map(int, raw_input().split())
9+
if n%4==0 or m%4==0:
10+
print(n*m/2)
11+
elif n%2==0 and m%2==0:
12+
print((n*m/4+1)*2)
13+
else:
14+
print(n*m/2+1)

‎2017校招真题编程题汇总/12.解救小易.py

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
# 起点到陷阱的最短距离为x+y-2
2+
num = int(raw_input())
3+
x = [int(i) for i in raw_input().split()]
4+
y = [int(i) for i in raw_input().split()]
5+
a = []
6+
for j in range(num):
7+
a.append(x[j]+y[j]-2)
8+
print(min(a))

‎2017校招真题编程题汇总/13.统计回文.py

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
# 插入后反转字符串，若与原来相等则是回文串
2+
a = list(raw_input())
3+
b = raw_input()
4+
c = a[:]
5+
count = 0
6+
for i in range(len(c)+1):
7+
a.insert(i, b)
8+
s = ''.join(a)
9+
if s[:]==s[::-1]:
10+
count += 1
11+
a = c[:]
12+
print(count)

‎2017校招真题编程题汇总/14.饥饿的小易.py

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
# 设f(x)=4x+3,g(x)=8x+7。计算可以得到以下两个规律：
2+
# （1） g(f(x))=f(g(x)) 即f和g的执行顺序没有影响。
3+
# （2） f(f(f(x)))=g(g(x)) 即做3次f变换等价于做2次g变换
4+
# 由于规律（1），可以调整其变换的顺序。如ffggfggff可以转化成 fffffgggg
5+
# 由于规律（2），为了使执行次数最少，每3个f可以转化成2个g。如fffffgggg可以转化成ffgggggg。
6+
# 因此一个最优的策略，f的执行次数只能为0,1,2。对于输入的x，只需要求x，4x+3,4（4x+3）+3的最小g执行次数就可以了。
7+
x = int(raw_input())
8+
num = 100001
9+
base = [x, 4*x+3, 4*(4*x+3)+3]
10+
for i,v in enumerate(base):
11+
for j in range(100000):
12+
v = (8*v+7)%1000000007
13+
if v == 0:
14+
num = min(num, i+j+1)
15+
break
16+
if num == 100001:
17+
print(-1)
18+
else:
19+
print(num)
20+
21+
22+
# 4x+3相当于做了两次2x+1， 8x+7做了三次。
23+
# 从起点开始令x0 = 2*x0+1，统计做了多少次2x+1后模1000000007等于0
24+
# 再把次数分解成若干个3与2的和，3的个数加上2的个数最小，不超过100000
25+
x = int(raw_input())
26+
r = 0
27+
while x!=0 and r<=300000:
28+
x = (2*x+1)%1000000007
29+
r += 1
30+
s = (r+2)/3
31+
print -1 if s>10**5 else s

‎2017校招真题编程题汇总/15.两种排序方法.py

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
# 字符串序列或字符串对应的长度序列调用sort()方法后，若与原序列相同，则已经排好序了
2+
n = int(raw_input())
3+
str1 = []
4+
len1 = []
5+
for i in range(n):
6+
str1.append(raw_input())
7+
len1.append(len(str1[i]))
8+
str2, len2 = str1[:], len1[:]
9+
str2.sort()
10+
len2.sort()
11+
if len1 == len2:
12+
if str1 == str2:
13+
print('both')
14+
else:
15+
print('lengths')
16+
elif str1 == str2:
17+
print('lexicographically')
18+
else:
19+
print('none')

‎2017校招真题编程题汇总/16.小易喜欢的单词.py

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
# 各条件逐一判断
2+
s = raw_input()
3+
res = 'Likes'
4+
if not s.isupper():
5+
res = 'Dislikes'
6+
for i in range(len(s)-1):
7+
if s[i] == s[i+1]:
8+
res = 'Dislikes'
9+
for i in range(len(s)-3):
10+
if s[i] == s[i+2] and s[i+1] == s[i+3]:
11+
res = 'Dislikes'
12+
print(res)

‎2017校招真题编程题汇总/17.Fibonacci数列.py

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
# 递推找到离整数最近的左右两个Fibonacci数，求差取最小即为最少步数
2+
a, b = 0, 1
3+
n = int(raw_input())
4+
while n>b:
5+
a, b = b, a+b
6+
print(min(n-a, b-n))

‎2017校招真题编程题汇总/18.数字游戏.py

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
# 1,2,3,7求和结果为13，则可组成的数为1-13
2+
n = int(raw_input())
3+
a = map(int, raw_input().split())
4+
a.sort()
5+
res = 0
6+
for i in a:
7+
# 相减大于1说明有空档
8+
if i-res>1:
9+
break
10+
res += i
11+
print(res+1)

0 commit comments

Comments
 (0)