Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode ZigZag Conversion

Leetcode algorithms 第 6 题:ZigZag Conversion。

题目

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: “PAHNAPLSIIGYIR”

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

解答

题目看半天没看懂,最终发现不是通常沿着对角线进行的zig-zag扫描,这里是沿着竖直方向的,类似一个左右颠倒的N字。那么问题变得非常简单,它这样扫描,从竖直方向看,就是一个指针一直在上下走动,走到尽头即调转方向继续。

于是,使用变量r表示当前在哪一行,d表示当前的方向,也就是r的递增值,向下为+1,向上为-1,遍历即可。

具体代码如下:

class Solution {
public:
    string convert(string s, int nRows) {
        if (nRows == 1) return s;
        
        vector<string> v(nRows);
        for (int i = 0, r = 0, d = 1; i < s.length(); i++)
        {
            v[r] += s[i];
            if (r == 0) d = 1;         //向下
            if (r == nRows - 1) d = -1;//向上
            r += d;
        }
        string ans;
        for (int i = 0; i < nRows; i++) ans += v[i];
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论