字节跳动校招笔试题汇总
1. 世界杯开幕式
思路:跟leetcode上求岛屿数量问题很像,使用DFS,这里要注意的是搜索方向从4个变成了8个,并且要输出最大区域里的人数。
# coding:utf-8
M, N = list(map(int, raw_input().split(',')))
book = []
for i in range(M):
line = list(map(int, raw_input().split(',')))
book.append(line)
class Solution:
def __init__(self, grid):
self.grid = grid
# 当前区域的人数
self.cnt = 0
# 保存所有区域中的人数,返回其长度,及其最大值
self.dp = []
def dfs(self, i, j):
if 0 <= i < M and 0 <= j < N:
if self.grid[i][j] == 1:
self.cnt += 1
# 经过的点就置0
self.grid[i][j] = 0
# (i-1,j-1) (i-1,j) (i-1,j+1)
# (i,j-1) (i,j) (i,j+1)
# (i+1,j-1) (i+1,j) (i+1,j+1)
# 8个方向搜索
self.dfs(i - 1, j)
self.dfs(i + 1, j)
self.dfs(i, j - 1)
self.dfs(i, j + 1)
self.dfs(i - 1, j - 1)
self.dfs(i + 1, j + 1)
self.dfs(i + 1, j - 1)
self.dfs(i - 1, j + 1)
def solve(self):
for i in range(M):
for j in range(N):
if self.grid[i][j] == 1:
# 每找到一个新区域就清0,因为被搜索过的1都置0了,所以新区还是1
self.cnt = 0
self.dfs(i, j)
if self.cnt > 0:
self.dp.append(self.cnt)
return len(self.dp), max(self.dp)
2. 文章病句标识
思路
- 区间合并
- 排序 + 贪心
对 [l1,r1], [l2,r2],如果 r1 > l2,则 r1 = max(r1, r2)
# coding:utf-8
m = int(raw_input())
temp = []
for _ in range(m):
line = [list(map(int, item.split(','))) for item in raw_input().split(';')]
# [[1, 10], [32, 45]]
temp.extend(line)
# 按每段病句[l, r]的第一个位置l排序
temp = sorted(temp, key=lambda x: x[0])
# [[1, 10]]
ret = [temp[0]]
# 与之后的病句段进行比较
for item in temp[1:]:
# res[-1][1] == 10从后往前取
# item == [32, 45], item[0] == 32
if ret[-1][1] >= item[0]:
# 贪心:对 [l1,r1], [l2,r2],如果 r1 > l2,则 r1 = max(r1, r2)
# [5, 16], [16, 32], 16 >= 16, max(16, 32) ---> [5, 32]
ret[-1][1] = max(ret[-1][1], item[1])
else:
# [[1, 10], [32, 45]]
ret.append(item)
s = ''
# 不取最后一位,因为最后一位末尾不添加分号
for item in ret[:-1]:
s += str(item[0]) + ',' + str(item[1]) + ';'
# 单独处理
s += str(ret[-1][0]) + ',' + str(ret[-1][1])
print s
3. 积分卡牌游戏
思路
- 动态规划
-
DP 定义:
d[i][j] := 前 i 张牌,两人所选择的牌的差值为 j 时的最大值
-
转移方程
d[i][j] = max(d[i-1][j], d[i-1][j-x[i]] + y[i], d[i-1][j+x[i]] + y[i])
# coding:utf-8
n = int(raw_input())
x, y = [], []
for i in range(n):
_x, _y = list(map(int, raw_input().split()))
x.append(_x)
y.append(_y)
xy = list(zip(x, y))
# print xy
# 根据y的值进行排序
xy = sorted(xy, key=lambda t: t[1])
# print xy
ret = 0
# 如果所有 x 的和为偶数
# 直接输出所有 y 的和
if sum(x) % 2 == 0:
print sum(y)
else:
for i in range(len(xy)):
if xy[i][0] % 2 == 1:
# j只取偶数,排除掉x中的奇数项
ret = sum([xy[j][1] for j in range(len(xy)) if j != i])
print ret
break
思路:leetcode原题
N = int(raw_input())
line = list(map(int, raw_input().split()))
count = 0
for i in line:
if count == 0:
if i >> 3 == 0b11110:
count = 3
elif i >> 4 == 0b1110:
count = 2
elif i >> 5 == 0b110:
count = 1
elif i >> 7 == 0b0:
count = 0
else:
print 0
else:
if i >> 6 == 0b10:
count -= 1
else:
print 0
print 1