(leetcode)Z字形变换 -- 模拟算法

2024-01-07 21:19:35

?个人主页:Lei宝啊?

愿所有美好如期而遇?


题目链接

. - 力扣(LeetCode)

输入描述

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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。