河南网站建设首选公司,如何做汉服,什么伪原创网站好,godaddy空间建立wordpress目录
力扣6. Z 字形变换
解析代码 力扣6. Z 字形变换
6. Z 字形变换
难度 中等
将一个给定字符串 s 根据给定的行数 numRows #xff0c;以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 PAYPALISHIRING 行数为 3 时#xff0c;排列如下#xff…目录
力扣6. Z 字形变换
解析代码 力扣6. Z 字形变换
6. Z 字形变换
难度 中等
将一个给定字符串 s 根据给定的行数 numRows 以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 PAYPALISHIRING 行数为 3 时排列如下
P A H N
A P L S I I G
Y I R
之后你的输出需要从左往右逐行读取产生出一个新的字符串比如PAHNAPLSIIGYIR。
请你实现这个将字符串进行指定行数变换的函数
string convert(string s, int numRows);示例 1
输入s PAYPALISHIRING, numRows 3
输出PAHNAPLSIIGYIR示例 2
输入s PAYPALISHIRING, numRows 4
输出PINALSIGYAHRPI
解释
P I N
A L S I G
Y A H R
P I示例 3
输入s A, numRows 1
输出A提示
1 s.length 1000s 由英文字母小写和大写、, 和 . 组成1 numRows 1000
class Solution {
public:string convert(string s, int numRows) {}
}; 解析代码
暴力解法就是开一个n*len的二维数组填输出然后遍历这样时间空间复杂度都是ON^2
绝大部分模拟题的优化方法都是找规律先画出下面第一个图数字代表数组下标 通过第一个图发现每隔竖着的一列都能用一个公差d来计算公差d 2 * numRows - 2比如第一个图的公差d 2 * 4 - 2 6然后就发现完整竖列中间的下标和左边竖列下标加起来刚好等于d第k行一次遍历两个下标最后一行和第一行类似此时就能通过直接遍历数组的下标得到要返回的字符串
首先遍历第一行设下标为i要返回的字符串为ret原字符串为sret s[i d]; 然后遍历中间行设中间行为kk1knumRows -1要避免数组越界
ret s[ki d]; ret s[d-k d];ki dj k-dj d
最后遍历最后一行ret s[numRows-1 i];
class Solution {
public:string convert(string s, int numRows) {if(numRows 1) // 处理边界return s;string ret;int n s.size(), d 2 * numRows - 2;for(int i 0; i n; i d) // 处理第一行{ret s[i];}for(int k 1; k numRows-1; k) // 处理中间行{for(int i k, j d-k; i n || j n; i d, j d){ // i n 和 j n都要加到ret里if(i n)ret s[i];if(j n)ret s[j];}}for(int i numRows-1; i n; i d) // 处理最后一行{ret s[i];}return ret;}
};
