|
|
f*****e
发帖数: 2992 | 3 想想又好像是对的，caiwu的那个题比这个难，最小周期只是其中一部分。 |
|
|
c********t
发帖数: 5706 | 5 啥时候我被你提鞋成大牛了，感觉是这个意思。
public int count(char[] str) {
int n = str.length, count = 0;
for (int i = 1; i < n;) {
if (str[i] != str[0]) {
count = i;
i++;
} else {
for (int j = 0; i < n && j < i && str[i] == str[j]; j++)
i++;
}
}
return count;
} |
|
m*****1
发帖数: 147 | 6 我当时做这个test的方法跟你差不多，这样做过不了他的extreme large dataset的测
试，显示超时，然后我就跪了，后来我想到一个方法，不知道可行不可行，就是要组成
这个所谓的词组，必定是有特定substring重复出现，比如byebye是bye的重复两次，这
样，我想可不可以只找到当前string的长度，然后找到所有约数，也就是说约数长度的
substring重复n次才能构成当前string，比如abcdefgabcdefg，当前长度是14，重复
substring长度是7，这样，我们检查长度为2，7的substring就行了。这样快了很多 |
|
|
f*****e
发帖数: 2992 | 8 这题的证明outline如下:
1)假设前n个元素的最小周期为k， 加入新元素后的新的最小周期j不可能
前n个元素的最小周期为k矛盾。
2)假设前n个元素的最小周期为k， 加入新元素后的新的最小周期j不可能k
然A[0,...,j%k]也是前n个元素的重复串，但是长度
所以j只能是n+1。 |
|
p*****2
发帖数: 21240 | 9
这题你的greedy算法感觉是对的,我没有找到反例。但是我也在考虑怎么证明呢。感觉
这题的关键就是substr以后，可以从下一个开始了，前边的都可以抛弃掉了。 |
|
f*****e
发帖数: 2992 | 10 我说的就是文献的内容，我刚才凭记忆又证明了一遍，你可以在书上画画，从最简单的
case考察起，比如1.5个周期加一个不符合周期的元素。 |
|
b*****6
发帖数: 179 | 11 前些天我也看到这个题，顺手写了一下：思路是找到s.length()的所有prime factor，
然后看根据这个factor移位是不是满足题的条件，如果是，结果加length/factor - 1
public static int cyclic(String s)
{
int len = s.length();
if (len <= 1)
return 1;
int result = 1;
ArrayList factors = get_factors(len);
for (int fctr : factors)
{
if (valid_cyclic(s, fctr))
result += len / fctr - 1;
}
return result;
}
sta... 阅读全帖 |
|
b*****6
发帖数: 179 | 12 上面这个算法复杂度，假如输入字符串长度是N，O(N * (number of prime factors of
N))，数学上是不是等价于O（N）我就不知道了 |
|
|
f*****e
发帖数: 2992 | 14 周期为7，有7个？
aadaaad
adaaada
daaadaa
aaadaad
aadaada
adaadaa
daadaaa |
|
|
|
c***s
发帖数: 192 | 17 好像不对吧：
比如 ababa
i = 1, k = 2
i = 2, k = 2
i = 3, k = 2
i = 4, k = 2
但这里 k应该等于5 |
|
|
|
|
d**********x
发帖数: 4083 | 21 一般还是能想到 str+str 然后kmp或者hash的吧
利用周期性确实太巧妙了。 |
|
|
p******9
发帖数: 47 | 23 相当于找这个字符串的最小循环节的长度，求出kmp算法的next数组，假设字符串长度
为N，最小循环节的长度是 N - next[N] 同时要求 N % (N - next[N]) == 0 |
|
|
l****i
发帖数: 2772 | 25 byeby,这个K最后也是3？
但是按照题目，这个应该输出5吧.
byeby
yebyb
ebyby
bybye
ybyeb |
|
|
f*****e
发帖数: 2992 | 27 延长之后继续求周期也可以，只要周期不大于长度就行。复杂度还是O(N)，未经
验证，慎用:-)
byebybyeby
35
stop |
|
|
e******i
发帖数: 106 | 29 擦，真心跪了，我找了HR要了test的结果，各位大牛看看吧，貌似我题目理解错了？
extreme_single_letter
single letter
0.25 s. WRONG ANSWER got 0 expected 1
extreme_a5
a*5
0.24 s. WRONG ANSWER got 0 expected 5
medium1
ab*1000
0.31 s. WRONG ANSWER got 1 expected 1000
好可惜。。这个教训好深刻 |
|
|
l********5
发帖数: 230 | 31 。。。所以是求最小周期的重复次数？学名叫什么来着。 。。。。 |
|
|
l********5
发帖数: 230 | 33 single letter
a*5
ab*1000 |
|
|
p*****2
发帖数: 21240 | 35
能想到。不过online test不好写呀。hash那个，我不清楚怎么选mod。kmp我从来也没
写过。不知道能不能写对，通过test case呢。话说tc用到kmp的时候多不多呀？ |
|
|
p*****2
发帖数: 21240 | 37
这道题说了一定是O(n)吗？按照数据的规模，感觉nlogn应该能过呀。 |
|
m******s
发帖数: 165 | 38 好像最近只见过一道用kmp来dp的。。。srm 557 div 2 1000 |
|
p*****2
发帖数: 21240 | 39
多谢大牛。有时间得练练kmp了。看了一下感觉还挺麻烦的。 |
|
|
x********y
发帖数: 14 | 41 不重复的单词个数是 最小周期数。
然后每个不重复单词出现的次数是一样的。根据这两个推论，可以直接append
original str， 然后kmp查找最先出现的次数找到最小周期 |
|
H****s
发帖数: 247 | 42 对， 除非用rolling hash 或 KMP 否则就是O(N^2). 上个班的功夫怎么就这么多回帖
啦，慢慢看吧。 |
|
e******i
发帖数: 106 | 43
说了，我看了大case，我还是超时了几十毫秒的样子 |
|
|
p*****2
发帖数: 21240 | 45
要求是多少？2秒？你是用O(n)的解做的吗？ |
|
e******i
发帖数: 106 | 46
要求是1.04，我做了1.6.。。。sigh,总之是做错了 |
|
|
p*****2
发帖数: 21240 | 48
how about "aabaaaba"?
aabaaabaaabaaaba
abaaabaaabaaabaa
baaabaaabaaabaaa
aaabaaabaaabaaab
aabaaabaaabaaaba |
|
|
c********t
发帖数: 5706 | 50 这样行不？
public int count2(char[] str) {
int n = str.length, count = 1;
for (int i = 1; i < n;i++) {
if (str[i] != str[i-count]) {
count = i+1;
}
}
return count>n/2? n/2: count;
} |
|
