006. ZigZag Conversion

 题目地址：https://leetcode.com/problems/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".

题目翻译： 给出一个字符串，和行数，将其形成Z字型格式表示，最后按行输出

例如：“ABCDEFGHIJK”，4

A      G

B   F H

C E   I  K

D      J

这样就形成了Z字型，按行输出为AGBFHCEIKDJ 题目分析：

对于上述题目，可以通过将每一行内的字符构成一个字串例如“AG”,"BFH","CEIK","DJ",构成4个字串，每个字串存在一个单独的类型中，可以使数组，结构体， 遍历输入字符串，将其分别放入上述单独的类型中，最后，将所有的子串进行拼接

代码：

C

运行时间20ms

struct Node {//用于保存子字符串的数据结构 char* czson; struct Node * pPri; struct Node * pNext; }; char* convert(char* s, int numRows){ int ilen = strlen(s); if (numRows<=1 || numRows>= ilen) return s;//控制numRows大小使其能够形成Z类型 struct Node * pHead; struct Node * pTail; //创建用于保存numRows个相连的节点 int i = 0; for(i = 0; i < numRows; i++) { struct Node* pNode = (struct Node *)malloc(sizeof(struct Node)); pNode->czson = (char *)malloc(sizeof(char) * (ilen + 1)); memset(pNode->czson, 0, ilen + 1); pNode->pPri = NULL; pNode->pNext = NULL; if(0 == i) {//首次创建节点 pHead = pNode; pTail = pNode; } else {//用新的节点追加到上一节点后面 pTail->pNext = pNode; pNode->pPri = pTail; pTail = pNode; } } struct Node * pNow;//用于执行现在操作的节点 int iIsNext = 1;//用于表示是否向Next遍历， 1 - 是 ， 0 - 向Pri pNow = pHead; //变量S字符串，保存到上面创建的数据结构中 for(i = 0; i < ilen; i++) { char sc = s[i]; strncat(pNow->czson, &sc, 1); if(1 == iIsNext) { if(!pNow->pNext) {//若为空，下步转向Pri遍历 iIsNext = 0; } } if(0 == iIsNext) { if(!pNow->pPri) {//若为空，下步转向Pri遍历 iIsNext = 1; } } //不管那个方向每次都要移动一次 if(1 == iIsNext) { pNow = pNow->pNext; } if(0 == iIsNext) { pNow = pNow->pPri; } } pNow = pHead; char* output = (char*) malloc(sizeof(char) * ( ilen + 1)); memset(output, 0, ilen + 1); do { strncat(output, pNow->czson, ilen); pNow = pNow->pNext; delete(pHead->czson); delete(pHead); pHead = pNow; }while(pNow); return output; }

C++

运行时间28ms

class Solution { public: struct Node {//用于保存子字符串的数据结构 string strson; struct Node * pPri; struct Node * pNext; }; string convert(string s, int numRows) { if (numRows<=1 || numRows>=s.size()) return s;//控制numRows大小使其能够形成Z类型 struct Node * pHead; struct Node * pTail; //创建用于保存numRows个相连的节点 int i = 0; for(i = 0; i < numRows; i++) { struct Node* pNode = new struct Node; pNode->strson = ""; pNode->pPri = NULL; pNode->pNext = NULL; if(0 == i) {//首次创建节点 pHead = pNode; pTail = pNode; } else {//用新的节点追加到上一节点后面 pTail->pNext = pNode; pNode->pPri = pTail; pTail = pNode; } } struct Node * pNow;//用于执行现在操作的节点 int iIsNext = 1;//用于表示是否向Next遍历， 1 - 是 ， 0 - 向Pri pNow = pHead; //变量S字符串，保存到上面创建的数据结构中 for(i = 0; i < s.length(); i++) { pNow->strson += s[i]; if(1 == iIsNext) { if(!pNow->pNext) {//若为空，下步转向Pri遍历 iIsNext = 0; } } if(0 == iIsNext) { if(!pNow->pPri) {//若为空，下步转向Pri遍历 iIsNext = 1; } } //不管那个方向每次都要移动一次 if(1 == iIsNext) { pNow = pNow->pNext; } if(0 == iIsNext) { pNow = pNow->pPri; } } pNow = pHead; string sResult; do { sResult += pNow->strson; pNow = pNow->pNext; free(pHead); pHead = pNow; }while(pNow); return sResult; } };

或

class Solution { public: string convert(string s, int numRows) { if (numRows<=1 || numRows>=s.size()) return s; vector<string> r(numRows); int row = 0; int step = 1; for(int i=0; i<s.size(); i ++) { if (row == numRows-1) step = -1; if (row == 0) step = 1; r[row] += s[i]; row += step; } string result; for (int i=0; i<numRows; i++){ result += r[i]; } return result; } };

Python

运行时间为148ms

class Solution(object): def convert(self, s, numRows): """ :type s: str :type numRows: int :rtype: str """ if numRows <= 1 or numRows >= len(s): return s tmp = ['' for i in range(numRows)] nRows = 0 nStep = 1 for i in range(len(s)): if nRows == numRows - 1: nStep = -1 if nRows == 0: nStep = 1 tmp[nRows] += s[i] nRows += nStep result = '' for i in range(numRows): result += tmp[i] return result