2021届自己参加的秋招笔试题记录

2021届秋招正如火如荼地进行着,截止目前,我已经参加了绝大部分互联网企业的秋招,我想将自己写过的代码保存一下,供以后再来回味。 代码基本都是用Python写的,有些并没有100%AC。

不匹配括号数量

Input: 包含若干(, ), [, ]的字符串。

Output: 不能配对的括号的数量。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def BracketsMatch(text, flag):
arr = []
if flag == 1:
left = '('
right = ')'
else:
left = '['
right = ']'
for c in text:
if c == left:
arr.append(c)
elif c == right:
if len(arr) == 0:
arr.append(c)
else:
if arr[-1] == left:
arr.pop()
else:
arr.append(c)
return len(arr)
text = input().strip()
print(BracketsMatch(text, 0) + BracketsMatch(text, 1))

分析

针对任意一对括号,可以用栈来存储无法匹配的括号。同时这种写法可以拓展到其他需要前后配对的字符上,例如{}或者等。

前m个值最大选项的序号

Input: 第一行n和m,n代表有几个物品,m代表取价值前m大;以后n行输入n个物品的重量和体积。

Output: 从小到大输出价值前m大的物品编号。

*物品价值 = 重量 + 2 × 体积

代码

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
line1 = input().split(' ')
n = int(line1[0])
m = int(line1[1])
matrix = [[0 for i in range(4)] for j in range(n)]
for i in range(n):
line_n = input().split(' ')
matrix[i][0] = float(line_n[0])
matrix[i][1] = float(line_n[1])
matrix[i][2] = float(line_n[0]) + 2 * float(line_n[1])
matrix[i][3] = i + 1
matrix = sorted(matrix, key = lambda item:item[2])[::-1]
max_m = int(matrix[0][2])
result_m = [[0 for i in range(n + 1)] for j in range(max_m + 1)]
for i in range(len(matrix)):
result_m[int(matrix[i][2])][int(matrix[i][3])] = 1
result = []
for i in range(max_m, -1, -1):
for j in range(n + 1):
if result_m[i][j] == 1:
result.append(j)
result = sorted(result[0 : m])
strs = ''
for i in range(m):
strs += str(result[i]) + ' '
print(strs.strip())

分析

类似于Excel之中排序,主排序标准和次排序标准。

0/1背包

0/1背包作为经典的动态规划问题,经常考察,但是只要掌握状态转移方程,动态规划基本上很少的代码就可以写出来。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def Package(W, V, max_w):
len_w = len(W)
dp = [[0 for i in range(max_w + 1)] for j in range(len_w)]
for i in range(len_w):
for j in range(max_w + 1):
if W[i] > j:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j - W[i]] + V[i], dp[i - 1][j])
return dp[-1][-1]
W = [10, 20, 20, 30]
V = [12, 18, 17, 32]
max_w = 50
print(Package(W, V, max_w))

根据输入操作数字串

Input: 一行n和m,代表长度为n的值为下标的数字串;m行不同的操作。(1:将串首元素移动到最尾;2:交换第“2 × i + 1”和第“2 × i + 2”号元素,其中i从1开始。)

Output: 操作结束的数字串

代码

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
line1 = input().split(' ')
n = int(line1[0])
m = int(line1[1])
line2 = input().split(' ')
line = []
for i in range(n):
line.append(i + 1)
def OP1(line):
new_line = []
for i in range(1, len(line)):
new_line.append(line[i])
new_line.append(line[0])
return new_line
def OP2(line):
for i in range(0, len(line), 2):
t = line[i]
line[i] = line[i + 1]
line[i + 1] = t
return line
for i in range(m):
if int(line2[i]) == 1:
line = OP1(line)
elif int(line2[i]) == 2:
line = OP2(line)
else:
line = line
ret = ''
for i in range(n):
ret += str(line[i]) + ' '
print(ret)

分析

这种题目就是按照题目要求,写出不同操作的函数,然后调用就OK啦。在今年的秋招中,出现过很多次类似的题目,虽然操作不尽相同。

计算面积

求y = 0, x = C, x = D 与y = Ax^2 + x + B相交区域的面积。

