首页 > 其他 > 详细

leetcode ZigZag Conversion

时间:2014-03-16 20:23:57      阅读:616      评论:0      收藏:0      [点我收藏+]

ZigZag Conversion

 Total Accepted: 5160 Total Submissions: 22837My Submissions

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

Have you been asked this question in an interview? 


I treat this problem in a direct way:

class Solution {
 public:
  string convert(string s, int nRows) {
    int i, j, flg;
    vector<char> vec;
    vector<vector<char>> zigzag(nRows,vec);
    for (i = 0, j = 0, flg = 1; i < s.length(); ++i) {
      zigzag[j].push_back(s[i]);
      if (flg && j == nRows - 1)
        flg = 0;
      else if (!flg && j == 0)
        flg = 1;
      if (nRows > 1)
        j = flg > 0 ? (j + 1):(j - 1);
    }
    string res = "";
    for (i = 0; i < nRows; ++i)
      for (j = 0; j < zigzag[i].size(); ++j)
        res += zigzag[i][j];
    return res;
  }
};

But a better way is from http://blog.unieagle.net/2012/11/08/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Azigzag-conversion/

class Solution {
 public:
  string convert(string s, int nRows) {
    int len = s.length(), zigSize = nRows*2 - 2, i, j, tmp;
    string res = "";
    if (nRows <= 1) return s;
    for (i = 0; i < nRows; ++i) {
      for (j = i; j < len; j += zigSize) {
        res += s.substr(j,1);
        tmp = j + zigSize - 2 * i;
        if (i != 0 && i != nRows - 1 && tmp < len) {
          res += s.substr(tmp, 1);
        }
      }
    }
    return res;
  }
};





leetcode ZigZag Conversion,布布扣,bubuko.com

leetcode ZigZag Conversion

原文:http://blog.csdn.net/taoqick/article/details/21331569

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!