首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

刷题之路第六题-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 是小写;

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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190411A0C3HB00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券