Input: A,B,C和D。

Output: 面积(保留6位小数)

代码

1
2
3
4
5
6
7
8
9
10
11
n = int(input())
ret = []
def Area(a, b, c, d):
right = (float(a) / 3) * d * d * d + 0.5 * d * d + float(b) * float(d)
left = (float(a) / 3) * c * c * c + 0.5 * c * c + float(b) * float(c)
return right - left
for i in range(n):
line = input().split(' ')
ret.append(Area(int(line[0]), int(line[1]), int(line[2]), int(line[3])))
for i in range(n):
print("%.6f" % ret[i])

分析

这种题乍一看没有思路,需要结合数学知识,求面积就是求一定范围内的积分。当函数变化时,也是同样的做法。

全组合

Input: 一个正整数n。

Ouput: 从1到n的全组合,并且每种组合从组合中选一个代表的总可能数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = int(input())
ret = 0
def C(n, i):
ret = 1
d = 1
while i > 0:
ret *= n % (pow(10, 9) + 7)
n -= 1
d *= i % (pow(10, 9) + 7)
i -= 1
return int(ret/ d) % (pow(10, 9) + 7)
for i in range(1, n + 1):
ret += (i * C(n, i)) % (pow(10, 9) + 7)
print(ret % (pow(10, 9) + 7))

分析

全组合可以通过转化成2进制,然后数1的个数来确定,也可以使用从1到n组合求和来做。

求图中链接相同元素的节点对的数量

Input: 节点数n,边数m;以后m行,m条边。

Output: 链接相同元素的节点对的数量

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
line = input().split(' ')
n = int(line[0])
m = int(line[1])
matrix = [[0 for i in range(n + 1)] for j in range(n + 1)]
for i in range(m):
tmp = input().split(' ')
matrix[int(tmp[0])][int(tmp[1])] = 1
matrix[int(tmp[1])][int(tmp[0])] = 1
def Equal(list1, list2, n):
flag = True
for i in range(1, n + 1):
if list1[i] != list2[i]:
flag = False
return flag
ret = 0
for i in range(1, n + 1):
for j in range(i + 1, n + 1):
if Equal(matrix[i], matrix[j], n):
ret += 1
print(ret)

分析

