Hello, 前几天面了字节跳动算法岗的面试. 其中有一道题, 面试时候有点紧张就只写了一个枚举法, 感觉有点凉了。 面完后面试官说其实O(n). 想让大家帮忙一起看看这题应该如何更好更高效的求解.

原题如下:

有一个长度为N的数列, 其中的每个元素是0,1,? 三种之一. 其中?表示待定, 即可以为0, 也可以为1.
给定正整数K。
想知道, 能否找到一种给每个?赋值分配0或者1的方案, 使得数列中任意连续K个数字中, 1的个数和0的个数都相等

我当时有点紧张, 就想着写了一个枚举的方法.

1. 扫一遍数列， 找到每个?的下标
2. 根据1找出来的下标, 生成每个下标里填充0或者1的数组结果
3. 对2里每个填充结果进行K-长度的滑动窗口的检查, 任何一个能滑到底就返回True
4. 不然就返回False

但这样写出来的话, 时间复杂度最差是O(n*2^n)， 就差得挺离谱.

想问问大家怎么写一个O(n)的思路的算法, 谢谢