题目

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”PAHNAPLSIIGYIR”。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);

  1. 输入：s = "PAYPALISHIRING", numRows = 3
  2. 输出："PAHNAPLSIIGYIR"
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

输入：s = "A", numRows = 1
输出："A"
  • 1 <= s.length <= 1000
  • s 由英文字母（小写和大写）、’,’ 和 ‘.’ 组成
  • 1 <= numRows <= 1000

    思路

    这题主要考虑一个周期性，以z字形的一横加一斜杠的组合作为一个周期，那么这个周期内的字符总数为p = 2*numrow-2.考虑这里的有效性，当numrow为1时p=0，此时会陷入死循环。也就是说当字符s[i]处于某一行m时，s[i+p]有效时也处于m行。由于这的形状为z字形，除去首位两行，其余行都存在两个i%p不同的值会处于同一行的状态，此时i1%p+i2%p=p

    源代码

    class Solution {
public:
  string convert(string s, int numRows) {
      string ans = "";
      int p = 2*numRows-2, begin;
      for(int i = 0; i < numRows; i++)
      {
          begin = i;
          if(i == 0)
          {
              if(numRows == 1)
                  return s;
              while(begin < s.size())
              {
                  ans.append(1,s[begin]);
                  begin = begin + p;
              }
          }
          if(i > 0 && i < numRows-1)
          {
              int same = p - begin;
              while(begin < s.size() || same < s.size())
              {
                  if(begin < s.size())
                  {
                      ans.append(1,s[begin]);
                      begin = begin + p;
                  }
                  if(same < s.size())
                  {
                      ans.append(1,s[same]);
                      same = same + p;
                  }    
              }
          }
          if(i == numRows-1)
          {
              while(begin < s.size())
              {
                  ans.append(1,s[begin]);
                  begin = begin + p;
              }
          }
      }
      return ans;
  }
};