java 中字符串的转置和取消转置

Question

我一直在研究两种分别转置和取消转置字符串的方法。据我所知，我提出的解决方案都有效。我只是想知道是否可以用更简单的方式解决这些问题。我的代码对于正在执行的任务来说似乎太长了。第一个方法 transpose() 将采用 String 作为参数并对其进行转置。如果输入“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

Answer 1

使用递归

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);
    }
}

Answer 2

该解具有良好的对称性。

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();
}

这清楚地表明两种方法之间的逻辑是相同的；唯一的区别是：

• 索引
• 在转置中，i 和 j 是读取索引，x 是写入 untranspose、i 和 j 是写入索引，x 是读取索引（即相反）

这真的很简单：

• i 总是从字符串的开头到中间
• j 总是从字符串的末尾到中间
• x 总是从开头到end of string
• 如果输入是奇数长度，最终不可避免地 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);
}

Answer 3

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

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）贝吉德
3）桥

Answer 4

快速尝试使用 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 方法:+)

Answer 5

这是一种不需要根据字符串长度是偶数还是奇数而采取不同行为的方法。

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();
}

Answer 6

好吧，我能够稍微简化 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();
}

Update

尝试了 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();
}

Answer 7

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

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);
}

Answer 8

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

/** 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);
}