【leetcode】006 N字形变换

写了一下午终于写出来了

题目

leetcode 6. N 字形变换

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

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

1
2
3

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

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

1	string convert(string s, int numRows);

示例 1：

1 2	输入：s = "PAYPALISHIRING", numRows = 3 输出："PAHNAPLSIIGYIR"

示例 2：

1 2	输入：s = "PAYPALISHIRING", numRows = 4 输出："PINALSIGYAHRPI"

解释：

P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

1 2	输入：s = "A", numRows = 1 输出："A"

提示：

1
2
3

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

分析

刚开始我想的过于简单了，所以写的代码下标控制有严重问题，弄了这么久，其实一直都是在改下标……

1.写几个例子

如下是n从3到7的例子，能基本满足题目需要的情况

题目的要求是，给你一个 ABCDEFG...这样的字符串，再给一个行数n，让你按上面这种N的形式排列出来，再按行读出一个新的字符串。

我们肯定不可能真的用二维数组给她摆出来一个这样的图像再去遍历，哪样效率太低了。而是用n次遍历，利用下标的规律，以下标访问拼出新的字符串。

2.分析规律

按行号写出每一个的间隔，能的出来一个基本规律（最左列是行下标）

首先，我们能发现，每一个N型的第一行和最后一行的间隔（步长）是相同的，且和行数符合一个公式

1	(行数 - 1) * 2

除了这两个边界行，中间的行数都是简单的递减 2

3.步长翻转

但除了只有三行的示例之外，其余都有一个 步长翻转 的问题

如下，比如第1行（这里说的是下标）B->H符合从第0行开始递减2的步长6，但下一次查找的步长H->J就变成了2了

同理，看第3行，D->F的步长为2，而F->L的步长为6，两者正好和第1行相反。

而第1行和第3行，正好是两个对称的

这便是第二个规律

1 2	除了首末两行，和奇数行数的中间行（比如行数为5，第2行即为中间行 0 1 [2] 3 4 ）其余行数按上下分，其步长每走一次需要切换一次

以上图中的第1行为例

第一步，B->H，走的是正常的6步（由8-2得来）
第二步，H->J，走的是第三行的正常步2（由8-2*3得来）

由此往后，每走一步都需要在6和2之间切换。

复盘的时候才发现一个更简单的翻转，其实每一行的几次查找的步长最终加起来和首末两行是相同的

4.循环解释

找到了这个规律之后，写代码就好写了！下面解释一下完整代码中while循环中的判断部分，一共分为三种情况

首末行和奇数中间行，不需要翻转，正常进行步长的相加
需要翻转的行数，分为中间行上面的和下面的两种情况。该行第一次进入while，不需要加上翻转步长，而是加上由上一行步长sep-2得来的正常步长cur_sep。此时需要对翻转步长reverFlag进行初始化：
- 中间行上面，翻转步长为对称行步长的负数（比如第一行和第三行对称，此时第一行的翻转步长就是第三方的正常步长取负数。）
- 中间行下面，翻转步长为对称行步长的正数（同上）
该行第二次进入while，需要加上翻转步长reverFlag后，并对翻转步长取负数（对称行两个步长之间差值相同，取负数相当于恢复原始步长）
直到index大于string的长度，一行遍历完毕，sep-=2

完整代码

注意啊，如果你和我一样，写题的时候喜欢用print来找bug，那么写完了之后，一定要把这些题目需求中没有的打印给删除掉。不然会影响性能，甚至有可能因此超时无法通过题目。

class Solution {
public:
    // 奇数行，最中间的
    // 5 -> 2 | 7 -> 3
    bool isMidRow(int n,int numRows)
    {
        return (numRows%2!=0) && n == numRows/2;
    }
    bool isFirstEnd(int n,int numRows)
    {
        return n==0 || n==numRows-1;
    }

    string convert(string s, int numRows) {
        if(numRows<=1)
        {
            return s;
        }
        string ret;
        int begin_sep = (numRows-1)*2;
        int sep = begin_sep;// 第一行和最后一行都是这个长度
        // 中间的是从第一行开始，每次-2
        
        // 开始遍历，排除最后一行
        for(int i=0;i<numRows;i++)
        {
            if(i==numRows-1){
                sep = begin_sep;// 最后一行的长度分割
            }
            int index = i;
            int reverFlag = 1;
            int cur_sep = sep;
            while(index<s.size()){
                ret+=s[index];
                //是否是单数行中间的，如果是那就不需要反转
                if(isMidRow(i,numRows) || isFirstEnd(i,numRows)){
                    index+=sep;
                    //cout << i << " continue" << endl;
                    continue;
                }
                else if(reverFlag == 1){//本行第一次进来
                    index+=sep;
                    //cout << i << " 1r-sped "<<sep<<endl;
                    //int reverNum = abs((numRows/2-1)*2);
                    //cout << i << " 1r-rever "<<reverNum <<endl;
                    // 4行，上对称行1第一次翻转是-2
                    // 5行，上对称行1第一次反转是-4
                    int k = numRows - i - 1;
                    if(i<(numRows/2))//上对成行
                    {
                        //获取对称的行号的sep，并计算两者差值
                        reverFlag = - abs((begin_sep - k*2) - cur_sep);
                    }
                    else
                    {
                        reverFlag = abs((begin_sep - k*2) - cur_sep);
                    }
                    //cout <<i <<" 1r-flag "<<reverFlag<<endl;
                }
                else//第二次以上，开始反转
                {
                    cur_sep += reverFlag;
                    index+= cur_sep;
                    //cout <<i <<" sepd "<<( cur_sep)<<endl;
                    reverFlag = -reverFlag;//逆置
                    //cout <<i <<" flag "<<reverFlag<<endl;
                }
            }
            // 一行走完了，更新sep
            sep-=2;
        }

        return ret;
    }
};