在网上哪个网站可以做兼职,最好免费高清影视,沧州网站建设网海申,网站前端模板下载Z字形变换原题地址
方法一#xff1a;利用二维矩阵模拟
对于特殊情况#xff0c;z字形变换后只有一行或只有一列#xff0c;则变换后的字符串和原字符串相同。
对于一般情况#xff0c;我们可以考虑按照题目要求#xff0c;把字符串按照Z字形存储到二维数组中#xff…Z字形变换原题地址
方法一利用二维矩阵模拟
对于特殊情况z字形变换后只有一行或只有一列则变换后的字符串和原字符串相同。
对于一般情况我们可以考虑按照题目要求把字符串按照Z字形存储到二维数组中再横向遍历所有有效字符。
假设Z字形变换后的矩阵有r行字符串的长度为n。
Z字形变换是按照周期t先向下再向右上运动。一个周期tr(r-2)r*2-2。 其中r-2不包含两个红圈的位置。 一个周期t内的行数为r行列数为1(r-2)r-1列即最左边的一列以及中间的r-2列。矩阵的周期数为(n/t)向上取整即(nt-1)/t加上的t-1是为了向上取整。矩阵的总列数为周期数*每个周期的列数即c(nt-1)/t*(r-1)。
那么什么时候向下走什么时候向右上方走呢这要看当前处在周期的什么位置。假设当前遍历到下标为i的字符如果imodtr-1即当前处在周期的前r-1个位置就需要向下走否则就要向右上方走。
// 方法一利用二维矩阵模拟
class Solution {
public:string convert(string s, int numRows) {int n s.size();int r numRows; // 行数// 只有一行或者只有一列if (r 1 || r n)return s;// 周期trr-2int t r * 2 - 2;// 一共有 (n/t)向上取整 个周期// 即(nt-1)/t个周期// 每个周期有1r-2r-1列int c (n t - 1) / t * (r - 1); // 列数// 构造矩阵即r个string的数组每个string的长度为cvectorstring mat(r, string(c, 0));int x 0, y 0; // 左上角for (int i 0; i n; i){mat[x][y] s[i];// 周期前r-1次都是向下移动// 否则向右上方移动if (i % t r - 1){x;}else{--x;y;}}string ans;// 拼接每行有效字符for (auto row : mat){for (auto ch : row){if (ch)ans ch;}}return ans;}
};
方法二压缩矩阵空间
模拟时可以不按照Z字形存储到矩阵中而是根据当前字符在第几行就存储在该行的最后一个位置即尾插到当前行。这样的话可以节省矩阵的空间。
如果采用这种方案就只需要考虑是向下走还是向上走。按照相同的思路当imodtr-1即当前周期的前r-1个字符需要向下走反之就向上走。
// 方法二压缩矩阵空间
class Solution {
public:string convert(string s, int numRows) {int n s.size();int r numRows; // 行数// 只有一行或只有一列if (r 1 || r n)return s;vectorstring mat(r);// 周期trr-2int t r * 2 - 2;int x 0; // 在第几个string后面添加字符for (int i 0; i n; i){mat[x] s[i];// 每个周期前r-1次向下移动if (i % t r - 1)x;else--x;}string ans;// 拼接所有行for (auto row : mat){ans row;}return ans;}
};
方法三方法二的另一种写法
在考虑是向下走还是向上走时可以不用计算在当前周期的第几个位置而是直接判断当前所处位置是否在最上面还是最下面。也就是说如果当前在第x行若x1或者xr-1说明要转向本来是向下走就要转为向上走本来是向上走就要转为向下走。
我们可以定义一个flag如果flag1代表向下走flag-1代表向上走每次只需要xflag就能求出新的所在行x了。如果要转向只需执行flag-flag。
// 方法三方法二的另一种写法利用flag记录何时转向
class Solution {
public:string convert(string s, int numRows) {int n s.size();int r numRows; // 行数// 只有一行或只有一列if (r 1 || r n)return s;vectorstring mat(r);int x 0; // 在第几个string后面添加字符int flag 1; // 行转向标志1代表向下走-1代表向上走for (int i 0; i n; i){mat[x] s[i];x flag;// 转向if (x r - 1 || x 0)flag -flag;}string ans;// 拼接所有行for (auto row : mat){ans row;}return ans;}
};
方法四直接构造
前三种方法都需要构造一个新的矩阵来模拟我们可以考虑直接构造也就是直接取出原字符串的字符来构造ans字符串。这就需要找出Z字形变换的规律看图 按照“Z字形”的顺序来看就是0-1-2-3-...-t-2-t-1-t-t1-t2-...-2t-2-2t-1-2t-2t1-2t2-...
如果我们横着看呢 我们用i来控制行i从0递增到r-1。再用j控制列j从0开始每次递增t也就是0,t,2t,3t,...。那么下图中每个周期都是线方框线是ij框柱的是jt-i。 对于每一行都有线但是第0行和第r-1行没有方框内的元素利用这点直接构造字符串即可。
// 方法四直接构造
class Solution {
public:string convert(string s, int numRows) {int n s.size();int r numRows; // 行数// 只有一行或只有一列if (r 1 || r n)return s;string ans;// 周期trr-2int t r * 2 - 2;for (int i 0; i r; i){for (int j 0; j i n; j t){// 当前周期第一个字符ans s[j i];// 若不是第一行和最后一行还有第二个字符if (0 i i r - 1 j t - i n)ans s[j t - i];}}return ans;}
};
