我最近遇到了一个问题陈述,它说:
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
我尝试了一种强力方法,将每个遇到的0替换为1,并且在每次替换之后,我计算出最大的连续重复序列1,并且每次更新它.
这个问题有更好的方法/算法吗？
应该有一个解决方案.总的想法是计算那些并计算每个零的长度.好吧,不是每个零,只是最后遇到的一个和最长的.
你需要跟踪两件事:
然后过程如下:
开始穿过弦,直到遇到零.随时跟踪一些数量.
当你达到零时,记住零的位置以及前面的1的数量.
将1s计数到下一个零.
回到前一个零,并将新的"1"添加到之前的"1".如果这比最长的链长,则更换最长的链.
记住这个零以及前面的1.
重复,直到到达字符串的末尾.
在字符串的末尾,返回并将长度添加到前一个零,并在适当时替换最长的链.
| 归档时间： |
|
| 查看次数： |
3108 次 |
| 最近记录： |