w***g
发帖数: 5958 | 1 就那个一个01字符串，求0和1个数相等的最长子串那个？难道那个题目是昨天我做梦时
看见的？ |
X****r
发帖数: 3557 | 2 大概不是这个版吧。
【在 w***g 的大作中提到】
: 就那个一个01字符串，求0和1个数相等的最长子串那个？难道那个题目是昨天我做梦时
: 看见的？
|
a****d
发帖数: 114 | 3 jobHunting
【在 w***g 的大作中提到】
: 就那个一个01字符串，求0和1个数相等的最长子串那个？难道那个题目是昨天我做梦时
: 看见的？
|
a*******s
发帖数: 79 | 4 这题目很简单啊
【在 w***g 的大作中提到】
: 就那个一个01字符串，求0和1个数相等的最长子串那个？难道那个题目是昨天我做梦时
: 看见的？
|
w***g
发帖数: 5958 | 5 这个有时间和空间复杂度要求的。我忘了原题的要求了。好象是O(1)空间和O(n)时间，
想确认一下。
【在 a*******s 的大作中提到】
: 这题目很简单啊
|
a*******s
发帖数: 79 | 6 也不算很难吧，没有具体写代码验证，先瞎想想给个解决：
两个cursor，一个指向子序列头，一个指向子序列尾（初始化为整个序列的第0，1两个
位置）
指向尾的每次后移1位，把这位的值加到sum里面，如果两个cursor的差值 + 1恰好是
sum的2倍
那么序列符合条件（只有序列长度为偶数才需要判断），更新下最长序列的长度len，
否则把指向头部的
cursor也后移一位，并从sum中删除这一位的值
最后输出len，如果你想知道最长子序列的位置，再记录下这个的起始位置就行
存储的中间变量是常数级就是O(1),整个遍历过程也是O(n)的，而且还可以进一步优化
【在 w***g 的大作中提到】
: 这个有时间和空间复杂度要求的。我忘了原题的要求了。好象是O(1)空间和O(n)时间，
: 想确认一下。
|
X****r
发帖数: 3557 | 7 你这个不对啊，比如
11110000
你这个只能得到中间的1100。
【在 a*******s 的大作中提到】
: 也不算很难吧，没有具体写代码验证，先瞎想想给个解决：
: 两个cursor，一个指向子序列头，一个指向子序列尾（初始化为整个序列的第0，1两个
: 位置）
: 指向尾的每次后移1位，把这位的值加到sum里面，如果两个cursor的差值 + 1恰好是
: sum的2倍
: 那么序列符合条件（只有序列长度为偶数才需要判断），更新下最长序列的长度len，
: 否则把指向头部的
: cursor也后移一位，并从sum中删除这一位的值
: 最后输出len，如果你想知道最长子序列的位置，再记录下这个的起始位置就行
: 存储的中间变量是常数级就是O(1),整个遍历过程也是O(n)的，而且还可以进一步优化
|
