【leetcode】第6题 Z字形变换，详细题解， C++实现，#6. ZigZag Conversion

ゝ一纸荒年。 2021-12-18 20:41 194阅读 0赞

这几天因为状态不太好，在这题上花了比较多的时间，记录一下。  
因为题目很老了，Leetcode上关于此题的题解很多，然而很多题解解释得都不是很清楚，包括leetcode官方题解，题解中符号所表示的意思都不写明，无力吐槽，还是自己写一个当笔记吧。

#### 题目详情 ####

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。  
比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：  
![20190701152425991.png][]  
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“LCIRETOESIIGEDHN”。

请你实现这个将字符串进行指定行数变换的函数：  
string convert(string s, int numRows);

示例 1:

输入: s = “LEETCODEISHIRING”, numRows = 3  
输出: “LCIRETOESIIGEDHN”  
示例 2:

输入: s = “LEETCODEISHIRING”, numRows = 4  
输出: “LDREOEIIECIHNTSG”  
解释:  
![在这里插入图片描述][20190701152454539.png]

#### 解法一：找规律 ####

此解法图较多，因此先讲该解法，看过解法一的图再讲解法二就更易于让人理解。

###### 思路： ######

1.  根据观察，找出 Z 字形矩阵中，每行所包含的字符在字符串s中的下标，找出下标之间的规律；
2.  根据规律，遍历字符串 s，拼接出Z字形结果字符串。

先用几个例子将 s 的 Z 字形变换写出来，然后观察规律，下面给出两个例子：  
**例1：**  
![在这里插入图片描述][20190701153451162.png]  
**例2：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]  
**通过观察，可以得出以下规律：**  
![在这里插入图片描述][20190701153740471.png]  
**即：**

令  n = n u m R o w s n = numRows n=numRows， row 表示 Z 字形结果矩阵的行号：  
Z 字形结果矩阵中每一行所包含的字符的下标 i 间差值的规律为：  
首尾两行：  i n t e r v a l = 2 ∗ n − 2 interval = 2\*n - 2 interval=2∗n−2；  
中间行： i n t e r v a l = 2 ∗ n − 2 − 2 ∗ r o w interval = 2\*n - 2 - 2\*row interval=2∗n−2−2∗row 或  i n t e r v a l = 2 ∗ r o w interval = 2\*row interval=2∗row。

其中首尾两行的规律其实也是：  i n t e r v a l = 2 ∗ n − 2 − 2 ∗ r o w interval = 2\*n - 2 - 2\*row interval=2∗n−2−2∗row 或  i n t e r v a l = 2 ∗ r o w interval = 2\*row interval=2∗row。  
只不过首行的  2 ∗ r o w = 0 2\*row=0 2∗row=0，  
而尾行的  2 ∗ n − 2 = 2 ∗ r o w 2\*n - 2 = 2\*row 2∗n−2=2∗row  
所以首尾两行的  i n t e r v a l = 2 ∗ n − 2 interval = 2\*n - 2 interval=2∗n−2

**所以若两个规律合一的话总的规律就是：**  
 i n t e r v a l = 2 ∗ n − 2 − 2 ∗ r o w interval = 2\*n - 2 - 2\*row interval=2∗n−2−2∗row 或  i n t e r v a l = 2 ∗ r o w interval = 2\*row interval=2∗row  
其中 interval 为 0 时舍去。

**将该规律使用代码实现：**

string convert(string s, int numRows) {
        
            int sLen = s.size();
            if(sLen <= 2 || numRows == 1){
        
                return s;
            }
    
            string res = "";
            for(int currRow = 0; currRow < numRows; currRow++){
        
                int interval;
                int firstInterval = (2 * numRows - 2) - 2 * currRow; // 避免重复计算
                int secondInterval = 2 * currRow;  // 避免重复计算
                bool isFirst = true; // 用于区分interval取何值，true：取firstInterval; false：取secondInterval;
                int index = currRow;
    
                while( index < sLen ){
        
                    interval = isFirst ? firstInterval : secondInterval;
    
                    // 跳过首尾两行有个interval为0的情况
                    if( interval == 0 ){
        
                        isFirst = !isFirst;
                        continue;
                    }
                    res += s[index];
                    index += interval;
                    isFirst = !isFirst;
                }
            }
            return res;
        }

[github地址][github]  
提交结果：（选时间最短的）  
![在这里插入图片描述][20190701160959307.png]

#### 解法二 ####

思路：

1.  先将 Z 字形变换结果矩阵存入一个容器中；
2.  从第 0 行开始遍历容器，依次拼接出结果字符串。

string convert(string s, int numRows) {
        
            int sLen = s.size();
            if(sLen <= 2 || numRows == 1){
        
                return s;
            }
            int currRow = 0;
            bool goingDown = false;                             // 方向标志位 true：方向向下，行+1； false：方向斜向上，行-1
            vector<string> convertArr(min(numRows, sLen));      // 使用min防止有空行
    
            for(int i = 0; i < sLen; i++ ){
                             // 以Z字形将字符串放入vector容器中
                convertArr[currRow] += s[i];
                cout << convertArr[currRow] << endl;
                if( currRow == numRows-1 || currRow == 0 ){
        
                    goingDown = !goingDown;
                }
                if(goingDown){
        
                    currRow++;
                }else{
        
                    currRow--;
                }
            }
            string res = "";
            for(int i = 0; i < convertArr.size(); i++){
        
                res += convertArr[i];
            }
            return res;
        }

提交结果：（选时间最短的）  
![在这里插入图片描述][20190730120107516.png]  
[github地址][github]

[20190701152425991.png]: /images/20211219/0a2ee39394784a7b8f79157dea73096d.png
[20190701152454539.png]: /images/20211219/7dc6a75f9a98467ebd85c79cffbba113.png
[20190701153451162.png]: /images/20211219/741c0c96809849ac9df46b7eaae27187.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20211219/4323915181cb49c5926625e1ebfd0c37.png
[20190701153740471.png]: /images/20211219/bbbbb6d9c817439987153828461a9a12.png
[github]: https://github.com/yohstone/Programming-practice/blob/master/leetcode-6-zigZag%20conversion.cpp
[20190701160959307.png]: /images/20211219/d7851179354743bebdcaa8c67820dc9c.png
[20190730120107516.png]: /images/20211219/8e4669302f1d437982bed46404137518.png