刷题之路第六题-ZigZag Conversion

ZigZag Conversion

简介：

字符串“PAYPALISHIRING”以Z字形图案写在给定数量的行上,如下所示:

其实也就是蛇形字符串但端点不重复的情况

我们按行输出的结果是 : “PAHNAPLSIIGYIR”

条件是方法中传入一个字符串 s ,一个行数要求 numRows

string convert(string s, int numRows);

举例

1:

输入: s = “PAYPALISHIRING”, numRows = 3

输出: “PAHNAPLSIIGYIR”

2:

输入: s = “PAYPALISHIRING”, numRows = 4

输出: “PINALSIGYAHRPI”

解释:

解法一:Sort by Row

我们可以定义一个List 元素是StringBuilder类型, 代表着每一行的字符串,再通过定义两个标志为当前行curRow和换行方向goingDown,当到第一行和最后一行时改变方向(从上到下和从下到上)

复杂度分析：

时间复杂度 : O(n) 都是一次遍历

空间复杂度: O(n).

解法2: Visit by Row

因为我们所取的每一行字符串是有规律的写入的，,P A Y P A L 可以看作一个循环规律为2n-2,可以按2n-2来添加字符串

复杂度分析：

时间复杂度 : O(n) 我们对给定的字符串s中的每个字符s.charAt()只访问一次

空间复杂度: O(n).

注：

1.substring() string 是小写；

小白刷题之路,请多指教— — 要么大器晚成,要么石沉大海