2019-02-24-算法-进化

迈不过友情╰ 2022-03-16 20:18 173阅读 0赞

**题目描述**  
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。  
比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：

L   C   I   R
    E T O E S I I G
    E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“LCIRETOESIIGEDHN”。  
请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3
    输出: "LCIRETOESIIGEDHN"

示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4
    输出: "LDREOEIIECIHNTSG"
    解释:
    
    L     D     R
    E   O E   I I
    E C   I H   N
    T     S     G

**我的解决方案**  
使用坐标法，建立x轴、y轴，计算每个字符所处的位置  
二维坐标：  
y：处于多少行  
x：每行元素的相对位置

public static String convert(String s, int numRows) {
            if(numRows < 2 || s==null || s.length()<=1) {
            	return s;
            }
            Character[][] c = new Character[numRows][s.length()/2 + 1];
            
            int x=0,y=0;
            for(int i=0;i<s.length();i+=2*(numRows-1)) {
            	y =0;
            	//每个字符必定有其位置
            	for(int j=0;j<numRows && (i + j)<s.length();j++) {
            		c[y++][x] = s.charAt(i + j);
            	}
            	y = numRows-2;
            	if(y>0) {
            		for(int k=numRows;k<2*(numRows-1) && (i + k)<s.length(); k++) {
            			c[y--][++x] = s.charAt(i+k);
            		}
            	}
            	x++;
            }
            
            StringBuilder result = new StringBuilder();
            for(int i=0;i<numRows;i++) {
            	for(int j=0;j<s.length()/2 + 1;j++) {
            		if(c[i][j] != null) {
            			result.append(c[i][j]);
            		}
            	}
            }
    		return result.toString();
        }

**改进方案**

本以为此算法除了建立二维数组，浪费一部分空间之外，时间复杂度很难优化了。看了参考答案之后，豁然开朗，原来，不必计算二维坐标值，每行元素的位置，在从左至右遍历的时候，就已经有序了。只需要记录元素在第几行就可以了。  
改进后的算法：

public static String convert(String s, int numRows) {
            if(numRows == 1) {
            	return s;
            }
            List<StringBuilder> arrList = new ArrayList<StringBuilder>();
            for(int i=0; i<Math.min(s.length(), numRows);i++) {
            	arrList.add(new StringBuilder());
            }
            int row=0;
            boolean changeDirect = true;
            for(char c:s.toCharArray()) {
            	arrList.get(row).append(c);
            	changeDirect = (row == 0 || row == numRows -1)?!changeDirect:changeDirect;
            	row = row + (changeDirect?-1:1);
            }
            StringBuilder rep = new StringBuilder();
            for(StringBuilder sb : arrList) {
            	rep.append(sb);
            }
            return rep.toString();
        }

代码逻辑更加清晰，更加便于维护，并且减少了部分运算量，执行速度提高了近一倍。

持续精进，加油！