由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - storm8 online code给跪了
相关主题
请教leetcode上的count and say问一下OJ的Anagrams那道题
一道用叶子过河题星期一福利:某公司店面题
发一道G家的onsite题及教训,顺便求linkedin和twitter内推Leetcode的Substring with Concatenation of All Words超时。
LRU cache 问题这题怎么做?
一道面试题a problem from leetcode: high efficiency algorithm for combinations problem
问个fb onsite题目combinations 有没有 iterative的方法阿 ?
Apple Siri 组 Java 测试题问个递归的问题
4sum o(n^2)超时求点评:电话面试(今天第二天没有消息回复,感觉可能挂了)
相关话题的讨论汇总
话题: int话题: string话题: integer话题: return话题: cur
进入JobHunting版参与讨论
1 (共1页)
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
2
上面的code是我在eclipse里面测试写的
l****i
发帖数: 2772
3
用Set?
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 判断就行了!

相关主题
问个fb onsite题目问一下OJ的Anagrams那道题
Apple Siri 组 Java 测试题星期一福利:某公司店面题
4sum o(n^2)超时Leetcode的Substring with Concatenation of All Words超时。
进入JobHunting版参与讨论
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
17
n的大小是多少呢?
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 判断就行了!

相关主题
这题怎么做?问个递归的问题
a problem from leetcode: high efficiency algorithm for combinations problem求点评:电话面试(今天第二天没有消息回复,感觉可能挂了)
combinations 有没有 iterative的方法阿 ?有人做过codility.com的题吗?
进入JobHunting版参与讨论
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很大,需要点数学知识
了。
相关主题
[求解]codility online test的cannon打炮问题一道用叶子过河题
关于leetcode 的strStr这题发一道G家的onsite题及教训,顺便求linkedin和twitter内推
请教leetcode上的count and sayLRU cache 问题
进入JobHunting版参与讨论
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

相关主题
LRU cache 问题Apple Siri 组 Java 测试题
一道面试题4sum o(n^2)超时
问个fb onsite题目问一下OJ的Anagrams那道题
进入JobHunting版参与讨论
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.

相关主题
星期一福利:某公司店面题a problem from leetcode: high efficiency algorithm for combinations problem
Leetcode的Substring with Concatenation of All Words超时。combinations 有没有 iterative的方法阿 ?
这题怎么做?问个递归的问题
进入JobHunting版参与讨论
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。

相关主题
求点评:电话面试(今天第二天没有消息回复,感觉可能挂了)关于leetcode 的strStr这题
有人做过codility.com的题吗?请教leetcode上的count and say
[求解]codility online test的cannon打炮问题一道用叶子过河题
进入JobHunting版参与讨论
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 的大作中提到】
: 看到大牛,服气了。
相关主题
一道用叶子过河题一道面试题
发一道G家的onsite题及教训,顺便求linkedin和twitter内推问个fb onsite题目
LRU cache 问题Apple Siri 组 Java 测试题
进入JobHunting版参与讨论
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 的大作中提到】
:
: 这题面到肯定跪了。

相关主题
4sum o(n^2)超时Leetcode的Substring with Concatenation of All Words超时。
问一下OJ的Anagrams那道题这题怎么做?
星期一福利:某公司店面题a problem from leetcode: high efficiency algorithm for combinations problem
进入JobHunting版参与讨论
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
84
3个test case是啥?
l********5
发帖数: 230
85
single letter
a*5
ab*1000

【在 s***y 的大作中提到】
: 3个test case是啥?
e***s
发帖数: 799
86
ab*1000 expect 1000?
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应该能过呀。

相关主题
combinations 有没有 iterative的方法阿 ?有人做过codility.com的题吗?
问个递归的问题[求解]codility online test的cannon打炮问题
求点评:电话面试(今天第二天没有消息回复,感觉可能挂了)关于leetcode 的strStr这题
进入JobHunting版参与讨论
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 的大作中提到】
: 二爷,能过
相关主题
请教leetcode上的count and sayLRU cache 问题
一道用叶子过河题一道面试题
发一道G家的onsite题及教训,顺便求linkedin和twitter内推问个fb onsite题目
进入JobHunting版参与讨论
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
110
用Set?
相关主题
问个fb onsite题目问一下OJ的Anagrams那道题
Apple Siri 组 Java 测试题星期一福利:某公司店面题
4sum o(n^2)超时Leetcode的Substring with Concatenation of All Words超时。
进入JobHunting版参与讨论
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啊
相关主题
这题怎么做?问个递归的问题
a problem from leetcode: high efficiency algorithm for combinations problem求点评:电话面试(今天第二天没有消息回复,感觉可能挂了)
combinations 有没有 iterative的方法阿 ?有人做过codility.com的题吗?
进入JobHunting版参与讨论
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
124
n的大小是多少呢?
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++;
: }

