【优选算法必刷100题】第41-42题（模拟）：Z 字形变换，外观数列

🔥个人主页：Cx330🌸

❄️个人专栏：《C语言》《LeetCode刷题集》《数据结构-初阶》《C++知识分享》

《优选算法指南-必刷经典100题》《Linux操作系统》:从入门到入魔

《Git深度解析》:版本管理实战全解

🌟心向往之行必能至

🎥Cx330🌸的简介：

前言：

聚焦算法题实战，系统讲解三大核心板块：“精准定位最优解”——优选算法，“简化逻辑表达，系统性探索与剪枝优化”——递归与回溯，“以局部最优换全局高效”——贪心算法，讲解思路与代码实现，帮助大家快速提升代码能力

41. Z 字形变换

题目链接：

6. Z 字形变换 - 力扣（LeetCode）

题目描述：

题目示例：

算法原理（模拟）：

思路：

找规律，用 row 代替行数，row = 4 时画出的 N 字形如下：
0 2row - 2 4row - 4
1 2row - 3 2row - 1 4row - 5 4row - 3
2 2row-4 2row 4row - 6 4row - 2
3 2row + 1 4row - 1

不难发现，数据是以 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）的倍数左右取值。
以此规律，我们可以写出迭代算法。

模拟解法代码（C++）：

class Solution { public: string convert(string s, int numRows) { string ret; int d=2*numRows-2,n=s.size(); //如果n=1直接返回原字符串 if(numRows==1) return s; //处理第一行 for(int i=0;i<n;i+=d) ret+=s[i]; //处理中间行 for(int k=1;k<numRows-1;k++) { for(int i=k,j=d-k;i<n||j<n;i+=d,j+=d) { if(i<n) ret+=s[i]; if(j<n) ret+=s[j]; } } //处理最后一行 for(int i=numRows-1;i<n;i+=d) ret+=s[i]; return ret; } };

博主手记（字体还请见谅哈）：

42. 外观数列

题目链接：

38. 外观数列 - 力扣（LeetCode）

题目描述：

题目示例：

算法原理（模拟）：

思路：

所谓【外观数列】，其中只是依次统计字符串中连续且相同的字符的个数。依据题意，依次模拟即可。

模拟解法代码（C++）：

class Solution { public: string countAndSay(int n) { string ret="1"; for(int i=1;i<n;i++)//解释n-1次ret { string tmp; int len=ret.size(); for(int left=0,right=0;right<len;) { while(right<len&&ret[left]==ret[right]) right++; //to_string获取元素个数 tmp+=to_string(right-left)+ret[left]; left=right; } ret=tmp; } return ret; } };

博主手记（字体还请见谅哈）：

总结：

结语：本文分享了两个算法题的解题思路和C++实现。首先针对"Z字形变换"问题，通过观察字符排列规律，采用周期模拟法将字符串按特定顺序重组。其次解决"外观数列"问题，通过统计连续相同字符个数生成新字符串。两题均采用模拟解法，文章以实战为导向，简洁明了地展示了从问题分析到代码落地的完整过程。