云浮 网站建设免费网络营销平台
leetcode算法每天一题006
题目描述
-
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行N 字形排列，输出正常顺序的结果。
-
比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R
暴力解法（用二维向量存储重排的结果，然后正序读取出来）
c++
class Solution {
public:string convert(string s, int numRows) {int column = 7000;const int n = numRows;string res;vector< vector<char> > asd1(numRows, vector<char>(column, 0)); //初始化row*column二维动态数组，初始化值为0if(n==1){return s;}if(n==2){for(int i=0;i<s.size();i++){if(i%2==0){asd1[0][i/2]=s[i];}else{asd1[1][i/2 + 1 ] = s[i];}}}if(n>2){for(int i=0;i<s.size();i++){if(i%(2*n-2)<n){asd1[i%(2*n-2)][(i/(2*n-2))*(n-1)]=s[i];}else{asd1[((n-1)-((i%(2*n-2))-n ))-1][(i/(2*n-2))*(n-1) + (i%(2*n-2))-n+1 ] = s[i];}//((i%(2*n-2))-n ) 是在[n,n-1]的n-2个元素中的排序}}for(int tn=0;tn<numRows;tn++){for(int m=0;m<7000;m++){if(asd1[tn][m]!= 0){res.push_back(asd1[tn][m]);}}}return res;}
};
class Solution {
public:string convert(string s, int numRows) {int column = 0;const int n = numRows;string res="";vector< vector<char> > asd1(numRows, vector<char>(column, 0)); //初始化row*column二维动态数组，初始化值为0int flag = 0;for(int i=0,row=0;i<s.size();i++){asd1[row].push_back(s[i]);if( row == 0 || row == numRows-1 ) flag = !flag;row += flag ? 1:-1;}for(int tn=0;tn<numRows;tn++){for(int m=0;m<asd1[tn].size();m++){res.push_back(asd1[tn][m]);}}return res;
}
};
c++(动态数组直接存储)
class Solution {
public:string convert(string s, int numRows) {int column = 0;const int n = numRows;string res="";if(numRows==1) return s;vector< vector<char> > asd1(numRows, vector<char>(column, 0)); //初始化row*column二维动态数组，初始化值为0int flag = 0;for(int i=0,row=0;i<s.size();i++){asd1[row].push_back(s[i]);if( row == 0 || row == numRows-1 ) flag = !flag;row += flag ? 1:-1;}for(int tn=0;tn<numRows;tn++){for(int m=0;m<asd1[tn].size();m++){res.push_back(asd1[tn][m]);}}return res;
}
};
java java中的动态数组ArrayList
class Solution {public String convert(String s, int numRows) {int column = 0;int n = numRows;if(numRows==1) return s;//特殊情况StringBuilder[] stringLine = new StringBuilder[numRows];for (int i = 0; i < stringLine.length; i++) {stringLine[i] = new StringBuilder();}boolean flag = false;for(int i=0,row=0;i<s.length();i++){stringLine[row].append(s.charAt(i));if( row == 0 || row == numRows-1 ) {flag = (!flag);}row += flag ? 1:-1;}StringBuilder res = new StringBuilder();for (int i = 0; i < stringLine.length; i++) {res.append(stringLine[i]);}return res.toString();}
};
其他方法
StringBuilder 类在 Java 5 中被提出，它和 StringBuffer 之间的最大不同在于 StringBuilder 的方法不是线程安全的（不能同步访问）。
【数据结构和算法】LeetCode 6. Z 字形变换