Java算法练习—— Z 字形变换

迈不过友情╰ 2021-12-21 15:25 137阅读 0赞

# [题目链接][Link 1] #

# 题目描述 #

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

L   C   I   R
    E T O E S I I G
    E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

## 示例 1 ##

输入: s = "LEETCODEISHIRING", numRows = 3
    输出: "LCIRETOESIIGEDHN"

## 示例 2 ##

输入: s = "LEETCODEISHIRING", numRows = 4
    输出: "LDREOEIIECIHNTSG"
    解释:
    
    L     D     R
    E   O E   I I
    E C   I H   N
    T     S     G

# 题解 1 (按行排序) #

public String convert(String s, int numRows) { if (numRows == 1) return s; List<StringBuilder> rows = new ArrayList<>(); for (int i = 0; i < Math.min(numRows, s.length()); i++) rows.add(new StringBuilder()); int curRow = 0; boolean goingDown = false; for (char c : s.toCharArray()) { rows.get(curRow).append(c); // 按行存值 if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown; // 转向,很独特的方法,学到了 curRow += goingDown ? 1 : -1; // 递增或递减 } StringBuilder ret = new StringBuilder(); for (StringBuilder row : rows) ret.append(row); // 拼接字符串 return ret.toString(); }

## 复杂度分析 ##

*  时间复杂度：$O(n)$，其中$ n==len(s)$
 *  空间复杂度：$O(n)$

# 题解 2 (按行访问) #

public String convert(String s, int numRows) { if (numRows == 1) return s; StringBuilder ret = new StringBuilder(); int n = s.length(); int cycleLen = 2 * numRows - 2; // 一个循环的长度 for (int i = 0; i < numRows; i++) { for (int j = 0; j + i < n; j += cycleLen) { ret.append(s.charAt(j + i)); if (i != 0 && i != numRows - 1 && j + cycleLen - i < n) ret.append(s.charAt(j + cycleLen - i)); } } return ret.toString(); }

## 复杂度分析 ##

*  时间复杂度：$O(n)$，其中 $n==len(s)$。每个索引被访问一次。
 *  空间复杂度：$O(n)$。
    
    ## 手记 ##
    
    两种方法都不错，尤其是第一种。  
    可惜我个菜鸡，自己写了半天超内存是最难受的。

转载于:https://www.cnblogs.com/mxwbq/p/10941338.html

[Link 1]: https://leetcode-cn.com/problems/zigzag-conversion/