|
c********t
发帖数: 5706 | 2 这样行不？
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;
} |
|
|
|
c********t
发帖数: 5706 | 5 嗯，还是不行，看来每个字母都要从头比较，还是要N^2算法才行。
KMP感觉在这道题不好用。 |
|
c********t
发帖数: 5706 | 6 现在看来，这个解法似乎最优。不过应该是所有factor,而不是所有prime factor吧。
all factor of a num 似乎是个sqrt(n)数量级。
1 |
|
c********t
发帖数: 5706 | 7 嗯，就是你这个算法，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.... 阅读全帖 |
|
|
s******s
发帖数: 63 | 9 根据楼上的某个版本写的 大概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(f... 阅读全帖 |
|
p*****2
发帖数: 21240 | 10 擦，真心跪了，我找了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
好可惜。。这个教训好深刻
O(n)的解法。 |
|
l****i
发帖数: 2772 | 11 二爷，我告诉你吧，这个题不是之前帖子里那个意思！我今早做了，一激动提交了，结
果后悔了，忘了考虑worst case的复杂度。估计要跪了。 |
|
l****i
发帖数: 2772 | 12 正确题意:
按照string长度N，一共有N种shift.当i shift （0=
叫做cyclic automorphism。要求return一共有多少cyclic automorphism。
byebye 0 shift counter = 1
yebyeb 1 shift
ebyeby 2 shift
byebye 3 shift counter = 2
yebyeb 4 shift
ebyeby 5 shift
return counter;
可以用KMP去比较（s+s,s）。结果我早上傻了，用KMP把所有的s在s+s里找了一遍。。
。。提交了才发现，我跪了。其实只要找到第一个出现的重复出现的S的位置就够了。
比如byebye，第一次重复在位置3,用s的length去除第一次位置，就是结果。
所有a*5,其实是aaaaa，应该结果是5！ |
|
p*****2
发帖数: 21240 | 13
对。我这个帖子的题意就是这个意思。原帖的问题是错的。LZ纠正了，可是没人看了。 |
|
p*****2
发帖数: 21240 | 14
看来还是得搞KMP呀。我这个周末得好好学学。 |
|
c********t
发帖数: 5706 | 15 算出周期，length再一除，不也一样？
如何算周期，看我那个另外一个帖子的最后回帖。
KMP不是 O(n), 把所有length都试一遍，不还是O(n^2)? |
|
l****i
发帖数: 2772 | 16 在S1里找到S2的第一次出现，用KMP是O(n) |
|
p*****2
发帖数: 21240 | 17
你那个帖子的回帖不是O(n)吧？KMP为什么不是O(n)? |
|
c********t
发帖数: 5706 | 18 KMP搜s是O(n), 问题是这道题，你难道不要试 从length 1到n/2的所有substring吗？ |
|
l****i
发帖数: 2772 | 19 用KMP其实也是找到你所说的周期，然后用length去除。 |
|
c********t
发帖数: 5706 | 20 对啊，所以还是O(n^2), 因为你要从1试到n/2看有没有周期啊，难道还有别的trick? |
|
l****i
发帖数: 2772 | 21 为什么O(n^2)？KMP去找，是O（n）啊。 |
|
e******i
发帖数: 106 | 22 原帖楼主表示第一次做这种Online test 不看清题目狠丢人，教训狠深刻，吃亏狠深 |
|
|
c********t
发帖数: 5706 | 24 我也有点懵了。
给你一个string abaaabaa
你拿什么去kmp找周期？难道不是要拿a, ab, aba, abaa去找吗？O(n*n)啊 |
|
l****i
发帖数: 2772 | 25 我的意思是，比如这题输入是"abab"
KMP("abababab","abab")，从index位置1开始找，可以找到index位置2，发现找到了。
这样KMP找到index是2.这个2就是你所说的周期吧。 |
|
|
p****e
发帖数: 3548 | 27 这个问题，简化一下就是求一个矩阵的秩
矩阵是字符串的数值 |
|
p*****2
发帖数: 21240 | 28 找到这题的出处了。还没看太懂。
A typical problem seen quite often is: given a string find its shortest
substring, such that the concatenation of one or more copies of it results
in the original string. Again the problem can be reduced to the properties
of the failure function. Let's consider the string
A B A B A B
and all its proper suffix/prefixes in descending order:
1 A B A B
2 A B
3 /the empty string/
Every such suffix/prefix uniquely defines a string, which after being "
inserted" in front of the given su... 阅读全帖 |
|
p*****2
发帖数: 21240 | 29
大牛。我刚才做了一个KMP，没发现比BF快呀。 |
|
|
|
|
|
|
p*****2
发帖数: 21240 | 35 算了，自己动手丰衣足食，写了一个
def maxsub(s:String):Int={
val n=s.length
val dp=new Array[Int](n)
for(i<-1 until n){
var j=i
while(j>0 && s(i)!=s(dp(j-1))) j=dp(j-1)
dp(i)=if(j>0) dp(j-1)+1 else 0
}
var j=dp(n-1)
while(n%(n-j)!=0) j=dp(j-1)
n/(n-j)
} |
|
|
|
p*****2
发帖数: 21240 | 38
原帖是我转的。不过这题我碰到也完了，因为从来没写过KMP。 |
|
p*****2
发帖数: 21240 | 39
那OJ咋办呢？比如storm8那个题，用KMP不快的话，BF过不了，KMP也不一定能过呀。 |
|
c**s
发帖数: 159 | 40 twitter
ms
rocket fuel
pocket gems
AthinkingApe
storm8 不确定。。。
quora |
|
j*******e
发帖数: 1058 | 41 最近拿了他家的offer。背景cs专业20学校，美国名校硕士，也就是那种做了几个
project的半路出家的和尚。本科EE的。
帮别人问的。
另外他家在湾区什么档次？比paypal，ebay好么？比fb google差多少档次？比storm8
，pocket gems之类。谢谢 |
|
|
l******i
发帖数: 880 | 43 根本不能和google,fb相提并论
当然也比不上ebay, paypal
storm8 |
|
|
j*****y
发帖数: 1071 | 45 确实用 kmp简单，和那个 storm8 的题目一样
pattern = S
source = S + S
找 pattern 在 source中的位置，如果某个 位置 i 使得 i 整除 |S|, 那么就
return
true, 否则 return false |
|
p*****2
发帖数: 21240 | 46 今天晚上练练这些题。storm8那个这么做可以吗？
int twoStack(int n){
int[][] dp=new int[n+1][n+1];
Arrays.fill(dp[0],1);
for(int i=1;i<=n;i++)
for(int j=0;j<=n-i;j++){
dp[i][j]=dp[i-1][j+1];
if(j>0)
dp[i][j]+=dp[i][j-1];
}
return dp[n][0];
} |
|
p*****2
发帖数: 21240 | 47 今天晚上练练这些题。storm8那个这么做可以吗？
int twoStack(int n){
int[][] dp=new int[n+1][n+1];
Arrays.fill(dp[0],1);
for(int i=1;i<=n;i++)
for(int j=0;j<=n-i;j++){
dp[i][j]=dp[i-1][j+1];
if(j>0)
dp[i][j]+=dp[i][j-1];
}
return dp[n][0];
} |
|
x*********w
发帖数: 533 | 48 这种公司还没见有人报过offer吧，
什么pocket gem, 啥storm8的 |
|
A**u
发帖数: 2458 | 49 lol
storm8好像也是，以前蛮简单，现在好难
you |
|
l****i
发帖数: 2772 | 50 昨天发了A家onsite杯具的面经，几位同胞建议我要总结一下面试的技巧。我就一次把6
个杯具都简单总结一下，包括一些面筋，也希望版上的大牛指点一下。
基本个人背景，US CS fresh PhD,国内3年国企IT部门经验，国内的工作基本就是天天
写SQL。1月初才是投简历，至今，10+个电面，拿到6个onsite，已全部杯具。
Onsite 1：
某电脑公司美国做cloud的分支。电面一轮，拿到onsite。onsite面了有5轮，有3轮
都很顺。感觉悲剧有2轮，如下：
1.2 国女，拿着一本中文打印的java面试题目，随便翻到一题，就写着版上问我，基本
都是关于java一些属性的题。其中有2道题，我不是很确定，就询问，能否讨论一下结
果，国女每次都很严肃的和我，“This is interview, I cannot tell you true or
false. I cannot tell you anything.”. 拒绝和我讨论任何题目的答案。此国女的态
度，就是interview就是考试。不需要沟通讨论。
1.4 台湾CTO，上来写了一个算法给我，就是常见的二分法求乘积。让... 阅读全帖 |
|
