LeetCode 6 （ZigZag Conversion）算法

ZigZag Conversion（ZigZag转换）
1、题目描述： 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 s, int numRows);
Example 1:
Input: s = “PAYPALISHIRING”, numRows = 3
Output: “PAHNAPLSIIGYIR”
? ?给出一个指定字符串和numRows，把字符串按倒Z的形式排列，行数为numRows，按行排列返回字符串。
2、解决方法1：按行分类(Java实现) ? ?仔细观察这个Z型的图形，它是由nomRows行子串构成。所以可以遍历整个字符串把字符依次添加到指定行字符串上，方向为先下后上。

public String convert(String s, int numRows) {//numRows为1，直接返回s if (numRows==1){ return s; }//构建Math.min(numRows, s.length())个字符串(字符串的长度小于numRows，集合长度取s.length)， // 放在集合中。也可以使用字符串数组实现。 //使用StringBuilder可以使字符串拼接更快。 List> rows = new ArrayList<>(); for (int i = 0; i < Math.min(numRows, s.length()); i++) { StringBuilder stringBuilder = new StringBuilder(); rows.add(stringBuilder); }int curRow = 0; //当前行 boolean dir = false; //当前方向true向下 false向上for (char c : s.toCharArray()) { rows.get(curRow).append(c); //第一行或最后一行时，换方向 if (curRow ==0 || curRow ==numRows -1 ){ dir= ! dir; }//换行 curRow += dir ? 1 : -1; }//拼接字符串集合 StringBuilder str = new StringBuilder(); for (StringBuilder sb : rows) { str.append(sb); }return str.toString(); }

运行耗时：53ms

文章图片

时间复杂度：O(n) 遍历字符串的长度为len(s)。
空间复杂度：O(n) 存储了len(s)的字符。
解决方法2：按行访问(C语言实现) 原理：找到每一行中的字符在字符串中的出现位置。
如图：

文章图片

? ?仔细观察第一行中P和A中间距中间相隔3个子串，实际下标相差4。在图上看的话其实是相差一列加一条对角线，所以第一行的字符位置可以表示为k*(2 * numRows - 2) ，k为字符在一行字符串中所处的位置。最后一行的字符位置可以用第一行加numRows-1表示，所以可以表示为k*(2 * numRows - 2) - numRows -1。中间的字符包含两个部分，分别是 k*(numRows -2) + i 和（k+1)*(numRows -2) - i。

char *convert_2(char *s, int numRows) {if (numRows == 1) { return s; }int length = strlen(s); int cycleLen = 2 * numRows - 2; //长度比原字符串多1，有个'\0' char *ret = (char *) malloc(sizeof(char) * (length + 1)); int index = 0; for (int i = 0; i < numRows; ++i) { for (int j = 0; j + i < length; j += cycleLen) { //第一行、最后一行和中间行的列部分 ret[index++] = s[j + i]; //中间行字符串的对角线部分 if (i != 0 && i != numRows - 1 && j + cycleLen - i < length) { ret[index++] = s[j + cycleLen - i]; } } } ret[index] = '\0'; return ret; }

【LeetCode 6 （ZigZag Conversion）】运行耗时：12ms