我这里用了一种最笨的方法,将图存成邻接矩阵,然后两行完全相同(不包含全为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
def Right(i, j, right_end, bottom_end, ret, matrix):
if j == right_end and i < bottom_end:
return Down(i, j, right_end, bottm_end, ret, matrix)
elif j == right_end and i == bottom_end:
return
else:
ret.append(matrix[i][j + 1])
if i == bottom_end:
return RightUp(i, j + 1, right_end, bottom_end, ret, matrix)
else:
return LeftDown(i, j + 1, right_end, bottom_end, ret, matrix)
def Down(i, j, right_end, bottom_end, ret, matrix):
if i == bottom_end and j == right_end:
return
elif i == bottom_end and j < right_end:
Right(i, j, right_end, bottom_end, ret, matrix)
else:
ret.append(matrix[i + 1][j])
if j == right_end:
return LeftDown(i + 1, j, right_end, bottom_end, ret, matrix)
else:
return RightUp(i + 1, j, right_end, bottom_end, ret, matrix)
def LeftDown(i, j, right_end, bottom_end, ret, matrix):
if i == bottom_end and j == right_end:
return
elif i == bottom_end:
return Right(i, j, right_end, bottom_end, ret, matrix)
elif j == 0:
return Down(i, j, right_end, bottom_end, ret, matrix)
else:
ret.append(matrix[i + 1][j - 1])
return LeftDown(i + 1, j - 1, right_end, bottom_end, ret, matrix)
def RightUp(i, j, right_end, bottom_end, ret, matrix):
if i == bottom_end and j == right_end:
return
elif j == right_end:
return Down(i, j, right_end, bottom_end, ret, matrix)
elif i == 0:
return Right(i, j, right_end, bottom_end, ret, matrix)
else:
ret.append(matrix[i - 1][j + 1])
return RightUp(i - 1, j + 1, right_end, bottom_end, ret, matrix)
n = int(input())
matrix = [[str(j) + '+' + str(i) for i in range(n)] for j in range(n)]
ret = []
ret.append(matrix[0][0])
Down(0, 0, n - 1, n - 1, ret, matrix)
print(ret)

子串长度

Input: 只包含小写字母的字符串。

Output: 包含连续两个“abcde”或者不包含“abcde”的子串最长长度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
strs = input()
chars = 'abcde'
dp = [0 for i in range(len(strs) + 1)]
for i in range(len(strs)):
if strs[i] not in chars:
dp[i + 1] = dp[i] + 1
else:
if i == 0:
dp[i + 1] = dp[i]
elif strs[i] == strs[i - 1]:
dp[i + 1] = dp[i - 1] + 2
else:
dp[i + 1] = 0
max = 0
for i in range(len(strs) + 1):
if dp[i] > max:
max = dp[i]
print(max)

字符串分割相等

Input: ","分隔的两个字符串。

Output: 如果两个字符串相同或者分隔成子串相同,则输出“true”,否则输出“false”。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
line = input().split(',')
str1 = line[0]
str2 = line[1]
def Equal(str1, str2):
if len(str1) != len(str2):
return False
elif len(str1) == 1 and str1 != str2:
return False
elif str1 == str2:
return True
elif len(str1) % 2 == 1:
return Equal(str1[0: int(len(str1) / 2)], str2[int(len(str2) / 2) - 1:]) and Equal(str2[0: int(len(str2) / 2) - 1], str1[int(len(str1) / 2):]) or (Equal(str1[0: int(len(str1) / 2) - 1], str2[int(len(str2) / 2):]) and Equal(str2[0: int(len(str2) / 2)], str1[int(len(str1) / 2) - 1:]))
else:
return Equal(str1[0: int(len(str1) / 2)], str2[int(len(str2) / 2):]) and Equal(str2[0: int(len(str2) / 2)], str1[int(len(str1) / 2):])
if Equal(str1, str2):
print('true')
else:
print('false')

分析

递归的思想,如果当前串相同则返回True,否则将串二等分,看子串是否相等。

杨辉三角

Input: 行数n;每一行有2 × i - 1个数字,构成一个三角形。

Output: 从第一行走到最后一行最大的和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = int(input().strip())
matrix = [[0 for i in range(2 * n + 1)] for j in range(n + 1)]
for i in range(1, n + 1):
line = input().split(' ')
for j in range(n + 1 - i, n + 1 - i + len(line)):
matrix[i][j] = int(line[j - n + i - 1])
dp = [[0 for i in range(2 * n + 1)] for j in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, 2 * n):
if i == 1:
dp[i][j] = matrix[i][j]
else:
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j]
print(max(dp[-1]))

分析

比较经典的动态规划题。动态规划与递归的区别在于动态规划利用“最优子结构”这个特性,所以下一个状态由上一个状态推出,写代码时是从头往后,而递归则是从后往前。

回字形写入斐波拉契数列

Input: 矩阵的边长n。

Output: 回字形写入斐波拉契数列的n × n矩阵。

代码

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
def Trans(matrix):
if len(matrix) == 0:
return
new_matrix = []
tmp_line = []
for j in range(len(matrix[0]) - 1, -1, -1):
tmp_line = []
for i in range(len(matrix)):
tmp_line.append(matrix[i][j])
new_matrix.append(tmp_line)
return new_matrix
ret = []
def ReadLine(matrix):
if len(matrix) > 1:
ret.append(matrix[0])
return ReadLine(Trans(matrix[1:]))
elif len(matrix) == 1:
ret.append(matrix[0])
else:
return
n = int(input())
matrix = [['' for i in range(n)] for j in range(n)]
for i in range(n):
for j in range(n):
matrix[i][j] = str(i) + '+' + str(j)
ReadLine(matrix)
m = n * n
def FB(m):
fb_arr = []
fb_arr.append(0)
for i in range(1, m + 1):
if i == 1 or i == 2:
fb_arr.append(1)
else:
fb_arr.append(fb_arr[i - 2] + fb_arr[i - 1])
return fb_arr
fb_arr = FB(m)[::-1]
ret_matrix = [[0 for i in range(n)] for j in range(n)]
for i in range(len(ret)):
for j in range(len(ret[i])):
tmp = ret[i][j].split('+')
t = int(tmp[0])
k = int(tmp[1])
ret_matrix[t][k] = fb_arr[0]
fb_arr = fb_arr[1:]
print(ret_matrix)

