当前位置：首页 > article >正文

【LeetCode】06.Z字形变换

article 2024/9/24 19:25:41

题目要求

在这里插入图片描述

解题思路

首先映入我们脑海的就是暴力。这一方法可行，但是时间复杂度空间复杂度很高，因此我们使用找规律的方法。这样的话我们可以模拟插入下标，这样的话很容易发现首行和末行插入的位置刚好是d=2*n-2，而中间行的两个位置的下标之和刚好为d的整数倍。

代码实现

class Solution 
{
public:
    string convert(string s, int numRows) 
    {
        //处理特殊情况
        if(numRows==1)  return s;
        //确定返回值
        string ret;
        int n=s.size(),d=numRows*2-2;
        //第一行
        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;
    }
};