LeetCode 6. Z 字形变换

发表于 | 更新于 | 分类于

题意

根据给定的行数，将字符串从上到下、从左到右进行Z字形排列，详见样例。

思路

  • 想法1：直接模拟，时间复杂度$O(n)$。为什么运行时间只击败了21%的用户，内存消耗却击败了83%的用户？难道有什么空间换时间的方法？
  • 想法2：看了官方题解，并没有。但是，可以通过计算每个位置的数学关系来解答。时间复杂度也是$O(n)$。

代码

  • 代码1（二维数组直接模拟）：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    class Solution {
    public:
        string convert(string s, int numRows) {

            if(numRows == 1)    return s;

            int len = s.size();
            char res[numRows][len];
            memset(res, 0, sizeof(res));

            bool flag = true;
            int col = 0, row = 0;
            for(int i = 0; i < len; ++i)
            {
                if(flag)    //down
                {
                    res[row++][col] = s[i];
                    if(row == numRows)
                    {
                        flag = false;
                        --row;  //back
                    }
                }
                else    //up
                {
                    res[--row][++col] = s[i];
                    if(row == 0)
                    {
                        flag = true;
                        --i;
                    }
                }
            }

            /*
            for(int i = 0; i < numRows; ++i, puts(""))
                for(int j = 0; j <= col; ++j)
                    cout << res[i][j];
            */

            string ans = "";
            for(int i = 0; i < numRows; ++i)
                for(int j = 0; j <= col; ++j)
                    if(res[i][j] != 0)
                        ans.push_back(res[i][j]);

            return ans;
        }
    };

  • 代码2（数学关系）：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class Solution {
    public:
        string convert(string s, int numRows) {
            
            if(numRows == 1)    return s;
            
            string res;
            int len = s.size();
            int cycleLen = 2 * numRows - 2;
            
            for(int i = 0; i < numRows; ++i)
            {
                for(int j = 0; j + i < len; j += cycleLen)
                {
                    res.push_back(s[i + j]);
                    if(i > 0 && i < numRows - 1 && j + cycleLen - i < len)
                        res.push_back(s[j + cycleLen - i]);
                }
            }
            return res;
        }
    };

总结

这种关系的一般都会和数学（找关系式？）有关系的，如以前遇到过的“蛇形填数”。

Donate comment here
0%