分析

回字形输出,等价于先输出矩阵第一行,然后将矩阵旋转(这个时候之前的最右列就变成了第一行)再输出,往复到矩阵为空。

前K大的数

求一堆数中前K大的数。 一般可以使用小顶堆来实现。用数组保存堆的时候:左子树 = 父节点 × 2;右子树 = 父节点 × 2 + 1。

代码

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
k = 4
k_tree = [-1 for i in range(0, k + 1)]
def FindLeft(root):
if root * 2 <= k:
return root * 2
return -1
def FindRight(root):
if root * 2 <= k - 1:
return root * 2 + 1
return -1
def BuildTree(val, root):
if val <= k_tree[root]:
return
else:
swap(val, root)
def swap(val, root):
if FindLeft(root) != -1 and val <= k_tree[FindLeft(root)]:
k_tree[root] = val
elif FindRight(root) != -1 and val >= k_tree[FindRight(root)]:
k_tree[root] = k_tree[FindRight(root)]
k_tree[FindRight(root)] = val
swap(k_tree[root], root)
swap(val, FindRight(root))
elif FindLeft(root) != -1 and FindRight(root) != -1 and val > k_tree[FindLeft(root)] and val < k_tree[FindRight(root)]:
k_tree[root] = k_tree[FindLeft(root)]
k_tree[FindLeft(root)] = val
swap(val, FindLeft(root))
elif FindLeft(root) != -1 and FindRight(root) == -1 and val >= k_tree[FindLeft(root)]:
k_tree[root] = k_tree[FindLeft(root)]
k_tree[FindLeft(root)] = val
swap(val, FindLeft(root))
for i in [12,32,53,45,6,7,6,8,9,9,324,6,5,4]:
BuildTree(i, 1)
print(k_tree)

两个有序的整数列表合并

简单版的归并排序。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def Sort(list1, list2):
ret_list = []
len1 = len(list1)
len2 = len(list2)
idx1 = idx2 = 0
while idx1 < len1 or idx2 < len2:
if idx1 >= len1:
ret_list.append(list2[idx2])
idx2 += 1
elif idx2 >= len2:
ret_list.append(list1[idx1])
idx1 += 1
elif list1[idx1] < list2[idx2]:
ret_list.append(list1[idx1])
idx1 += 1
else:
ret_list.append(list2[idx2])
idx2 += 1
return ret_list
list1 = [1,2,5,6,7,32,44]
list2 = [32,43,45,56,767]
print(Sort(list1, list2))

快速排序

快速排序作为排序的代表,原型或者其变型经常被考察。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def quick_sort(array, left, right):
if left >= right:
return
low = left
high = right
key = array[left]
while left < right:
if left < right and array[right] > key:
right -= 1
array[left] = array[right]
if left < right and array[left] <= key:
left += 1
array[right] = array[left]
array[left] = key
quick_sort(array, low, left - 1)
quick_sort(array, left + 1, high)
array = [1,4,2,3,45,46,6,57,68,79,98,223]
quick_sort(array, 0, len(array) - 1)
print(array)

矩阵查找

一个行、列都递增的矩阵中查找某个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solution(matrix, target):
if not matrix:
return False
if not matrix[0]:
return False
if target > matrix[-1][-1] or target < matrix[0][0]:
return False
j = 0
i = len(matrix) - 1
while True:
if i < 0 or j < 0 or i >= len(matrix) or j >= len(matrix[0]):
return False
if matrix[i][j] > target:
i -= 1
elif matrix[i][j] < target:
j += 1
else:
return True

连续不为0的区间和最大

Input: 数组长度n;数组的n个值;m个不同分割下标。

