LeetCode 6Z字形变换
400 Words|Read in about 2 Min|本文总阅读量次
leetcode第6题，采用动态规划的算法来完成。
Z字形变换
问题描述
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：(这里用#表示空格加以区分)
L # C # I # R # E T O E S I I G E # D # H # N #
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“LCIRETOESIIGEDHN”。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1:
输入: s = “LEETCODEISHIRING”, numRows = 3 输出: “LCIRETOESIIGEDHN”
示例 2:
输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3：
输入: s = “LEETCODEISHIRING”, numRows = 4 输出: “LDREOEIIECIHNTSG” 解释: L # # D # # R E # O E # I I E C # I H # N T # # S # # G
思路1：遍历法
这里以c/c++语言来具体化
具体思路开始（可以参考下面几幅图）
-
创建一个字符串的动态数组vector < string > str(min(int(s.length()),numRows))，用来存放numRows个元素
-
循环时，动态数组的行数增加或减小，设置一个flag值用于转换方向，设置一个i值用于累加行数，判断如果i为0或者i为numRows-1，flag反值，继续叠加（叠加不一定是正叠加，可能是负叠加）
-
遍历字符串的动态数组
代码
1/*
2直接遍历,遍历的过程中输出添加到vector<string> str
3*/
4class Solution {
5public:
6 string convert(string s, int numRows) {
7 //边界条件
8 if(numRows==1) return s;
9 int i=0;
10 bool flag=false;
11 string tmp;
12 vector<string> str(min(int(s.length()),numRows));//强制转换s.length()为int
13 for(char c:s)//c为当前元素，遍历整个s
14 {
15 str[i]+=c;
16 if(i==0||i==numRows-1) flag=!flag;
17 i+=flag?1:-1;
18 }
19 for(string ss:str)
20 tmp+=ss;
21 return tmp;
22 }
23};
思路2：找规律
- 很明显可以查找到规律，第一行和最后一行的间距都是2*numRows-2
- 其他的行，都会出现两次辗转累加的过程，而两次累加和为2numRows-2，例如第i行，第二个数比第一个数多2numRows-2-2i，第三个数则比第二个数多2i
- 设置一个flag用来判断辗转
代码
1/*
2找规律
3*/
4class Solution {
5public:
6 string convert(string s, int numRows) {
7 //临时变量,用于存放新数组
8 string tmp;
9 int i,j;
10 bool flag=true;//除第一行最后一行都会辗转相加
11 //判断边界条件
12 if(s.length() < numRows) return s;
13 else if(numRows == 1) return s;
14 else if(numRows == 2)//奇偶输出
15 {
16 for(i = 0;i < s.length();i += 2)
17 {
18 tmp.push_back(s[i]);
19 }
20 for(i = 1;i <s.length();i += 2)
21 {
22 tmp.push_back(s[i]);
23 }
24 return tmp;
25 }
26 else //一般情况
27 {
28 for( i=0;i<numRows;i++)
29 {
30
31 if(i == 0)
32 {
33 for(j=i;j<s.length();j+= numRows*2-2)
34 tmp.push_back(s[j]);
35 }
36 else if(i == numRows-1)
37 {
38 for(j=i;j<s.length();j+= numRows*2-2)
39 tmp.push_back(s[j]);
40 }
41 else//其他的位置
42 {
43 flag=true;//下一行自动为true
44 tmp.push_back(s[i]);//第一列第一个数
45 j=i;
46 while(j<s.length())
47 {
48 if(flag)
49 {
50 flag=false;
51
52 j+= numRows*2-2-2*i;
53 if(j>=s.length()) break;
54 tmp.push_back(s[j]);
55
56 }
57 if(!flag)
58 {
59 flag=true;
60
61 j+= 2*i;
62 if(j>=s.length()) break;
63 tmp.push_back(s[j]);
64
65 }
66 }
67 }
68 }
69
70 }
71 return tmp;
72 }
73};
如果本文对宝宝打开思路有帮助，可以点个赞哦~