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 是小写;
小白刷题之路,请多指教— — 要么大器晚成,要么石沉大海
领取专属 10元无门槛券
私享最新 技术干货