你好,游客 登录 注册 搜索
背景:
阅读新闻

【leetcode】Zigzag Conversion - IT-Homer 专栏

[日期:2013-04-20] 来源:  作者: [字体: ]

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






收藏 推荐 打印 | 录入:admin | 阅读:
相关新闻