6. ZigZag Conversion-白红宇

6. ZigZag Conversion

阅读量：2352 次

发布时间：2019-05-10

本文共 2577 字，大约阅读时间需要 8 分钟。

题目

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P A H N

A P L S I I G

Y I R

And then read line by line: “PAHNAPLSIIGYIR”

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example :

Input: s = “PAYPALISHIRING”, numRows = 4
Output: “PINALSIGYAHRPI”
Explanation:
P I N
A L S I G
Y A H R
P I

我的思路

找到了周期 $(n u m R o w s * 2 - 2)$ ，头行表示为 $k * (n u m R o w s * 2 - 2)$ 和尾行为 $k * (n u m R o w s * 2 - 2) + (n u m R o w s - 1)$ 。但在斜边的规律不太一样，作罢。

解答

leetcode solution1: sort by row

用curRow和goingDown两个游标来控制。当curRow为第一行或最后一行时，goingDown反向，由此直接按照Z顺序将s分行存入list中，最后合并成一行。

class Solution {
       public String convert(String s, int numRows) {
           if (numRows == 1) return s;        List
   
     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();    }}

leetcode solution2: visit by row

周期公式的解法，原来中间重叠的部分可以用两个公式来表达，

i

为当前行

k * (n u m R o w s * 2 - 2) + i

和

(k + 1) * (n u m R o w s * 2 - 2) - i

这样整个算法可以写为两个公式：

k * (n u m R o w s * 2 - 2) + i

(k + 1) * (n u m R o w s * 2 - 2) - i

//表示斜边上的元素

虽说空间复杂度更低，但是没有solution 1更加便于理解

class Solution {
       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();    }}

转载地址：http://zfqvb.baihongyu.com/

你可能感兴趣的文章