原文在这，可以来我blog翻翻哦。第二天。今天AC掉了一道之前没AC掉的题目。。。今天的题目是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 NA P L S I I GY I RAnd 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 s, int numRows);Example 1:Input: s = “PAYPALISHIRING”, numRows = 3Output: “PAHNAPLSIIGYIR"Input: s = “PAYPALISHIRING”, numRows = 4Output: “PINALSIGYAHRPI"Explanation:P I NA L S I GY A H RP I恩，又是一道“编程题“， 并不涉及到什么算法，静下心来仔细想想还是能做出来的。做这道题的思路就是一点一点跑例子，找出其中的规律就好了。我们先以输入为s = “PAYPALISHIRING”, numRows = 3为例子，这是题目给出的例子，正确答案已经有了。先把Z字型画出来（不难发现，题目在最开始其实已经给出了答案）：P A H NA P L S I I GY I R观察上面的例子我们可以发现：第一行中的元素在原来的字符串中下标相差4个。第二行中的元素在原来字符串中下标相差2个。ok，看起来好像找到了一些规律，继续跑一个例子验证一下，这次的输入是s = “PAYPALISHIRING”, numRows = 3，把Z字型画出来：P I NA L S I GY A H RP I可以看到第一行的元素在原来字符串中的下标相差6个，但是第二行却出现了一些不一样的情况：A与L相差4个，L与S却相差2个S与I相差4个，I与G却相差2个看起来offset是有规律的，而且好像需要分成两种情况，继续看看第3行：Y与A相差2个，A与H相差4个H与R相差4个，如果还有元素的话，下一个元素与R之间显然相差2个。从上面的例子来看显然是要分成两种情况的，某一行中下标之间的offset是不断在两个数字间不断变换的。我们尝试用两个数组来保存这些offset，我们把这两个数组定义为skipDown和skipUp。其中skipDown表示下标在z字型中经过了一个向下的剪头，如第二个例子中，第一行的P移动到I时，P经过了AYPAl组成的向下的剪头。skipUp同理可推。如果我们继续跑例子的话，应该是比较容易找出规律的：第i行的skipDown为2*(i-1)，而第一行和最后一行的skipDown都应该为2*(numRows)。skipDown与skipUp是逆序的关系。综上，我们可以写出下面的代码：string convert(string s, int numRows) { if (numRows < 2) return s; vector<int> skipDown(numRows); vector<int> skipUp(numRows); skipDown[0] = 2*(numRows-1); skipUp[0] = 0; for(int i = 1;i < numRows; i++) { skipDown[i] = skipDown[i-1] - 2; skipUp[i] = skipUp[i-1] + 2; } skipDown[numRows-1] = skipDown[0]; skipUp[0] = skipUp[numRows-1]; string res(s.size(), ’ ‘); int index = 0; for(int i = 0;i < numRows; i++) { bool flag = true; for(int j = i;j < s.size();index++) { res[index] = s[j]; if (flag) { j += skipDown[i]; } else { j += skipUp[i]; } flag = !flag; } } return res;}当然这肯定不是最优的代码，比如其实我们可以不用两个数组，甚至不用数组来保存的offset，但是这样写会比较容易理解，代码会比较简单点。