用旧技术做网站能过毕设么知乎,一米八效果图网站,个人信息怎么在百度推广,南宁网站建设托管题目链接#xff1a;6. Z 字形变换 - 力扣#xff08;LeetCode#xff09;
普通版本#xff08;二维矩阵的直接读写#xff09; 解决办法#xff1a;直接依据题目要求新建并填写一个二维数组#xff0c;最后再将该二维数组中的有效字符按从左到右、从上到下的顺序读取并…题目链接6. Z 字形变换 - 力扣LeetCode
普通版本二维矩阵的直接读写 解决办法直接依据题目要求新建并填写一个二维数组最后再将该二维数组中的有效字符按从左到右、从上到下的顺序读取并放到新数组中 分析1当我们在矩阵上填写字符时会先向下填写 r 个字符然后向右上继续填写 r−2 个字符最后回到第一行 结论1Z 字形变换的周期 t r r − 2 2r − 2一个残缺的斜着的v每个周期会占用矩阵上的1 r - 2 r − 1列 结论2总周期数 n总字符数/ t向上取整总列数c n / t * r - 1 结论3新建二维数组的行数为r列数为c 填写操作设当前填写的位置为(x,y)即矩阵的第 x 行的第 y 列初始 (x,y)(0,0)矩阵左上角若当前字符下标 i 满足 i mod t r − 1则向下移动否则向右上移动
class Solution {
public:string convert(string s, int numRows) {int n s.length(), r numRows;if (r 1 || r n) {return s;}int t r * 2 - 2;//一个周期中的个数//一个周期中的列数 (r - 1)int c (n t) / t * (r - 1);//总列数 周期个数 * 一个周期的列数周期个数 总个数 / 一个周期中的个数//如果总个数只是单纯的n的话可能会导致不满一个周期的字符不被计算在内且不被算在内的情况有多1、2、3个三种情况//而我们只需要在一个完整的总个数中再加上一个周期的个数即可这样就可以将多出来的元素也算入一个新周期尽管可能有空位但无所谓了vectorstring mat(r, string(c, 0));//创建一个r行、每行长度为c即c列的二维字符串数组mat并初始化每个位置的字符为0for (int i 0, x 0, y 0; i n; i) //先从二维数组的左上角开始填写,先填写后判断下一次要填写的方向{//因为是先插入后判断的所以判断时已经插入一个了因此能继续向下移动的次数为r-1次mat[x][y] s[i];if (i % t r - 1 ) //下标i是逐渐递增因此要%t重新映射原字符串中下标为i的字符在新周期中的位置相当于在新周期中已经走了几次了{//已经走的次数要小于该周期中向下可以走的次数-1否则就是向右上走x; // 向下移动} else{ --x;y; // 向右上移动}}string ans;//遍历二维数组将非空的位置的字符插入新stringfor (auto row : mat) {for (char ch : row) {if (ch) {ans ch;}}}return ans;}
};
时间复杂度ON创建数组的时间复杂度为O(r * c)填充数组的时间复杂度为O(N)构造最最终结果的时间复杂度为O(r * c)由于 r * c 和 n 都是输入规模 n 的线性函数我们可以认为时间复杂度是 O(n)
空间复杂度ONstring ans 用来存储结果字符串占用了 O(n) 的空间
优化版本压缩矩阵空间待补充
优化版本直接构造待补充
~over~
