Leetcode 6. ZigZag Conversion

xiaoxiao2021-03-01  24

6. ZigZag Conversion

题目描述

将一个字符串以Z字形输出,这么说可能不太清楚,看一下下面的例子就知道了,给定一个源字符串,然后和Z字的大小(就是每一笔用几个字母组成),输出Z字形的字符串。

源字符串 Z字大小

PAYPALISHIRING size:3

输出下面图形按行排列的顺序

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

最后的返回是没有空格和换行的,就是将上面的Z字形从第一行到最后一行从左到右的顺序输出。 也即返回:

PAHNAPLSIIGYIR

思路

最开始的想法是想用数学关系式的方式,计算出映射关系然后再来编程输出。 后来一边编写程序之后,逐渐思路转移到了通过第一行的顶点前移后移来推出其他的值。然后后面还有字符串长度的影响,我用了补全它的想法,补成特殊的形状,然后再删除我补进去的字符。 应该是一个比较有意思的题目了,让我想起某个输出666的笔试题。

代码

class Solution { public: string convert(string s, int numRows) { int len = s.size(); // 字符串长度 int size = numRows * 2 - 2; // 一个Z字形重复单元 if (len <= numRows || numRows == 1) return s; // 长度小于一划直接返回 string result; // 保存结果的字符串 int n = len / (size) + 1; // Z字形重复单元的数量 int w = len % (size); // 字串长度多出一个单元的数量后面补齐用到 if (1) { for (int i = 0; i < 3 * size - w; i++) s.push_back('%'); // 补齐成倍数 } int top[n + 1]; //保存第一行的顶点,后面要根据他们来获得第二行到第N行的字符 // 计算第一行代码 for (int i = 0; i <= n; i++) { top[i] = size * i; result.push_back(s[size * i]); } cout << endl; // 推算第二行到Row减一 for (int j = 1; j < numRows - 1; j++) { int i = 0; result.push_back(s[top[i] + j]); result.push_back(s[top[i] - j]); result.push_back(s[top[i] + j]); } } // 推算最后一行 for (int i = 0; i < n; i++) { char c = s[size * i + numRows - 1]; if (c == 0) break; result.push_back(c); } // 去除我们补齐用到的字符 string::iterator iter = result.begin(); while (iter != result.end()) { if (*iter == '%') { result.erase(iter); } else { iter++; } } return result; } };
转载请注明原文地址: https://www.6miu.com/read-4200300.html

最新回复(0)