相关主题
[求解]codility online test的cannon打炮问题一道用叶子过河题
关于leetcode 的strStr这题发一道G家的onsite题及教训,顺便求linkedin和twitter内推
请教leetcode上的count and sayLRU cache 问题
进入JobHunting版参与讨论
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很大,需要点数学知识
: 了。

相关主题
LRU cache 问题Apple Siri 组 Java 测试题
一道面试题4sum o(n^2)超时
问个fb onsite题目问一下OJ的Anagrams那道题
进入JobHunting版参与讨论
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?

相关主题
星期一福利:某公司店面题a problem from leetcode: high efficiency algorithm for combinations problem
Leetcode的Substring with Concatenation of All Words超时。combinations 有没有 iterative的方法阿 ?
这题怎么做?问个递归的问题
进入JobHunting版参与讨论
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的那个题比这个难,最小周期只是其中一部分。
相关主题
求点评:电话面试(今天第二天没有消息回复,感觉可能挂了)关于leetcode 的strStr这题
有人做过codility.com的题吗?请教leetcode上的count and say
[求解]codility online test的cannon打炮问题一道用叶子过河题
进入JobHunting版参与讨论
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

相关主题
一道用叶子过河题一道面试题
发一道G家的onsite题及教训,顺便求linkedin和twitter内推问个fb onsite题目
LRU cache 问题Apple Siri 组 Java 测试题
进入JobHunting版参与讨论
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
相关主题
4sum o(n^2)超时Leetcode的Substring with Concatenation of All Words超时。
问一下OJ的Anagrams那道题这题怎么做?
星期一福利:某公司店面题a problem from leetcode: high efficiency algorithm for combinations problem
进入JobHunting版参与讨论
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
190
3个test case是啥?
相关主题
combinations 有没有 iterative的方法阿 ?有人做过codility.com的题吗?
问个递归的问题[求解]codility online test的cannon打炮问题
求点评:电话面试(今天第二天没有消息回复,感觉可能挂了)关于leetcode 的strStr这题
进入JobHunting版参与讨论
l********5
发帖数: 230
191
single letter
a*5
ab*1000

【在 s***y 的大作中提到】
: 3个test case是啥?
e***s
发帖数: 799
192
ab*1000 expect 1000?
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了。看了一下感觉还挺麻烦的。

相关主题
请教leetcode上的count and sayLRU cache 问题
一道用叶子过河题一道面试题
发一道G家的onsite题及教训,顺便求linkedin和twitter内推问个fb onsite题目
进入JobHunting版参与讨论
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 的大作中提到】
:
: 你的改进版的计算结果是多少?

相关主题
问个fb onsite题目问一下OJ的Anagrams那道题
Apple Siri 组 Java 测试题星期一福利:某公司店面题
4sum o(n^2)超时Leetcode的Substring with Concatenation of All Words超时。
进入JobHunting版参与讨论
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
213
mark
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)
1 (共1页)
进入JobHunting版参与讨论
相关主题
求点评:电话面试(今天第二天没有消息回复,感觉可能挂了)一道面试题
有人做过codility.com的题吗?问个fb onsite题目
[求解]codility online test的cannon打炮问题Apple Siri 组 Java 测试题
关于leetcode 的strStr这题4sum o(n^2)超时
请教leetcode上的count and say问一下OJ的Anagrams那道题
一道用叶子过河题星期一福利:某公司店面题
发一道G家的onsite题及教训,顺便求linkedin和twitter内推Leetcode的Substring with Concatenation of All Words超时。
LRU cache 问题这题怎么做?
相关话题的讨论汇总
话题: int话题: string话题: integer话题: return话题: cur