【leetcode】Zigzag Conversion

阳光岛主

发布于 2019-02-19 11:27:26

3310

发布于 2019-02-19 11:27:26

Question ：

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".

Anwser 1 ：

class Solution {
 public:
     string convert(string s, int nRows) {
         // Start typing your C/C++ solution below
         // DO NOT write int main() function    
         string ret(s);
         
         int stepArray[2];
         int steps = 2 * nRows - 2;
         
         int retSize = 0;
         for(int i = 0; i < nRows; i++)
         {
             int num = nRows - (i + 1) + nRows - (i + 1) - 1;
             num++;
             stepArray[0] = num;
             if (stepArray[0] == 0)
                 stepArray[0] = steps;
             stepArray[1] = steps - num;
             if (stepArray[1] == 0)
                 stepArray[1] = steps;
                 
             int j = i;
             int index = 0;
             while(j < s.size())
             {
                 ret[retSize++] = s[j];
                 if (j == j + stepArray[index])
                     break;
                 j = j + stepArray[index];
                 index = 1 - index;
             }
         }    
         
         return ret;
     }
 };

Anwser 2 ：

class Solution {
public:
    string convert(string s, int nRows) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (nRows == 1) return s;
        
        vector<vector<char>> v(nRows, vector<char>());
        
        int i = 0;
        int d = 0;
        
        for (int j = 0; j < s.size(); j++) {
            v[i].push_back(s[j]);
            
            if (d == 0) {
                if (i + 1 == nRows) {
                    i--;
                    d = 1;
                } else {
                    i++;
                }
            } else {
                if (i == 0) {
                    i++;
                    d = 0;
                } else {
                    i--;
                }
            }
        }
        
        string ret = "";
        
        for (int j = 0; j < nRows; j++) {
            for (int k = 0; k < v[j].size(); k++)
                ret += v[j][k];
        }
        
        return ret;
    }
};

参考推荐：

pay pal interview question

[LeetCode] Zigzag Conversion

[LeetCode] ZigZag Conversion

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2013年04月20日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法