有没有木工版 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Living

有没有木工版

有没有木工版# Living

a*22011-04-01 07:04

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

T*U2011-04-01 07:04

2 楼

想要搞2×8×25的beam，最长的也就2×8×16，怎么连起来结实好看？不是用来承重的
。

a*g2011-04-01 07:04

3 楼

第二题的意思是说：
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

e*t2011-04-01 07:04

4 楼

按照做molding的方法，是斜切45度∠。

【在 T*U 的大作中提到】

: 想要搞2×8×25的beam，最长的也就2×8×16，怎么连起来结实好看？不是用来承重的
: 。

a*22011-04-01 07:04

5 楼

不是，如果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么？

T*U2011-04-01 07:04

6 楼

有道理，记下。

【在 e********t 的大作中提到】

: 按照做molding的方法，是斜切45度∠。

g*i2011-04-01 07:04

7 楼

写了一个要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;iif(visited[i]==1)
continue;
temp=i;
newCycle=true;
while(tempif(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

m*y2011-04-01 07:04

8 楼

Steel fasteners.
We used to just nail 2X8s to two opposite sides.

g*i2011-04-01 07:04

9 楼

这题in space什么思路?

【在 a**********2 的大作中提到】

R*r2011-04-01 07:04

10 楼

凹凸型，然后上胶，不放心中间再上根螺丝

【在 T*U 的大作中提到】

: 想要搞2×8×25的beam，最长的也就2×8×16，怎么连起来结实好看？不是用来承重的
: 。

P*c2011-04-01 07:04

11 楼

第二题有重复数字吗？

【在 a**********2 的大作中提到】

m*y2011-04-01 07:04

12 楼

Hehe, if you want to play it fancy, start with tongue and groove.
Can find more patterns on internet.

【在 e********t 的大作中提到】

: 按照做molding的方法，是斜切45度∠。

n*s2011-04-01 07:04

13 楼

in space may need to change the array

n*s2011-04-01 07:04

14 楼

int x[]= {...} // assuming -1 is not an eclement in the arrray
int i, t;
int cyc_count = 0;
for(i = 0; iif(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*c2011-04-01 07:04

15 楼

这个好像不太对，上来就把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*c2011-04-01 07:04

16 楼

这个时间复杂度是多少？每个元素最多被访问几次？

【在 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*22011-04-01 07:04

17 楼

对，不考虑重复

【在 P**********c 的大作中提到】

: 第二题有重复数字吗？

a*22011-04-01 07:04

18 楼

我当时也是这个思路

【在 P**********c 的大作中提到】

: 这个好像不太对，上来就把x[i]设成－1, 后面应该判断是不是回到原位置了吧。

g*y2011-04-01 07:04

19 楼

Test fail:
{0, 2, 1, 9, 10} expected 4, returned 2
{1, 9, 3, 0} expected 1, returned 2

g*y2011-04-01 07:04

20 楼

这可能不是最简洁的, 但是应该work, 重复也可以。唯一要求是所有数 >= 0
public int count(int[] x) {
int count = 0;

for (int i=0; iif (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*i2011-04-01 07:04

21 楼

不需要改动原数组：
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*i2011-04-01 07:04

22 楼

这个应该是2
这个应该是0吧

【在 g**********y 的大作中提到】

: Test fail:
: {0, 2, 1, 9, 10} expected 4, returned 2
: {1, 9, 3, 0} expected 1, returned 2

g*y2011-04-01 07:04

23 楼

1, 9, 3, 0
相当于 3 -> 0 -> 1 - > 9
按题意这是一个cycle，见原题: 出界的也算cycle。

【在 o***i 的大作中提到】

:
: 这个应该是2
: 这个应该是0吧

g*y2011-04-01 07:04

24 楼

这个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*y2011-04-01 07:04

25 楼

这个改一下可以处理出界的情况，也不需要改原数组。但时间是O(N^2)

【在 o***i 的大作中提到】

o*i2011-04-01 07:04

26 楼

不好意思，没认真看原题，出界的我的code里不算的，呵呵

【在 g**********y 的大作中提到】

: 1, 9, 3, 0
: 相当于 3 -> 0 -> 1 - > 9
: 按题意这是一个cycle，见原题: 出界的也算cycle。

o*i2011-04-01 07:04

27 楼

这是个奇迹，:)

【在 g**********y 的大作中提到】

: 这个code怎么测试过的？array[array[t]]直接就出界了

o*i2011-04-01 07:04

28 楼

出界也算的话不太好处理了

【在 g**********y 的大作中提到】

: 这个改一下可以处理出界的情况，也不需要改原数组。但时间是O(N^2)

o*i2011-04-01 07:04

29 楼

这次应该可以了：
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*y2011-04-01 07:04

30 楼

#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 的大作中提到】

b*82011-04-01 07:04

31 楼

看起来很妙啊。

【在 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*y2011-04-01 07:04

32 楼

把olivi的写法再简化一下:
public int numberOfCycles(int[] a) {
int cycle = 0;
for (int i=0; iif (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 的大作中提到】