第十八天LeetCode刷题-算法

第十八天习题——对给定字符的 Z 字形变换

此题仅为个人总结参考，如有错误还请指出

首先先上原题：

来源：力扣（LeetCode）
原题链接：https://leetcode-cn.com/problems/zigzag-conversion/

在看到题之出，也许能够立刻想到的方法便是通过对字符坐标位置的坐标位置寻找规律以此来寻找在对应Z形字符的坐标位置。通过题目所给定的两个示例我们不难发现：在给定对应列下标能被指定总行数整除的列中，所有的元素都会被按顺序放满。而在当列到下一个能被指定行数整除的列之间，每一列的元素放置位置是依次从倒数第二行开始以此上升，直到倒数第numRows-1行的位置。所以，我们可以得到一个规律总结式，即除了列下标能被指定行数整除的列以外，其他列数的元素放置位置都一定遵循：col % (numRows - 1) = element’s position 。根据此规律排序完所有字符后，我们再依次按行读取各字符即可。该思想具体的实践过程可参考方法1。

方法1——暴力破解法（基于z字形坐标规律的字符串排列过程）

class Solution:def convert(self, s: str, numRows: int) -> str:# 特处if len(s) <= numRows or numRows == 1:return s# 初始化z行字符串的内存空间z_str = [["" for _ in range(len(s))] for _ in range(numRows)]col = i = 0# 循环结束的条件是字符串的循环完毕while i < len(s):# 列下标能被整除的列直接按顺序填满即可if col % (numRows - 1) == 0:for row in range(numRows):if i >= len(s):breakz_str[row][col] = s[i]i += 1# 针对其他不能被整除的列下标else:z_str[numRows - 1 - col % (numRows) - 1][col] = s[i]i += 1col += 1# 结果串的处理result = ""for i in range(numRows):for j in range(len(z_str[i])):if z_str[i][j] != "":result += z_str[i][j]return result

该方法的复杂度分析：
时间复杂度：O(n^2) (涉及对整个二维列表的遍历)
空间复杂度：O(n^2) （开辟了一个对应的二维数组）

该算法在执行器里面的消耗内存空间和时间开销如下图所示：

方法2——优化解法（基于flag转向标志位的字符串排列过程）

思想：通过对第一种方法的解析，我们可以得知：要实现对字符串的z字形排列，最关键的点便在于对能被整除的列下标进行适当的转角工作。通过完成适当的转角工作来以此实现对字符串的排列。而基于此，我们可以通过设定一个flag标志位来实现对转角标志的判定。当 i=0 时，我们以此向下排列元素，此时flag = 1。而当 i = numRows - 1 时，我们将flag设置为 - 1 来实现对字符串的转向操作。而在储存元素方面，我们则可以通过只设定一个拥有 numRows 行的列表来完成对结果中每行元素的存储。然后将每行所保存的结果进行拼接即可得到对应的所求的结果。该方法的具体操作流程如下代码所示。

class Solution:def convert(self, s: str, numRows: int) -> str:# 特处if numRows < 2:return s# 对结果列表的初始化result = ["" for _ in range(numRows)]i, flag = 0, -1for c in s:result[i] += c# 标志位的转换条件if i == 0 or i == numRows - 1 :flag = - flagi += flagreturn "".join(result)

该方法的复杂度分析：
时间复杂度：O(n) (仅涉及对整个字符串的遍历)
空间复杂度：O(n) （开辟了一个numRows行的一维列表）

该算法在执行器里面的消耗内存空间和时间开销如下图所示：

总结

从此题我们可以看出，我们通过对字符串排序中抽象规律的抽取，分别利用flag标志位和一个numRows行的一维列表来分别完成转角标志的判定和对结果的直接存取操作。从而间接上实现了对算法效率的提升。这便是算法的精妙所在。