4

我一直在研究两种分别转置和反转置字符串的方法。据我所知，我提出的解决方案都有效。我只想知道我是否可以用更简单的方式解决这些问题。我的代码似乎对于正在执行的任务来说太长了。第一个方法 transpose() 将一个字符串作为参数并转置它。如果输入“bridge”，输出将是“bergid”。同样，使用 unTranspose() 方法，如果用户输入“bergid”，则输出将是“bridge”。

  public void transpose( String s )
  {
      String t = ""; 
      int end = s.length() - 1;


        for ( int i = 0; i < s.length()  / 2; i++ )
        {
            t += Character.toString( s.charAt( i ) ) + Character.toString( s.charAt( end ) );
            end--;
        }
        // Lenth of String is odd
        if ( s.length() % 2 == 1 )
        {
            // add character in middle of String to the end of the new String
            t+= Character.toString( s.charAt( s.length() / 2 ) );
        }

        System.out.println( t );
  }

    public void unTranspose( String s )
    {
    String t = ""; 

      // Length of String is odd
      if ( s.length() % 2 == 1 )
      {
      for ( int i = 0; i < s.length(); i+=2 )
      {
        t+= Character.toString( s.charAt( i ) );
      }

      for ( int i = s.length() - 2; i > 0; i -= 2 )
      {
        t += Character.toString( s.charAt( i ) );
      }

         System.out.println( t );
      }



   // Length of String is even
   else if ( s.length() % 2 == 0 )
   {
    for ( int i = 0; i < s.length() - 1; i+=2 )
    {
       t+= Character.toString( s.charAt( i ) );
    }

    for ( int i = s.length() - 1; i > 0; i -= 2 )
    {
        t+= Character.toString( s.charAt( i ) );
    }


    System.out.println( t );
}
   }

我的代码看起来很糟糕。我仍然不习惯正确格式化我的代码。请多多包涵。

谢谢你的时间

定义

         transpose
         --------->
"123Xcba"            "1a2b3cX"
        <-----------
        untranspose
4

8 回答 8

4

使用递归

public static String transpose(String str) {

    if (str == null || str.length() == 1 || str.length() == 2) {
        return str;
    } else {
        return str.substring(0, 1) + str.substring(str.length() -1, str.length()) + transpose(str.substring(1, str.length() -1) );
    }
}

public static String untranspose(String str) {
    if (str == null || str.length() == 1 ||str.length() == 2) {
        return str;
    } else {
        return  str.substring(0, 1) + untranspose(str.substring(2, str.length())) + str.substring(1, 2);
    }
}
于 2010-04-13T12:24:27.360 回答
3

该解决方案具有很好的对称性。

public static String transpose(String s) {
    StringBuilder sb = new StringBuilder();
    sb.setLength(s.length());
    for (int i = 0, j = s.length() - 1, x = 0; i <= j; ) {
        sb.setCharAt(x++, s.charAt(i++));
        if (i > j) break;
        sb.setCharAt(x++, s.charAt(j--));
    }
    return sb.toString();
}

public static String untranspose(String s) {
    StringBuilder sb = new StringBuilder();
    sb.setLength(s.length());
    for (int i = 0, j = s.length() - 1, x = 0; i <= j; ) {
        sb.setCharAt(i++, s.charAt(x++));
        if (i > j) break;
        sb.setCharAt(j--, s.charAt(x++));
    }
    return sb.toString();
}

这很明显两种方法之间的逻辑是相同的；唯一的区别是：

  • 在transpose和是读索引，i是写索引jx
  • Inuntranspose和是写索引，i是读索引（即相反）jx

这真的很简单：

  • i总是从字符串的开头到中间
  • j总是从字符串的末端到中间
  • x总是从字符串的开头到结尾
  • 如果输入是奇数长度，i == j最终 不可避免
    • 那时你只需要i，所以break

Lalith 提出了第一个递归解决方案；这个基本相同，稍作修改：

public static String transpose(String s) {
  int L = s.length();
  return (L < 2) ? s
    : s.substring(0, 1) + s.substring(L-1, L) + transpose(s.substring(1, L-1));
}

public static String untranspose(String s) {
  int L = s.length();
  return (L < 2) ? s
    : s.substring(0, 1) + untranspose(s.substring(2, L)) + s.substring(1, 2);
}
于 2010-04-13T03:25:11.563 回答
1

这是我对此的回应-我在您的代码中看到的主要问题是您在代码的多个区域中将字符串创建为临时对象-这使得它非常低效且非常缓慢。另一个问题是你想从循环中尽可能地外化。我已经编译并运行它并且它可以工作。

package com.rch.test;

public class Transposer
{
    public static String transpose(String s)
    {
        int length = s.length();
        int end = length - 1;

        StringBuilder t = new StringBuilder();
        for (int i = 0; i < length / 2; i++)
        {
            t.append(s.charAt(i));
            t.append(s.charAt(end));
            end--;
        }

        // Length of String is odd
        if (length % 2 == 1)
        {
            // add character in middle of String to the end of the new String
            t.append(s.charAt(length / 2));
        }
        return t.toString();
    }

