Z字形变换

大家好，欢迎来到IT知识分享网。

Z字形变换

• direction模拟
• 本文介绍的算法直观明了，给出1个固定的解题思路。（如螺旋矩阵也是direction解题思路）

题目描述

将一个给定字符串 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); 

C++实现

class Solution { public: string convert(string s, int numRows) { if (numRows == 1) { return s; } vector<string> dp(numRows); vector<int> direction = {1, -1}; int step = 0; int row = 0; for (const auto & e : s) { dp[row].push_back(e); int nextRow = row + direction[step]; if (nextRow < 0 || nextRow >= numRows) { step = (step+1)%direction.size(); } row += direction[step]; } string res; for (const auto & e : dp) { res += e; } return res; } }; 

golang实现

func convert(s string, numRows int) string { if numRows == 1 { return s } direction := []int{1, -1} step := 0 dp := make([][]byte, numRows) row := 0 for _, v := range s { dp[row] = append(dp[row], byte(v)) nextRow := row + direction[step] if nextRow < 0 || nextRow >= numRows { step = (step+1)%len(direction) } row += direction[step] } res := []byte{} for _, v := range dp { res = append(res, v...) } return string(res) }