前言

因为有朋友在线面试字节跳动,需要我帮帮忙,因此便有了这篇文章。
(虽然我写完题目之后,朋友的面试已经时间截止了,不过留作参考也不错 >_<|||)
朋友希望能够顺利的看懂语句,所以我的注释写的比较多。

字节跳动

进入主题

第一题

题目描述:
抖音上每天都有几亿用户,如果用户 A 和 B 互动不少于 3 次,我们就认为 A 和 B 属于“豆油”,如果 A 和 B 是“豆油”,B 和 C 也是“豆油”, 那么 A 和 C 也互为“豆油”,我们定义“豆油瓶”就是由直系和间接朋友所组成的群体。

给定个 N×N 的矩阵 M,代表抖音上所有用户的互动次数,如果M[i][j]= 5,那么第i个和第j个用户就互动过5次,为 0 的话代表没有互动,对于i = j,即同个用户, 互动次数我们计为0。请你计算并输出发现的抖音上所有“豆油瓶”的个数。

输入描述:

输入第1行:二维数组的行数(列数一样) N
接下来的N行每行N个数字,空格分割

输出描述:

输出发现的“豆油瓶”数量 k

示例1:

输入

3
0 4 0
4 0 0
0 0 0

输出

2

解释:第1个和第2个用户互动超过3次,互为豆油第3个学生和其他人没有互动,自成个豆油瓶,所以结果为2

示例2:

输入

3
0 4 0
4 0 6
0 6 0

输出

1

解释:第1个和第2个用户互动超过3次,互为豆油,第2个和第3个用户也互为豆油,所以1和3互为间接豆油,三个用户都在同一个豆油瓶里,返回1

N的范围为[1,200]
所有学生自己对自己都是1,即M[i][i]=1
如果M[i][j]=1,那么M[j][i]=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
35
36
37
38
39
40
if __name__ == "__main__":
print('输入第1行:二维数组的行数(列数一样) N \n接下来的 N 行每行 N 个数字,空格分割')
# 设定 N 为 二维数组的行数,
# input()是输入事件,
# int()把输入的字符串型的数据 转换成整型
N = int(input())
# 根据已知条件,给定一个 N*N 的矩阵 M, 矩阵 M 本质上是一个二维数据
# 设定 M 为 二维数组
M = []
# 使用For循环 生成 M 二维数组
# 根据 N (二维数组的行数) 接收 N 次输入的信息 并 依次填充到 M 二维数组中
for i in range(N):
# 接收输入的信息
# 使用For循环 接收 输入的信息
# strip()方法 去掉 字符串中头尾的空格或换行符
# split()方法 根据指定的字符,将字符串拆分成若干个元素的数组
node = [int(x) for x in input().strip().split(' ')]
# 填充到 M 二维数组中
M.append(node)
# 设定一个 N 大小的临时数组
temp = [0] * N
# 设定 k 为 豆油瓶的数量
k = 0
# 获得临时数组中的最小值,当最小值为0时,进入while循环
while min(temp) == 0:
# 使用For循环 依次将 N 二维数组中的数据取出,存入
t = [i for i in range(N) if temp[i] == 0]
temp[t[0]] = 1
q = []
q.append(t[0])
while q:
# pop()方法 移除列表中的一个元素并返回该元素的值
h = q.pop(0)
for j in range(N):
# 如果互动大于 3 次
if M[h][j] >=3 and temp[j] == 0:
q.append(j)
temp[j] = 1
k += 1
print('输出发现的“豆油瓶”数量 k: %d'%k)

运行结果:


第二题

题目描述:
现有一个圆形花园共有 n 个入口,现在要修些路,穿过这些花园。要求每个入口只能有一条路,所有的路均不会相交,求所有可行的方法总数。

输入描述

整数n,代表有n个花园入口,n为2的倍数,n在2到1000的整数区间范围内

输出描述

输出整数 m mod 1000000007,采用 mod 1000000007 降低数字量级。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if __name__ == "__main__":
print('请输入整数 n (代表有 n 个花园入口,n 为 2 的倍数,n 在 2 到 1000 的整数区间范围内):')
# 设定 整数n,代表有n个花园入口,n为2的倍数,n在2到1000的整数区间范围内
n = int(input())
# 设定 输出整数 m
m = [0] * (n + 1)
m[0] = 1
# 使用For循环,从 2 开始,每次循环增加 2
for i in range(2, n+1, 2):
for j in range(0, (i-2)+1, 2):
# 使用卡特兰数的递推公式
m[i] += (m[j] * m[i - 2 - j])
# 采用 mod 1000000007 降低数字量级
m[i] = m[i] % 1000000007
print(m[n])
print('输出整数 m: %d'%m[n])

运行结果:


第三题

题目描述:
2048游戏是一个4*4的矩阵,用户可以按上下左右4个方向键让所有的方块向同一个方向运动,两个相同数字方块撞在一起之后合并成为他们的和,每次操作之后随机生成一个2或者4.