Output: 分别输出m个以对应下标分割的子区间的连续不为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
n = int(input())
line2 = input().split(' ')
line3 = input().split(' ')
line = [0 for i in range(n + 1)]
for i in range(n):
line[i + 1] = int(line2[i])
def BIG(sep, line):
line[sep] = 0
ret_sep = []
tmp = 0
for i in range(n + 1):
if line[i] == 0:
ret_sep.append(tmp)
tmp = 0
else:
tmp += line[i]
ret_sep.append(tmp)
max = 0
for item in ret_sep:
if item > max:
max = item
return max
for i in range(n):
sep = int(line3[i])
print(BIG(sep, line))

矩阵中“CHINA”的个数

Input: 矩阵大小n,以及n × n的字符矩阵。

Output: "CHINA"的个数。

代码

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
n = int(input())
n_lines = []
for i in range(n):
n_lines.append(input())
china_num = 0
arr_i = [1, -1, 0, 0]
arr_j = [0, 0, 1, -1]
def DFS(i, j, len):
if len == 5:
china_num += 1
else:
for t in range(4):
new_i = i + arr_i[t]
new_j = j + arr_j[t]
if new_i >= 0 and new_j >= 0 and new_i < n and new_j < n:
if len == 1 and n_lines[new_i][new_j] == 'H':
DFS(new_i, new_j, len + 1)
elif len == 2 and n_lines[new_i][new_j] == 'I':
DFS(new_i, new_j, len + 1)
elif len == 3 and n_lines[new_i][new_j] == 'N':
DFS(new_i, new_j, len + 1)
elif len == 4 and n_lines[new_i][new_j] == 'A':
DFS(new_i, new_j, len + 1)
for i in range(n):
for j in range(len(n_lines[i])):
if n_lines[i][j] == 'C':
DFS(i, j, 1)
print(china_num)

分析

在矩阵中可以上下左右组合的字符串或者递增子序列之类的问题,都可以使用DFS来做。

字符串中“Good”的数量

Input: 字符串。

Output: Good的数量

代码

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
line = input().strip()
mark = [0 for i in range(len(line))]
ret = 0
for i in range(len(line)):
if line[i] == 'G':
mark[i] = 1
j = i
o_count = 0
d_count = 0
while j < len(line) and o_count < 2:
if line[j] == 'o' and mark[j] == 0:
o_count += 1
mark[j] = 1
j += 1
if o_count == 2:
while j < len(line) and d_count < 1:
if line[j] == 'd' and mark[j] == 0:
d_count += 1
j += 1
if d_count == 1:
ret += 1
else:
break
else:
break
print(ret)

分析

字符串中存在某种子序列,做法大致相同。

矩阵的递增序列

Input: n × n矩阵。

Output: 最长递增序列的长度

代码

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
n = int(input())
matrix = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
line = input().strip().split(' ')
for j in range(n):
matrix[i][j] = int(line[j])
dfs = [[0 for i in range(n)] for j in range(n)]
x_d = [0, 0, 1, -1]
y_d = [1, -1, 0, 0]
def DFS(x, y, dfs):
if dfs[x][y] != 0:
return dfs[x][y]
for i in range(len(x_d)):
new_x = x + x_d[i]
new_y = y + y_d[i]
if new_x >= 0 and new_y >= 0 and new_x < n and new_y < n:
if matrix[new_x][new_y] > matrix[x][y]:
dfs[x][y] = max(DFS(new_x, new_y, dfs) + 1, dfs[x][y])
else:
dfs[x][y] = max(1, dfs[x][y])
return dfs[x][y]
for i in range(n):
for j in range(n):
dfs[i][j] = DFS(i, j, dfs)
print(max(max(dfs)))

分析

一个很明显的思路就是从某点出发,DFS查找最长的递增路径,但是考虑到某些节点可能在之前已经遍历过,可以使用其保存的信息。

不重叠区间

Input: n个不同区间。

