力扣6-N 字形变换

时间：2023-02-21 12:54:48

原题链接：https://leetcode.cn/problems/zigzag-conversion/

题目描述

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

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

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。 请你实现这个将字符串进行指定行数变换的函数： string convert(string s, int numRows);

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

示例 2： 输入：s = "PAYPALISHIRING", numRows = 4 输出："PINALSIGYAHRPI" 解释：

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

示例 3： 输入：s = "A", numRows = 1 输出："A"

  提示：

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

解题思路

读完题干，能很明显感觉到这个题的规律性很强，感觉不难找，但这样的结果就是代码很复杂。

我们换一个思路。

首先，这个N型字的间隔是不用我们管的，我们只需要处理字符。 然后，这道题就会简单很多。 找个简单的为例：ABCDEF，3

  1. 我们设一个容量为三的字符串数组，分别存储三行字符
  2. 使用循环和两个指针：
    1. 一个指针随循环移动从字符串中取出字符
    2. 一个指针随循环移动切换字符串数组，以交替接受上一个指针中取出的字符
  3. 由于N型字需要切换方向移动，我们需要设置一个变量用于标记当前行指针移动的方向
  4. 根据移动方向，判断临界情况，当行数等于0或(字符串长度-1)时，切换方向，修改行数

原理不难，但很容易出问题 我就把行数和字符串位置给弄混了 还忽略了一行的情况，一行时可以直接返回原字符串 力扣6-N 字形变换

敲代码

如果觉得上面的文字太抽象，就多看看下面的代码，如果觉得下面的代码难以理解，就多看看上面的文字

class Solution {
public:
    string convert(string s, const int& numRows) {
        if (numRows == 1)
            return s;
        string* part = new string[numRows];
        int direction = 1;
        for (int i(0), row(0); i < s.size(); i++,row+=direction)
        {
            part[row] += s[i];
            if ((row == numRows - 1 && direction == 1) || (row == 0&&direction==-1))
                direction = -direction;
        }
        string result = part[0];
        for (int i = 1; i < numRows; i++)
        {
            result += part[i];
        }
        return result;
    }
};

运行结果 执行用时：12 ms, 在所有 C++ 提交中击败了52.53%的用户 内存消耗：10.4 MB, 在所有 C++ 提交中击败了49.35%的用户 通过测试用例：1157 / 1157 力扣6-N 字形变换

标签：

相关文章