LeetCode OJ-6.ZigZag Conversion

题目描述

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"

.

Subscribe to see which companies asked this question.

题目理解

​ 光看题目第一眼可能要看懵，对照例子，自己换一个行数画一下就清楚了。题目的意思就是以曲折线条的形式去重新排列给定字符串，排列时，每一步移动只有两种情况，一种是向下，即所在行+1，一种是向右上方，即所在行-1，所在列+1。处理时记录一下状态就好了，可以定义一个二维数组来做重新排列的结果，但要动态分配内存，还不如直接使用vector。初始时全置为0，获取结果字符串时，非0的元素push_back到结果字符串里就行了。具体代码在下方。

Code

class Solution { public: string convert(string s, int numRows) { string res; size_t len = s.length(); vector<vector<char>> vec(len, vector<char>(len, 0)); enum move_state { // 记录移动状态 start = 0, down, rup } state; state = start; int i; int j = 0; int k = 0; for (i = 0; i < len; ++i) { vec[j][k] = s[i]; if (j == numRows - 1) { // 向下移动到达最后一行 state = rup; } if (j == 0) { // 向右上方移动到达第一行 state = down; } if (state == down) { ++j; } else { --j, ++k; } } for (j = 0; j < len; ++j) { for (k = 0; k < len; ++k) { if (vec[j][k] != 0) { res.push_back(vec[j][k]); } } } //cout << res << endl; return res; } };