LeetCode算法6：java Z 字形变换

56 阅读 0 评论 37 点赞

我是靠谱客的博主飞快猎豹，最近开发中收集的这篇文章主要介绍LeetCode算法6：java Z 字形变换，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 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

说明：
仍旧是一个技巧题，网上很多网友的答案是寻找数据之间的错综复杂的关系，通过公式对关系的模拟，在达到最终的结果。
理解起来非常复杂，由于该题并没有算法复杂度的要求，因此应该用最简单易懂的方式达到算法目的才是该题的最好答案。

思路说明：
其实类似矩阵的布局方式，可以通过设置一个类似矩阵的存储，来达到将每行数据存储在一起。因为字符中间的空白字符并没有要求记录，这就简化了很多记录和运算。

注意点：
1、对于跳转方向的思路；
2、对于边界的处理，即行数为1时要满足要求。这里将行数为1直接作为原结果返回，没有参与到算法的运算。

代码：

package _01_50;

public class _06ZigZagConversion{
	
	public String convert(String s , int nums){
		
		if(nums<2) return s;
		
		String[] rows= new String[nums];

		for(int i=0 ;i< nums;i++){	
			rows[i]="";
			}
			//it is useful for the j=0
		int direction = -1;
		//for the rounding
		int count = nums-1;
		int row = 0;
		System.out.println(s.length());
		
		for(int j=0;j< s.length();j++){
			rows[row]=rows[row]+s.charAt(j);
			//make the direction to be plus for first time
			if(j%count == 0){
				direction = -direction;
				}
			row = row + direction;
			System.out.println(row);
			}
			
		String convertStr = "";
		for(int i = 0;i< nums;i++){
			convertStr = convertStr+rows[i];
			}
			return convertStr;
		}
	
	public static void main(String[] arg){
		
		_06ZigZagConversion ZigZagConversion = new _06ZigZagConversion();
		
		String input = "PAYPALISHIRING";
		int nums = 1;
		String output = ZigZagConversion.convert(input,nums);
		System.out.println(output);
		}
	}

参考：
Z字型变换