题目描述
将一个给定字符串根据给定的行数,以从上往下、从左到右进行 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
对于这题该如何处理呢?首先要理解题意,它就是本来给一个字符串,然后要按照Z字形排列等到一个形状,根据这个形状按照从左往右的顺序取值得到一个新的字符串。
在这里插入图片描述
法一模拟法: 既然这个字符串是固定的,那么我们是否可以模拟这个过程?
这样当然可以,但是模拟真的有必要这么搞嘛?当然没必要。二维数组占据太多无用的空间浪费内存。我们其实可以对内存进行优化考虑:
在这里插入图片描述
这样只需要考虑上下两个方向往集合中添加元素,最终就可以实现啦。不过在字符串叠加时候尽量不要使用String直接加,会很慢。这种方法只能干掉40%的人,一般般。 ac代码为:
public String convert(String s, int numRows) {
List<Character> list[]=new ArrayList[numRows];
for(int i=0;i<numRows;i++)
{
list[i]=new ArrayList<Character>();
}
int index=0;
boolean up=false;//方向 初始向下
for(int i=0;i<s.length();i++)
{
list[index].add(s.charAt(i));
if(numRows==1) {continue;}
if(up)//向上
{
if(index==0)
{
index++;up=false;
}
else {
index--;
}
}
else {
if(index==numRows-1)
{
index--;up=true;
}
else {
index++;
}
}
}
StringBuilder builder=new StringBuilder();
for(int i=0;i<numRows;i++)
{
for(int j=0;j<list[i].size();j++)
{
builder.append(list[i].get(j));
}
}
return builder.toString();
}
法二数学分析 上面的一种方法为模拟Z字形操作的整个流程,需要往里添加,取值也需要遍历取值。我们能不能用另一种角度去思考问题呢?
因为每次只加一个字符,我们如果按照以下的思路看待这个问题(原字符串弯曲),从每一层看,能不能找到每一层有什么规律呢?
在这里插入图片描述
0 6 12
也就是 0 0+(n-1)2 0+(n-1)3
这样整个逻辑分析就完成了,可以根据位置添加元素进去再取值。ac的代码如下:
public String convert(String s, int numRows) {
if(numRows==1)return s;
List<Character> list[]=new ArrayList[numRows];
for(int i=0;i<numRows;i++)
{
list[i]=new ArrayList<Character>();
}
//处理第一行最后一行
for(int i=0;i<s.length();i+=(numRows-1)*2)
{
list[0].add(s.charAt(i));
if(i+numRows-1<s.length())
{
list[numRows-1].add(s.charAt(i+numRows-1));
}
}
for(int i=0;i<s.length()+numRows;i+=(numRows-1)*2)
{
for(int j=1;j<numRows-1;j++)//中间所有行
{
int index1=i-j;
int index2=i+j;
if(index1>=0&&index1<s.length())
list[j].add(s.charAt(index1));
if(index2>=0&&index2<s.length())
list[j].add(s.charAt(index2));
}
}
StringBuilder builder=new StringBuilder();
for(int i=0;i<numRows;i++)
{
for(int j=0;j<list[i].size();j++)
{
builder.append(list[i].get(j));
}
}
return builder.toString();
}
但这种方法也只能干掉40%+的人,该如何优化呢?
在这里插入图片描述
注意一些细节情况,最终ac的代码为:
public static String convert2(String s, int numRows) {
if(numRows==1)return s;
//处理第一行
StringBuilder builder=new StringBuilder();
for(int i=0;i<s.length();i+=(numRows-1)*2)
{
builder.append(s.charAt(i));
}
for(int i=1;i<numRows-1;i++)
{
for(int j=0;j<s.length()+numRows;j+=(numRows-1)*2)//中间所有行
{
int index1=j+i;
int index2=j+(numRows-1)*2-i;
if(index1<s.length())
builder.append(s.charAt(index1));
if(index2<s.length())
builder.append(s.charAt(index2));
}
}
for(int i=numRows-1;i<s.length();i+=(numRows-1)*2)
{
builder.append(s.charAt(i));
}
return builder.toString();
}
最终的效果还行(偶尔三毫秒):
在这里插入图片描述
在这里插入图片描述
这题的话注意以下数组越界问题,可以用long类型处理最终再用整形处理。
主要有两种处理方法,一个就是转成字符串处理,第二个就是用数值处理。但是一般尽量不要用字符串处理比较慢。
ac代码为:
public int reverse(int x) {
if(x==0)return 0;
String value=x+"";
if(value.charAt(0)=='-')
value=value.substring(1);
StringBuilder sb=new StringBuilder();
for(int i=value.length()-1;i>=0;i--)
{
sb.append(value.charAt(i));
}
long num=Long.parseLong(sb.toString());
if(x<0)num=-num;
if(num<Integer.MIN_VALUE||num>Integer.MAX_VALUE)
{
return 0;
}
return (int)num;
}
数值类型处理方式为:
public int reverse(int x) {
if(x==0)return 0;
long num=0;
while (x%10==0) {
x/=10;
}
int t;
while (x!=0) {
t=x%10;//各位
num=num*10+t;
x/=10;
if(num>Integer.MAX_VALUE||num<Integer.MIN_VALUE)
return 0;
}
return (int)num;
}
时间还行: