【力扣刷题实战】Z字形变换

大家好，我是小卡皮巴拉

文章目录

目录

力扣题目：Z字形变换

题目描述

解题思路

问题理解

算法选择

具体思路

解题要点

完整代码（C++）

兄弟们共勉 ！！！ 

---

每篇前言

博客主页：小卡皮巴拉

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。

力扣题目：Z字形变换

原题链接：6. Z 字形变换 - 力扣（LeetCode）

题目描述

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

解题思路

问题理解

本题要求将给定字符串 s 按照指定的行数 numRows 进行 Z 字形排列，然后从左到右逐行读取排列后的字符，生成一个新的字符串。

算法选择

通过分析 Z 字形排列的规律，根据字符在原字符串中的索引位置来构建最终的结果字符串，而无需真正构建 Z 字形的二维矩阵，这样可以节省空间。

具体思路

1. 边界情况处理：当 numRows 为 1 时，字符串无需变换，直接返回原字符串 s。

2. 计算周期长度：计算 Z 字形排列的一个周期内字符的数量 d，公式为 d = 2 * numRows - 2。

3. 按行处理字符：

   • 第一行：第一行的字符在原字符串中的索引间隔为 d，从索引 0 开始，依次将符合条件的字符添加到结果字符串 ret 中。

   • 中间行：对于中间的每一行（从第 1 行到第 numRows - 2 行），每个周期内有两个字符需要添加到结果字符串中。第一个字符的索引 i 从当前行号 k 开始，每次增加一个周期长度 d；第二个字符的索引 j 从 d - k 开始，每次也增加一个周期长度 d。在添加字符时，需要检查索引是否在字符串长度范围内。

   • 最后一行：最后一行的字符在原字符串中的索引间隔也为 d，起始索引为 numRows - 1，依次将符合条件的字符添加到结果字符串 ret 中。

4. 返回结果：返回最终的结果字符串 ret。

解题要点

1. 周期规律分析：准确找出 Z 字形排列的周期长度 d 以及每一行字符在原字符串中的索引规律。

2. 边界检查：在添加字符到结果字符串时，要检查索引是否在字符串长度范围内，避免越界访问。

3. 按行处理：分别处理第一行、中间行和最后一行，确保每个字符都能正确添加到结果字符串中。

完整代码（C++）

class Solution {
public:string convert(string s, int numRows) {// 处理边界情况：如果行数为 1，那么字符串无需变换，直接返回原字符串if(numRows == 1) return s;// 用于存储最终转换后的字符串string ret;// 计算一个循环周期的长度，Z 字形排列的一个周期内字符数量为 2 * numRows - 2int d = 2 * numRows - 2, n = s.size();// 1. 先处理第一行// 第一行的字符在原字符串中的索引间隔为 dfor(int i = 0; i < n; i += d)ret += s[i];// 2. 处理中间行// 枚举每一行，从第 1 行到第 numRows - 2 行（因为第 0 行和第 numRows - 1 行单独处理）for(int k = 1; k < numRows - 1; k++)// 对于中间行的每个周期，有两个字符需要添加到结果字符串中// i 从当前行号 k 开始，每次增加一个周期长度 d// j 从 d - k 开始，每次也增加一个周期长度 dfor(int i = k, j = d - k; i < n || j < n; i += d, j += d){// 如果 i 索引在字符串长度范围内，将该字符添加到结果字符串中if(i < n) ret += s[i];// 如果 j 索引在字符串长度范围内，将该字符添加到结果字符串中if(j < n) ret += s[j];}// 3. 处理最后一行// 最后一行的字符在原字符串中的索引间隔也为 d，起始索引为 numRows - 1for(int i = numRows - 1; i < n; i += d)ret += s[i];// 返回转换后的字符串return ret;}
};

兄弟们共勉 ！！！ 

码字不易，求个三连

抱拳了兄弟们！