xindoo is
always here

Leetcode 6. ZigZag Conversion

原题链接:6.ZigZag Conversion

  题目名称『曲折变换』,但给的样例只有三行,看不出到底怎么样曲折变化,所以这里我再补充一个样例,大家肯定一下就懂了。

 a        i         q        y
 b      h j      p  r      x z
 c    g   k    o    s    w
 d  f     l  n      t  v
 e        m         u

  如上所示,这就是26个小写字母表的5行曲折变换。 其中在做这道题的时候把不需要我们构造出这样五行字符,然后拼接。其实你把字母换成1-n的数字,很容易找到每个位置的字母在原字符串中的位置。

 1         9        17        25
 2      8 10     16 18     24 26
 3    7   11   15   19   23
 4  6     12 14     20 22
 5        13        21

  多画几个,可以尝试下3行6行,其实你就会发现,每行每两两之间的间隔是有规律的,注意看,除了第一行和最后一行,中间行的间隔有两种,但都是成对出现了。其实我们可以把第一行和最后一行的数字间隔也看做一对,只不过另一个是0罢了。
第i行的间隔对[2*(numRows-1)-i*2, 0+i*2] (0<=i<numRows)

public class Solution {
    public String convert(String s, int numRows) {
        if (1 == numRows) 
            return s;
        int len = s.length();
        //频繁变动的字符串建议用StringBuffer,String变动的性能成本比较高
        StringBuffer t = new StringBuffer();
        int[] a = {2*(numRows-1), 0};
        for (int i = 0; i < numRows; i++) {
            int pos = i;
            int index = 0;
            while (pos < len) {
                if (0 != a[index]) {//这里其实是特殊处理第一行和最后一行,因为这俩行只用到了非0间隔
                    t.append(s.charAt(pos));
                    pos += a[index];
                }
                index = index^1; //通过异或来实现index值0和1之间的相互转换
            }
            a[0] -= 2;
            a[1] += 2;
        }
        return new String(t);
    }
}
打赏
未经允许不得转载:XINDOO » Leetcode 6. ZigZag Conversion
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