e******i 发帖数: 106 | 1 昨天做了storm8 的online code,挂了。
题目变了,不再是以前说的find max sum path in one grid。
题目如下:
给定一个string,如 “codility”,每次向左循环一个char.
codility 0th;
odilityc 1st;
dilityco 2nd;
ilitycod 3rd;
....
codility 8th;
要求返回Unique 的string. 如上所示,应当返回 7.
然后又举例,“byebye”,应当返回二
任何string,包括空数组,应当最少返回1.
要求time complexity 和 space complexity 都为O(N).
我的code:
import java.util.HashMap;
public class Cyclic {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String s = "";
System.out.println(cyclic_automorphisms(s));
}
public static int cyclic_automorphisms ( String S ) {
int lens = S.length();
HashMap map = new HashMap();
if(lens < 1)
return 0;
for(int i = 0; i < lens; i++){
if(!map.containsKey(S)){
map.put(S,i);
}
S = shiftLeft(S);
}
return map.size()-1;
}
public static String shiftLeft(String s){
return s.substring(1)+s.charAt(0);
}
}
在eclipse里测试,没有问题,也通过了测试,但他说我这个不是最优解。
我当时第一反应就是用Hashmap做,从前也没有想过哈希表的空间复杂度问题。我想是
不是跪在这个地方了,求大神指点。
另外,求大神Refer. |
e******i 发帖数: 106 | |
l****i 发帖数: 2772 | |
e******i 发帖数: 106 | 4
不知道啊,以前做题都没有想过这个问题,而且不是说他们的问题对空间复杂度要求不
高么
【在 l****i 的大作中提到】 : 用Set?
|
j*****y 发帖数: 1071 | 5 为什么是返回7阿,这个unique的string没想明白
【在 e******i 的大作中提到】 : 昨天做了storm8 的online code,挂了。 : 题目变了,不再是以前说的find max sum path in one grid。 : 题目如下: : 给定一个string,如 “codility”,每次向左循环一个char. : codility 0th; : odilityc 1st; : dilityco 2nd; : ilitycod 3rd; : .... : codility 8th;
|
p*****2 发帖数: 21240 | 6 然后又举例,“byebye”,应当返回二
这个为什么是2? |
H****s 发帖数: 247 | 7 这个题目 先将string 复制级联然后每次shift一位判断是否相等
如 "codility" --> "codilitycodility" 然后再跟原string 判断就行了!
【在 e******i 的大作中提到】 : 昨天做了storm8 的online code,挂了。 : 题目变了,不再是以前说的find max sum path in one grid。 : 题目如下: : 给定一个string,如 “codility”,每次向左循环一个char. : codility 0th; : odilityc 1st; : dilityco 2nd; : ilitycod 3rd; : .... : codility 8th;
|
M********5 发帖数: 715 | 8 好像原来的题目意思是这样子的,有一个string,如果string的length为len,那么可
以循环移位[0,len-1],如果循环移位后得到的string和原来的string一样,那么就
count++,因为循环移位为0的时候得到的string肯定是跟原来的string一样的,所以
count至少为1。。。反正我是这样理解的,不知道对不对? |
p*****2 发帖数: 21240 | 9 是不是要用那个叫什么rolling hashing一类的东西来作了? |
M********5 发帖数: 715 | 10 嗯,我觉得这个是最优解。。。
【在 H****s 的大作中提到】 : 这个题目 先将string 复制级联然后每次shift一位判断是否相等 : 如 "codility" --> "codilitycodility" 然后再跟原string 判断就行了!
|
|
|
H****s 发帖数: 247 | 11 对啊, 应该是3啊
【在 p*****2 的大作中提到】 : 然后又举例,“byebye”,应当返回二 : 这个为什么是2?
|
p*****2 发帖数: 21240 | 12
这个是O(n)的吗?
【在 M********5 的大作中提到】 : 嗯,我觉得这个是最优解。。。
|
M********5 发帖数: 715 | 13 byebye移0和3得到的string和原来的string一样,所以是2吧,是这样理解的吧?
【在 H****s 的大作中提到】 : 对啊, 应该是3啊
|
M********5 发帖数: 715 | 14 这个应该是空间时间都是O(n)的吧。。。我当时做的应该是空间是O(n^2)的,其实这题
就是这样一个trick
【在 p*****2 的大作中提到】 : : 这个是O(n)的吗?
|
e******i 发帖数: 106 | 15
我觉得可能没有那么复杂
【在 p*****2 的大作中提到】 : 是不是要用那个叫什么rolling hashing一类的东西来作了?
|
e******i 发帖数: 106 | 16
因为从0开始排序啊,有3个,所以返回2
【在 p*****2 的大作中提到】 : 然后又举例,“byebye”,应当返回二 : 这个为什么是2?
|
p*****2 发帖数: 21240 | |
e******i 发帖数: 106 | 18
当时我也想到了这个算法,有点类似cracking 上的一道题,后来觉得hashmap简单就没
有细想了
【在 H****s 的大作中提到】 : 这个题目 先将string 复制级联然后每次shift一位判断是否相等 : 如 "codility" --> "codilitycodility" 然后再跟原string 判断就行了!
|
M********5 发帖数: 715 | 19 int CountString(std::string& str){
if( str.empty() )
return 0;
std::string shift_copy = str + str;
int count=0;
int len = str.length();
for(int i=0; i
if( shift_copy.substr(i,len) == str )
count++;
}
return count;
} |
p*****2 发帖数: 21240 | 20
没看明白。每次shift一位之后怎么比较呢?
【在 H****s 的大作中提到】 : 这个题目 先将string 复制级联然后每次shift一位判断是否相等 : 如 "codility" --> "codilitycodility" 然后再跟原string 判断就行了!
|
|
|
p*****2 发帖数: 21240 | 21
任何string,包括空数组,应当最少返回1.
这个怎么理解?
【在 e******i 的大作中提到】 : : 当时我也想到了这个算法,有点类似cracking 上的一道题,后来觉得hashmap简单就没 : 有细想了
|
M********5 发帖数: 715 | 22 我跟你理解的好像不一样,我理解错了?
【在 e******i 的大作中提到】 : : 当时我也想到了这个算法,有点类似cracking 上的一道题,后来觉得hashmap简单就没 : 有细想了
|
p*****2 发帖数: 21240 | 23
你这个不是O(n)的。
【在 M********5 的大作中提到】 : int CountString(std::string& str){ : if( str.empty() ) : return 0; : std::string shift_copy = str + str; : int count=0; : int len = str.length(); : for(int i=0; i: if( shift_copy.substr(i,len) == str ) : count++; : }
|
M********5 发帖数: 715 | 24 两倍的space还是算O(n)吧?
【在 p*****2 的大作中提到】 : : 你这个不是O(n)的。
|
e******i 发帖数: 106 | 25
【在 p*****2 的大作中提到】 : : 你这个不是O(n)的。
|
p*****2 发帖数: 21240 | 26
我是说时间。
【在 M********5 的大作中提到】 : 两倍的space还是算O(n)吧?
|
e******i 发帖数: 106 | 27
hashmap是o(n)么
你是说我写的么
【在 M********5 的大作中提到】 : 这个应该是空间时间都是O(n)的吧。。。我当时做的应该是空间是O(n^2)的,其实这题 : 就是这样一个trick
|
p*****2 发帖数: 21240 | 28
LZ说说N的范围是多少?
【在 e******i 的大作中提到】 : : hashmap是o(n)么 : 你是说我写的么
|
M********5 发帖数: 715 | 29 如果这个string是aaaaa,那space是不是O(n^2)
【在 e******i 的大作中提到】 : : hashmap是o(n)么 : 你是说我写的么
|
p*****2 发帖数: 21240 | 30 我目前的想法就是rolling hashing了。如果N不大好些,如果N很大,需要点数学知识
了。 |
|
|
w****x 发帖数: 2483 | 31
同跪,今天给Zynga跪了, 最近跪的几家都是代码还来不及写就给据了,NND
【在 e******i 的大作中提到】 : 昨天做了storm8 的online code,挂了。 : 题目变了,不再是以前说的find max sum path in one grid。 : 题目如下: : 给定一个string,如 “codility”,每次向左循环一个char. : codility 0th; : odilityc 1st; : dilityco 2nd; : ilitycod 3rd; : .... : codility 8th;
|
M********5 发帖数: 715 | 32 为什么这个时间不是O(n),不是总共循环n次吗?
【在 p*****2 的大作中提到】 : 我目前的想法就是rolling hashing了。如果N不大好些,如果N很大,需要点数学知识 : 了。
|
m******s 发帖数: 165 | 33 s匹配ss,KMP?
【在 e******i 的大作中提到】 : 昨天做了storm8 的online code,挂了。 : 题目变了,不再是以前说的find max sum path in one grid。 : 题目如下: : 给定一个string,如 “codility”,每次向左循环一个char. : codility 0th; : odilityc 1st; : dilityco 2nd; : ilitycod 3rd; : .... : codility 8th;
|
e******i 发帖数: 106 | 34 貌似是100000吧,我记不清了,反正挺大的
【在 p*****2 的大作中提到】 : 我目前的想法就是rolling hashing了。如果N不大好些,如果N很大,需要点数学知识 : 了。
|
p*****2 发帖数: 21240 | 35
仔细看看。你这个是O(n^2)。这题哪里会那么简单呢。你仔细分析一下复杂度。
【在 M********5 的大作中提到】 : 为什么这个时间不是O(n),不是总共循环n次吗?
|
p*****2 发帖数: 21240 | 36
这个也可以。
【在 m******s 的大作中提到】 : s匹配ss,KMP?
|
p*****2 发帖数: 21240 | 37
ZKSS
【在 w****x 的大作中提到】 : : 同跪,今天给Zynga跪了, 最近跪的几家都是代码还来不及写就给据了,NND
|
M********5 发帖数: 715 | 38 嗯,好像是这个数。。。
【在 e******i 的大作中提到】 : 貌似是100000吧,我记不清了,反正挺大的
|
f*****e 发帖数: 2992 | 39 别吵了,求最小周期,n久之前,caiwu出过类似题,我给答案就是O(N),我找找。
【在 e******i 的大作中提到】 : 昨天做了storm8 的online code,挂了。 : 题目变了,不再是以前说的find max sum path in one grid。 : 题目如下: : 给定一个string,如 “codility”,每次向左循环一个char. : codility 0th; : odilityc 1st; : dilityco 2nd; : ilitycod 3rd; : .... : codility 8th;
|
e******i 发帖数: 106 | 40
二爷,我现在想就两个问题,一个是用了hashmap.而是用了Java的substring导致空间
复杂度超标了, 这两个的JAVA原理我都没有深究,substring我一直按o(1)来考虑,会
不会是O(n)啊,那样的话,那我的时间复杂度也错了。。。
【在 p*****2 的大作中提到】 : : ZKSS
|
|
|
H****s 发帖数: 247 | 41 好像是,根据题目的例子应该是2
【在 e******i 的大作中提到】 : : 二爷,我现在想就两个问题,一个是用了hashmap.而是用了Java的substring导致空间 : 复杂度超标了, 这两个的JAVA原理我都没有深究,substring我一直按o(1)来考虑,会 : 不会是O(n)啊,那样的话,那我的时间复杂度也错了。。。
|
p*****2 发帖数: 21240 | 42
substring O(n)
这题rolling hash, 不过要选mod的话,我就没有经验了。不知道应该怎么选择好。
再有就是KMP。mshearts说的。
【在 e******i 的大作中提到】 : : 二爷,我现在想就两个问题,一个是用了hashmap.而是用了Java的substring导致空间 : 复杂度超标了, 这两个的JAVA原理我都没有深究,substring我一直按o(1)来考虑,会 : 不会是O(n)啊,那样的话,那我的时间复杂度也错了。。。
|
f*****e 发帖数: 2992 | 43 想到了,很简单,记前n个数的周期为k,当你碰到第n+1个数,不满足这个周期,该如何
update k?
【在 f*****e 的大作中提到】 : 别吵了,求最小周期,n久之前,caiwu出过类似题,我给答案就是O(N),我找找。
|
d*********g 发帖数: 154 | 44
如何
不满足周期的话就说明前n+1个数不是周期的,应该暂设k=n+1吧,是这样么?
【在 f*****e 的大作中提到】 : 想到了,很简单,记前n个数的周期为k,当你碰到第n+1个数,不满足这个周期,该如何 : update k?
|
c********t 发帖数: 5706 | 45 高!simple!
【在 f*****e 的大作中提到】 : 想到了,很简单,记前n个数的周期为k,当你碰到第n+1个数,不满足这个周期,该如何 : update k?
|
f*****e 发帖数: 2992 | 46 这个里面的reasoning相当有趣。
【在 d*********g 的大作中提到】 : : 如何 : 不满足周期的话就说明前n+1个数不是周期的,应该暂设k=n+1吧,是这样么?
|
f*****e 发帖数: 2992 | 47 好像不对。不过思路是对的。
【在 d*********g 的大作中提到】 : : 如何 : 不满足周期的话就说明前n+1个数不是周期的,应该暂设k=n+1吧,是这样么?
|
p*****2 发帖数: 21240 | 48
如何
byebye
开始第一个b,周期1
第二个y, 怎么检查周期呢?
【在 f*****e 的大作中提到】 : 想到了,很简单,记前n个数的周期为k,当你碰到第n+1个数,不满足这个周期,该如何 : update k?
|
f*****e 发帖数: 2992 | 49 b[i - k] != b[i], thus update k,具体怎么update的,我忘了,公式很简单,reaso
ning很tricky.
【在 p*****2 的大作中提到】 : : 如何 : byebye : 开始第一个b,周期1 : 第二个y, 怎么检查周期呢?
|
p*****2 发帖数: 21240 | 50
reaso
如果相等怎么办?
【在 f*****e 的大作中提到】 : b[i - k] != b[i], thus update k,具体怎么update的,我忘了,公式很简单,reaso : ning很tricky.
|
|
|
p*****2 发帖数: 21240 | 51
大牛看明白了,写个code练练?
【在 c********t 的大作中提到】 : 高!simple!
|
f*****e 发帖数: 2992 | 52 相等就下一个字符呗。
【在 p*****2 的大作中提到】 : : 大牛看明白了,写个code练练?
|
f*****e 发帖数: 2992 | 53 想想又好像是对的,caiwu的那个题比这个难,最小周期只是其中一部分。
【在 f*****e 的大作中提到】 : 相等就下一个字符呗。
|
p*****2 发帖数: 21240 | 54
没明白。能不能走个"byebye"的例子呢?
【在 f*****e 的大作中提到】 : 想想又好像是对的,caiwu的那个题比这个难,最小周期只是其中一部分。
|
f*****e 发帖数: 2992 | 55 update k=n+1是对的,数学证明真的很tricky。
A=byebye
A[0] == 'b', k = 1;
A[1] == 'y' != 'b' == A[1-k], update k = 2;
A[2] == 'e' != 'b' == A[2-k], update k = 3;
A[3] == 'b' == 'b' == A[3-k], continue
A[4] == 'y' == 'y' == A[4-k], continue
A[5] == 'e' == 'e' == A[5-k], continue
final k = 3,
there are 3 unique rotated sequences
pseudocode只有4行,4行code就可以搞定storm8的题目,不过这题太偏了。
int k=1;
for(int i = 1; i < A.size(); i++)
if(A[i] != A[i - k])
k = i + 1;
【在 p*****2 的大作中提到】 : : 没明白。能不能走个"byebye"的例子呢?
|
c********t 发帖数: 5706 | 56 啥时候我被你提鞋成大牛了,感觉是这个意思。
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;
}
【在 p*****2 的大作中提到】 : : 没明白。能不能走个"byebye"的例子呢?
|
m*****1 发帖数: 147 | 57 我当时做这个test的方法跟你差不多,这样做过不了他的extreme large dataset的测
试,显示超时,然后我就跪了,后来我想到一个方法,不知道可行不可行,就是要组成
这个所谓的词组,必定是有特定substring重复出现,比如byebye是bye的重复两次,这
样,我想可不可以只找到当前string的长度,然后找到所有约数,也就是说约数长度的
substring重复n次才能构成当前string,比如abcdefgabcdefg,当前长度是14,重复
substring长度是7,这样,我们检查长度为2,7的substring就行了。这样快了很多 |
c********t 发帖数: 5706 | 58 和大牛的一比,我的codes一把渣啊
【在 f*****e 的大作中提到】 : update k=n+1是对的,数学证明真的很tricky。 : A=byebye : A[0] == 'b', k = 1; : A[1] == 'y' != 'b' == A[1-k], update k = 2; : A[2] == 'e' != 'b' == A[2-k], update k = 3; : A[3] == 'b' == 'b' == A[3-k], continue : A[4] == 'y' == 'y' == A[4-k], continue : A[5] == 'e' == 'e' == A[5-k], continue : final k = 3, : there are 3 unique rotated sequences
|
f*****e 发帖数: 2992 | 59 这题的证明outline如下:
1)假设前n个元素的最小周期为k, 加入新元素后的新的最小周期j不可能
前n个元素的最小周期为k矛盾。
2)假设前n个元素的最小周期为k, 加入新元素后的新的最小周期j不可能k
然A[0,...,j%k]也是前n个元素的重复串,但是长度
所以j只能是n+1。
【在 f*****e 的大作中提到】 : update k=n+1是对的,数学证明真的很tricky。 : A=byebye : A[0] == 'b', k = 1; : A[1] == 'y' != 'b' == A[1-k], update k = 2; : A[2] == 'e' != 'b' == A[2-k], update k = 3; : A[3] == 'b' == 'b' == A[3-k], continue : A[4] == 'y' == 'y' == A[4-k], continue : A[5] == 'e' == 'e' == A[5-k], continue : final k = 3, : there are 3 unique rotated sequences
|
p*****2 发帖数: 21240 | 60
这题你的greedy算法感觉是对的,我没有找到反例。但是我也在考虑怎么证明呢。感觉
这题的关键就是substr以后,可以从下一个开始了,前边的都可以抛弃掉了。
【在 f*****e 的大作中提到】 : 这题的证明outline如下: : 1)假设前n个元素的最小周期为k, 加入新元素后的新的最小周期j不可能: 前n个元素的最小周期为k矛盾。 : 2)假设前n个元素的最小周期为k, 加入新元素后的新的最小周期j不可能k: 然A[0,...,j%k]也是前n个元素的重复串,但是长度: 所以j只能是n+1。
|
|
|
f*****e 发帖数: 2992 | 61 我说的就是文献的内容,我刚才凭记忆又证明了一遍,你可以在书上画画,从最简单的
case考察起,比如1.5个周期加一个不符合周期的元素。
【在 p*****2 的大作中提到】 : : 这题你的greedy算法感觉是对的,我没有找到反例。但是我也在考虑怎么证明呢。感觉 : 这题的关键就是substr以后,可以从下一个开始了,前边的都可以抛弃掉了。
|
b*****6 发帖数: 179 | 62 前些天我也看到这个题,顺手写了一下:思路是找到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;
}
static boolean valid_cyclic(String s, int v) {
for (int i = 0, j = v; i < s.length(); i++, j++) {
if (j == s.length())
j = 0;
if (s.charAt(i) != s.charAt(j))
return false;
}
return true;
}
// find all prime factors plus one
static ArrayList get_factors(int val) {
ArrayList result = new ArrayList();
result.add(1);
int cur = 2;
do {
if (val % cur == 0)
{
result.add(cur);
do {
val /= cur;
} while (val % cur == 0);
}
cur++;
} while (cur <= val);
return result;
} |
b*****6 发帖数: 179 | 63 上面这个算法复杂度,假如输入字符串长度是N,O(N * (number of prime factors of
N)),数学上是不是等价于O(N)我就不知道了 |
p*****2 发帖数: 21240 | 64
这个例子能过吗?"aadaaad"?
【在 f*****e 的大作中提到】 : update k=n+1是对的,数学证明真的很tricky。 : A=byebye : A[0] == 'b', k = 1; : A[1] == 'y' != 'b' == A[1-k], update k = 2; : A[2] == 'e' != 'b' == A[2-k], update k = 3; : A[3] == 'b' == 'b' == A[3-k], continue : A[4] == 'y' == 'y' == A[4-k], continue : A[5] == 'e' == 'e' == A[5-k], continue : final k = 3, : there are 3 unique rotated sequences
|
f*****e 发帖数: 2992 | 65 周期为7,有7个?
aadaaad
adaaada
daaadaa
aaadaad
aadaada
adaadaa
daadaaa
【在 p*****2 的大作中提到】 : : 这个例子能过吗?"aadaaad"?
|
l****i 发帖数: 2772 | 66 看到大牛,服气了。
【在 f*****e 的大作中提到】 : update k=n+1是对的,数学证明真的很tricky。 : A=byebye : A[0] == 'b', k = 1; : A[1] == 'y' != 'b' == A[1-k], update k = 2; : A[2] == 'e' != 'b' == A[2-k], update k = 3; : A[3] == 'b' == 'b' == A[3-k], continue : A[4] == 'y' == 'y' == A[4-k], continue : A[5] == 'e' == 'e' == A[5-k], continue : final k = 3, : there are 3 unique rotated sequences
|
p*****2 发帖数: 21240 | 67
不过意思。我看错了。
【在 f*****e 的大作中提到】 : 周期为7,有7个? : aadaaad : adaaada : daaadaa : aaadaad : aadaada : adaadaa : daadaaa
|
c***s 发帖数: 192 | 68 好像不对吧:
比如 ababa
i = 1, k = 2
i = 2, k = 2
i = 3, k = 2
i = 4, k = 2
但这里 k应该等于5
【在 f*****e 的大作中提到】 : update k=n+1是对的,数学证明真的很tricky。 : A=byebye : A[0] == 'b', k = 1; : A[1] == 'y' != 'b' == A[1-k], update k = 2; : A[2] == 'e' != 'b' == A[2-k], update k = 3; : A[3] == 'b' == 'b' == A[3-k], continue : A[4] == 'y' == 'y' == A[4-k], continue : A[5] == 'e' == 'e' == A[5-k], continue : final k = 3, : there are 3 unique rotated sequences
|
p*****2 发帖数: 21240 | 69
str+str 找到长度为n的match
【在 c***s 的大作中提到】 : 好像不对吧: : 比如 ababa : i = 1, k = 2 : i = 2, k = 2 : i = 3, k = 2 : i = 4, k = 2 : 但这里 k应该等于5
|
p*****2 发帖数: 21240 | 70
这题面到肯定跪了。
【在 l****i 的大作中提到】 : 看到大牛,服气了。
|
|
|
f*****e 发帖数: 2992 | 71 没有违反周期性啊。A[i-k]!=A[i]
【在 c***s 的大作中提到】 : 好像不对吧: : 比如 ababa : i = 1, k = 2 : i = 2, k = 2 : i = 3, k = 2 : i = 4, k = 2 : 但这里 k应该等于5
|
d**********x 发帖数: 4083 | 72 一般还是能想到 str+str 然后kmp或者hash的吧
利用周期性确实太巧妙了。
【在 p*****2 的大作中提到】 : : 这题面到肯定跪了。
|
c***s 发帖数: 192 | 73 但这个周期是5吧。
难道我看错题目了?
【在 f*****e 的大作中提到】 : 没有违反周期性啊。A[i-k]!=A[i]
|
p******9 发帖数: 47 | 74 相当于找这个字符串的最小循环节的长度,求出kmp算法的next数组,假设字符串长度
为N,最小循环节的长度是 N - next[N] 同时要求 N % (N - next[N]) == 0 |
l****i 发帖数: 2772 | 75 storm8刚给我发了online test的link.......
【在 p*****2 的大作中提到】 : : 这题面到肯定跪了。
|
c********t 发帖数: 5706 | 76 还真有点问题
ababa+ababa
【在 p*****2 的大作中提到】 : : 这题面到肯定跪了。
|
l****i 发帖数: 2772 | 77 byeby,这个K最后也是3?
但是按照题目,这个应该输出5吧.
byeby
yebyb
ebyby
bybye
ybyeb
【在 f*****e 的大作中提到】 : update k=n+1是对的,数学证明真的很tricky。 : A=byebye : A[0] == 'b', k = 1; : A[1] == 'y' != 'b' == A[1-k], update k = 2; : A[2] == 'e' != 'b' == A[2-k], update k = 3; : A[3] == 'b' == 'b' == A[3-k], continue : A[4] == 'y' == 'y' == A[4-k], continue : A[5] == 'e' == 'e' == A[5-k], continue : final k = 3, : there are 3 unique rotated sequences
|
f*****e 发帖数: 2992 | 78 还真是,想想再怎么改改。
【在 l****i 的大作中提到】 : byeby,这个K最后也是3? : 但是按照题目,这个应该输出5吧. : byeby : yebyb : ebyby : bybye : ybyeb
|
f*****e 发帖数: 2992 | 79 延长之后继续求周期也可以,只要周期不大于长度就行。复杂度还是O(N),未经
验证,慎用:-)
byebybyeby
35
stop
【在 f*****e 的大作中提到】 : 还真是,想想再怎么改改。
|
e***s 发帖数: 799 | 80 二爷,能过
【在 p*****2 的大作中提到】 : : 这题面到肯定跪了。
|
|
|
e******i 发帖数: 106 | 81 擦,真心跪了,我找了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****i 发帖数: 2772 | 82 没看懂...是哪3个test cases?
【在 e******i 的大作中提到】 : 擦,真心跪了,我找了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 | 83 。。。所以是求最小周期的重复次数?学名叫什么来着。 。。。。
【在 e******i 的大作中提到】 : 擦,真心跪了,我找了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
|
s***y 发帖数: 203 | |
l********5 发帖数: 230 | 85 single letter
a*5
ab*1000
【在 s***y 的大作中提到】 : 3个test case是啥?
|
e***s 发帖数: 799 | |
p*****2 发帖数: 21240 | 87
能想到。不过online test不好写呀。hash那个,我不清楚怎么选mod。kmp我从来也没
写过。不知道能不能写对,通过test case呢。话说tc用到kmp的时候多不多呀?
【在 d**********x 的大作中提到】 : 一般还是能想到 str+str 然后kmp或者hash的吧 : 利用周期性确实太巧妙了。
|
p*****2 发帖数: 21240 | 88
不是一个题呀。
【在 e******i 的大作中提到】 : 擦,真心跪了,我找了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
|
p*****2 发帖数: 21240 | 89
这道题说了一定是O(n)吗?按照数据的规模,感觉nlogn应该能过呀。
【在 e******i 的大作中提到】 : 擦,真心跪了,我找了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
|
m******s 发帖数: 165 | 90 好像最近只见过一道用kmp来dp的。。。srm 557 div 2 1000
【在 p*****2 的大作中提到】 : : 这道题说了一定是O(n)吗?按照数据的规模,感觉nlogn应该能过呀。
|
|
|
p*****2 发帖数: 21240 | 91
多谢大牛。有时间得练练kmp了。看了一下感觉还挺麻烦的。
【在 m******s 的大作中提到】 : 好像最近只见过一道用kmp来dp的。。。srm 557 div 2 1000
|
w********p 发帖数: 948 | 92 赞
【在 H****s 的大作中提到】 : 这个题目 先将string 复制级联然后每次shift一位判断是否相等 : 如 "codility" --> "codilitycodility" 然后再跟原string 判断就行了!
|
x********y 发帖数: 14 | 93 不重复的单词个数是 最小周期数。
然后每个不重复单词出现的次数是一样的。根据这两个推论,可以直接append
original str, 然后kmp查找最先出现的次数找到最小周期 |
H****s 发帖数: 247 | 94 对, 除非用rolling hash 或 KMP 否则就是O(N^2). 上个班的功夫怎么就这么多回帖
啦,慢慢看吧。
【在 p*****2 的大作中提到】 : : 多谢大牛。有时间得练练kmp了。看了一下感觉还挺麻烦的。
|
e******i 发帖数: 106 | 95
说了,我看了大case,我还是超时了几十毫秒的样子
【在 p*****2 的大作中提到】 : : 多谢大牛。有时间得练练kmp了。看了一下感觉还挺麻烦的。
|
e******i 发帖数: 106 | 96
【在 H****s 的大作中提到】 : 对, 除非用rolling hash 或 KMP 否则就是O(N^2). 上个班的功夫怎么就这么多回帖 : 啦,慢慢看吧。
|
p*****2 发帖数: 21240 | 97
要求是多少?2秒?你是用O(n)的解做的吗?
【在 e******i 的大作中提到】
|
e******i 发帖数: 106 | 98
要求是1.04,我做了1.6.。。。sigh,总之是做错了
【在 p*****2 的大作中提到】 : : 要求是多少?2秒?你是用O(n)的解做的吗?
|
g****y 发帖数: 240 | 99 为啥ab×1000是1000?不应该是2吗?
【在 e******i 的大作中提到】 : : 要求是1.04,我做了1.6.。。。sigh,总之是做错了
|
p*****2 发帖数: 21240 | 100
how about "aabaaaba"?
aabaaabaaabaaaba
abaaabaaabaaabaa
baaabaaabaaabaaa
aaabaaabaaabaaab
aabaaabaaabaaaba
【在 e***s 的大作中提到】 : 二爷,能过
|
|
|
p*****2 发帖数: 21240 | 101
你的复杂度是多少?
【在 e******i 的大作中提到】 : : 要求是1.04,我做了1.6.。。。sigh,总之是做错了
|
c********t 发帖数: 5706 | 102 这样行不?
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;
}
【在 f*****e 的大作中提到】 : 还真是,想想再怎么改改。
|
c********t 发帖数: 5706 | 103 看看的改进版,在楼上。
【在 p*****2 的大作中提到】 : : 你的复杂度是多少?
|
p*****2 发帖数: 21240 | 104
你的改进版的计算结果是多少?
【在 c********t 的大作中提到】 : 看看的改进版,在楼上。
|
c********t 发帖数: 5706 | 105 嗯,还是不行,看来每个字母都要从头比较,还是要N^2算法才行。
KMP感觉在这道题不好用。
【在 p*****2 的大作中提到】 : : 你的改进版的计算结果是多少?
|
c********t 发帖数: 5706 | 106 现在看来,这个解法似乎最优。不过应该是所有factor,而不是所有prime factor吧。
all factor of a num 似乎是个sqrt(n)数量级。
1
【在 b*****6 的大作中提到】 : 前些天我也看到这个题,顺手写了一下:思路是找到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;
|
c********t 发帖数: 5706 | 107 嗯,就是你这个算法,O(n*sqrt(n)),改了改ben5736的codes 不知过不过的了大case;
public static int cyclic(String s) {
int len = s.length();
if (len <= 1)
return 1;
ArrayList factors = get_factors(len);
for (int i = factors.size() - 1; i >= 0; i--) {
int fctr = factors.get(i);
if (valid_cyclic(s, fctr))
return fctr;
}
return len;
}
static boolean valid_cyclic(String s, int v) {
for (int i = 0, j = v; i < s.length(); i++, j++) {
if (j == s.length())
j = 0;
if (s.charAt(i) != s.charAt(j))
return false;
}
return true;
}
static ArrayList get_factors(int val) {
ArrayList result = new ArrayList();
result.add(1);
int cur = 2;
do {
if (val % cur == 0) {
result.add(cur);
}
cur++;
} while (cur <= val / 2);
return result;
}
【在 m*****1 的大作中提到】 : 我当时做这个test的方法跟你差不多,这样做过不了他的extreme large dataset的测 : 试,显示超时,然后我就跪了,后来我想到一个方法,不知道可行不可行,就是要组成 : 这个所谓的词组,必定是有特定substring重复出现,比如byebye是bye的重复两次,这 : 样,我想可不可以只找到当前string的长度,然后找到所有约数,也就是说约数长度的 : substring重复n次才能构成当前string,比如abcdefgabcdefg,当前长度是14,重复 : substring长度是7,这样,我们检查长度为2,7的substring就行了。这样快了很多
|
e******i 发帖数: 106 | 108 昨天做了storm8 的online code,挂了。
题目变了,不再是以前说的find max sum path in one grid。
题目如下:
给定一个string,如 “codility”,每次向左循环一个char.
codility 0th;
odilityc 1st;
dilityco 2nd;
ilitycod 3rd;
....
codility 8th;
要求返回Unique 的string. 如上所示,应当返回 7.
然后又举例,“byebye”,应当返回二
任何string,包括空数组,应当最少返回1.
要求time complexity 和 space complexity 都为O(N).
我的code:
import java.util.HashMap;
public class Cyclic {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String s = "";
System.out.println(cyclic_automorphisms(s));
}
public static int cyclic_automorphisms ( String S ) {
int lens = S.length();
HashMap map = new HashMap();
if(lens < 1)
return 0;
for(int i = 0; i < lens; i++){
if(!map.containsKey(S)){
map.put(S,i);
}
S = shiftLeft(S);
}
return map.size()-1;
}
public static String shiftLeft(String s){
return s.substring(1)+s.charAt(0);
}
}
在eclipse里测试,没有问题,也通过了测试,但他说我这个不是最优解。
我当时第一反应就是用Hashmap做,从前也没有想过哈希表的空间复杂度问题。我想是
不是跪在这个地方了,求大神指点。
另外,求大神Refer. |
e******i 发帖数: 106 | 109 上面的code是我在eclipse里面测试写的 |
l****i 发帖数: 2772 | |
|
|
e******i 发帖数: 106 | 111
不知道啊,以前做题都没有想过这个问题,而且不是说他们的问题对空间复杂度要求不
高么
【在 l****i 的大作中提到】 : 用Set?
|
j*****y 发帖数: 1071 | 112 为什么是返回7阿,这个unique的string没想明白
【在 e******i 的大作中提到】 : 昨天做了storm8 的online code,挂了。 : 题目变了,不再是以前说的find max sum path in one grid。 : 题目如下: : 给定一个string,如 “codility”,每次向左循环一个char. : codility 0th; : odilityc 1st; : dilityco 2nd; : ilitycod 3rd; : .... : codility 8th;
|
p*****2 发帖数: 21240 | 113 然后又举例,“byebye”,应当返回二
这个为什么是2? |
H****s 发帖数: 247 | 114 这个题目 先将string 复制级联然后每次shift一位判断是否相等
如 "codility" --> "codilitycodility" 然后再跟原string 判断就行了!
【在 e******i 的大作中提到】 : 昨天做了storm8 的online code,挂了。 : 题目变了,不再是以前说的find max sum path in one grid。 : 题目如下: : 给定一个string,如 “codility”,每次向左循环一个char. : codility 0th; : odilityc 1st; : dilityco 2nd; : ilitycod 3rd; : .... : codility 8th;
|
M********5 发帖数: 715 | 115 好像原来的题目意思是这样子的,有一个string,如果string的length为len,那么可
以循环移位[0,len-1],如果循环移位后得到的string和原来的string一样,那么就
count++,因为循环移位为0的时候得到的string肯定是跟原来的string一样的,所以
count至少为1。。。反正我是这样理解的,不知道对不对? |
p*****2 发帖数: 21240 | 116 是不是要用那个叫什么rolling hashing一类的东西来作了? |
M********5 发帖数: 715 | 117 嗯,我觉得这个是最优解。。。
【在 H****s 的大作中提到】 : 这个题目 先将string 复制级联然后每次shift一位判断是否相等 : 如 "codility" --> "codilitycodility" 然后再跟原string 判断就行了!
|
H****s 发帖数: 247 | 118 对啊, 应该是3啊
【在 p*****2 的大作中提到】 : 然后又举例,“byebye”,应当返回二 : 这个为什么是2?
|
p*****2 发帖数: 21240 | 119
这个是O(n)的吗?
【在 M********5 的大作中提到】 : 嗯,我觉得这个是最优解。。。
|
M********5 发帖数: 715 | 120 byebye移0和3得到的string和原来的string一样,所以是2吧,是这样理解的吧?
【在 H****s 的大作中提到】 : 对啊, 应该是3啊
|
|
|
M********5 发帖数: 715 | 121 这个应该是空间时间都是O(n)的吧。。。我当时做的应该是空间是O(n^2)的,其实这题
就是这样一个trick
【在 p*****2 的大作中提到】 : : 这个是O(n)的吗?
|
e******i 发帖数: 106 | 122
我觉得可能没有那么复杂
【在 p*****2 的大作中提到】 : 是不是要用那个叫什么rolling hashing一类的东西来作了?
|
e******i 发帖数: 106 | 123
因为从0开始排序啊,有3个,所以返回2
【在 p*****2 的大作中提到】 : 然后又举例,“byebye”,应当返回二 : 这个为什么是2?
|
p*****2 发帖数: 21240 | |
e******i 发帖数: 106 | 125
当时我也想到了这个算法,有点类似cracking 上的一道题,后来觉得hashmap简单就没
有细想了
【在 H****s 的大作中提到】 : 这个题目 先将string 复制级联然后每次shift一位判断是否相等 : 如 "codility" --> "codilitycodility" 然后再跟原string 判断就行了!
|
M********5 发帖数: 715 | 126 int CountString(std::string& str){
if( str.empty() )
return 0;
std::string shift_copy = str + str;
int count=0;
int len = str.length();
for(int i=0; i
if( shift_copy.substr(i,len) == str )
count++;
}
return count;
} |
p*****2 发帖数: 21240 | 127
没看明白。每次shift一位之后怎么比较呢?
【在 H****s 的大作中提到】 : 这个题目 先将string 复制级联然后每次shift一位判断是否相等 : 如 "codility" --> "codilitycodility" 然后再跟原string 判断就行了!
|
p*****2 发帖数: 21240 | 128
任何string,包括空数组,应当最少返回1.
这个怎么理解?
【在 e******i 的大作中提到】 : : 当时我也想到了这个算法,有点类似cracking 上的一道题,后来觉得hashmap简单就没 : 有细想了
|
M********5 发帖数: 715 | 129 我跟你理解的好像不一样,我理解错了?
【在 e******i 的大作中提到】 : : 当时我也想到了这个算法,有点类似cracking 上的一道题,后来觉得hashmap简单就没 : 有细想了
|
p*****2 发帖数: 21240 | 130
你这个不是O(n)的。
【在 M********5 的大作中提到】 : int CountString(std::string& str){ : if( str.empty() ) : return 0; : std::string shift_copy = str + str; : int count=0; : int len = str.length(); : for(int i=0; i: if( shift_copy.substr(i,len) == str ) : count++; : }
|
|
|
M********5 发帖数: 715 | 131 两倍的space还是算O(n)吧?
【在 p*****2 的大作中提到】 : : 你这个不是O(n)的。
|
e******i 发帖数: 106 | 132
【在 p*****2 的大作中提到】 : : 你这个不是O(n)的。
|
p*****2 发帖数: 21240 | 133
我是说时间。
【在 M********5 的大作中提到】 : 两倍的space还是算O(n)吧?
|
e******i 发帖数: 106 | 134
hashmap是o(n)么
你是说我写的么
【在 M********5 的大作中提到】 : 这个应该是空间时间都是O(n)的吧。。。我当时做的应该是空间是O(n^2)的,其实这题 : 就是这样一个trick
|
p*****2 发帖数: 21240 | 135
LZ说说N的范围是多少?
【在 e******i 的大作中提到】 : : hashmap是o(n)么 : 你是说我写的么
|
M********5 发帖数: 715 | 136 如果这个string是aaaaa,那space是不是O(n^2)
【在 e******i 的大作中提到】 : : hashmap是o(n)么 : 你是说我写的么
|
p*****2 发帖数: 21240 | 137 我目前的想法就是rolling hashing了。如果N不大好些,如果N很大,需要点数学知识
了。 |
w****x 发帖数: 2483 | 138
同跪,今天给Zynga跪了, 最近跪的几家都是代码还来不及写就给据了,NND
【在 e******i 的大作中提到】 : 昨天做了storm8 的online code,挂了。 : 题目变了,不再是以前说的find max sum path in one grid。 : 题目如下: : 给定一个string,如 “codility”,每次向左循环一个char. : codility 0th; : odilityc 1st; : dilityco 2nd; : ilitycod 3rd; : .... : codility 8th;
|
M********5 发帖数: 715 | 139 为什么这个时间不是O(n),不是总共循环n次吗?
【在 p*****2 的大作中提到】 : 我目前的想法就是rolling hashing了。如果N不大好些,如果N很大,需要点数学知识 : 了。
|
e******i 发帖数: 106 | 140 貌似是100000吧,我记不清了,反正挺大的
【在 p*****2 的大作中提到】 : 我目前的想法就是rolling hashing了。如果N不大好些,如果N很大,需要点数学知识 : 了。
|
|
|
p*****2 发帖数: 21240 | 141
仔细看看。你这个是O(n^2)。这题哪里会那么简单呢。你仔细分析一下复杂度。
【在 M********5 的大作中提到】 : 为什么这个时间不是O(n),不是总共循环n次吗?
|
p*****2 发帖数: 21240 | 142
这个也可以。
【在 m******s 的大作中提到】 : s匹配ss,KMP?
|
p*****2 发帖数: 21240 | 143
ZKSS
【在 w****x 的大作中提到】 : : 同跪,今天给Zynga跪了, 最近跪的几家都是代码还来不及写就给据了,NND
|
M********5 发帖数: 715 | 144 嗯,好像是这个数。。。
【在 e******i 的大作中提到】 : 貌似是100000吧,我记不清了,反正挺大的
|
f*****e 发帖数: 2992 | 145 别吵了,求最小周期,n久之前,caiwu出过类似题,我给答案就是O(N),我找找。
【在 e******i 的大作中提到】 : 昨天做了storm8 的online code,挂了。 : 题目变了,不再是以前说的find max sum path in one grid。 : 题目如下: : 给定一个string,如 “codility”,每次向左循环一个char. : codility 0th; : odilityc 1st; : dilityco 2nd; : ilitycod 3rd; : .... : codility 8th;
|
e******i 发帖数: 106 | 146
二爷,我现在想就两个问题,一个是用了hashmap.而是用了Java的substring导致空间
复杂度超标了, 这两个的JAVA原理我都没有深究,substring我一直按o(1)来考虑,会
不会是O(n)啊,那样的话,那我的时间复杂度也错了。。。
【在 p*****2 的大作中提到】 : : ZKSS
|
H****s 发帖数: 247 | 147 好像是,根据题目的例子应该是2
【在 e******i 的大作中提到】 : : 二爷,我现在想就两个问题,一个是用了hashmap.而是用了Java的substring导致空间 : 复杂度超标了, 这两个的JAVA原理我都没有深究,substring我一直按o(1)来考虑,会 : 不会是O(n)啊,那样的话,那我的时间复杂度也错了。。。
|
p*****2 发帖数: 21240 | 148
substring O(n)
这题rolling hash, 不过要选mod的话,我就没有经验了。不知道应该怎么选择好。
再有就是KMP。mshearts说的。
【在 e******i 的大作中提到】 : : 二爷,我现在想就两个问题,一个是用了hashmap.而是用了Java的substring导致空间 : 复杂度超标了, 这两个的JAVA原理我都没有深究,substring我一直按o(1)来考虑,会 : 不会是O(n)啊,那样的话,那我的时间复杂度也错了。。。
|
f*****e 发帖数: 2992 | 149 想到了,很简单,记前n个数的周期为k,当你碰到第n+1个数,不满足这个周期,该如何
update k?
【在 f*****e 的大作中提到】 : 别吵了,求最小周期,n久之前,caiwu出过类似题,我给答案就是O(N),我找找。
|
d*********g 发帖数: 154 | 150
如何
不满足周期的话就说明前n+1个数不是周期的,应该暂设k=n+1吧,是这样么?
【在 f*****e 的大作中提到】 : 想到了,很简单,记前n个数的周期为k,当你碰到第n+1个数,不满足这个周期,该如何 : update k?
|
|
|
c********t 发帖数: 5706 | 151 高!simple!
【在 f*****e 的大作中提到】 : 想到了,很简单,记前n个数的周期为k,当你碰到第n+1个数,不满足这个周期,该如何 : update k?
|
f*****e 发帖数: 2992 | 152 这个里面的reasoning相当有趣。
【在 d*********g 的大作中提到】 : : 如何 : 不满足周期的话就说明前n+1个数不是周期的,应该暂设k=n+1吧,是这样么?
|
f*****e 发帖数: 2992 | 153 好像不对。不过思路是对的。
【在 d*********g 的大作中提到】 : : 如何 : 不满足周期的话就说明前n+1个数不是周期的,应该暂设k=n+1吧,是这样么?
|
p*****2 发帖数: 21240 | 154
如何
byebye
开始第一个b,周期1
第二个y, 怎么检查周期呢?
【在 f*****e 的大作中提到】 : 想到了,很简单,记前n个数的周期为k,当你碰到第n+1个数,不满足这个周期,该如何 : update k?
|
f*****e 发帖数: 2992 | 155 b[i - k] != b[i], thus update k,具体怎么update的,我忘了,公式很简单,reaso
ning很tricky.
【在 p*****2 的大作中提到】 : : 如何 : byebye : 开始第一个b,周期1 : 第二个y, 怎么检查周期呢?
|
p*****2 发帖数: 21240 | 156
reaso
如果相等怎么办?
【在 f*****e 的大作中提到】 : b[i - k] != b[i], thus update k,具体怎么update的,我忘了,公式很简单,reaso : ning很tricky.
|
p*****2 发帖数: 21240 | 157
大牛看明白了,写个code练练?
【在 c********t 的大作中提到】 : 高!simple!
|
f*****e 发帖数: 2992 | 158 相等就下一个字符呗。
【在 p*****2 的大作中提到】 : : 大牛看明白了,写个code练练?
|
f*****e 发帖数: 2992 | 159 想想又好像是对的,caiwu的那个题比这个难,最小周期只是其中一部分。
【在 f*****e 的大作中提到】 : 相等就下一个字符呗。
|
p*****2 发帖数: 21240 | 160
没明白。能不能走个"byebye"的例子呢?
【在 f*****e 的大作中提到】 : 想想又好像是对的,caiwu的那个题比这个难,最小周期只是其中一部分。
|
|
|
f*****e 发帖数: 2992 | 161 update k=n+1是对的,数学证明真的很tricky。
A=byebye
A[0] == 'b', k = 1;
A[1] == 'y' != 'b' == A[1-k], update k = 2;
A[2] == 'e' != 'b' == A[2-k], update k = 3;
A[3] == 'b' == 'b' == A[3-k], continue
A[4] == 'y' == 'y' == A[4-k], continue
A[5] == 'e' == 'e' == A[5-k], continue
final k = 3,
there are 3 unique rotated sequences
pseudocode只有4行,4行code就可以搞定storm8的题目,不过这题太偏了。
int k=1;
for(int i = 1; i < A.size(); i++)
if(A[i] != A[i - k])
k = i + 1;
【在 p*****2 的大作中提到】 : : 没明白。能不能走个"byebye"的例子呢?
|
c********t 发帖数: 5706 | 162 啥时候我被你提鞋成大牛了,感觉是这个意思。
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;
}
【在 p*****2 的大作中提到】 : : 没明白。能不能走个"byebye"的例子呢?
|
m*****1 发帖数: 147 | 163 我当时做这个test的方法跟你差不多,这样做过不了他的extreme large dataset的测
试,显示超时,然后我就跪了,后来我想到一个方法,不知道可行不可行,就是要组成
这个所谓的词组,必定是有特定substring重复出现,比如byebye是bye的重复两次,这
样,我想可不可以只找到当前string的长度,然后找到所有约数,也就是说约数长度的
substring重复n次才能构成当前string,比如abcdefgabcdefg,当前长度是14,重复
substring长度是7,这样,我们检查长度为2,7的substring就行了。这样快了很多 |
c********t 发帖数: 5706 | 164 和大牛的一比,我的codes一把渣啊
【在 f*****e 的大作中提到】 : update k=n+1是对的,数学证明真的很tricky。 : A=byebye : A[0] == 'b', k = 1; : A[1] == 'y' != 'b' == A[1-k], update k = 2; : A[2] == 'e' != 'b' == A[2-k], update k = 3; : A[3] == 'b' == 'b' == A[3-k], continue : A[4] == 'y' == 'y' == A[4-k], continue : A[5] == 'e' == 'e' == A[5-k], continue : final k = 3, : there are 3 unique rotated sequences
|
f*****e 发帖数: 2992 | 165 这题的证明outline如下:
1)假设前n个元素的最小周期为k, 加入新元素后的新的最小周期j不可能
前n个元素的最小周期为k矛盾。
2)假设前n个元素的最小周期为k, 加入新元素后的新的最小周期j不可能k
然A[0,...,j%k]也是前n个元素的重复串,但是长度
所以j只能是n+1。
【在 f*****e 的大作中提到】 : update k=n+1是对的,数学证明真的很tricky。 : A=byebye : A[0] == 'b', k = 1; : A[1] == 'y' != 'b' == A[1-k], update k = 2; : A[2] == 'e' != 'b' == A[2-k], update k = 3; : A[3] == 'b' == 'b' == A[3-k], continue : A[4] == 'y' == 'y' == A[4-k], continue : A[5] == 'e' == 'e' == A[5-k], continue : final k = 3, : there are 3 unique rotated sequences
|
p*****2 发帖数: 21240 | 166
这题你的greedy算法感觉是对的,我没有找到反例。但是我也在考虑怎么证明呢。感觉
这题的关键就是substr以后,可以从下一个开始了,前边的都可以抛弃掉了。
【在 f*****e 的大作中提到】 : 这题的证明outline如下: : 1)假设前n个元素的最小周期为k, 加入新元素后的新的最小周期j不可能: 前n个元素的最小周期为k矛盾。 : 2)假设前n个元素的最小周期为k, 加入新元素后的新的最小周期j不可能k: 然A[0,...,j%k]也是前n个元素的重复串,但是长度: 所以j只能是n+1。
|
f*****e 发帖数: 2992 | 167 我说的就是文献的内容,我刚才凭记忆又证明了一遍,你可以在书上画画,从最简单的
case考察起,比如1.5个周期加一个不符合周期的元素。
【在 p*****2 的大作中提到】 : : 这题你的greedy算法感觉是对的,我没有找到反例。但是我也在考虑怎么证明呢。感觉 : 这题的关键就是substr以后,可以从下一个开始了,前边的都可以抛弃掉了。
|
b*****6 发帖数: 179 | 168 前些天我也看到这个题,顺手写了一下:思路是找到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;
}
static boolean valid_cyclic(String s, int v) {
for (int i = 0, j = v; i < s.length(); i++, j++) {
if (j == s.length())
j = 0;
if (s.charAt(i) != s.charAt(j))
return false;
}
return true;
}
// find all prime factors plus one
static ArrayList get_factors(int val) {
ArrayList result = new ArrayList();
result.add(1);
int cur = 2;
do {
if (val % cur == 0)
{
result.add(cur);
do {
val /= cur;
} while (val % cur == 0);
}
cur++;
} while (cur <= val);
return result;
} |
b*****6 发帖数: 179 | 169 上面这个算法复杂度,假如输入字符串长度是N,O(N * (number of prime factors of
N)),数学上是不是等价于O(N)我就不知道了 |
p*****2 发帖数: 21240 | 170
这个例子能过吗?"aadaaad"?
【在 f*****e 的大作中提到】 : update k=n+1是对的,数学证明真的很tricky。 : A=byebye : A[0] == 'b', k = 1; : A[1] == 'y' != 'b' == A[1-k], update k = 2; : A[2] == 'e' != 'b' == A[2-k], update k = 3; : A[3] == 'b' == 'b' == A[3-k], continue : A[4] == 'y' == 'y' == A[4-k], continue : A[5] == 'e' == 'e' == A[5-k], continue : final k = 3, : there are 3 unique rotated sequences
|
|
|
f*****e 发帖数: 2992 | 171 周期为7,有7个?
aadaaad
adaaada
daaadaa
aaadaad
aadaada
adaadaa
daadaaa
【在 p*****2 的大作中提到】 : : 这个例子能过吗?"aadaaad"?
|
l****i 发帖数: 2772 | 172 看到大牛,服气了。
【在 f*****e 的大作中提到】 : update k=n+1是对的,数学证明真的很tricky。 : A=byebye : A[0] == 'b', k = 1; : A[1] == 'y' != 'b' == A[1-k], update k = 2; : A[2] == 'e' != 'b' == A[2-k], update k = 3; : A[3] == 'b' == 'b' == A[3-k], continue : A[4] == 'y' == 'y' == A[4-k], continue : A[5] == 'e' == 'e' == A[5-k], continue : final k = 3, : there are 3 unique rotated sequences
|
p*****2 发帖数: 21240 | 173
不过意思。我看错了。
【在 f*****e 的大作中提到】 : 周期为7,有7个? : aadaaad : adaaada : daaadaa : aaadaad : aadaada : adaadaa : daadaaa
|
c***s 发帖数: 192 | 174 好像不对吧:
比如 ababa
i = 1, k = 2
i = 2, k = 2
i = 3, k = 2
i = 4, k = 2
但这里 k应该等于5
【在 f*****e 的大作中提到】 : update k=n+1是对的,数学证明真的很tricky。 : A=byebye : A[0] == 'b', k = 1; : A[1] == 'y' != 'b' == A[1-k], update k = 2; : A[2] == 'e' != 'b' == A[2-k], update k = 3; : A[3] == 'b' == 'b' == A[3-k], continue : A[4] == 'y' == 'y' == A[4-k], continue : A[5] == 'e' == 'e' == A[5-k], continue : final k = 3, : there are 3 unique rotated sequences
|
p*****2 发帖数: 21240 | 175
str+str 找到长度为n的match
【在 c***s 的大作中提到】 : 好像不对吧: : 比如 ababa : i = 1, k = 2 : i = 2, k = 2 : i = 3, k = 2 : i = 4, k = 2 : 但这里 k应该等于5
|
p*****2 发帖数: 21240 | 176
这题面到肯定跪了。
【在 l****i 的大作中提到】 : 看到大牛,服气了。
|
f*****e 发帖数: 2992 | 177 没有违反周期性啊。A[i-k]!=A[i]
【在 c***s 的大作中提到】 : 好像不对吧: : 比如 ababa : i = 1, k = 2 : i = 2, k = 2 : i = 3, k = 2 : i = 4, k = 2 : 但这里 k应该等于5
|
d**********x 发帖数: 4083 | 178 一般还是能想到 str+str 然后kmp或者hash的吧
利用周期性确实太巧妙了。
【在 p*****2 的大作中提到】 : : 这题面到肯定跪了。
|
c***s 发帖数: 192 | 179 但这个周期是5吧。
难道我看错题目了?
【在 f*****e 的大作中提到】 : 没有违反周期性啊。A[i-k]!=A[i]
|
p******9 发帖数: 47 | 180 相当于找这个字符串的最小循环节的长度,求出kmp算法的next数组,假设字符串长度
为N,最小循环节的长度是 N - next[N] 同时要求 N % (N - next[N]) == 0 |
|
|
l****i 发帖数: 2772 | 181 storm8刚给我发了online test的link.......
【在 p*****2 的大作中提到】 : : 这题面到肯定跪了。
|
c********t 发帖数: 5706 | 182 还真有点问题
ababa+ababa
【在 p*****2 的大作中提到】 : : 这题面到肯定跪了。
|
l****i 发帖数: 2772 | 183 byeby,这个K最后也是3?
但是按照题目,这个应该输出5吧.
byeby
yebyb
ebyby
bybye
ybyeb
【在 f*****e 的大作中提到】 : update k=n+1是对的,数学证明真的很tricky。 : A=byebye : A[0] == 'b', k = 1; : A[1] == 'y' != 'b' == A[1-k], update k = 2; : A[2] == 'e' != 'b' == A[2-k], update k = 3; : A[3] == 'b' == 'b' == A[3-k], continue : A[4] == 'y' == 'y' == A[4-k], continue : A[5] == 'e' == 'e' == A[5-k], continue : final k = 3, : there are 3 unique rotated sequences
|
f*****e 发帖数: 2992 | 184 还真是,想想再怎么改改。
【在 l****i 的大作中提到】 : byeby,这个K最后也是3? : 但是按照题目,这个应该输出5吧. : byeby : yebyb : ebyby : bybye : ybyeb
|
f*****e 发帖数: 2992 | 185 延长之后继续求周期也可以,只要周期不大于长度就行。复杂度还是O(N),未经
验证,慎用:-)
byebybyeby
35
stop
【在 f*****e 的大作中提到】 : 还真是,想想再怎么改改。
|
e***s 发帖数: 799 | 186 二爷,能过
【在 p*****2 的大作中提到】 : : 这题面到肯定跪了。
|
e******i 发帖数: 106 | 187 擦,真心跪了,我找了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****i 发帖数: 2772 | 188 没看懂...是哪3个test cases?
【在 e******i 的大作中提到】 : 擦,真心跪了,我找了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 | 189 。。。所以是求最小周期的重复次数?学名叫什么来着。 。。。。
【在 e******i 的大作中提到】 : 擦,真心跪了,我找了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
|
s***y 发帖数: 203 | |
|
|
l********5 发帖数: 230 | 191 single letter
a*5
ab*1000
【在 s***y 的大作中提到】 : 3个test case是啥?
|
e***s 发帖数: 799 | |
p*****2 发帖数: 21240 | 193
能想到。不过online test不好写呀。hash那个,我不清楚怎么选mod。kmp我从来也没
写过。不知道能不能写对,通过test case呢。话说tc用到kmp的时候多不多呀?
【在 d**********x 的大作中提到】 : 一般还是能想到 str+str 然后kmp或者hash的吧 : 利用周期性确实太巧妙了。
|
p*****2 发帖数: 21240 | 194
不是一个题呀。
【在 e******i 的大作中提到】 : 擦,真心跪了,我找了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
|
p*****2 发帖数: 21240 | 195
这道题说了一定是O(n)吗?按照数据的规模,感觉nlogn应该能过呀。
【在 e******i 的大作中提到】 : 擦,真心跪了,我找了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
|
p*****2 发帖数: 21240 | 196
多谢大牛。有时间得练练kmp了。看了一下感觉还挺麻烦的。
【在 m******s 的大作中提到】 : 好像最近只见过一道用kmp来dp的。。。srm 557 div 2 1000
|
w********p 发帖数: 948 | 197 赞
【在 H****s 的大作中提到】 : 这个题目 先将string 复制级联然后每次shift一位判断是否相等 : 如 "codility" --> "codilitycodility" 然后再跟原string 判断就行了!
|
x********y 发帖数: 14 | 198 不重复的单词个数是 最小周期数。
然后每个不重复单词出现的次数是一样的。根据这两个推论,可以直接append
original str, 然后kmp查找最先出现的次数找到最小周期 |
H****s 发帖数: 247 | 199 对, 除非用rolling hash 或 KMP 否则就是O(N^2). 上个班的功夫怎么就这么多回帖
啦,慢慢看吧。
【在 p*****2 的大作中提到】 : : 多谢大牛。有时间得练练kmp了。看了一下感觉还挺麻烦的。
|
e******i 发帖数: 106 | 200
说了,我看了大case,我还是超时了几十毫秒的样子
【在 p*****2 的大作中提到】 : : 多谢大牛。有时间得练练kmp了。看了一下感觉还挺麻烦的。
|
|
|
e******i 发帖数: 106 | 201
【在 H****s 的大作中提到】 : 对, 除非用rolling hash 或 KMP 否则就是O(N^2). 上个班的功夫怎么就这么多回帖 : 啦,慢慢看吧。
|
p*****2 发帖数: 21240 | 202
要求是多少?2秒?你是用O(n)的解做的吗?
【在 e******i 的大作中提到】
|
e******i 发帖数: 106 | 203
要求是1.04,我做了1.6.。。。sigh,总之是做错了
【在 p*****2 的大作中提到】 : : 要求是多少?2秒?你是用O(n)的解做的吗?
|
g****y 发帖数: 240 | 204 为啥ab×1000是1000?不应该是2吗?
【在 e******i 的大作中提到】 : : 要求是1.04,我做了1.6.。。。sigh,总之是做错了
|
p*****2 发帖数: 21240 | 205
how about "aabaaaba"?
aabaaabaaabaaaba
abaaabaaabaaabaa
baaabaaabaaabaaa
aaabaaabaaabaaab
aabaaabaaabaaaba
【在 e***s 的大作中提到】 : 二爷,能过
|
p*****2 发帖数: 21240 | 206
你的复杂度是多少?
【在 e******i 的大作中提到】 : : 要求是1.04,我做了1.6.。。。sigh,总之是做错了
|
c********t 发帖数: 5706 | 207 这样行不?
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;
}
【在 f*****e 的大作中提到】 : 还真是,想想再怎么改改。
|
c********t 发帖数: 5706 | 208 看看的改进版,在楼上。
【在 p*****2 的大作中提到】 : : 你的复杂度是多少?
|
p*****2 发帖数: 21240 | 209
你的改进版的计算结果是多少?
【在 c********t 的大作中提到】 : 看看的改进版,在楼上。
|
c********t 发帖数: 5706 | 210 嗯,还是不行,看来每个字母都要从头比较,还是要N^2算法才行。
KMP感觉在这道题不好用。
【在 p*****2 的大作中提到】 : : 你的改进版的计算结果是多少?
|
|
|
c********t 发帖数: 5706 | 211 现在看来,这个解法似乎最优。不过应该是所有factor,而不是所有prime factor吧。
all factor of a num 似乎是个sqrt(n)数量级。
1
【在 b*****6 的大作中提到】 : 前些天我也看到这个题,顺手写了一下:思路是找到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;
|
c********t 发帖数: 5706 | 212 嗯,就是你这个算法,O(n*sqrt(n)),改了改ben5736的codes 不知过不过的了大case;
public static int cyclic(String s) {
int len = s.length();
if (len <= 1)
return 1;
ArrayList factors = get_factors(len);
for (int i = factors.size() - 1; i >= 0; i--) {
int fctr = factors.get(i);
if (valid_cyclic(s, fctr))
return fctr;
}
return len;
}
static boolean valid_cyclic(String s, int v) {
for (int i = 0, j = v; i < s.length(); i++, j++) {
if (j == s.length())
j = 0;
if (s.charAt(i) != s.charAt(j))
return false;
}
return true;
}
static ArrayList get_factors(int val) {
ArrayList result = new ArrayList();
result.add(1);
int cur = 2;
do {
if (val % cur == 0) {
result.add(cur);
}
cur++;
} while (cur <= val / 2);
return result;
}
【在 m*****1 的大作中提到】 : 我当时做这个test的方法跟你差不多,这样做过不了他的extreme large dataset的测 : 试,显示超时,然后我就跪了,后来我想到一个方法,不知道可行不可行,就是要组成 : 这个所谓的词组,必定是有特定substring重复出现,比如byebye是bye的重复两次,这 : 样,我想可不可以只找到当前string的长度,然后找到所有约数,也就是说约数长度的 : substring重复n次才能构成当前string,比如abcdefgabcdefg,当前长度是14,重复 : substring长度是7,这样,我们检查长度为2,7的substring就行了。这样快了很多
|
h****p 发帖数: 87 | |
s******s 发帖数: 63 | 214 根据楼上的某个版本写的 大概1秒可以run ~1,000,000 长度的输入
import sys
def prime_factors(n):
pf={}
prime = 2
while n>=prime:
if n%prime == 0:
pf[prime] = 1
n = n/prime
while n%prime==0:
n = n/prime
pf[prime] = pf[prime]+1
prime = prime + 1
return pf
def main(s):
n = len(s)
sl = set(s)
if n <= 1 or n==len(sl):
return 1
pf = prime_factors(n)
print(pf)
multiplier = 1
for factor in pf:
while pf[factor]>0:
divide = 1
for i in range(factor-1):
if s[int(i*n/factor):int((i+1)*n/factor)] != s[int((i+1)*n/factor):
int((i+2)*n/factor)]:
divide = 0
if divide == 1:
multiplier = multiplier*factor
s = s[0:int(n/factor)]
n = n/factor
pf[factor] = pf[factor]-1
else:
pf[factor]=0
return multiplier
t0 = time.clock()
main(s)
print(str(time.clock()-t0))
if __name__ == '__main__':
output = main(sys.argv[1])
print(output) |