LeetCode-6. Z字形变换（找规律）

小灰灰 2022-05-26 12:17 106阅读 0赞

### 6. Z字形变换 ###

[题目描述][Link 1]

--------------------

将字符串 `"PAYPALISHIRING"` 以Z字形排列成给定的行数：

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

*  [字符串][Link 2]

--------------------

#include<bits/stdc++.h>
    using namespace std;
    /********************提交代码********************/
    char* convert(char* s, int numRows)
    {
        if(numRows==1) return s;//特殊处理1
        int n=strlen(s),i=0,cnt=0;
        int x=4+2*(numRows-3),y=0,z=0,t=0;
        bool flag=true;//x和y均非零时true取x,false取y
        char *ans=(char*)malloc((n+1)*sizeof(char));
        for(; i<numRows; ++i)
        {
            ans[cnt++]=s[i];
            t=i;
            while(true)
            {
                if(flag)
                    z=x;
                else
                    z=y;
                if(x==0)//特殊处理第一行和最后一行
                    z=y;
                else if(y==0)
                    z=x;
                if(t+z>=n) break;//跳出条件
                ans[cnt++]=s[t+z];
                flag=!flag;
                t+=z;
            }
            x-=2,y+=2,z=0;
            flag=true;
        }
        ans[cnt]='\0';
        return ans;
    }
    /***************************************************/
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("F:/cb/read.txt","r",stdin);
        //freopen("F:/cb/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        char s[1000],ss[10];
        while(cin.getline(s,1000))
        {
            int numRows;
            cin>>numRows;
            cout<<s<<endl;
            cout<<numRows<<endl;
            cout<<"/"<<convert(s,numRows)<<"/"<<endl;
            cin.getline(ss,10);//吃回车符
        }
        return 0;
    }

当作找规律来做的。

下标化成数字后Z型排列如下：

**numRows=3时：**

![2018050212533021][]

第一行数字之间相差4；

第二行数字之间相差2；

第三行数字之间相差4。

**numRows=4时：**

![20180502125433823][]

第一行数字之间相差6；

第二行数字之间相差4，2；

第三行数字之间相差2，4。

第四行数字之间相差6。

**numRows=5时：**

**![2018050212553697][]**

第一行数字之间相差8；

第二行数字之间相差6，2；

第三行数字之间相差4，4。

第四行数字之间相差2，6；

第五行数字之间相差8。

**……………………分隔线……………………**

依给定的行数，按行遍历，找规律发现第一行和最后一行差值是**4+2\*(numRows-3)**

竖着看，每行之间两个差值相差**2**

x和y分别表示某行两个相邻数的差值（为保持一致性，第一行和最后一行加个0）

交替取x和y，用flag标记当前取x还是y

[Link 1]: https://leetcode-cn.com/problems/zigzag-conversion/description/
[Link 2]: https://leetcode-cn.com/tag/string
[2018050212533021]: /images/20220526/11714b6436464bb98d18aa786a7d23ed.png
[20180502125433823]: /images/20220526/2d8f85cdc25c411284df24e1539ef132.png
[2018050212553697]: /images/20220526/bf8648cb078e4771b723b93bd72a50a9.png