春招-字节笔试

体验

平台：牛客网

特点：

1. 标准 sys 输入和输出，给输入和输出的范例，主要是多行输入和单行输出
2. 可以自测，可以print

题目

总共有四道题目

1）环形数组 - 找座位问题

给出一个环形数组，其中全部为 0 或 1

请找到一个 0，它距离两侧的 1 应该最远

比如：

【0 0 0 0 0 1 0 0】

那么 应该是在索引2的位置放1，距离最远，最远距离为 4

分析：

其实就是找两个 1 之间最大距离，或者说 连续 0 的最多数量

我的方法就是找 两个 1 之间的最大距离

而且，为了满足环形要求，直接在现在的数组后面续上一个数组

这样遍历一遍，就能解决问题了

【本题全部测试用例通过，10分】

2）多叉树寻根问题

问题描述：

一个初代病毒 T 可以分裂出多个子代病毒

子代病毒还可以继续分裂

原病毒是无致命性的，但是分裂和遗传的过程中可能会有致命性

如果已知某几个病毒是有致命性的，请找出它们的最近的共同根节点

输入的写法【多行输入】：

N 个病毒，R 条分裂

M个致病：编号依次是

分裂关系1：亲代、子代数量、子代编号

分裂关系2：亲代、子代数量、子代编号

分析：

其实本题充分描绘了一颗多叉树的全貌，但是问题是：

（1）如何进行还原

（2）怎么样找最近的

我首先想到的就是 Union-find 并查集的方法，一个建图的问题

复习一下：并查集问题涉及以下几个步骤：

union - 建图

connected - 判断是不是连通

count - 用于计数（对于岛屿问题可以使用）

在建图和判断连通的过程中，会使用 find 函数寻找根节点

那么本题中虽然有非常明确的多叉树结构，但是还不需要把全图建好，重要的是根据 find 函数寻找到根节点

所以我的方法就是根据所给树的信息建立 parents 的表单

因为输入信息中 父 - 子 节点的关系十分明确，可以直接对子节点存储 parent 的情况

然后就是比较 各致命病毒 的父节点，什么是否是一样的？

• 这个问题有点难，我想的可能不够完整

我的想法是：

由于该树中，其实大小是有一定的顺序的，是一颗二叉搜索树

致命病毒id 也是有顺序的，可以根据最小的节点为标准

如果别的病毒的父节点 id > 该节点的父节点 id，那么其他病毒就找父节点，然后再比较父节点

只有 别的病毒的父节点 id < 该节点的父节点 id 时，才会找该节点的父节点 id

---

几点说明：

共同父节点是一定存在的，怎么说 0 也是共节点

但是要找的是最近的

【结果，本题通过了 70% 的测试用例， 本题30分】

3）破解机关问题 - 环形数组

这个问题很有意思，我也想问

比如原神中有多个火柱子，初始状态有亮 - 1，有灭 - 0

请问怎么样用最少的次数将所有的火柱子都点亮，如果不能全部点亮，就返回 -1

举例：

10

0 1 1 0 0 0 1 0 0 1

最后应该是 4次就可以将所有火柱子点亮

分析：

我的方法应该是贪心算法

只要遇到0，那么下一个柱子就点亮，这样会同时影响 i, i+1, i+2三个柱子的值：

if f[i] == 0:
    f[i] = 1
    f[i+1] = int(f[i+1]==0)
    f[i+2] = int(f[i+2]==0)

个人觉得这个地方的逻辑判断做的还可以：

如果 f[i+1]=1，那么，就会变成 false - 0

如果 f[i+1]=0，那么，就会变成 true - 1

相当于是与 0 异或

按照这种方法前面都好说，但是当 i = n - 2的时候， i + 2 = n，会超出索引

由于这是一个环形，所以需要把第一个柱子续在后面，一个即可【应该吧】

我当时的判断条件是：当 i = n - 1时，如果 f[i] = 0，那么就判断 false

但是现在看来还是不太对

因为 i = n - 2的时候， i + 2 = n，会改掉第一个柱子的值，这样还是不太对

应该是 i = n - 2 的时候，如果 f [i] = 0，那么其实就是 false 了

【本题最好的通过情况是 37.5% ， 本题30分】

---

而且这个方法对很多问题的算法并不是最佳的，比如：

4

0 0 1 0

很显然一次就够了，但是按算法，会是 false

4）棋盘游戏问题

这类几何拓扑的问题，一看到就想放弃，确实不擅长做，主要是觉得二维进行遍历和存储的时候很麻烦

问题描述：

给一个 n * m 的棋盘，以及棋盘的状态（有的位置是空的·，有的非空 #）

有若干 1 * 2 的棋子可以进行填充

问是不是可以用棋子将棋盘填满，而且填法唯一，返回唯一填法

如果不是，就返回 -1

---

其实如果是唯一 填法，那么填起来应该也不会太难

我们可以看几个案例：

（1）

· ·

· ·

这是 2x2 的棋盘，有两种方式可以填满，所以不是唯一的

那么是不是说只要有这样的位置，就可以断定填不满了呢？不是

（2）

· · #
· · ·
· # #

这是有唯一解的，唯一解为

< > #
^ < >
v # #

其中 < > 表示横着放的棋子，^ v 表示竖着放的棋子

经过和同学的讨论，大家认为是这样，可以从头开始遍历，但是需要深度优先

比如从左上角开始遍历：

• 可能有两种放置方法，可以任选一种【任选也说明了多叉树的分支，这肯定要用回溯算法进行回调的，复杂度比较高】
  • 但是最好有顺序，比如优先 横放，次之 竖放
• 然后选择没有被占领的一个空格，看是不是可以放下棋子
  • 如果放不下，这条路肯定走不通了，就要返回了
  • 如果可以放下，那么继续选择旁边没有被占领的空格，遍历
• 如果没有上面说的空格，那么就按照竖列，遍历到底
  • 如果没有返回 false，肯定需要遍历完整个棋盘

这个问题里面，如果有很多种解法，那么至少需要找到两组成功的解法，才能说明 false

否则需要一直找下去，找不到成功解法才 false

还是应该找一种能判断 false 的方法