文档章节

LeetCode ZigZag Conversion

cindy_han
 cindy_han
发布于 2017/04/19 12:40
字数 612
阅读 11
收藏 1

刚开启LeetCode刷题之旅,看每道题都感觉不怎么会,仔细想了很久,结合别人博客给的答案,写一些自己的理解。

首先,这道题只需要考虑字符串下标的变换问题,不需要把变型后的形式输出,这就稍微降低了一些困难,所以多写几种类型的就很容易找出规律。

"PAYPALISHIRING" 3行的话

0P    4A    8H     12N
1A 3P 5L 7S 9I 11I 13G
2Y    6I   10R

变成4行的话

0P      6I        12N
1A   5L 7S    11I 13G
2Y 4A   8H  10R
3P      9I

我们想象把整个Z字压缩一下,左右向中间挤,很容易发现从第0列开始计数的话,奇数列的第一行和最后一行都会比偶数列少一个数。最上和最下行的相邻的两个字符的坐标都是相差为2*row-2,比如第0行第0列的P坐标为0,该行中下一个坐标的字符I的坐标为0+2*4-2=6,以此类推。

然后看中间行,需要通过讨论列的奇偶性来找规律。当所要计算的字符的列为奇数时,我们可以发现,第i行该字符与它前一个字符的坐标相差2*(row-1-i)(其中row-1是为了与行数列数从0开始保持一致)举个例子,第一行第0列的A下标为1,则与它相邻的L在第1列(奇数列中)下标为1+2*(row-1-1)=5。当所要计算的字符所在的列为偶数时,第i行该字符与它前一个字符坐标相差2*i。举例:第1行第一列的L下标为5,它下一个字符在第二列(偶数列)所以下标为5+2*1=7。

还要讨论边界条件,当row=1的时候应该返回原字符串

当row<1或者字符串为空的时候,要返回空字符串。

根据以上便可以写出代码(java):

public class Solution {
    public static String convert(String s, int numRows) {
        if(s == null || s.length() == 0 || numRows <= 0 ){
            return "";
        }
        if(numRows == 1){
            return s;
        }
        String res = "";
        int len = s.length();
        for(int i = 0; i < len && i < numRows; i++){
            int index = i;
            res += s.charAt(index);
            for(int k = 1; index < len; k++){
                if(i == 0 || i == numRows-1){
                    index += 2 * numRows - 2;
                }else{
                    if((k & 0x1) == 1){
                        index += 2*(numRows - 1 - i);
                    }else{
                        index += 2*i;
                    }
                }
                if(index < len){
                    res += s.charAt(index);
                }
            }
        }
        return res;
    }
    public static void main(String[] args){
        String s = "PAYPALISHIRING";
        String res = convert(s,3);
        System.out.print(res);
    }

}

© 著作权归作者所有

cindy_han
粉丝 2
博文 1
码字总数 612
作品 0
大连
私信 提问
加载中

评论(3)

大光头兰翔
大光头兰翔

引用来自“cindy_han”的评论

引用来自“大光头兰翔”的评论

up是果果的小学弟吗?

回复@大光头兰翔 : 你猜我是谁呀
han。。。不会是涵姐吧我天
cindy_han
cindy_han

引用来自“大光头兰翔”的评论

up是果果的小学弟吗?

回复@大光头兰翔 : 你猜我是谁呀
大光头兰翔
大光头兰翔
up是果果的小学弟吗?
[leetcode] ZigZag Conversion

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 ......

jdflyfly
2014/06/24
0
0
LeetCode-ZigZag conversion

Zigzag Conversion Solution mind path We can notice that it has a pattern. Every zigzag pattern is composed by a list of structures.As of example 2, Let's write the zigzag positi......

Quan全
2018/07/10
0
0
Leetcode 6. ZigZag Conversion

版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn.net/Quincuntial/article/details/82747050 文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Descr...

SnailTyan
2018/09/17
0
0
6. ZigZag Conversion - LeetCode

LeetCode Problems Solutions question description: 问题描述 //问题截图: origin.png //锯齿状 sawtooth.png Thinking 你们可以自己先考虑一下。 solution with java - Java解决方案 solu......

才华惊动党中央
2017/08/23
0
0
LeetCode - ZigZagConversion

以下题干翻译自LeetCode,原文题目请参见LeetCode网址: ZigZagConversion 有一个字符串,当使用ZigZag模式写,并且指定了对应的行数时,如下所示(最好设置一个定长的字体来看): 然后我们要将...

Mock2052
2017/11/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

使用kubeadm 搭建K8s集群

1. 参考官网 https://kubernetes.io/docs/setup/independent/install-kubeadm/

whhbb
26分钟前
2
0
Dubbo 3.0 !提升不止一点点!

Dubbo 自 2011 年 10 月 27 日开源后,已被许多非阿里系的公司使用,其中既有当当网、网易考拉等互联网公司,也不乏中国人寿、青岛海尔等大型传统企业。 自去年 12 月开始,Dubbo 3.0 便已正...

编程SHA
27分钟前
2
0
提升不止一点点,Dubbo 3.0 预览版详细解读

Dubbo 自 2011 年 10 月 27 日开源后,已被许多非阿里系的公司使用,其中既有当当网、网易考拉等互联网公司,也不乏中国人寿、青岛海尔等大型传统企业。更多用户信息,可以访问Dubbo @GitHub...

阿里云云栖社区
30分钟前
13
0
HanLP Analysis for Elasticsearch

基于 HanLP 的 Elasticsearch 中文分词插件,核心功能: 兼容 ES 5.x-7.x; 内置词典,无需额外配置即可使用; 支持用户自定义词典; 支持远程词典热更新(待开发); 内置多种分词模式,适合...

左手的倒影
52分钟前
1
0
spark部署之yarn模式

spark部署之yarn模式 hadoop-3.0.0集群搭建 配置相应环境 java环境 scala(可配可不配) hadoop环境 从官网下载spark 解压 配置 /conf/spark-env.sh export JAVA_HOME=/usr/java/jdk1.8.0_4...

jackmanwu
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部