6.N字形变换

题目要求

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：

P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”PAHNAPLSIIGYIR”。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

样例 #1

输入 #1

1
s = "PAYPALISHIRING", numRows = 3

输出 #1

1
"PAHNAPLSIIGYIR"

样例 #2

输入 #2

1
s = "PAYPALISHIRING", numRows = 4

输出 #2

1
"PINALSIGYAHRPI"

样例 #3

输入 #3

1
s = "A", numRows = 1

输出 #3

1
"A"

提示

1 <= s.length <= 1000
s 由英文字母（小写和大写）、’,’ 和 ‘.’ 组成
1 <= numRows <= 1000

解题思路

首先可以发现排序有一定的周期2*numRows-2（numRows>1），可以想到取余来找规律

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
char * convert(char * s, int numRows)
{
    int i, n = 1, j = 0, k = 0;
    int len = strlen (s);
    char * ch;
    ch = malloc( sizeof( char ) * ( len + 1 ));
    for ( i = 0; i < numRows; i++ ){
        for ( j = 0; j < len; j++ ){
            if( j % (2 * numRows -2) == i || j % (2 * numRows - 2) == 2 * numRows - 2 - i ){
                ch[k] = s[j];
                k++;
            }
        }
    }
    ch[k]= '\0';
    return ch;
}