|
|
c********t
发帖数: 5706 | 3 嗯，还是不行，看来每个字母都要从头比较，还是要N^2算法才行。
KMP感觉在这道题不好用。 |
|
c********t
发帖数: 5706 | 4 现在看来，这个解法似乎最优。不过应该是所有factor,而不是所有prime factor吧。
all factor of a num 似乎是个sqrt(n)数量级。
1 |
|
c********t
发帖数: 5706 | 5 嗯，就是你这个算法，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.... 阅读全帖 |
|
|
|
e******i
发帖数: 106 | 8
不知道啊，以前做题都没有想过这个问题，而且不是说他们的问题对空间复杂度要求不
高么 |
|
j*****y
发帖数: 1071 | 9 为什么是返回7阿，这个unique的string没想明白 |
|
p*****2
发帖数: 21240 | 10 然后又举例，“byebye”，应当返回二
这个为什么是2？ |
|
H****s
发帖数: 247 | 11 这个题目 先将string 复制级联然后每次shift一位判断是否相等
如 "codility" --> "codilitycodility" 然后再跟原string 判断就行了！ |
|
M********5
发帖数: 715 | 12 好像原来的题目意思是这样子的，有一个string，如果string的length为len，那么可
以循环移位[0,len-1],如果循环移位后得到的string和原来的string一样，那么就
count++，因为循环移位为0的时候得到的string肯定是跟原来的string一样的，所以
count至少为1。。。反正我是这样理解的，不知道对不对？ |
|
p*****2
发帖数: 21240 | 13 是不是要用那个叫什么rolling hashing一类的东西来作了？ |
|
|
|
|
M********5
发帖数: 715 | 17 byebye移0和3得到的string和原来的string一样，所以是2吧，是这样理解的吧？ |
|
M********5
发帖数: 715 | 18 这个应该是空间时间都是O(n)的吧。。。我当时做的应该是空间是O(n^2)的，其实这题
就是这样一个trick |
|
|
|
|
e******i
发帖数: 106 | 22
当时我也想到了这个算法，有点类似cracking 上的一道题，后来觉得hashmap简单就没
有细想了 |
|
M********5
发帖数: 715 | 23 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 | 24
没看明白。每次shift一位之后怎么比较呢？ |
|
p*****2
发帖数: 21240 | 25
任何string，包括空数组，应当最少返回1.
这个怎么理解？ |
|
|
|
|
|
|
|
|
M********5
发帖数: 715 | 33 如果这个string是aaaaa，那space是不是O(n^2) |
|
p*****2
发帖数: 21240 | 34 我目前的想法就是rolling hashing了。如果N不大好些，如果N很大，需要点数学知识
了。 |
|
w****x
发帖数: 2483 | 35
同跪，今天给Zynga跪了， 最近跪的几家都是代码还来不及写就给据了，NND |
|
M********5
发帖数: 715 | 36 为什么这个时间不是O(n)，不是总共循环n次吗？ |
|
|
p*****2
发帖数: 21240 | 38
仔细看看。你这个是O(n^2)。这题哪里会那么简单呢。你仔细分析一下复杂度。 |
|
|
|
|
f*****e
发帖数: 2992 | 42 别吵了，求最小周期，n久之前，caiwu出过类似题，我给答案就是O(N)，我找找。 |
|
e******i
发帖数: 106 | 43
二爷，我现在想就两个问题，一个是用了hashmap.而是用了Java的substring导致空间
复杂度超标了， 这两个的JAVA原理我都没有深究，substring我一直按o(1)来考虑，会
不会是O(n)啊，那样的话，那我的时间复杂度也错了。。。 |
|
|
p*****2
发帖数: 21240 | 45
substring O(n)
这题rolling hash, 不过要选mod的话，我就没有经验了。不知道应该怎么选择好。
再有就是KMP。mshearts说的。 |
|
f*****e
发帖数: 2992 | 46 想到了，很简单，记前n个数的周期为k，当你碰到第n+1个数，不满足这个周期，该如何
update k？ |
|
d*********g
发帖数: 154 | 47
如何
不满足周期的话就说明前n+1个数不是周期的，应该暂设k=n+1吧，是这样么？ |
|
|
|
|
