f*****e
发帖数: 2992 | 1 来自主题: JobHunting版 - G 家面经 storm8的 online test 的升级版，3个循环搞定。
for(int j = 0; j < m; j++) // row from bottom to top
for(int i = 0; i < n; i++) // column from left to right
for(int k = 0; k <=j; k++) // calculate diagnal '\' elements
dp2[i][j][i+k][j-k] = max{of the 4 combinations};
// k = 0 is what we want, other values of k are prepared for later
calculation of the 4 combinations (left, left), (left, down), (down, left),
(down, down)
O(n*(1+...+m))=O(nm^2)=O(MN*min(M,N)), m = min(M, N)
-------(i,j... 阅读全帖 |
|
|
|
e******i
发帖数: 106 | 4
不知道啊，以前做题都没有想过这个问题，而且不是说他们的问题对空间复杂度要求不
高么 |
|
j*****y
发帖数: 1071 | 5 为什么是返回7阿，这个unique的string没想明白 |
|
p*****2
发帖数: 21240 | 6 然后又举例，“byebye”，应当返回二
这个为什么是2？ |
|
H****s
发帖数: 247 | 7 这个题目 先将string 复制级联然后每次shift一位判断是否相等
如 "codility" --> "codilitycodility" 然后再跟原string 判断就行了！ |
|
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 | 13 byebye移0和3得到的string和原来的string一样，所以是2吧，是这样理解的吧？ |
|
M********5
发帖数: 715 | 14 这个应该是空间时间都是O(n)的吧。。。我当时做的应该是空间是O(n^2)的，其实这题
就是这样一个trick |
|
|
|
|
e******i
发帖数: 106 | 18
当时我也想到了这个算法，有点类似cracking 上的一道题，后来觉得hashmap简单就没
有细想了 |
|
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一位之后怎么比较呢？ |
|
p*****2
发帖数: 21240 | 21
任何string，包括空数组，应当最少返回1.
这个怎么理解？ |
|
|
|
|
|
|
|
|
M********5
发帖数: 715 | 29 如果这个string是aaaaa，那space是不是O(n^2) |
|
p*****2
发帖数: 21240 | 30 我目前的想法就是rolling hashing了。如果N不大好些，如果N很大，需要点数学知识
了。 |
|
w****x
发帖数: 2483 | 31
同跪，今天给Zynga跪了， 最近跪的几家都是代码还来不及写就给据了，NND |
|
M********5
发帖数: 715 | 32 为什么这个时间不是O(n)，不是总共循环n次吗？ |
|
|
|
p*****2
发帖数: 21240 | 35
仔细看看。你这个是O(n^2)。这题哪里会那么简单呢。你仔细分析一下复杂度。 |
|
|
|
|
f*****e
发帖数: 2992 | 39 别吵了，求最小周期，n久之前，caiwu出过类似题，我给答案就是O(N)，我找找。 |
|
e******i
发帖数: 106 | 40
二爷，我现在想就两个问题，一个是用了hashmap.而是用了Java的substring导致空间
复杂度超标了， 这两个的JAVA原理我都没有深究，substring我一直按o(1)来考虑，会
不会是O(n)啊，那样的话，那我的时间复杂度也错了。。。 |
|
|
p*****2
发帖数: 21240 | 42
substring O(n)
这题rolling hash, 不过要选mod的话，我就没有经验了。不知道应该怎么选择好。
再有就是KMP。mshearts说的。 |
|
f*****e
发帖数: 2992 | 43 想到了，很简单，记前n个数的周期为k，当你碰到第n+1个数，不满足这个周期，该如何
update k？ |
|
d*********g
发帖数: 154 | 44
如何
不满足周期的话就说明前n+1个数不是周期的，应该暂设k=n+1吧，是这样么？ |
|
|
|
|
p*****2
发帖数: 21240 | 48
如何
byebye
开始第一个b，周期1
第二个y, 怎么检查周期呢？ |
|
f*****e
发帖数: 2992 | 49 b[i - k] != b[i], thus update k，具体怎么update的，我忘了，公式很简单，reaso
ning很tricky. |
|
|
