m******0
发帖数: 222 | 1 我之前的描述有问题，现在补充一下描述：
define: a distinct character in returned string means the character's number
of appearance equals one.
Given a string, find the length of longest sub-string(s) which contain at
most K distinct characters.
for example,
given string="AABBCC", K=1, return="AABBCC"
given string="AAXBBYCCC", K=1, return="BBYCCC"
想了半天只想到了O(n^2)的解法。各位有更好的办法没 |
b********6
发帖数: 35437 | 2 Leetcode原题，有O(n)解。问题简化成，对于一个已知的subtring，怎么快速地查找
substring的下一个字母是不是在substring里，不在的话就增加substring，在的话就
要更新substring和最长substring的长度。
用一个256的整形数组保存上次发现这个字母的位置，然后用一个变量start保存当前
substring的起始位置。如果上次发现字母的位置在start之前，就扩展substring，如
果在start之后就要更新start
这个算法把整个string遍历一次O(n)，中间的查找是O(1)，总共耗时O(n) |
s**9
发帖数: 207 | 3 invariable:
p1: start of substring,
p2: end of substring,
hashset: set of chars in substring.
pmax: start of answer so far
lmax: size of answer so far
forword p2, update hashset, pmax, lmax. depending on size of hashset,
forward p1 or p2.
【在 b********6 的大作中提到】
: Leetcode原题，有O(n)解。问题简化成，对于一个已知的subtring，怎么快速地查找
: substring的下一个字母是不是在substring里，不在的话就增加substring，在的话就
: 要更新substring和最长substring的长度。
: 用一个256的整形数组保存上次发现这个字母的位置，然后用一个变量start保存当前
: substring的起始位置。如果上次发现字母的位置在start之前，就扩展substring，如
: 果在start之后就要更新start
: 这个算法把整个string遍历一次O(n)，中间的查找是O(1)，总共耗时O(n)
|
m******0
发帖数: 222 | 4 thanks！
我之前的描述有问题，现在补充一下描述。已经修改了题目。
【在 b********6 的大作中提到】
: Leetcode原题，有O(n)解。问题简化成，对于一个已知的subtring，怎么快速地查找
: substring的下一个字母是不是在substring里，不在的话就增加substring，在的话就
: 要更新substring和最长substring的长度。
: 用一个256的整形数组保存上次发现这个字母的位置，然后用一个变量start保存当前
: substring的起始位置。如果上次发现字母的位置在start之前，就扩展substring，如
: 果在start之后就要更新start
: 这个算法把整个string遍历一次O(n)，中间的查找是O(1)，总共耗时O(n)
|
s******y
发帖数: 416 | 5 K=1?
number
【在 m******0 的大作中提到】
: 我之前的描述有问题，现在补充一下描述：
: define: a distinct character in returned string means the character's number
: of appearance equals one.
: Given a string, find the length of longest sub-string(s) which contain at
: most K distinct characters.
: for example,
: given string="AABBCC", K=1, return="AABBCC"
: given string="AAXBBYCCC", K=1, return="BBYCCC"
: 想了半天只想到了O(n^2)的解法。各位有更好的办法没
|
b********6
发帖数: 35437 | 6 思路差不多，可以用array[queue]来解决，同样的O(n)
queue里存对应字母的所有位置，substring用start和end来标定，end每进一位，就把
位置存到对应字母的queue里。如果最小重复的要求被打破，就把start进位，start每
进一位就把start经过的那个字母的queue里pop。直到有一个pop以后变成distinct字母。
array的查找是O(1)，queue的push pop操作是O(1)，整个数组遍历下来，pop和push的
次数不超过string长度。用queue而不用多重array或vector是因为要可变数组和删头节
点。
【在 m******0 的大作中提到】
: thanks！
: 我之前的描述有问题，现在补充一下描述。已经修改了题目。
|
m******0
发帖数: 222 | 7 这个办法不work，因为无法确定right pointer停止的位置。如果你扫到的distinct
char多于K，于是就停止，但如果你继续向右扫，distinct char可能就小于K了。
e.g.
ABB, K=1. in your method, when end points to index=1 it will stop, since
there are two distinct chars (A, B), but you should go on, since when you
have ABB, distinct char drops to one.
母。
【在 b********6 的大作中提到】
: 思路差不多，可以用array[queue]来解决，同样的O(n)
: queue里存对应字母的所有位置，substring用start和end来标定，end每进一位，就把
: 位置存到对应字母的queue里。如果最小重复的要求被打破，就把start进位，start每
: 进一位就把start经过的那个字母的queue里pop。直到有一个pop以后变成distinct字母。
: array的查找是O(1)，queue的push pop操作是O(1)，整个数组遍历下来，pop和push的
: 次数不超过string长度。用queue而不用多重array或vector是因为要可变数组和删头节
: 点。
|
b********6
发帖数: 35437 | 8 想错了，我的算法是at least有这么多distinct字母
我现在有个思路是先把string过一遍，保存每个字母的位置信息。整个string就被那些
只出现一次的字母分割成n < length的小区间。然后就把两头的区间砍掉，如何取舍砍
哪头，greedy algorithm不合适，我也没想出好办法，问题在于砍小区间的时候可能会
生成更多的distinct characters
【在 m******0 的大作中提到】
: 这个办法不work，因为无法确定right pointer停止的位置。如果你扫到的distinct
: char多于K，于是就停止，但如果你继续向右扫，distinct char可能就小于K了。
: e.g.
: ABB, K=1. in your method, when end points to index=1 it will stop, since
: there are two distinct chars (A, B), but you should go on, since when you
: have ABB, distinct char drops to one.
:
: 母。
|
m******0
发帖数: 222 | 9 at least的话，也不对，道理是一样的，随着right pointer移动，distinct字母数既
可能增加，也可能减少。传统two pointer方法失去了basis。
我的想法是：
设置两个pointers，p1
1. p1=0, p2 scan from 1 to len
2. p1=1, p2 scan from len to 2
以上两步，就能得到所有[0,i], [1,i] (1<=i<=len)范围内的distinct char的个数（
pointer每移动一次，可以O(1)时间得到distinct char的个数）
然后再令p1=2, 重复上面步骤，又得到[2,i], [3,i]的distinct char个数
依次下去，O(n^2)时间可以搜索到所有情况。
【在 b********6 的大作中提到】
: 想错了，我的算法是at least有这么多distinct字母
: 我现在有个思路是先把string过一遍，保存每个字母的位置信息。整个string就被那些
: 只出现一次的字母分割成n < length的小区间。然后就把两头的区间砍掉，如何取舍砍
: 哪头，greedy algorithm不合适，我也没想出好办法，问题在于砍小区间的时候可能会
: 生成更多的distinct characters
|
c****d
发帖数: 2418 | 10 abcdefgabcdefg k=1 return abcdefgabcdefg
是这个意思吧，感觉方法不容易想啊
number
【在 m******0 的大作中提到】
: 我之前的描述有问题，现在补充一下描述：
: define: a distinct character in returned string means the character's number
: of appearance equals one.
: Given a string, find the length of longest sub-string(s) which contain at
: most K distinct characters.
: for example,
: given string="AABBCC", K=1, return="AABBCC"
: given string="AAXBBYCCC", K=1, return="BBYCCC"
: 想了半天只想到了O(n^2)的解法。各位有更好的办法没
|
|
|
b********6
发帖数: 35437 | 11 at least是对的，你再想想
你的方法可以简化成
for i = 1 to n
scan to end，
找scan过程中的符合条件的最大string。
最后是O(n^2)
【在 m******0 的大作中提到】
: at least的话，也不对，道理是一样的，随着right pointer移动，distinct字母数既
: 可能增加，也可能减少。传统two pointer方法失去了basis。
: 我的想法是：
: 设置两个pointers，p1: 1. p1=0, p2 scan from 1 to len
: 2. p1=1, p2 scan from len to 2
: 以上两步，就能得到所有[0,i], [1,i] (1<=i<=len)范围内的distinct char的个数（
: pointer每移动一次，可以O(1)时间得到distinct char的个数）
: 然后再令p1=2, 重复上面步骤，又得到[2,i], [3,i]的distinct char个数
: 依次下去，O(n^2)时间可以搜索到所有情况。
|
c****d
发帖数: 2418 | 12 我觉得只能用递归吧
getsubstr(str,k)
{
num = number of distinct charactor in str
p = positions of distinct charactor in str
if num<=k
return str
else
str_1=str(1,p_{k+1}-1)
str_2=str(p_1+1,p_{k+2}-1)
...
str_m=str(p_{num-k-1}+1,end of str)
for all i
substr_i=getsubstr(str_i,k)
return substr_i with max length
}
number
【在 m******0 的大作中提到】
: 我之前的描述有问题，现在补充一下描述：
: define: a distinct character in returned string means the character's number
: of appearance equals one.
: Given a string, find the length of longest sub-string(s) which contain at
: most K distinct characters.
: for example,
: given string="AABBCC", K=1, return="AABBCC"
: given string="AAXBBYCCC", K=1, return="BBYCCC"
: 想了半天只想到了O(n^2)的解法。各位有更好的办法没
|
m******0
发帖数: 222 | 13 我仍然不觉得at least是对的，因为随着一个pointer增加，distinct char的数量可能
增加可能减少。你可以把你steps详细写出来，我帮你找一个反例
你后面summary没错，这样的确是简化了。
【在 b********6 的大作中提到】
: at least是对的，你再想想
: 你的方法可以简化成
: for i = 1 to n
: scan to end，
: 找scan过程中的符合条件的最大string。
: 最后是O(n^2)
|
b********6
发帖数: 35437 | 14 我又想了一下，at least也是不对的。我的那个解是假设先找到一个符合条件的
substring
【在 m******0 的大作中提到】
: 我仍然不觉得at least是对的，因为随着一个pointer增加，distinct char的数量可能
: 增加可能减少。你可以把你steps详细写出来，我帮你找一个反例
: 你后面summary没错，这样的确是简化了。
|
c****d
发帖数: 2418 | 15 再提一下，可以建立一个nxn的table储存每次substr的搜索结果
最原始的方法相当于找出table所有的值，递归的方法只需要找出很小一部分
at
【在 c****d 的大作中提到】
: 我觉得只能用递归吧
: getsubstr(str,k)
: {
: num = number of distinct charactor in str
: p = positions of distinct charactor in str
: if num<=k
: return str
: else
: str_1=str(1,p_{k+1}-1)
: str_2=str(p_1+1,p_{k+2}-1)
|
r******t
发帖数: 250 | 16 就用一个包含 k 个不同的 s li ding window 就好了 |
r******t
发帖数: 250 | 17 就用一个包含 k 个不同的 s li ding window 就好了 |
D***r
发帖数: 7511 | 18 我遇到了这道题。以前没刷题所以没看过解法。
我很快给出了O（N^2）解法，然后做出了一些小优化，但当场没完成O（N）解法。
后来面试人说可以给每个window一个character counter，窗口移动的时候update那个
counter，其实非常简单。
要是早点看网经就好了 |
l******t
发帖数: 238 | 19 想了半天，想不出o（n）的，和leetcode原题不同 |
c****l
发帖数: 1280 | 20 didn't get it. more details?
【在 D***r 的大作中提到】
: 我遇到了这道题。以前没刷题所以没看过解法。
: 我很快给出了O（N^2）解法，然后做出了一些小优化，但当场没完成O（N）解法。
: 后来面试人说可以给每个window一个character counter，窗口移动的时候update那个
: counter，其实非常简单。
: 要是早点看网经就好了
|
