LeetCode

LeetCode-06 Z字形变换

nkul · 9月3日 · 2020年 53次已读

容易看出:

1、第一行和最后一行是等差数列,公差是2n-2,因为列有n-1个元素,斜有n-1个元素

2、如图所示,中间的行,列列之间是等差,斜斜之间也是等差:
2.1、类比第一行,可以知道列列公差是2n-2
2.2、斜斜公差同样也是2n-2,因为相邻的两个斜斜,都是列列元素下标-(i+1),自然公差也是2n-2

3、第一行和最后一行,以及列列的首项元素都是s[i]

4、斜项的首元素为2n-2-i;

因为第i行的首项下标为i,设随之的斜线首项下标为j,如图所示,j后面的尖顶(即j所在斜线的第一行,同时,也是第一行的第二个元素)它的下标为j+i(因为j在第i行,所以j的右斜上方还有i个元素),下标还可以用等差数列算为0+2n-2
于是就有了i+j=2n-2

class Solution {
public:
    string convert(string s, int n) {
        string res;
        if(n==1)return s;
        for(int i=0;i < n;i++){
            //第一行和最后一行是公差为2n-2的等比数列
            if(i==0 | i== n-1 ){
                for(int j=i;j < s.size();j+=2*n-2){
                    res+=s[j];
                }
            }
            else{
                //j为列首项,k为斜首项,交叉相加
                for(int j=i, k=2*n-2-i;j < s.size() || k < s.size();j+=2*n-2,k+=2*n-2){
                    if(j < s.size())res+=s[j];
                    if(k < s.size())res+=s[k];
                }
            }
        }
    return res;
    }
};


0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!