LeetCode算法(和中等打的有来有回)——Z字形变换

LeetCode第6题

假设最后转换为n行Z字矩阵，那么Z字矩阵第一列就是

0
1
2
...
n-1

并且易于知道：

那第二行第2个x的索引就是0+k+k-2=2k-2，依次往后就是2(2k-2)、3(2k-2)
而对于其他行来说，与如果忽略中间斜着的内容，只考虑竖直部分，那么与本行上一位的索引永远都是2k-2的差距

因此如果忽略中间的内容，那么构建垂直的内容，代码可以简化为

class Solution {
    public String convert(String s, int numRows) {
    	String rst = "";
    	// 依次构造转换成Z字后的每行
        for(int k=0;k<numRows;k++){
        	// 每行在原本字符串中的索引
            int k_ = k;
            // 索引不超出界限时
            while(k_<s.length()){
				// 加入新的Z字形字符串
                rst+=s.charAt(k_);
                // 比本行的上一位的索引增加2k-2
                k_ = k_+2*numRows-2;
            }
        }
        return rst;
    }
}

此时，我们只需要单独处理中间位置的索引，也就是Z字形既不是第0行也不是第k-1行时，假设当前行为k，上一位索引为k_那么，该位的索引为k_+2n-2+2k
计算如下：

因此加入中间位置计算内容后变为：

class Solution {
    public String convert(String s, int numRows) {
    	// 特殊情况处理
        if(numRows==1||s.length()<2)return s;
        // 收集结果
        String rst = "";
        for(int k=0;k<numRows;k++){
            int k_ = k;
            while(k_<s.length()){
                rst+=s.charAt(k_);
                // 当既不是第一行也不是最后一行时，中间进行单独处理
                if(k!=0&&k!=numRows-1){
                	// 如果本次计算没有超出index，那么加入结果
                    if(2*numRows+k_-2*k-2<s.length())
                    rst+=s.charAt(2*numRows+k_-2*k-2);
                }
                k_ = k_+2*numRows-2;
            }
        }
        return rst;
    }
}

此时算法已经可以通过，但是时间效率很低，这是因为在Java中String字符串拼接的效率很低，因此我们将String替换为StringBuilder，具体可以查看StringBuilder和String以及StringBuffer的区别
因此代码最终优化为：

class Solution {
    public String convert(String s, int numRows) {
        if(numRows==1||s.length()==1)return s;
        StringBuilder rst = new StringBuilder();
        for(int k=0;k<numRows;k++){
            int k_ = k;
            while(k_<s.length()){
                rst.append(s.charAt(k_));
                if(k!=0&&k!=numRows-1){
                    if(2*numRows+k_-2*k-2<s.length())
                    rst.append(s.charAt(2*numRows+k_-2*k-2));
                }
                k_ = k_+2*numRows-2;
            }
        }
        return rst.toString();
    }
}

对比起构建依次遍历s，然后遍历并补充不同行的字符串，最终进行拼接的方法。该算法空间复杂度为1，并且不需要跳转遍历不同的字符串，因此时间效率和空间效率均较优