p*****2 发帖数: 21240 | 1
如何
byebye
开始第一个b,周期1
第二个y, 怎么检查周期呢? |
|
f*****e 发帖数: 2992 | 2 b[i - k] != b[i], thus update k,具体怎么update的,我忘了,公式很简单,reaso
ning很tricky. |
|
|
|
|
f*****e 发帖数: 2992 | 6 想想又好像是对的,caiwu的那个题比这个难,最小周期只是其中一部分。 |
|
|
c********t 发帖数: 5706 | 8 啥时候我被你提鞋成大牛了,感觉是这个意思。
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 | 9 我当时做这个test的方法跟你差不多,这样做过不了他的extreme large dataset的测
试,显示超时,然后我就跪了,后来我想到一个方法,不知道可行不可行,就是要组成
这个所谓的词组,必定是有特定substring重复出现,比如byebye是bye的重复两次,这
样,我想可不可以只找到当前string的长度,然后找到所有约数,也就是说约数长度的
substring重复n次才能构成当前string,比如abcdefgabcdefg,当前长度是14,重复
substring长度是7,这样,我们检查长度为2,7的substring就行了。这样快了很多 |
|
|
f*****e 发帖数: 2992 | 11 这题的证明outline如下:
1)假设前n个元素的最小周期为k, 加入新元素后的新的最小周期j不可能
前n个元素的最小周期为k矛盾。
2)假设前n个元素的最小周期为k, 加入新元素后的新的最小周期j不可能k
然A[0,...,j%k]也是前n个元素的重复串,但是长度
所以j只能是n+1。 |
|
p*****2 发帖数: 21240 | 12
这题你的greedy算法感觉是对的,我没有找到反例。但是我也在考虑怎么证明呢。感觉
这题的关键就是substr以后,可以从下一个开始了,前边的都可以抛弃掉了。 |
|
f*****e 发帖数: 2992 | 13 我说的就是文献的内容,我刚才凭记忆又证明了一遍,你可以在书上画画,从最简单的
case考察起,比如1.5个周期加一个不符合周期的元素。 |
|
b*****6 发帖数: 179 | 14 前些天我也看到这个题,顺手写了一下:思路是找到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 | 15 上面这个算法复杂度,假如输入字符串长度是N,O(N * (number of prime factors of
N)),数学上是不是等价于O(N)我就不知道了 |
|
|
f*****e 发帖数: 2992 | 17 周期为7,有7个?
aadaaad
adaaada
daaadaa
aaadaad
aadaada
adaadaa
daadaaa |
|
|
|
c***s 发帖数: 192 | 20 好像不对吧:
比如 ababa
i = 1, k = 2
i = 2, k = 2
i = 3, k = 2
i = 4, k = 2
但这里 k应该等于5 |
|
|
|
|
d**********x 发帖数: 4083 | 24 一般还是能想到 str+str 然后kmp或者hash的吧
利用周期性确实太巧妙了。 |
|
|
p******9 发帖数: 47 | 26 相当于找这个字符串的最小循环节的长度,求出kmp算法的next数组,假设字符串长度
为N,最小循环节的长度是 N - next[N] 同时要求 N % (N - next[N]) == 0 |
|
|
l****i 发帖数: 2772 | 28 byeby,这个K最后也是3?
但是按照题目,这个应该输出5吧.
byeby
yebyb
ebyby
bybye
ybyeb |
|
|
f*****e 发帖数: 2992 | 30 延长之后继续求周期也可以,只要周期不大于长度就行。复杂度还是O(N),未经
验证,慎用:-)
byebybyeby
35
stop |
|
|
e******i 发帖数: 106 | 32 擦,真心跪了,我找了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 | 34 。。。所以是求最小周期的重复次数?学名叫什么来着。 。。。。 |
|
|
l********5 发帖数: 230 | 36 single letter
a*5
ab*1000 |
|
|
p*****2 发帖数: 21240 | 38
能想到。不过online test不好写呀。hash那个,我不清楚怎么选mod。kmp我从来也没
写过。不知道能不能写对,通过test case呢。话说tc用到kmp的时候多不多呀? |
|
|
p*****2 发帖数: 21240 | 40
这道题说了一定是O(n)吗?按照数据的规模,感觉nlogn应该能过呀。 |
|
p*****2 发帖数: 21240 | 41
多谢大牛。有时间得练练kmp了。看了一下感觉还挺麻烦的。 |
|
|
x********y 发帖数: 14 | 43 不重复的单词个数是 最小周期数。
然后每个不重复单词出现的次数是一样的。根据这两个推论,可以直接append
original str, 然后kmp查找最先出现的次数找到最小周期 |
|
H****s 发帖数: 247 | 44 对, 除非用rolling hash 或 KMP 否则就是O(N^2). 上个班的功夫怎么就这么多回帖
啦,慢慢看吧。 |
|
e******i 发帖数: 106 | 45
说了,我看了大case,我还是超时了几十毫秒的样子 |
|
|
p*****2 发帖数: 21240 | 47
要求是多少?2秒?你是用O(n)的解做的吗? |
|
e******i 发帖数: 106 | 48
要求是1.04,我做了1.6.。。。sigh,总之是做错了 |
|
|
p*****2 发帖数: 21240 | 50
how about "aabaaaba"?
aabaaabaaabaaaba
abaaabaaabaaabaa
baaabaaabaaabaaa
aaabaaabaaabaaab
aabaaabaaabaaaba |
|