首页 > 基础算法 > 模拟法 > LeetCode-ZigZag Conversion[模拟]
2014
11-19

LeetCode-ZigZag Conversion[模拟]

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

标签: String
分析

要找到数学规律。真正面试中,不大可能出这种问题。

n=4:
\begin{Code}
P I N
A L S I G
Y A H R
P I
\end{Code}

n=5:
\begin{Code}
P H
A S I
Y I R
P L I G
A N
\end{Code}

所以,对于每一层垂直元素的坐标 $(i,j)= (j+1 )*n +i$;对于每两层垂直元素之间的插入元素(斜对角元素),$(i,j)= (j+1)*n -i$

代码1

// LeetCode, ZigZag Conversion
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    string convert(string s, int nRows) {
        if (nRows <= 1 || s.size() <= 1) return s;
        string result;
        for (int i = 0; i < nRows; i++) {
            for (int j = 0, index = i; index < s.size();
                    j++, index = (2 * nRows - 2) * j + i) {
                result.append(1, s[index]);  // 垂直元素
                if (i == 0 || i == nRows - 1) continue;   // 斜对角元素
                if (index + (nRows - i - 1) * 2 < s.size())
                    result.append(1, s[index + (nRows - i - 1) * 2]);
            }
        }
        return result;
    }
};

Java代码:

public class Solution {
    public String convert(String s, int nRows) {
        if(s == null || s.length() == 0 || nRows <= 1) return s;
        char arr[] = s.toCharArray();
        char carr[] = new char[arr.length];

        int step = nRows * 2 - 2;
        int zcnt = arr.length / step;
        int k = 0;

        for(int i=0; i<nRows; i++){
            for(int j=0; j<=zcnt; j++){
                if(i == 0){
                    if(j*step < arr.length)
                        carr[k++] = arr[j*step];
                }else if(i == nRows-1){
                    if(j*step+i < arr.length)
                        carr[k++] = arr[j*step+i];
                }else{
                    if(j*step+i < arr.length)
                        carr[k++] = arr[j*step+i];
                    if((j+1)*step-i < arr.length)
                        carr[k++] = arr[(j+1)*step-i];

                }
            }

        }
        return new String(carr);
    }
}

  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  2. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

  3. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?