`

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   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 text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

[分析] 找规律类型的题目,给出三种实现,实现1和2均是按找到的规律计算每一行各列元素在原串中的下标,实现3是按照原串的顺序构造出zigzag图,然后从上到下逐行遍历,时间和空间使用上均不如前两种好,但是更直观易懂。

[ref]
http://blog.unieagle.net/2012/11/08/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Azigzag-conversion/

    // method 3
    public String convert(String s, int numRows) {
        if (s == null || s.length() <= 1 || numRows == 1) 
            return s;
        // build zigzag map
        ArrayList<ArrayList<Character>> map = new ArrayList<ArrayList<Character>>(numRows);
        for (int i = 0; i < numRows; i++)
            map.add(new ArrayList<Character>());
        boolean down = true;
        int n = s.length();
        int i = 0, row = 0;
        while (i < n) {
            if (row < numRows && down) {
                map.get(row++).add(s.charAt(i++));
            } else if (row >= 0 && !down) {
                map.get(row--).add(s.charAt(i++));
            } else {//ajust direction
                row += down ? -2 : 2;
                down = !down;
            }
        }
        // read map row by row
        StringBuilder ret = new StringBuilder();
        for (ArrayList<Character> line : map) {
            for (Character c : line) {
                ret.append(c);
            }
        }
        return ret.toString();
     }
    // method 2
    public String convert2(String s, int numRows) {
        if (s == null || s.length() <= 1 || numRows == 1) 
            return s;
        int n = s.length();
        int delta = 2 * numRows - 2, diff1 = 0;
        StringBuilder ret = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            int j = i;
            diff1 = delta - 2 * i;
            while (j < n) {
                if (diff1 > 0)
                    ret.append(s.charAt(j));
                j += diff1;
                diff1 = delta - diff1;
            }
        }
        return ret.toString();
    }
    // method 1
    public String convert1(String s, int numRows) {
        if (s == null || s.length() <= 1 || numRows == 1) 
            return s;
        int n = s.length();
        if (n < numRows) 
            numRows = n;
        int delta = 2 * numRows - 2;
        StringBuilder ret = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            int j = i;
            while (j < n) {
                ret.append(s.charAt(j));
                int next = j + delta - 2 * i;
                if (i != 0 && i != numRows - 1 && next < n) {
                    ret.append(s.charAt(next));
                }
                j += delta;
            }
        }
        return ret.toString();
    }
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics