欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2020字节跳动秋招笔试题解析与代码分享(持续更新中)

程序员文章站 2022-04-28 23:35:26
...

引言

2020年秋招已经结束了,小伙伴的情况如何啊。趁着过年前在家,把今年字节跳动秋招上机笔试题整理分享给大家。
2020字节跳动秋招笔试题解析与代码分享(持续更新中)

1. 圆形花园的入口

题目描述
现有一个圆形花园共有 n 个入口,现在要修些路,穿过这些花园。要求每个入口只能有一条路,所有的路均不会相交,求所有可行的方法总数。
若圆形花园中有四个入口,答案2
若圆形花园中有六个入口,答案4
2020字节跳动秋招笔试题解析与代码分享(持续更新中)

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

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

**分析:**以n = 8为例,之前的n = 6,4,2,0的情况都已经知道了。8是在6的基础上添加了两个点,例如把1,2连接在一起,剩下的就是6个点连接方式就是dp[ 6 ],1还可以连接哪些点呢?3是不可以的,因为要求直线不可以相交,1,3相连之后,2就被包围了,所以2的直线就肯定和别的直线相交。换句话说,从1开始和另外一个点把剩下的6个点分割成两个部分,这两部分只能内部连接,所以两部分的点数都必须是偶数。思路进一步等价=>遍历所有和等于6并且各自点数为偶数(包括0)的情况,又因为两个部分各自独立,所以总的情况等于两部分情况之积。所有的积之和就是当前的 dp[ 8 ]。推广到一般形式:8->n,6->n-2。

另外不用考虑不同的起点问题,以单一起点已经考虑了所有的情况,其他点作为起点的情况也被考虑在内了。

代码实现:
Python:

if __name__ == "__main__":
    n = int(input())
    res = [0]*(n+1)
    res[0] = 1
    for i in range(2, n+1, 2):
        for j in range(0, (i-2)+1, 2):
            res[i] += (res[j]*res[i-2-j])
        res[i] = res[i] % 1000000007
    print(res[n])

这一类题型为 卡特兰数,leetcode 96题,AC 100%

C++:

在这里插入代码片

2. 2048合并

2020字节跳动秋招笔试题解析与代码分享(持续更新中)
2020字节跳动秋招笔试题解析与代码分享(持续更新中)
2020字节跳动秋招笔试题解析与代码分享(持续更新中)
题目分析:

代码实现:

3. 得到更多糖果

2020字节跳动秋招笔试题解析与代码分享(持续更新中)
2020字节跳动秋招笔试题解析与代码分享(持续更新中)

题目分析:

代码实现:

4. 世界杯开幕式

思路:跟leetcode上求岛屿数量问题很像,使用DFS,这里要注意的是搜索方向从4个变成了8个,并且要输出最大区域里的人数。

代码实现: 引自Cytues - 1. 世界杯开幕式

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

5. 文章病句标识

思路

  • 区间合并
  • 排序 + 贪心
    对 [l1,r1], [l2,r2],如果 r1 > l2,则 r1 = max(r1, r2)

代码实现: 引自Cytues - 2. 文章病句标识

# 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

6. 积分卡牌游戏

思路

  • 动态规划
  • 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])​

代码实现: 引自Cytues - 3. 积分卡牌游戏

# 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

2020字节跳动秋招笔试题解析与代码分享(持续更新中)

2020字节跳动秋招笔试题解析与代码分享(持续更新中)

思路: 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


上一篇:从浏览器输入一个URL(www.baidu.com)后执行全过程

下一篇:TCP三次握手、四次挥手几常见面试题全集


欢迎各位订阅我,谢谢大家的点赞和专注!我会继续给大家分享我大学期间详细的实践项目。