C++实现LeetCode(6.字型转换字符串)

这篇文章主要介绍了C++实现LeetCode(6.字型转换字符串),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下

C++实现LeetCode(6.字型转换字符串),恰卡网带你了解更多相关信息。

[LeetCode] 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   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\”

Example 2:

Input: s = \”PAYPALISHIRING\”, numRows = 4
Output: \”PINALSIGYAHRPI\”
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I

这道题刚开始看了半天没看懂是咋样变换的,上网查了些资料,终于搞懂了,就是要把字符串摆成一个之字型的,比如有一个字符串 \”0123456789ABCDEF\”,转为 zigzag 如下所示:

当 n = 2 时:

0 2 4 6 8 A C E

1 3 5 7 9 B D F

当 n = 3 时:

0   4    8     C

1 3 5 7 9 B D F

2    6   A     E

当 n = 4 时:

0     6        C

1   5 7   B  D

2 4   8 A    E

3      9       F

可以发现,除了第一行和最后一行没有中间形成之字型的数字外,其他都有,而首位两行中相邻两个元素的 index 之差跟行数是相关的,为  2*nRows – 2, 根据这个特点,可以按顺序找到所有的黑色元素在元字符串的位置,将他们按顺序加到新字符串里面。对于红色元素出现的位置(Github 上可能无法正常显示颜色,请参见博客园上的帖子)也是有规律的,每个红色元素的位置为 j + 2 x numRows-2 – 2 x i, 其中,j为前一个黑色元素的 index,i为当前行数。 比如当 n = 4 中的那个红色5,它的位置为 1 + 2 x 4-2 – 2 x 1 = 5,为原字符串的正确位置。知道了所有黑色元素和红色元素位置的正确算法,就可以一次性的把它们按顺序都加到新的字符串里面。代码如下:

解法一:

class Solution {public:    string convert(string s, int numRows) {        if (numRows <= 1) return s;        string res;        int size = 2 * numRows - 2, n = s.size();        for (int i = 0; i < numRows; ++i) {            for (int j = i; j < n; j += size) {                res += s[j];                int pos = j + size - 2 * i;                if (i != 0 && i != numRows - 1 && pos < n) res += s[pos];            }        }        return res;    }};

若上面解法中的规律不是很好想的话,我们也可以用下面这种更直接的方法来做,建立一个大小为 numRows 的字符串数组,为的就是把之字形的数组整个存进去,然后再把每一行的字符拼接起来,就是想要的结果了。顺序就是按列进行遍历,首先前 numRows 个字符就是按顺序存在每行的第一个位置,然后就是 ‘之\’ 字形的连接位置了,可以发现其实都是在行数区间 [1, numRows-2] 内,只要按顺序去取字符就可以了,最后把每行都拼接起来即为所求,参见代码如下:

解法二:

class Solution {public:    string convert(string s, int numRows) {        if (numRows <= 1) return s;        string res;        int i = 0, n = s.size();        vector<string> vec(numRows);        while (i < n) {            for (int pos = 0; pos < numRows && i < n; ++pos) {                vec[pos] += s[i++];            }            for (int pos = numRows - 2; pos >= 1 && i < n; --pos) {                vec[pos] += s[i++];            }        }        for (auto &a : vec) res += a;        return res;    }};

到此这篇关于C++实现LeetCode(6.字型转换字符串)的文章就介绍到这了,更多相关C++实现字型转换字符串内容请搜索趣讯吧以前的文章或继续浏览下面的相关文章希望大家以后多多支持趣讯吧!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,请发送邮件至 55@qq.com 举报,一经查实,本站将立刻删除。转转请注明出处:https://www.szhjjp.com/n/2106.html

(0)
nan
上一篇 2021-07-10
下一篇 2021-07-10

相关推荐

  • 女生爱看的小说推荐云七念陆北深在线阅读-云七念陆北深完结

    陆北深这一走,便走了半月有余。云七念守在府中,一个人用膳,一个人看书。转眼到了除夕夜。大街小巷灯火通明,唯有陆府清冷萧瑟。云七念听见外面传来孩童的欢笑声和鞭炮声,有一瞬间失神。夜更深,喧嚣声渐静,她眸底的光也渐渐变得黯淡。在她落寞起身之际,外头传来脚步声。陆北深冷漠的身影踏着寒露进来,他冰冷的视线扫过桌上早已冰冷却丰盛的菜肴,微微蹙眉。“往后守岁不必等我。”云七念步子一滞,刚要开口,却蓦地闻到一股

    网络资讯 2023-05-11
    0
  • ubc是什么大学(ubc什么专业好)

    ubc是什么大学?ubc什么专业好,爱惜日带你了解相关信息。英属哥伦比亚大学,简称UBC,1908年成立,前身是麦吉尔大学不列颠哥伦比亚学院或者麦吉尔大学不列颠哥伦比亚分校(McGillUniversityCollegeofBritishColumbia),是不列颠哥伦比亚省历史最悠久的大学。于1915年成为独立的英属哥伦比亚大学,与麦吉尔大学,多伦多大学和皇后大学

    2021-08-14
    0
  • 空气能热泵零下10度制热效果(空气能热泵零下30度能用吗)

    大家好,相信大家对空气能热泵零下10度制热效果,空气能热泵零下30度能用吗的问题都很疑惑,这个问题很多人还不知道怎么解决,现在让我们一起来学习学习吧!一、空气能热泵零下30度能用吗低温型的可以,我国的北方冬季温度经常会达到负15到负20度,正常的采暖设施无法使用,因为它们没有防冻、低温制热、转换热的技术,而低温型热泵空气能采暖是针对这种情况设计的,能够在零下30度的环境下供热,而且热能的温度可以达

    2023-12-21
    0
  • 瓷肌产品多少钱一套 瓷肌美白套装多少钱

    想要呵护好肌肤,选择适合自己的护肤品是很重要的,不同的护肤品护肤的效果也不一样,不少人都用过瓷肌的护肤产品,特别是它们家的套装产品,很多妹子都非常喜欢,成为不少妹子护肤产品的首选,那瓷肌产品多少钱一套?瓷肌美白套装多少钱?1、瓷肌产品多少钱一套瓷肌针对不同的肤质,制定出了不同的护肤套餐价格也在100-500不等,而大家最喜欢的刺激美白退黑套装价格为358元每套,其实这个性价比还真的不错呢。瓷肌医生

    生活百科 2023-05-22
    0
  • win7管理工具命令(win7自带重装系统步骤)

    今天介绍Windows7提供大量的系统管理工具,如何设置审核账户登录事件。小伙伴们可能不一定了解,在Windows7操作系统中提供了大量的系统管理工具,例如任务管理器、事件查看器、性能监视器、设备管理器、磁盘管理器和虚拟机硬盘(virtualm

    2021-09-11 用户体验
    0
  • 2024户口不在武汉的小孩怎么上学 户口不在武汉小孩可以在武汉上学吗

    户籍不在武汉的小孩,其父母(或其他法定监护人)户籍必须在高新区或持有高新区有效居住证。2024秋季非武汉市户籍的适龄儿童在东湖高新新生入学范围:1、其父母(或其他法定监护人)户籍在高新区或持有高新区有效居住证,且自有房产。户籍或居住证地址与房产地址一致。2、其父母(或其他法定监护人)户籍在高新区或持有高新区有效居住证,随父母或其他法定监护人租住在服务范围内。户籍或居住证地址与实际居

    2024-01-02
    0

发表回复

登录后才能评论