做电影网站配什么公众号,模具外贸网站建设,网游推广,开发定制软件模拟算法题往往不涉及复杂的数据结构或算法#xff0c;而是侧重于对特定情景的代码实现#xff0c;关键在于理解题目所描述的情境#xff0c;并能够将其转化为代码逻辑。所以我们在处理这种类型的题目时#xff0c;最好要现在演草纸上把情况理清楚#xff0c;再动手编写代… 模拟算法题往往不涉及复杂的数据结构或算法而是侧重于对特定情景的代码实现关键在于理解题目所描述的情境并能够将其转化为代码逻辑。所以我们在处理这种类型的题目时最好要现在演草纸上把情况理清楚再动手编写代码
1. Z字形变换
6. Z 字形变换 - 力扣LeetCode 对这道题最容易想到的肯定是创建一个二维数组像题目描述的那样以Z字形填充数组然后再遍历一遍数组得到结果序列。然而这种做法比较复杂而且时空复杂度都是比较高的所以我们便来试着优化一下找到更优秀的解法。一般而言模拟题的优化往往都是根据找到的规律来编写代码这道题也不例外。 由于题目最后仅要求我们写出经过Z字形变换后得到的序列所以我们其实是不需要真的创建数组的只要能找到每一行的变换规律编写代码把每一行都加到要返回的字符串中就行了。 为了方便画图我们画的是要填入的字符串的下标通过下图我们可以发现图形中的第0行和最后一行填入的数规律是差不多的假设公差为d
则第0行0d2d……
最后一行n-1n-1dn-12d…… 对于第一行和最后一行用简单的数列知识就能得出d为2*n-2至于中间的n-2行看起来似乎有些复杂但我们根本就没必要理会填入的元素在二维数组中的位置只要知道它们的值就行了所以注意观察数值规律不难发现每一行的元素实际上可以被划分为两个数列的元素 那么现在我们已经可以找到了每一行的元素的规律代码实现也就压根不需要二维数组了希望大家看到这里可以尝试根据算法原理自行编写一下代码然后再来看答案。
class Solution {
public:string convert(string s, int numRows) {if(numRows 1) return s;int d 2 * numRows - 2;int r0 0, rn numRows - 1;string res;while(r0 s.size()){res s[r0];r0 d;}for(int k 1; k numRows - 1; k){for(int i k, j d - k; i s.size() || j s.size(); i d, j d){if(i s.size()) res s[i];if(j s.size()) res s[j];}}while(rn s.size()){res s[rn];rn d;}return res;}
};
