(leetcode)Z字形变换 -- 模拟算法
2024-01-07 21:19:35
?个人主页:Lei宝啊?
愿所有美好如期而遇?
题目链接
输入描述
string convert(string s, int numRows),输入一个字符串s,以及一个行数numRows,将字符串按照这个行数进行Z字形排列,实际上本题是将Z字形反转成了N字形。
输出描述
按照行将Z字形排列的字符打印出来。
算法分析
模拟算法,实际上就是根据题目要求做,优化就是找规律。
本道题,我们将通过画图来找规律,以示例二为例画图:
找规律,这没有什么比较好的方法,找得到就是找得到,根据图我们可以发现第一行和最后一行每个元素的下标差了6,也就是说公差为6,而中间行的元素,虽然也遵循这个规律,不过是两个数字两个数字这样来进行的--1+6=7? 5+6=11。
那么如何计算公差,你说公差是6就是了吗?我们可以多画几个图来进行验证,最后我们可以得到的结论是公差d = 2 * 行数 - 2;
对于第一行和最后一行而言,我们可以直接使用公差进行计算,而对于中间行来说,需要两个数字一起向后走,那么我们怎样得到第二个数字呢?观察后我们可以发现,这两个数字的下标加起来正好是公差d,所以我们可以用公差 - 下标一 = 下标二,后面的下标我们通过公差就可以得到了。
我们也就可以按照这样的规律,让下标和字母进行对应,直接把字符尾插进我们创建的string s变量中。
解题源码?
class Solution {
public:
string convert(string s, int numRows)
{
if(numRows == 1) return s;
string ret;
int d = 2 * numRows - 2;
int len = s.size();
for(int i=0; i<len; i+=d) ret += s[i];
for(int i=1; i<numRows-1; i++)
{
for(int j=i, k=d-i; j<len || k<len; j+=d, k+=d)
{
if(j<len) ret += s[j];
if(k<len) ret += s[k];
}
}
for(int i=numRows-1; i<len; i+=d) ret += s[i];
return ret;
}
};
文章来源:https://blog.csdn.net/m0_74824254/article/details/135438417
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!