leetcode 6

题目描述：

该开始就输在了理解题意上。。没搞懂zigzag是什么意思。

查了一些解释终于明白要干什么了。将一个字符串按照Z字形排列（侧着看）；再把结果按行输出。

刚开始的想法是讲字符串按照规则排列在一个二维数组中，然后按序扫描数组输出。时间复杂度为O(n²).

进一步改进，按行数生成n个字符串，按照规则将目标字符串中每个字符存入相应的字符串中，最后将n个字符串连接。省去了扫描二维数组的时间开销。

时间复杂度为O(n)。

代码如下：

class Solution {

public:

    string convert(string s, int numRows) {

        int l = s.length();

        if(numRows <=  || l < )

            return s;

        string* s_str = new string[numRows];

        int period =  * (numRows - );

        for(int i = ; i< l; ++ i)

        {

            s_str[numRows -  - abs(numRows -  - (i % period))].push_back(s[i]);

            //此处为借鉴的公式；

            //自己写的s_str[i%period].push_back(s[i])会出现越界错误。

        }

        string str_result;

        for(int i = ; i < numRows; ++ i)

        {

            str_result.append(s_str[i]);

        }

        return str_result;

    }

};

巴特西

leetcode 6

最新文章

热门文章