Z 字形变换

发布于 2020-07-18 14:27:39   阅读量 37  点赞 0  

原题地址:https://leetcode-cn.com/problems/zigzag-conversion/

题目

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

 比如输入字符串为"LEETCODEISHIRING"行数为 3 时,排列如下:

L   C   I   R
E T O E S I I G
E   D   H   N

 之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"LCIRETOESIIGEDHN"

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

string convert(string s, int numRows);


示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"


示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G



解法

 解决这个问题的要领在于找出每个字符位于 Z 字形图案的第几行,然后按顺序将第一行到最后一行的字符串接起来即可。

 故通过模仿 Z 字形图案形成的顺序找出各自行的字符即可,具体方法为迭代字符串,通过一个指向变量isGoingDown指示行号变化的方向(向上或向下)。



代码

string convert(string s, int numRows) {
    if(numRows==1){
        return  s;
    }

    vector<string> rows = vector<string>(min((int)s.size(),numRows));
    bool isGoingDown = false;

    int currentRow = 0;
    for(char c:s){
        rows[currentRow] += c;
        if(currentRow0 || currentRow  numRows-1){
            isGoingDown = !isGoingDown;
        }
        currentRow += isGoingDown?1:-1;
    }

    string result;
    for(const string& str:rows){
        result += str;
    }

    return result;
}


Last Modified : 2020-07-20 15:54:23