【LeetCode】6. ZigZag Conversion

1.题目

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 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I

2.分析

题目是对给定的一个字符串以及一个行数,对该字符串进行以倒Z形排列,然后将字符串输出。仔细观察,可以看出按照要求,把字符进行排列是有一定规律的,s = “PAYPALISHIRING”,numRows = 4为例,如下图有:

可以看出,是有单元划分的,每一个单元就是$2 \times numRows-2$,减去2,是因为,每个单元的首列会占据整列,后面的不会占据首行和末行。

3.程序实现

public class ZigZagConversion {
    public String convert(String s, int numRows) {
        if(numRows <= 1 ) return s;
        StringBuilder[] sb = new StringBuilder[numRows];
        // 初始化
        for ( int i = 0; i < sb.length; i++) sb[i] = new StringBuilder("");
        for ( int i = 0; i < s.length() ;i++){
            int index = i %(2 * numRows - 2);            // 获取每个单元数
            index = index < numRows ? index : 2 * numRows - 2 - index;  // 解决超过行数的元素的问题
            sb[index].append(s.charAt(i));              // 对应行数的内容添加
        }
        // 把除第一行意外的数据都放在第一行,便于输出
        for ( int i = 1; i< sb.length; i++) sb[0].append(sb[i]);
        return sb[0].toString();
    }
    @Test
    public void test(){
        ZigZagConversion zzc = new ZigZagConversion();
        System.out.println(zzc.convert("abcdefg",3));
    }
}

在程序实现中,我们需要注意的是StringBuilder的使用,可以参考官方文档,其和StringBuffer有很多的相似之处,StringBuilder的速度比StringBuffer快,但是,StringBuilder是线程不安全的,不适合做并发,StringBuffer是线程安全的。

4.程序分析

使用了多次单循环,时间复杂度为$O(n)$,由于时间StringBuilder,其时间复杂度也为$O(n)$.

5.个人订阅号

第一个订阅号侧重于:使用c/c++/java去实现一些经典算法,以及javaEE开发,Linux服务器操作等。第二个订阅号主要侧重于机器学习,深度学习,数学,自然语言处理等方面的知识。







 上一篇
【LeetCode】7. Reverse Integer 【LeetCode】7. Reverse Integer
1.题目Given a 32-bit signed integer, reverse digits of an integer. Example 1: Input: 123 Output: 321 Example 2: Input: -12
2019-01-29
下一篇 
如何使用python将多个png图片转为gif 如何使用python将多个png图片转为gif
前言最近遇到一个问题是,画了一个过程的图,为了更生动地展示出来,于是就想把这几张图合成一个gif图片,这样起来应该是不错的,于是在网上搜索了一些关于python如何将一些png图片转为gif的程序,自己实现更改如下。 环境准备系统:win1
2019-01-27
  目录