合并规则:相邻会碰撞的两个数字合并且一个位置只会出发一次合并,且优先合并移动方向顶部的位置
比如【2 2 2 2】行向右合并后为【0 0 4 4】
【0 2 2 2】行向右合并后为【0 0 2 4】

输入描述

输入第一行是用户按下的方向键,1代表上,2代表下,3代表左,4代表右
接下来是一个4*4的矩阵,空格分割,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
76
77
78
79
80
81
82
83
84
85
86
87
if __name__ == "__main__":
print('输入第一行是用户按下的方向键,1代表上,2代表下,3代表左,4代表右\n接下来是一个4*4的矩阵,空格分割,0代表这个位置没有数字')
# 输入用户按下的方向键
direction = int(input())
# 设定 M 为 二维数组
M = []
# 设定 N 为 矩阵的行数大小
N = 4
for i in range(N):
# 输入 矩阵数据
node = [int(x) for x in input().strip().split(' ')]
# 填充到 M 二维数组中
M.append(node)
# 当用户输入的方向键 为 1时,1代表上
if direction == 1:
for j in range(N):
for i in range(N-1):
# 判断相邻的数据是否相等,相等则相加,并将另一数据置零
if M[i][j] == M[i+1][j]:
M[i][j] *= 2
M[i+1][j] = 0
t = 0
for i in range(N):
if M[i][j] != 0:
# 将所有数据上移
M[t][j] = M[i][j]
t+=1
while(t < N):
M[t][j] = 0
t+=1
# 当用户输入的方向键 为 2时,2代表下
elif direction == 2:
for j in range(N):
for i in reversed(range(1,N)):
# 判断相邻的数据是否相等,相等则相加,并将另一数据置零
if M[i][j] == M[i-1][j]:
M[i][j] *= 2
M[i-1][j] = 0
t = N-1
for i in reversed(range(N)):
if M[i][j] != 0:
# 将所有数据下移
M[t][j] = M[i][j]
t-=1
while(t >= 0):
M[t][j] = 0
t-=1
# 当用户输入的方向键 为 3时,3代表左
elif direction == 3:
for i in range(N-1):
for j in range(N-1):
# 判断相邻的数据是否相等,相等则相加,并将另一数据置零
if M[i][j] == M[i][j+1]:
M[i][j] *= 2
M[i][j+1] = 0
t = 0
for j in range(N):
if M[i][j] != 0:
# 将所有数据左移
M[i][t] = M[i][j]
t+=1
while(t < N):
M[i][t] = 0
t+=1
# 当用户输入的方向键 为 4时,4代表右
elif direction == 4:
for i in range(N-1):
for j in reversed(range(1, N)):
# 判断相邻的数据是否相等,相等则相加,并将另一数据置零
if M[i][j] == M[i][j-1]:
M[i][j] *= 2
M[i][j-1] = 0
t = N-1
for j in reversed(range(N)):
if M[i][j] != 0:
# 将所有数据右移
M[i][t] = M[i][j]
t-=1
while(t >= 0):
M[i][t] = 0
t-=1
print('输出用户按下该方向键后的矩阵数值,忽略随机产生数字')
for i in range(N):
node = ""
for j in range(N):
node += str(M[i][j]) + " "
print(node)

运行结果:


第四题

题目描述:
在漫天的星空里散落着一些糖果,它们各有各的甜度。有一些糖果之间会按照一定的规则有桥梁连接,好让你获得这个糖果之后,可以去获得和该糖果相连的其他糖果。现在你要选择一个糖果开始,去尽可能的得到更多糖果。
我们将糖果一一编号1,2,3,……,n,每一个糖果的甜度记为a[n]。
若糖果i和糖果j的甜度的最大公约数>1,则糖果i和糖果j之间有桥梁连接。

输入描述

首先输入一个数字 n 表示天上有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
import math

### 判断两个数的最大公约数
def cal(a,b):
if (a<=1 or b<=1):
return 0
t = 2
while(t<=math.sqrt(a) and t <= math.sqrt(b)):
if (a % t == 0 and b % t == 0):
return 1
t+=1
return 0

if __name__ == "__main__":
print('首先输入一个数字 n 表示天上有n个糖果 \n接下来一行 有 n 个数字,表示各个糖果的甜度')
# 设定 n 表示天上有n个糖果
# input()是输入事件,
# int()把输入的字符串型的数据 转换成整型
n = int(input())
# 输入 每颗 糖果的甜度
sweet = input().strip().split(' ')
s = []
# 将糖果一一编号1,2,3,……,n
for num in range(1,n+1):
s.append(int(num))
queue = []
# 最少可获得一个糖果
sugar = 1
for i in range(n):
if i not in s:
count = 1
queue.append(i)
while(queue):
temp = queue[0]
# 将移除列表中的最后一个元素
queue.pop()
for j in range(n):
# 判断糖果i和糖果j的甜度的最大公约数
if temp not in s and cal(int(sweet[i]), int(sweet[j])) == 1 and i != j:
# 则糖果i和糖果j之间有桥梁连接
count+=1
queue.append(temp)
s.append(temp)
if count > sugar:
sugar = count
print('最多能获得%d个糖果'%sugar)

运行结果:


to be continued…