算法日常・每日刷题--＜模拟＞3

6. Z 字形变换 - 力扣LeetCode6. Z 字形变换 - 将一个给定字符串 s 根据给定的行数 numRows 以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 PAYPALISHIRING 行数为 3 时排列如下P A H NA P L S I I GY I R之后你的输出需要从左往右逐行读取产生出一个新的字符串比如PAHNAPLSIIGYIR。请你实现这个将字符串进行指定行数变换的函数string convert(string s, int numRows); 示例 1输入s PAYPALISHIRING, numRows 3输出PAHNAPLSIIGYIR示例 2输入s PAYPALISHIRING, numRows 4输出PINALSIGYAHRPI解释P I NA L S I GY A H RP I示例 3输入s A, numRows 1输出A 提示 * 1 s.length 1000 * s 由英文字母小写和大写、, 和 . 组成 * 1 numRows 1000https://leetcode.cn/problems/zigzag-conversion/description/题目描述将一个给定字符串s根据给定的行数numRows以从上往下、从左到右进行Z 字形排列。比如输入字符串为PAYPALISHIRING行数为 3 时排列如下P A H N A P L S I I G Y I R之后你的输出需要从左到右逐行读取产生一个新的字符串比如PAHNAPLSIIGYIR。请你实现这个将字符串进行指定行数变换的函数解法:模拟找规律我们先用下标来代替具体数字,更好的找到规律找规律 按行遍历观察 Z 字形排列可以发现一个周期以 numRows 4 为例 第0行: 0 6 12 18 第1行: 1 5 7 11 13 17 第2行: 2 4 8 10 14 16 第3行: 3 9 15 周期 d 2 * numRows - 2 6第一行和最后一行数字的变换都是再前面一个,数字的基础上加上一个公差第一行:kd第n-1行:(n-1)kd;非第一行和最后一行将两个两个看成一组,都是每一组相对应的位置上的数加上公差d,可以发现组的两个数相加恰好为公差{ikd , d-ikd}找到规律,我们按行开始填写即可#includestring class Solution { public: string convert(string s, int numRows) { if (numRows 1 || s.empty()) return s; //计算公差d int d2*numRows-2; int ns.size(); string s1; int kn/numRows1; for(int j0;jk;j) { if(j*dn) s1s[j*d]; } for(int i1;inumRows-1;i) for(int j0;jk;j) { if(ij*dn) s1s[ij*d]; if(d-ij*dn) s1s[d-ij*d]; } for(int j0;jk;j) { if(numRows-1j*dn) s1s[numRows-1j*d]; } return s1; } };