LeetCode(6):Z字形変換

Medium!
タイトルの説明:
文字列"PAYPALISHIRING"をZ字形で所定の行数に配列する:(以下のような形状)

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

その後、行順に並べ替えます:"PAHNAPLSIIGYIR" 
文字列を指定した行数に変換する関数を実装します.

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3)は"PAHNAPLSIIGYIR"を返さなければならない.
問題の説明:
例えば「0123456789 ABCDEF」という文字列がzigzagに変換されます
n=2の場合:
0 2 4 6 8 A C E
1 3 5 7 9 B D F
n=3の場合:
0   4    8     C
1 3 5 7 9 B D F
2    6   A     E
n=4の場合:
0     6        C
1   5 7   B  D
2 4   8 A    E
3      9       F
問題解決の考え方:
この問題は座標の変化を見ることだ.ブロック処理が必要です.
n=2の場合、文字列座標がzigzagになる歩き方は、
 0   2   4   6
 1   3   5   7
n=3の場合の歩き方は:
 0        4        8
 1   3   5   7   9
 2        6       10 
n=4の場合の歩き方は、
 0        6          12
 1   5   7   11   13
 2   4   8   10   14
 3        9          15 
最初の行と最後の行に中間に形成されていない字型の数字を除いて、他にもありますが、最初の2行の隣接する2つの要素のindexの差は行数に関連しています.2*nRows-2です.この特徴によって、すべての黒色要素がメタ文字列の位置を順番に見つけて、新しい文字列に順番に追加することができます.赤の要素が現れる位置についても規則的であり、各赤の要素の位置はj+2*nRows-2-2*iであり、jは前の黒の要素の列数であり、iは現在の行数である.例えば、n=4の赤い5の場合、その位置は1+2*4-2-2*1=5であり、元の文字列の正しい位置である.すべての黒い要素と赤い要素の位置の正しいアルゴリズムを知っていると、新しい文字列に一度に追加することができます.コードは次のとおりです.
C++参考答案:

 1 class Solution {
 2 public:
 3     string convert(string s, int nRows) {
 4         if (nRows <= 1) return s;
 5         string res = "";
 6         int size = 2 * nRows - 2;
 7         for (int i = 0; i < nRows; ++i) {
 8             for (int j = i; j < s.size(); j += size) {
 9                 res += s[j];
10                 int tmp = j + size - 2 * i;
11                 if (i != 0 && i != nRows - 1 && tmp < s.size()) res += s[tmp];
12             }
13         }
14         return res;
15     }
16 };

 

転載先:https://www.cnblogs.com/ariel-dreamland/p/8690523.html