佛山专业的免费建站,教育平台小程序,竞价托管公司联系方式,怎样做网站卖自己的产品个人主页#xff1a;C忠实粉丝 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 C忠实粉丝 原创 模拟算法(3)_Z字形变换 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记#xff0c;欢迎大家在评论区交流讨论#x1f48c; 目录 1. 题目链… 个人主页C忠实粉丝 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 C忠实粉丝 原创 模拟算法(3)_Z字形变换 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记欢迎大家在评论区交流讨论 目录 1. 题目链接 :
2. 题目描述 :
3. 解法(模拟) : 解法一(模拟 暴力): 题目分析 : 算法思路 : 示例展示: 代码展示 : 结果分析 : 解法二(模拟 规律) :
算法思路:
代码展示:
结果分析: 1. 题目链接 :
OJ链接 : Z字形变换
2. 题目描述 :
将一个给定字符串 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 1000s 由英文字母小写和大写、, 和 . 组成1 numRows 1000
3. 解法(模拟) : 解法一(模拟 暴力): 题目分析 :
假如题目给我们这样的字符串s : a. b. c. d. e. f. g. h. i. j. k. l. m. n numRows 4
从上往下进行Z字形排列,然后从左往右逐行读取产生出一个新的字符串: agmbfhlnceikdj
如下图所示: 算法思路 : 1. 输入判断 首先算法检查 numRows 是否小于等于 1 或大于等于字符串 s 的长度。如果是则直接返回原字符串 s因为在这些情况下不需要进行任何转换。2. 初始化 创建一个字符串向量 rows 来存储每一行的内容。这个向量的大小是 min(numRows, (int)s.size())以防字符串长度小于行数。 curRow 用于跟踪当前字符应该放入的行初始值为 0。 goingDown 是一个布尔值用于指示当前的遍历方向向下或向上。3. 遍历字符串 使用一个循环遍历字符串 s 中的每个字符。 将当前字符 ch 添加到对应的行 rows[curRow]。 判断是否到达了第一行curRow 0或最后一行curRow numRows - 1。如果到达了这些边界就反转方向即将 goingDown 的值取反。 根据当前方向更新 curRow 的值。如果 goingDown 为 true则 curRow 加 1否则减 1。4. 组合结果 最后创建一个字符串 ret将 rows 向量中的所有行连接在一起形成最终结果。 示例展示:
假设输入字符串 s PAYPALISHIRING并且 numRows 3算法的执行步骤如下
初始化
rows [, , ]三个空字符串 curRow 0 goingDown false遍历字符
添加 P → rows [P, , ], curRow 1 添加 A → rows [P, A, ], curRow 2 添加 Y → rows [P, A, Y], curRow 1 添加 P → rows [P, AP, Y], curRow 0 添加 A → rows [PA, AP, Y], curRow 1 添加 L → rows [PA, AP, YL], curRow 2 添加 I → rows [PA, API, YL], curRow 1 添加 S → rows [PA, APIS, YL], curRow 0 添加 H → rows [PAH, APIS, YL], curRow 1 添加 I → rows [PAH, APISI, YL], curRow 2 添加 R → rows [PAH, APISIR, YL], curRow 1 添加 I → rows [PAH, APISIRI, YL], curRow 0 添加 N → rows [PAHN, APISIRI, YL], curRow 1 添加 G → rows [PAHN, APISIRIG, YL], curRow 2 代码展示 :
class Solution {
public:string convert(string s, int numRows) {//如果行数小于等于或大于等于字符串长度,直接返回原字符串if(numRows 1 || numRows s.size()) return s;//创建一个字符串向量来存储每一行vectorstring rows(min(numRows, (int)s.size()));int curRow 0; //当前索引bool goingDown false;//方向标志,false表示向上,true表示向下//遍历字符串中的每个字符for(char ch : s){rows[curRow] ch;//将字符添加到当前行//当到达第一行或最后一行时,改变方向if(curRow 0 || curRow numRows - 1) goingDown !goingDown;//切换方向//更新当前索引curRow goingDown ? 1 : -1;}//组合所有行string ret;for(auto ch : rows)ret ch;return ret;}
}; 结果分析 : 时间复杂度 该算法的时间复杂度是 O(n)其中 n 是输入字符串的长度因为每个字符都会被遍历一次。空间复杂度 空间复杂度是 O(n)用于存储结果行数和结果字符串。 解法二(模拟 规律) :
算法思路: 不难发现数据是以 2row - 2 为⼀个周期进⾏规律变换的。将所有数替换成用周期来表示的变量 第⼀行的数是0, 2row - 2, 4row - 4 第⼆行的数是1, (2row - 2) - 1, (2row - 2) 1, (4row - 4) - 1, (4row - 4) 1 第三行的数是2, (2row - 2) - 2, (2row - 2) 2, (4row - 4) - 2, (4row - 4) 2 第四行的数是3, (2row - 2) 3, (4row - 4) 3。 可以观察到第⼀行、第四行为差为 2row - 2 的等差数列第二行、第三行除了第⼀个数取值为行 数每组下标为(2n - 1, 2n)的数围绕2row - 2的倍数左右取值。 以此规律我们可以写出迭代算法。 再进一步抽象成序号: 代码展示:
class Solution {
public:string convert(string s, int numRows) {string ret;if(numRows 1 || numRows s.size()) return s;//求出公差int d 2 * numRows - 2;//处理第一行for(int i 0; i s.size(); i d)ret s[i];//处理中间k行for(int i 1; i numRows - 1; i)for(int j i; j s.size(); j d){ret s[j];if(j d - 2 * i s.size()) ret s[j d - 2 * i]; }//处理最后一行for(int i numRows - 1; i s.size(); i d)ret s[i];return ret;}
}; 结果分析: 综合时间复杂度 : O(n) 空间复杂度 : O(n)