Output: 去掉多少区间之后,剩下的区间构成不重叠区间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
interval_list = []
n = int(input())
for i in range(n):
line = input().strip().split(' ')
interval_list.append([int(line[0]), int(line[1])])
interval_list = sorted(interval_list, key = lambda item:item[1])
dp = [1 for i in range(n)]
for i in range(n):
for j in range(i - 1, -1, -1):
if interval_list[i][0] >= interval_list[j][1]:
dp[i] = max(dp[j] + 1, dp[i])
else:
dp[i] = max(dp[i], dp[j])
print(n - dp[-1])

机器人行走

Input: 有t组测试,每一组机器人从(0, 0)位置朝向向上,向右为x轴正方向,向下为y轴正方向,指令有:向左转(L),向右转®,前进N步或者到头(G N)以及打印当前位置§。

Output: 打印每个Case的编号以及执行P指令之后的输出。

代码

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
t = int(input())
cur_x = 0
cur_y = 0
cur_t = 1
Turns = ['L', 'U', 'R', 'D']
step_x = [0, -1, 0, 1]
step_y = [-1, 0, 1, 0]
def Turn(cur_t, turn):
if turn == 'R':
cur_t += 1 % len(Turns)
else:
cur_t -= 1 % len(Turns)
return cur_t
def Walk(cur_x, cur_y, cur_t, step, n):
if cur_x + step * step_x[cur_t] >= 0 and cur_x + step * step_x[cur_t] < n and cur_y + step * step_y[cur_t] >= 0 and cur_y + step * step_y[cur_t] < n:
return cur_x + step * step_x[cur_t], cur_y + step * step_y[cur_t]
elif cur_x + step * step_x[cur_t] < 0:
cur_x = 0
elif cur_y + step * step_y[cur_t] < 0:
cur_x = 0
elif cur_x + step * step_x[cur_t] >= n:
cur_x = n - 1
elif cur_y + step * step_y[cur_t] >= n:
cur_y = n - 1
return cur_x, cur_y
ret = ''
for times in range(t):
ret += 'Case #' + str(times + 1) + ':\n'
n_m = input().strip().split(' ')
n = int(n_m[0])
m = int(n_m[1])
cur_x = 0
cur_y = 0
cur_t = 1
for i in range(m):
line = input().strip().split(' ')
if line[0] == 'L' or line[0] == 'R':
cur_t = Turn(cur_t, line[0])
elif line[0] == 'G':
cur_x, cur_y = Walk(cur_x, cur_y, cur_t, int(line[1]), n)
elif line[0] == 'P':
ret += str(cur_y) + ' ' + str(cur_x) + '\n'
print(ret)

将0/1表示的字符串根据莫斯密码转化成字符串

以‘1’表示摩斯密码中的‘·’,以‘111’表示摩斯密码中的‘-’。 以‘0’表示莫斯密码中的分割。 以‘000’表示不同字符摩斯密码的分割。 以‘0000000’表示不同单词的分割。

Input: 以0/1表示的字符串

Output: 转化后的字符串

代码

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
line = input().strip()
ret = ''
last = 0
letter = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890'
ms = ['01', '1000', '1010', '100', '0', '0010', '110', '0000', '00', '0111', '101', '0100', '11', '10', '111', '0110', '1101', '010', '000', '1', '001', '0001', '011', '1001', '1011', '1100', '01111', '00111', '00011', '00001', '0000', '10000', '11000', '11100', '11110', '11111']
def DealC(line):
chr = ''
for i in line.split('0'):
if i == '1':
chr += '0'
else:
chr += '1'
for i in range(len(ms)):
if ms[i] == chr:
return letter[i]
def DealL(line):
ret = ''
lst = 0
for i in range(len(line) - 3):
if line[i: i + 3] == '000':
ret += str(DealC(line[lst: i]))
lst = i + 3
ret += str(DealC(line[lst:]))
return ret
for i in range(len(line) - 7):
if line[i:i + 7] == '0000000':
ret += str(DealL(line[last: i])) + ' '
last = i + 7
ret += str(DealL(line[last:]))
print(ret)

数n中各位数字全排列能整除数m的个数

Input: 两个数字n和m。

Output: 数n中各位数字全排列能整除数m的个数。

