a**********2
发帖数: 340 | 1 1.判断string match是否包含string pattern里面的所有的character
2.一个数组，找出数组中有多少个cycle。cycle：每个element去找他对应的index，如
果index在界内，就继续找这个index的值所对应的下一个index直到找到一个cycle，或
者出界。大概就这个意思
比方说 0，2，1，9，10
对于0， index 0 就是 val 0， 所以是一个cycle
对于2， index 2 是 1， 在界内，就找 index 1，which is 2，所以又是一个cycle
总共4个cycles： 0-->0, 2 -> 1, 9 -> 界外， 10->界外
先要求写了个可以有extra space的，然后要求no extra space | a*****g
发帖数: 110 | 2 第二题的意思是说：
if (array[i] < array.length) 就是一个cycle么？
【在 a**********2 的大作中提到】
: 1.判断string match是否包含string pattern里面的所有的character
: 2.一个数组，找出数组中有多少个cycle。cycle：每个element去找他对应的index，如
: 果index在界内，就继续找这个index的值所对应的下一个index直到找到一个cycle，或
: 者出界。大概就这个意思
: 比方说 0，2，1，9，10
: 对于0， index 0 就是 val 0， 所以是一个cycle
: 对于2， index 2 是 1， 在界内，就找 index 1，which is 2，所以又是一个cycle
: 总共4个cycles： 0-->0, 2 -> 1, 9 -> 界外， 10->界外
: 先要求写了个可以有extra space的，然后要求no extra space
| a**********2
发帖数: 340 | 3 不是，如果array[i] < array.length)就把i=array[i]继续找直到找到这轮中已经访问
过的元素就是一个cycle
比方说2，0，1，4，3，
array[0] = 2,那么访问arry[2]
array[2] = 1,那么继续访问array[1]
array[1] = 0， 0已经在这次扫描中访问过了，那么就形成一个cycle
对于4，3也是一样，所有总共两个cycle
【在 a*****g 的大作中提到】
: 第二题的意思是说：
: if (array[i] < array.length) 就是一个cycle么？
| g*****i
发帖数: 2162 | 4 写了一个要extra space的
private static int findCycleNum(int[] input){
if(input==null||input.length<1)
return -1;
int len=input.length;
int[] visited=new int[len];
int visitedCount=0; //shorcut if all is visited
int cycleCount=0;
int temp;
boolean newCycle=false;
for(int i=0;i
if(visited[i]==1)
continue;
temp=i;
newCycle=true;
while(temp
if(visited[temp]==0){
visited[temp]=1;
visitedCount++;
temp=input[temp];
}
else if(temp==i){ //backto cycle start
break;
}
else{
newCycle=false;
break;
}
}
if(newCycle)
cycleCount++;
}
return cycleCount;
}
【在 a**********2 的大作中提到】
: 不是，如果array[i] < array.length)就把i=array[i]继续找直到找到这轮中已经访问
: 过的元素就是一个cycle
: 比方说2，0，1，4，3，
: array[0] = 2,那么访问arry[2]
: array[2] = 1,那么继续访问array[1]
: array[1] = 0， 0已经在这次扫描中访问过了，那么就形成一个cycle
: 对于4，3也是一样，所有总共两个cycle
| g*****i
发帖数: 2162 | 5 这题in space什么思路?
【在 a**********2 的大作中提到】
: 不是，如果array[i] < array.length)就把i=array[i]继续找直到找到这轮中已经访问
: 过的元素就是一个cycle
: 比方说2，0，1，4，3，
: array[0] = 2,那么访问arry[2]
: array[2] = 1,那么继续访问array[1]
: array[1] = 0， 0已经在这次扫描中访问过了，那么就形成一个cycle
: 对于4，3也是一样，所有总共两个cycle
| P**********c
发帖数: 3417 | 6 第二题有重复数字吗？
【在 a**********2 的大作中提到】
: 1.判断string match是否包含string pattern里面的所有的character
: 2.一个数组，找出数组中有多少个cycle。cycle：每个element去找他对应的index，如
: 果index在界内，就继续找这个index的值所对应的下一个index直到找到一个cycle，或
: 者出界。大概就这个意思
: 比方说 0，2，1，9，10
: 对于0， index 0 就是 val 0， 所以是一个cycle
: 对于2， index 2 是 1， 在界内，就找 index 1，which is 2，所以又是一个cycle
: 总共4个cycles： 0-->0, 2 -> 1, 9 -> 界外， 10->界外
: 先要求写了个可以有extra space的，然后要求no extra space
| n*******s
发帖数: 482 | 7 in space may need to change the array | n*******s
发帖数: 482 | 8 int x[]= {...} // assuming -1 is not an eclement in the arrray
int i, t;
int cyc_count = 0;
for(i = 0; i
if(x[i]!=-1){
t = x[i];
x[i]=-1;
while(x[t!]=-1 && t < size){
int tmp = t;
t = x[t]
x[tmp] = -1;
}
cyc_count++;
}
}
return cyc_count; | P**********c
发帖数: 3417 | 9 这个好像不太对，上来就把x[i]设成－1, 后面应该判断是不是回到原位置了吧。
【在 n*******s 的大作中提到】
: int x[]= {...} // assuming -1 is not an eclement in the arrray
: int i, t;
: int cyc_count = 0;
: for(i = 0; i: if(x[i]!=-1){
: t = x[i];
: x[i]=-1;
: while(x[t!]=-1 && t < size){
: int tmp = t;
: t = x[t]
| P**********c
发帖数: 3417 | 10 这个时间复杂度是多少？每个元素最多被访问几次？
【在 g*****i 的大作中提到】
: 写了一个要extra space的
: private static int findCycleNum(int[] input){
: if(input==null||input.length<1)
: return -1;
: int len=input.length;
: int[] visited=new int[len];
: int visitedCount=0; //shorcut if all is visited
: int cycleCount=0;
: int temp;
: boolean newCycle=false;
| | | a**********2
发帖数: 340 | 11 对，不考虑重复
【在 P**********c 的大作中提到】
: 第二题有重复数字吗？
| a**********2
发帖数: 340 | 12 我当时也是这个思路
【在 P**********c 的大作中提到】
: 这个好像不太对，上来就把x[i]设成－1, 后面应该判断是不是回到原位置了吧。
| g**********y
发帖数: 14569 | 13 Test fail:
{0, 2, 1, 9, 10} expected 4, returned 2
{1, 9, 3, 0} expected 1, returned 2 | g**********y
发帖数: 14569 | 14 这可能不是最简洁的, 但是应该work, 重复也可以。唯一要求是所有数 >= 0
public int count(int[] x) {
int count = 0;
for (int i=0; i
if (x[i] == i) {
count++;
x[i] = -x[i];
}
if (x[i] <= 0) continue;
int t = i;
while (x[t] > 0 && x[t] < x.length) {
x[t] = -x[t];
t = -x[t];
}
if (x[t] > 0 || t == i) count++;
if (x[t] > 0) x[t] = -x[t];
}
return count;
} | o***i
发帖数: 603 | 15 不需要改动原数组：
int CountCycle1 ( int array[], int len ) {
int t, sum = 0;
for ( int i=0; i< len; i++ ) {
t = i;
while(1) {
if (array[t] >= len || array[t] < i) break;
if (array[array[t]] == array[i]) {
sum++;
break;
}
t = array[t];
}
}
return sum;
}
测试结果：
{0, 2, 1, 9, 10}; 2
{3, 2, 1, 4, 0}; 2
{0, 2, 1, 9, 3}; 2
{0, 1, 2, 3, 4}; 5
{4, 0, 1, 2, 3}; 1
{0, 2, 1, 9, 10}; 2
{1, 9, 3, 0}; 0 | o***i
发帖数: 603 | 16
这个应该是2
这个应该是0吧
【在 g**********y 的大作中提到】
: Test fail:
: {0, 2, 1, 9, 10} expected 4, returned 2
: {1, 9, 3, 0} expected 1, returned 2
| g**********y
发帖数: 14569 | 17 1, 9, 3, 0
相当于 3 -> 0 -> 1 - > 9
按题意这是一个cycle，见原题: 出界的也算cycle。
【在 o***i 的大作中提到】
:
: 这个应该是2
: 这个应该是0吧
| g**********y
发帖数: 14569 | 18 这个code怎么测试过的？array[array[t]]直接就出界了
【在 o***i 的大作中提到】
: 不需要改动原数组：
: int CountCycle1 ( int array[], int len ) {
: int t, sum = 0;
: for ( int i=0; i< len; i++ ) {
: t = i;
: while(1) {
: if (array[t] >= len || array[t] < i) break;
: if (array[array[t]] == array[i]) {
: sum++;
: break;
| g**********y
发帖数: 14569 | 19 这个改一下可以处理出界的情况，也不需要改原数组。但时间是O(N^2)
【在 o***i 的大作中提到】
: 不需要改动原数组：
: int CountCycle1 ( int array[], int len ) {
: int t, sum = 0;
: for ( int i=0; i< len; i++ ) {
: t = i;
: while(1) {
: if (array[t] >= len || array[t] < i) break;
: if (array[array[t]] == array[i]) {
: sum++;
: break;
| o***i
发帖数: 603 | 20 不好意思，没认真看原题，出界的我的code里不算的，呵呵
【在 g**********y 的大作中提到】
: 1, 9, 3, 0
: 相当于 3 -> 0 -> 1 - > 9
: 按题意这是一个cycle，见原题: 出界的也算cycle。
| | | o***i
发帖数: 603 | 21 这是个奇迹，:)
【在 g**********y 的大作中提到】
: 这个code怎么测试过的？array[array[t]]直接就出界了
| o***i
发帖数: 603 | 22 出界也算的话不太好处理了
【在 g**********y 的大作中提到】
: 这个改一下可以处理出界的情况，也不需要改原数组。但时间是O(N^2)
| o***i
发帖数: 603 | 23 这次应该可以了：
int CountCycle ( int array[], int len ) {
int t, sum = 0;
for ( int i=0; i< len; i++ ) {
t = i;
if (array[t] >= len || array[t] < 0) sum++;
while(1) {
if (array[t] >= len || array[t] < i) break;
if (array[array[t]] == array[i]) {
sum++;
break;
}
t = array[t];
}
}
return sum;
}
加个判断出界的语句。
测试结果：
{1, 2, 3, 4, 10};
{1, 2, 3, 0, 10};
{1, 2, 0, 9, 30};
{0, 1, 2, 3, 4};
{4, 0, 1, 2, 3};
{10, 10, 10, 20, 30};
{1, 9, 3, 0};
1
2
3
5
1
5
1
【在 o***i 的大作中提到】
: 出界也算的话不太好处理了
| r*******y
发帖数: 1081 | 24 #2, any complexity requirements? Given an array A[1,...,N], starting from A[
1],
find a cycle and determine the smallest index i1 such that A[i1] is in the
cycle. Then starting from A[2] to find the second cycle and determine the
smallest index i2. if i2==i1, this means we find the same cycle and we need
to
ignore this cycle and go ahead starting from A[3]...
找他对应的
【在 a**********2 的大作中提到】
: 1.判断string match是否包含string pattern里面的所有的character
: 2.一个数组，找出数组中有多少个cycle。cycle：每个element去找他对应的index，如
: 果index在界内，就继续找这个index的值所对应的下一个index直到找到一个cycle，或
: 者出界。大概就这个意思
: 比方说 0，2，1，9，10
: 对于0， index 0 就是 val 0， 所以是一个cycle
: 对于2， index 2 是 1， 在界内，就找 index 1，which is 2，所以又是一个cycle
: 总共4个cycles： 0-->0, 2 -> 1, 9 -> 界外， 10->界外
: 先要求写了个可以有extra space的，然后要求no extra space
| b*******8
发帖数: 37364 | 25 看起来很妙啊。
【在 o***i 的大作中提到】
: 这次应该可以了：
: int CountCycle ( int array[], int len ) {
: int t, sum = 0;
: for ( int i=0; i< len; i++ ) {
: t = i;
: if (array[t] >= len || array[t] < 0) sum++;
: while(1) {
: if (array[t] >= len || array[t] < i) break;
: if (array[array[t]] == array[i]) {
: sum++;
| g**********y
发帖数: 14569 | 26 把olivi的写法再简化一下:
public int numberOfCycles(int[] a) {
int cycle = 0;
for (int i=0; i
if (a[i] >= a.length) cycle++;
int t = i;
while (a[t] > i && a[t] < a.length) t = a[t];
if (a[t] == i) cycle++;
}
return cycle;
}
【在 o***i 的大作中提到】
: 这次应该可以了：
: int CountCycle ( int array[], int len ) {
: int t, sum = 0;
: for ( int i=0; i< len; i++ ) {
: t = i;
: if (array[t] >= len || array[t] < 0) sum++;
: while(1) {
: if (array[t] >= len || array[t] < i) break;
: if (array[array[t]] == array[i]) {
: sum++;
|
|
