6 ZigZag Conversion

Medium

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

1
2
3

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

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

1	string convert(string s, int numRows);

Example 1:

1 2	Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

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

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

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

1
2
3

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

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

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

1	string convert(string s, int numRows);

示例 1:

1 2	输入: 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

想法

这道题是在听宣讲会的时候做的，想的时间有点长😂，其实就是根据位置拼字符即可。只不过需要判断一下几个边界条件：

只有一行；
最后一行不满，需要判断长度；
算源字符的位置的时候要算快一点了。

解

#include <iostream>
#include <string>
#include <climits>

using namespace std;

string convert(string s, int numRows)
{
    int m = numRows > 1 ? numRows * 2 - 2 : 1;
    int len = s.size();
    string ans;
    for (int i = 0; i < numRows; i++) {
        for (int j = 0; j < (len + m - 1) / m; j++) {
            if (j * m + i < len) {
                ans.push_back(s[j * m + i]);
                int q = j * m + m - i;
                if (i != 0 && i != numRows - 1 && q < len) {
                    ans.push_back(s[q]);
                }
            }
        }
    }
    return ans;
}

int main(void)
{
    cout << INT_MAX << ' ' << INT_MIN << endl;
    cout << convert("PAYPALISHIRING", 1) << endl;
    return 0;
}

6 ZigZag Conversion

想法

解

喜欢这篇文章？打赏一下作者吧

评论

链接

标签云

最新文章

归档

分类

标签

Your browser is out-of-date!