代码

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
line = input().split(' ')
n = int(line[0])
m = int(line[1])
num_list = [0 for i in range(10)]
lens = 0
while n > 0:
num_list[n % 10] += 1
n //= 10
lens += 1
ret = 0
def IN(num, num_list):
tmp_num_list = [0 for i in range(10)]
while num > 0:
tmp_num_list[num % 10] += 1
num //= 10
if tmp_num_list[0] <= num_list[0]:
for i in range(1, 10):
if tmp_num_list[i] != num_list[i]:
return False
return True
else:
return False
for i in range(1, int(pow(10, lens) / m)):
if IN(m * i, num_list):
print(m * i)
ret += 1
print(ret)

分析

我的思路是通过逆向观察m倍数需要的那些数字是否都在n里面来判断n的各位全排列能否得到m的倍数。当然,如果n中0的个数大于m的倍数中0的个数是不影响的。

最长回文子串

Input: 字符串

Output: 最长回文子串

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
line = input().strip()
dp = [0] * len(line)
for i in range(1, len(line)):
if line[i] == line[i - dp[i - 1] - 1] and i - dp[i - 1] - 1 >= 0:
dp[i] = dp[i - 1] + 2
elif line[i] == line[i - 2] and dp[i - 1] == 0:
dp[i] = 3
else:
dp[i] = 0

for i in range(len(dp)):
if max(dp) == dp[i]:
print(line[i + 1 - max(dp): i + 1])

分析

简单的动态规划,但是要考虑两种情况:(1)回文串长度为偶数;(2)回文串长度为奇数即中间的字母不用回文。

大鱼吃小鱼

Input: 长度为n的整数串

Output: 每次大鱼吃小鱼,可以同时进行,输出大鱼吃小鱼的次数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n = int(input())
line = input().split(' ')
int_list = [int(line[i]) for i in range(len(line))]
live = [1] * len(int_list)
left = len(int_list)
new_left = 65535
ret = -1
while left < new_left:
new_left = left
key = int_list[0]
for i in range(1, len(int_list)):
new_k = int_list[i]
if key > int_list[i]:
int_list[i] = -1
key = new_k
ret += 1
for i in range(len(int_list)- 1, -1, -1):
if int_list[i] == -1:
int_list.pop(i)
left = len(int_list)
print(ret)

非递归版二叉树深度

代码

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
num =int(input())
class TreeNode:
def __init__(self, val = None, left = None,right = None):
self.val = val
self.left = left
self.right = right
def Depth(root):
if root == None:
return 0
else:
queue = []
depth = 0
queue.append(root)
while len(queue):
depth += 1
cur = len(queue)
tmp = 0
while(tmp < cur):
tmp += 1
node = queue.pop(0)
if node.left != None:
queue.append(node.left)
if node.right != None:
queue.append(node.right)
return depth
treenode = [None for i in range(num)]
for i in range(num):
treenode[i] = TreeNode(i)
for i in range(num):
if i * 2 + 1 < num:
treenode[i].left = treenode[i * 2 + 1]
if i * 2 + 2 < num:
treenode[i].right = treenode[i * 2 + 2]
print(Depth(treenode[0]))

分析

二叉树深度就是二叉树层数,所以可以使用层序遍历二叉树实现。

数组中出现超过一半的数字

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def majorityElement(nums: List[int]) -> int:
dp = [0] * len(nums)
dp[0] = 1
votes = nums[0]
for i in range(1, len(nums)):
if dp[i - 1] == 0:
votes = nums[i]
dp[i] = 1
continue
if votes == nums[i]:
dp[i] = dp[i - 1] + 1
else:
dp[i] = dp[i - 1] - 1
return votes

分析

每一步设定当前值为“大于一半的数”并将此时的值记为“+1”,往后遇到不同的值在该值上“-1”,遇到值为0,则将前面的序列舍弃,重新开始计数。最终在序列扫描一遍之后的假设“大于一半的数”的值即为最终结果。



本文链接: http://home.meng.uno/articles/fdc308a8/ 欢迎转载!

© 2018.02.08 - 2020.10.14 Mengmeng Kuang  保留所有权利!

UV : | PV :

:D 获取中...

Creative Commons License