LeetCode-6. N 字形变换

 LeetCode   |  2023年05月18日   |  阅读：683次

难度：中等

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/zigzag-conversion/

1. 问题描述

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

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

2. 分析与解答

思路：矩阵模拟。分为两步：

  • 向下遍历
  • 向右上遍历
class Solution {
public:
    string convert(string s, int numRows) {
        // 模拟
        int n = s.length();
        if (numRows == 1 || numRows >= n) {
            return s;
        }
        vector<vector<char>> vec(numRows, vector<char>(n));
        int i = 0, j = 0, k = 0;
        
        // 向下走
        while (k < n) {
            while (i < numRows-1 && k < n) {
                vec[i][j] = s[k];
                i ++;
                k ++;
            }

            while (i > 0 && k < n) {
                vec[i][j] = s[k];
                i --;
                j ++;
                k ++;
            }
        }

        string res = "";
        for (int x = 0; x < numRows; x++) {
            for (int y = 0; y < n; y++) {
                if (vec[x][y]) res += vec[x][y];
            }
        }
        return res;
    }
};

目录