LC 6、Z 字形变换

superJade / 2023-07-30 / 原文

LC 6、Z 字形变换

题目描述

LeetCode 上的 6、Z 字形变换，难度中等

将一个给定字符串 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);

示例：

输入：s = "PAYPALISHIRING", numRows = 3

输出："PAHNAPLSIIGYIR"

模拟

题目理解;

字符串 s是以 Z 自行为顺序存储的字符串，目标是按行打印
设numRows行字符串分别为 s1, s2, ..., sn, 则容易发现；按顺序遍历字符串 s时，每个字符 czai Z字形中对应的行索引时先增大至n，再从n减小至1，如此反复
因此，解决方案为：摸摸你这个行索引的变化，再遍历 s中每个字符天道正确的行 res[i]

算法流程：按顺序遍历 `s`;

res[i] += c: 把每个字符 c填入对应的行 s_i；
i += flag ：更新当前字符 c对应的行索引；
flag = -flag ：在达到Z自行转折点时，执行反向。

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows < 2) return s;
        int flag = -1;
        int index = 0;
        vector<string> vec(numRows, "") ;
        for(int i = 0; i < s.size(); i++){
            vec[index].push_back(s[i]);
            if(index == 0 || index == numRows - 1) flag = -flag;
            index += flag;
        }
        string ans = "";
        for(int i = 0; i < vec.size(); i++){
            ans += vec[i];
        }
        return ans;
    }
};

时间复杂度 O(N) : 遍历一遍字符串 s:

空间复杂度 O(N): 隔行字符串共占用 O(N) 的额外空间。

Label：模拟