    public static String unTranspose(String s)
    {
        int length = s.length();
        StringBuilder t = new StringBuilder();

        if (length % 2 == 1)
        {
            for (int i = 0; i < length; i += 2)
            {
                t.append(s.charAt(i));
            }

            for (int i = length - 2; i > 0; i -= 2)
            {
                t.append(s.charAt(i));
            }
        }
        else if (length % 2 == 0)
        {
            for (int i = 0; i < length - 1; i += 2)
            {
                t.append(s.charAt(i));
            }

            for (int i = length - 1; i > 0; i -= 2)
            {
                t.append(s.charAt(i));
            }
        }
        return t.toString();
    }

    public static void main(String[] args)
    {
        String testString = "bridge";
        String transposedString = Transposer.transpose(testString); 
        String finalString = Transposer.unTranspose(transposedString);

        System.out.println("1)" + testString);
        System.out.println("2)" + transposedString);
        System.out.println("3)" + finalString);
    }
}

输出：1）桥 2）bergid 3）桥

于 2010-04-13T03:08:06.477 回答
0

使用 StringBuilder 快速完成转置方法，这通常会使此类操作更简单。这似乎适用于您的桥接示例以及奇数长度的字符串。

public static void transpose( String s ) 
{
    StringBuilder sb = new StringBuilder(s);

    for( int i=1; i<sb.length(); i=i+2 ) {          
        sb.insert( i, sb.charAt( sb.length()-1 ) );         
        sb.deleteCharAt( sb.length()-1 );
    }

    System.out.println( sb.toString() );
}

应该给你足够的想法来自己实现 untranspose 方法:+)

于 2010-04-13T03:12:51.357 回答
0

这是一种不需要基于字符串长度是偶数还是奇数的不同行为的方法。

public static String transpose(String in)
{
    StringBuilder out = new StringBuilder();
    for (int i=0; i<in.length(); ++i)
    {
        out.append(in.charAt(i));
        out.append(in.charAt(in.length() - i - 1));
    }
    return out.substring(0, in.length());
}

public static String untranspose(String in)
{
    StringBuilder out = new StringBuilder();
    for (int i=0; i<in.length(); i+=2)
    {
        out.append(in.charAt(i));
    }
    StringBuilder reversedSecondHalf = new StringBuilder();
    for (int i=1; i<in.length(); i+=2)
    {
        reversedSecondHalf.append(in.charAt(i));
    }
    out.append(reversedSecondHalf.reverse());
    return out.toString();
}
于 2010-04-13T03:18:49.373 回答
0

好吧，我能够稍微简化一下transpose方法：

public static String transpose(String s)
{
   StringBuilder sb = new StringBuilder();
   int i = 0;
   int length = s.length() - 1;
   while(i < length - i)
   {
      sb.append(s.charAt(i)).append(s.charAt(length - i));
      i++;
   }
   if(i == length - i) sb.append(s.charAt(i));
   return sb.toString();
}

更新

用 untranspose 试试我的运气 -

public static String untranspose(String s)
{
   StringBuilder sb1 = new StringBuilder();
   StringBuilder sb2 = new StringBuilder();
   int length = s.length();
   int iopp = (length % 2 == 0) ? length - 1 : length - 2;
   for(int i = 0; i < length; i += 2, iopp -= 2)
   {
      sb1.append(s.charAt(i));
      if(iopp >= 0) sb2.append(s.charAt(iopp));
   }
   return sb1.append(sb2).toString();
}
于 2010-04-13T03:18:57.777 回答
0

这是另一个解决方案，它显示了转置和非转置之间的对称性。

public static String transpose(String in)
{
    int length = in.length();
    StringBuilder out = new StringBuilder(in);
    for (int pos=1; pos<length; pos+=2)
    {
        swapCharacters(out, length-1, pos);
    }
    return out.toString();
}

public static String untranspose(String in)
{
    int length = in.length();
    StringBuilder out = new StringBuilder(in);
    for (int pos=length-1-(length%2); pos>0; pos-=2)
    {
        swapCharacters(out, pos, length-1);
    }
    return out.toString();
}

private static void swapCharacters(StringBuilder string, int oldPos, int newPos)
{
    char c = string.charAt(oldPos);
    string.deleteCharAt(oldPos);
    string.insert(newPos, c);
}
于 2010-04-13T03:52:38.717 回答
0

表达式可以很短，但不会变得太难理解。

/** Convert ABCDefg to AgBfCeD */
public static String transpose(String s){
    char[] ts = new char[s.length()];
    int i = 0, j = ts.length;
    for( int k = 0 ; k < ts.length ; k++ ){
        ts[k] = s.charAt(k%2==0 ? i++ : --j);
    }
    return new String(ts);
}
/** Convert AgBfCeD to ABCDefg */
public static String untranspose(String ts){
    char[] s = new char[ts.length()];
    int i = 0, j = ts.length();
    for( int k = 0 ; k < ts.length() ; k++ ){
        s[k%2==0 ? i++ : --j] = ts.charAt(k);
    }
    return new String(s);
}
于 2018-11-03T13:19:32.577 回答