z字形变换

z字形变换

题目：将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列，之后，需要从左往右逐行读取，产生出一个新的字符串。

方法一：

       首先，若字符串长度为 1 ，则该字符串经过 Z 字形排列后的输出仍然是该字符，故直接输出。

       然后，用一个 numRows * n 的二维数组 z[ i ][ j ] 来存放按 Z 字形排列的字符串，其中 n 是根据字符串 s 的长度来计算得到的二维数组的列数。 例如，字符串 s = “Iamabeautifulgirl”,按照 Z 字形排列时需要至少需要的列数为8列，如下图所示：

可以看出，在二维数组 z[ i ][ j ] 中，可以分为几种情况：

        1、当 j 为numRows-1 的倍数时，z[ i ][ j ]中存放得有字符串 s 中的元素 s[i + j *2] ；

        2、当 （i + j） 为 numRows-1 的倍数时，z[ i ][ j ]中也存放有字符串 s 中的元素 s[i + j *2] ；

        3、其他情况， z[ i ][ j ] 中不存放 s 的元素。     

因此，在遍历二维数组 z[ i ][ j ] 时，按行优先来遍历，当遍历到上述1、2两种情况是，输出该位置对应的 s 中存放的字符，遍历完成后，就成功的输出了 Z 字形变换后行优先得到的顺序。

    string convert(string s, int numRows) {
        if (numRows < 2) return s;

        //这个算式是根据画出z字形后找到的列数的规律
        int n = (s.length() / (2 * numRows - 2) + 1) * (numRows - 1); 
        string zs;  //存储输出字符串
        int pos = 0;  //指向zs字符串的最后一个字符的下一字符
        //numRows*n的二维数组
        vector > z(n, vector(numRows));
        for (int i = 0;i < numRows;i++) {
            for (int j = 0;j < n;j++) {
                //判断当前z[i][j]是否对应于字符串s中的某一元素 
                //要保证当前遍历到的元素的i，j满足i+2*j不超过字符串s的长度
                if (((i + 2 * j) < s.length()) && (!(j % (numRows - 1)) || !((i + j) % (numRows - 1)))) {
                    zs += s[i + 2 * j];  //在string类型后拼接字符可以用 str+= 
                    //zs[pos++] = s[i + 2 * j];
                }
            }
        }
        return zs;
    }

        按照上面这个方法，时间复杂度为o(n^2)，在leetcode中跑的分数如下（惨的一批hhh），之后有时间可能会学习一下leetcode上面的更优的方法。今天要休息啦~