我最近遇到了一个问题陈述它说:
Given an array of 0s and 1s, find the position of 0 to be
replaced with 1 to get longest continuous sequence of 1s.
For example : Array- 1,1,0,0,1,0,1,1,1,0,1,1,1
Output - index 9
我尝试了一种蛮力方法,用 1 替换每个遇到的 0,在每次这样的替换之后,我计算了 1 的最大连续重复序列并每次更新它。
是否有更好的方法/算法来解决这个问题?
最佳答案
应该有一个一次性的解决方案。总体思路是数一数,然后将每个零的长度加起来。好吧,不是每个零,只是最后遇到的一个和最长的。
您需要跟踪两件事:
- 迄今为止最长的链。
- 前一个零值,以及前面零值的长度。
流程如下:
开始遍历字符串,直到遇到零。随时记录人数。
当你击中零时,记住零的位置以及前面 1 的数量。
将 1 数到下一个零。
回到之前的零,将新的“一”加到之前的“一”上。如果这比最长的链长,则替换最长的链。
记住这个零和前面的 1。
重复直到到达字符串的末尾。
然后在字符串的末尾,返回并将长度添加到前一个零,并在适当的情况下替换最长的链。
关于arrays - 获取最长连续的 1 序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27141416/