LeetCode 刷题【6. Z 字形变换】

6. Z 字形变换

自己做

分析

解法1：合并多个子串

class Solution {
public:
    string convert(string s, int numRows) {
        vector<string> c(numRows,string());
        int j = 0;
        string save;

        int len = s.size();

        while(j < len){
            for(int i = 0; i < numRows && j < len; i++)            //竖向【从0~numRows-1】
                c[i] += s[j++];
            for(int i = numRows-2; i > 0 && j < len; i--)          //斜向【从numRows-2~1】      
                c[i] += s[j++];
        }

        for(int i = 0; i < numRows; i++)                            //合并
            save += c[i];

        return save;
    }
};

解法2：数学分析

结果比上面的还差

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1)       //行为1的特殊情况
            return s;

        int len = s.size();
        string save;        //新生成的字符串
        for (int i = 0; i < numRows; i++) {       //逐行累加
            int index = i;      //字符串s在该行对应的起始位置

            if (i == 0) {       //第0行，只有下角
                int j = 2 * numRows - 2 * i - 2;      //下角间隔
                while (index < len) {
                    save.push_back(s[index]);
                    index += j;
                }
            }
            else if (i == numRows - 1) {       //最后一行，只有上角
                while (index < len) {
                    int j = 2 * i;              //上角间隔
                    save.push_back(s[index]);
                    index += j;
                }
            }
            else {                          //剩下的情况
                int j1 = 2 * numRows - 2 * i - 2;       //下角间隔
                int j2 = 2 * i;                         //上角间隔

                //先先下角再上角
                while (index < len) {
                    save.push_back(s[index]);
                    index += j1;
                    if (index < len) {
                        save.push_back(s[index]);
                        index += j2;
                    }
                    else{
                        break;                          //越界
                    }
                }
            }
            cout << save << endl;
        }

        return save;
    }
};

看题解

en——在看人家的代码时发现了，人家初始话vector<string>时只指定了大小，而我又用string()初始化了一遍，优化自己的代码如下

class Solution {
public:
    string convert(string s, int numRows) {
        vector<string> c(numRows);
        int j = 0;
        string save;

        int len = s.size();

        while (j < len) {
            for (int i = 0; i < numRows && j < len; i++)            //竖向【从0~numRows-1】
                c[i] += s[j++];
            for (int i = numRows - 2; i > 0 && j < len; i--)          //斜向【从numRows-2~1】      
                c[i] += s[j++];
        }

        for (int i = 0; i < numRows; i++)                            //合并
            save += c[i];

        return save;
    }
};