[6] Zigzag Conversion

除了搞了一個小烏龍之外，其實算是一次PASS吧  XD

然後就得意忘形了～想要忽略掉其實跑的很慢的事實  XD

應該是可以不要用到二維，直接用各種算位置的方法去把它求出來吧

算是很久沒寫的第一題，我決定先放過自己XD

概念上就是每一個Z字型---是說為什麼不叫做N字型--當做一個round，

來去算矩陣的長寬應該宣告多少，後來填進去的時候也是一round 一round 的概念

因此如果把最後一round 多出來的部分放到迴圈外單獨處理的話，可以變快一些些

就一些些Orz 放在最後面。(但也不排除只是剛好server 比較不忙XD)

char* convert(char* s, int numRows) {

int len =strlen(s);

int realW=len;

if (numRows<2)

return s;

int square = numRows+(numRows-2);

int width = (len / square) ;

int more = len - (square * width);

if (more < numRows )

realW = (1+ (numRows-2))*width +1;

else

realW = (1+ (numRows-2))*width +1 + (more - numRows);

int **zigzag = calloc (numRows , sizeof (int *));

for (int i=0;i<numRows;i++)

{

zigzag[i]= calloc (realW,sizeof(int));

}

int idx = 0;

for (int i=0; i<= width ;i++)

{

int column = i*(numRows-1) ;

int row=0;

for (row=0; row<numRows;row++)

{

if (idx==len)

break;

zigzag[row][column] = s[idx++];

}

column ++;

row -= 2;

int subcount = square - numRows;

for (int j=0;j<subcount;j++)

{

if (idx==len)

break;

zigzag[row--][column++] = s[idx++];

}

}

idx=0;

for (int i=0 ; i<numRows ; i++)

{

for (int j=0;j<realW;j++)

{

if (zigzag[i][j]>0)

s[idx++]= zigzag[i][j];

}

}

return s;

}

加速版:

char* convert(char* s, int numRows) {

int len =strlen(s);

int realW=len;

if (numRows<2)

return s;

int square = numRows+(numRows-2);

int width = (len / square) ;

int more = len - (square * width);

if (more < numRows )

realW = (1+ (numRows-2))*width +1;

else

realW = (1+ (numRows-2))*width +1 + (more - numRows);

int **zigzag = calloc (numRows , sizeof (int *));

for (int i=0;i<numRows;i++)

{

zigzag[i]= calloc (realW,sizeof(int));

}

int idx = 0;

for (int i=0; i< width ;i++)

{

int column = i*(numRows-1) ;

int row=0;

for (row=0; row<numRows;row++)

zigzag[row][column] = s[idx++];

column ++;

row -= 2;

int subcount = square - numRows;

for (int j=0;j<subcount;j++)

zigzag[row--][column++] = s[idx++];

}

{

int column = width*(numRows-1) ;

int row=0;

for (row=0; row<numRows;row++)

{

if (idx==len)

break;

zigzag[row][column] = s[idx++];

}

column ++;

row -= 2;

int subcount = square - numRows;

for (int j=0;j<subcount;j++)

{

if (idx==len)

break;

zigzag[row--][column++] = s[idx++];

}

}

idx=0;

for (int i=0 ; i<numRows ; i++)

{

for (int j=0;j<realW;j++)

{

if (zigzag[i][j]>0)

s[idx++]= zigzag[i][j];

if (idx==len) //最後一行如果已經到長度了就不用跑完了

break;

}

}

return s;

}