那么有朋友大概会使用类似下面这样的循环方法

作者: 编程  发布:2019-11-03

     return new string(reverse);
}

Release:

10.通过char数组的方式遍历反转:

Java实例1:单词逆序

public class StackX {
private int maxSize;
private char[] stackArray;//栈数组
private int top;//指针
public StackX(int max) {
maxSize=max;
stackArray=new char[maxSize];
top=-1;//top开始的时候位置是0 所以=-1
}
public void push(char j) {
stackArray[++top]=j;//先让top递增一个再赋值
}
public char pop() {
return stackArray[top--];//弹出
}
public char peek() {
return stackArray[top];//查找
}
public boolean isEmpty() {
//栈是否为空
return top==-1;
}
}

public class Reverser {
private String input;//通过构造函数传过来的input
private String output;
public Reverser(String in) {
input=in;
}
public String doRev() {//反转
int stackSize=input.length();
StackX theStack=new StackX(stackSize);//创建一个栈
for(int j=0;j<input.length();j++) {
char ch=input.charAt(j);//拿出来字符串中指定的字符
theStack.push(ch);
}
output="";
while(!theStack.isEmpty()) {
char c=theStack.pop();
output=output+c;

    }
    return output;
}

}

import java.io.*;
public class ReverseApp {
public static void main(String[]args ) throws IOException{//抛出异常
String input,output;
while(true) {
System.out.println("Enter a String:");
System.out.flush();//刷新一下
input=getString();
if(input.equals(""))break;
Reverser theReverser=new Reverser(input);
output=theReverser.doRev();
System.out.println("Reversed:"+output);
StringBuilder sb=new StringBuilder("中华人民共和国");
System.out.println("StringBuilder reverse:"+sb.reverse());
}
}
public static String getString() throws IOException{
InputStreamReader isr=new InputStreamReader(System.in);//输入流的读取器
BufferedReader br=new BufferedReader(isr);//带缓存的读取器
String s=br.readLine();
return s;
}
}

public static string Reverse(string name)
{
     if (String.IsNullOrEmpty(name))
       {
           throw new Exception("字符串不能为空!");
       }
    StringBuilder sb = new StringBuilder(name.Length);
    for (int i = name.Length-1; i >= 0; i--)
     {
        sb.Append(name[i]);
    }
        return sb.ToString();
}

面是实现字符串反转的四种方法:

大致上我能想到的算法就是这么多了,但是我无意间发现了StackOverflow上的一篇帖子,才发现这么一个看似简单的反转算法实现起来真可谓花样繁多。
3. 使用StringBuilder
使用StringBuilder方法大致和ReverseByCharBuffer一样,只不过不使用字符数组做缓存,而是使用StringBuilder。

栈和队列 1.通常情况作为程序员的工具来运用

        2.受限访问
        3.更加抽象(主要通过接口进行定义)

栈就是一组记录,表现形式为先进后出

 

9159.com 1[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
9159.com 2public static void Reverse(Array array)
9159.com 39159.com 4...{
9159.com 5      if (array == null)
9159.com 69159.com 7      ...{
9159.com 8            throw new ArgumentNullException("array");
9159.com 9      }
9159.com 10      Array.Reverse(array, array.GetLowerBound(0), array.Length);
9159.com 11}
9159.com 12
9159.com 13[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
9159.com 14public static void Reverse(Array array, int index, int length)
9159.com 159159.com 16...{
9159.com 17      int num1;
9159.com 18      int num2;
9159.com 19      if (array == null)
9159.com 209159.com 21      ...{
9159.com 22            throw new ArgumentNullException("array");
9159.com 23      }
9159.com 24      if ((index < array.GetLowerBound(0)) || (length < 0))
9159.com 259159.com 26      ...{
9159.com 27            throw new ArgumentOutOfRangeException((index < 0) ? "index" : "length", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
9159.com 28      }
9159.com 29      if ((array.Length - (index - array.GetLowerBound(0))) < length)
9159.com 309159.com 31      ...{
9159.com 32            throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
9159.com 33      }
9159.com 34      if (array.Rank != 1)
9159.com 359159.com 36      ...{
9159.com 37            throw new RankException(Environment.GetResourceString("Rank_MultiDimNotSupported"));
9159.com 38      }
9159.com 39      if (!Array.TrySZReverse(array, index, length))
9159.com 409159.com 41      ...{
9159.com 42            num1 = index;
9159.com 43            num2 = (index + length) - 1;
9159.com 44            object[] objArray1 = array as object[];
9159.com 45            if (objArray1 == null)
9159.com 469159.com 47            ...{
9159.com 48                  goto Label_00DE;
9159.com 49            }
9159.com 50            while (num1 < num2)
9159.com 519159.com 52            ...{
9159.com 53                  object obj1 = objArray1[num1];
9159.com 54                  objArray1[num1] = objArray1[num2];
9159.com 55                  objArray1[num2] = obj1;
9159.com 56                  num1++;
9159.com 57                  num2--;
9159.com 58            }
9159.com 59      }
9159.com 60      return;
9159.com 61Label_00DE:
9159.com 62      if (num1 >= num2)
9159.com 639159.com 64      ...{
9159.com 65            return;
9159.com 66      }
9159.com 67      object obj2 = array.GetValue(num1);
9159.com 68      array.SetValue(array.GetValue(num2), num1);
9159.com 69      array.SetValue(obj2, num2);
9159.com 70      num1++;
9159.com 71      num2--;
9159.com 72      goto Label_00DE;
9159.com 73}

5. 使用逻辑异或也可以进行反转

栈和队列_栈

数组 链表 树 适用于数据库应用中作数据记录
int[] a =new int[10];
a[1]=100;
int b=a[1];

  return new string(nm);

9159.com 74   static void Main(string[] args)
9159.com 759159.com 76            ...{
9159.com 77                string testString = "测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转测试字符串反转";
9159.com 78                DateTime start = DateTime.Now;
9159.com 79                for (int i = 0; i < 3000000; i++)
9159.com 809159.com 81                ...{
9159.com 82                    string s = Reverse1(testString);
9159.com 83                }
9159.com 84                DateTime end = DateTime.Now;
9159.com 85                Console.WriteLine("1 :  "+(end - start));
9159.com 86
9159.com 87                start = DateTime.Now;
9159.com 88                for (int i = 0; i < 3000000; i++)
9159.com 899159.com 90                ...{
9159.com 91                    string s = Revease21(testString);
9159.com 92                }
9159.com 93                end = DateTime.Now;
9159.com 94                Console.WriteLine("21:  " + (end - start));
9159.com 95
9159.com 96                start = DateTime.Now;
9159.com 97                for (int i = 0; i < 3000000; i++)
9159.com 989159.com 99                ...{
9159.com 100                    string s = Revease22(testString);
9159.com 101                }
9159.com 102                end = DateTime.Now;
9159.com 103                Console.WriteLine("22:  " + (end - start));
9159.com 104
9159.com 105                start = DateTime.Now;
9159.com 106                for (int i = 0; i < 3000000; i++)
9159.com 1079159.com 108                ...{
9159.com 109                    string s = Revease3(testString);
9159.com 110                }
9159.com 111                end = DateTime.Now;
9159.com 112                Console.WriteLine("3 :  " + (end - start));
9159.com 113
9159.com 114                Console.ReadLine();
9159.com 115            }

 

表示栈的代码

public class StackX{
private long[] stackArray;
private int maxSize;
private int top;//指向最顶层的位置
public StackX(int s){
maxSize=s;
stackArray=new long[maxSize];
top=-1;//因为第一个放进去的数据应该放在数组的0里面,初始没有的话 就给-1
}
//添加数据,永远往上添加
public void push(long j){
stackArray[++top]=j;
}
//查看并删除
public long pop(){
return stackArray[top--];
}
//查看
public long peek(){
return stackArray[top];
}
public boolean isEmpty(){
return top==-1;//如果top==-1则是空的,因为我们初始设置的
}
public boolean isFull(){
return top==(maxSize-1);
}
}

Public class StackApp{
Public static void main(String[]args){
StackX theStack=new StackX(10);
theStack.push(20);
theStack.push(40);
theStack.push(60);
theStack.push(80);
while(theStack.isEmpty()){
long value=theStack.pop();
System.out.print(value+””);
}
System.out.println();
System.ut.println(“theStack.isEmpty=”+theStack.isEmpty());
}
}

public static string Reverse(string name)
{
   if (String.IsNullOrEmpty(name))
   {
      throw new Exception("字符串不能为空!");
   }
  char[] nm = name.ToCharArray();
  for (int i = 0; i < (nm.Length-1 )/ 2; i++)
  {
     char q = nm[i];
     nm[i]= nm[nm.Length - 1 - i];
    nm[nm.Length - 1 - i] = q;
  }

1 :  00:00:05.7812500
21:  00:00:07.4218750
22:  00:00:08.2500000
3 :  00:00:50.3593750

public static string ReverseByStringBuilder2(this string original)
{
StringBuilder sb = new StringBuilder(original);
for (int i = 0, j = original.Length - 1; i <= j; i++, j--)
{
sb[i] = original[j];
sb[j] = original[i];
}
return sb.ToString();
}

Java实例2:分隔符匹配

public class StackX {
private int maxSize;
private char[] stackArray;//栈数组
private int top;//指针
public StackX(int max) {
maxSize=max;
stackArray=new char[maxSize];
top=-1;//top开始的时候位置是0 所以=-1
}
public void push(char j) {
stackArray[++top]=j;//先让top递增一个再赋值
}
public char pop() {
return stackArray[top--];//弹出
}
public char peek() {
return stackArray[top];//查找
}
public boolean isEmpty() {
//栈是否为空
return top==-1;
}
}

public class BracketChecker {
private String input;
public BracketChecker(String in) {
input=in;
}
//写一个检查的方法
public void check() {
int stackSize=input.length();
StackX theStack=new StackX(stackSize);
//a{b(c[d]e)f} {([ ])}
for(int j=0;j<input.length();j++) {
char ch=input.charAt(j);
switch(ch) {
case '{':
case '(':
case '[':
theStack.push(ch);//放入栈里
break;
case '}':
case ')':
case ']':
if(theStack.isEmpty()) {
char chx=theStack.pop();
if((ch=='}'&& chx!='{')||(ch==']'&& chx!='[')||(ch==')'&& chx!='(')
) {
System.out.println("Error:"+ch+"at"+j);
}
}
else {
System.out.println("Error:"+ch+"at"+j);
}
break;
default:
break;
}
}
if(!theStack.isEmpty())System.out.println("Error:missing right delimiter.");
}
}

import java.io.*;

public class BracketApp {
public static void main(String[]args) throws IOException {
String input;
while(true) {
System.out.println("Enter string containing delimiters:");
System.out.flush();
input=getString();
if(input.equals(""))break;
BracketChecker theChecker=new BracketChecker(input);
theChecker.check();
}
}
public static String getString() throws IOException{
InputStreamReader isr=new InputStreamReader(System.in);//输入流的读取器
BufferedReader br=new BufferedReader(isr);//带缓存的读取器
String s=br.readLine();
return s;
}
}

}

附2:StringBuilder.Append()方法的源码(由Reflector.exe反汇编得到):

我们可以像使用字符缓存那样,对使用StringBuilder方法进行优化,使其遍历过程也减少一半

方法二:.NET3.5以上

9159.com 116            static string Reverse1(string original)
9159.com 1179159.com 118            ...{
9159.com 119                char[] arr = original.ToCharArray();
9159.com 120                Array.Reverse(arr);
9159.com 121                return new string(arr);
9159.com 122            }
9159.com 123
9159.com 124            static string Revease21(string original)
9159.com 1259159.com 126            ...{
9159.com 127                int length = original.Length;
9159.com 128                char[] arr = new char[length];
9159.com 129                for (int i = 0; i < (length & (~3)); i += 4)
9159.com 1309159.com 131                ...{
9159.com 132                    arr[i] = original[length - i - 1];
9159.com 133                    arr[i+1] = original[length - i - 2];
9159.com 134                    arr[i+2] = original[length - i - 3];
9159.com 135                    arr[i+3] = original[length - i - 4];
9159.com 136                }
9159.com 137                for (int i = length & (~3); i < length; i++)
9159.com 1389159.com 139                ...{
9159.com 140                    arr[i] = original[length - i - 1];
9159.com 141                }
9159.com 142                return new string(arr);
9159.com 143            }
9159.com 144
9159.com 145            static string Revease22(string original)
9159.com 1469159.com 147            ...{
9159.com 148                int length = original.Length;
9159.com 149                char[] arr = new char[length];
9159.com 150                for (int i = 0; i < length; i++)
9159.com 1519159.com 152                ...{
9159.com 153                    arr[i] = original[length - i - 1];
9159.com 154                }
9159.com 155                return new string(arr);
9159.com 156            }
9159.com 157
9159.com 158            static string Revease3(string original)
9159.com 1599159.com 160            ...{
9159.com 161                int length = original.Length;
9159.com 162                StringBuilder sb = new StringBuilder(length);
9159.com 163                for (int i = length-1; i >= 0; i--)
9159.com 164                sb.Append(original[i]);
9159.com 165                return sb.ToString();
9159.com 166            }

当然,你可以预见,这种算法的效率不会比ReverseByCharBuffer要高。

 

 Revease1()中对char[]进行了两次赋值(ToCharArray()和Array.Revease),所以我有想到了Revease2和Revease3()两种方法,下面是对这四种方法进行简单性能测试的代码:

对于字符串反转,我们可以使用.NET类库自带的Array.Reverse方法

 

 

public static string ReverseByCharBuffer2(string original)
{
char[] c = original.ToCharArray();
int l = original.Length;
for (int i = 0; i < l / 2; i++)
{
char t = c[i];
c[i] = c[l - i - 1];
c[l - i - 1] = t;
}
return new string(c);
}

方法三:二分法

但还有个奇怪的问题,就是Debug版本中的Revease1()和Revease21()运行起来要比Release版本中的要快,而Revease22()和Revease3()就比较正常。按说Release时做了更多的优化工作,运行起来更快才对,迷惑ing...,下面是测试结果:

以上这几种方法按算法角度来说,其实可以归结为一类。然而下面的几种算法就完全不是同一类型的了。
使用栈

 

Debug:

9. System.Enumerable里提供了默认的Reverse扩展方法,我们可以基于该方法来对String类型进行扩展

public static string Reverse(string name)
{
     char[] reverse = name.Reverse().ToArray();

测试结果是Revease1()代码最简洁,运行速度也最快,Revease21()和Revease22()其次,Revease3()最慢。可见.net framework中实现的ToCharArray()和Array.Revease()效率还是蛮高的^_^

public static string ReverseByLinq(this string original)
{
return new string(original.Reverse().ToArray());
}

方法一:

9159.com 167public StringBuilder Append(string value)
9159.com 1689159.com 169...{
9159.com 170      if (value != null)
9159.com 1719159.com 172      ...{
9159.com 173            string text1 = this.m_StringValue;
9159.com 174            IntPtr ptr1 = Thread.InternalGetCurrentThread();
9159.com 175            if (this.m_currentThread != ptr1)
9159.com 1769159.com 177            ...{
9159.com 178                  text1 = string.GetStringForStringBuilder(text1, text1.Capacity);
9159.com 179            }
9159.com 180            int num1 = text1.Length;
9159.com 181            int num2 = num1 + value.Length;
9159.com 182            if (this.NeedsAllocation(text1, num2))
9159.com 1839159.com 184            ...{
9159.com 185                  string text2 = this.GetNewString(text1, num2);
9159.com 186                  text2.AppendInPlace(value, num1);
9159.com 187                  this.ReplaceString(ptr1, text2);
9159.com 188            }
9159.com 189            else
9159.com 1909159.com 191            ...{
9159.com 192                  text1.AppendInPlace(value, num1);
9159.com 193                  this.ReplaceString(ptr1, text1);
9159.com 194            }
9159.com 195      }
9159.com 196      return this;
9159.com 197}
9159.com 198
9159.com 199private bool NeedsAllocation(string currentString, int requiredLength)
9159.com 2009159.com 201...{
9159.com 202      return (currentString.ArrayLength <= requiredLength);
9159.com 203
9159.com 204
9159.com 205internal unsafe void AppendInPlace(string value, int currentLength)
9159.com 2069159.com 207...{
9159.com 208      int num1 = value.Length;
9159.com 209      int num2 = currentLength + num1;
9159.com 210      fixed (char* chRef1 = &this.m_firstChar)
9159.com 2119159.com 212      ...{
9159.com 213            fixed (char* chRef2 = &value.m_firstChar)
9159.com 2149159.com 215            ...{
9159.com 216                  string.wstrcpy(chRef1 + currentLength, chRef2, num1);
9159.com 217            }
9159.com 218            chRef1[num2] = '

if (!TrySZReverse(array, index, length))
{
int num = index;
int num2 = (index + length) - 1;
object[] objArray = array as object[];
if (objArray == null)
{
while (num < num2)
{
object obj3 = array.GetValue(num);
array.SetValue(array.GetValue(num2), num);
array.SetValue(obj3, num2);
num++;
num2--;
}
}
else
{
while (num < num2)
{
object obj2 = objArray[num];
objArray[num] = objArray[num2];
objArray[num2] = obj2;
num++;
num2--;
}
}
}

1 :  00:00:03.4375000
21:  00:00:06.1250000
22:  00:00:09.9687500
3 :  00:01:05.5468750

对于反转这类算法,都可以使用递归方法

附1:Array.Revease()方法的源码(由Reflector.exe反汇编得到):

public static unsafe string ReverseByPointer(this string original)
{
fixed (char* pText = original)
{
char* pStart = pText;
char* pEnd = pText + original.Length - 1;
for (int i = original.Length / 2; i >= 0; i--)
{
char temp = *pStart;
*pStart++ = *pEnd;
*pEnd-- = temp;
}

public static string ReverseByXor(string original)
{
char[] charArray = original.ToCharArray();
int l = original.Length - 1;
for (int i = 0; i < l; i++, l--)
{
charArray[i] ^= charArray[l];
charArray[l] ^= charArray[i];
charArray[i] ^= charArray[l];
}
return new string(charArray);
}

两次循环和栈的开销无疑使这种方法成为目前为止开销最大的方法。但使用栈这个数据结构的想法还是非常有价值的。
使用XOR

使用指针可以达到最快的速度,但是unsafe代码不是微软所推荐的,在这里我们就不多做讨论了

public static string ReverseByArray(string original)
{
char[] c = original.ToCharArray();
Array.Reverse(c);
return new string(c);
}

public static string ReverseByRecursive(string original)
{
if (original.Length == 1)
return original;
else
return original.Substring(1).ReverseByRecursive() + original[0];
}

在C#中,x ^= y相当于x = x ^ y。通过3次异或操作,可以将两个字符为止互换。对于算法具体的解释可以参考这篇文章。
9159.com ,6. 使用指针

4. 栈是一个很神奇的数据结构。我们可以使用它后进先出的特性来对数组进行反转。先将数组所有元素压入栈,然后再取出,顺序很自然地就与原先相反了。
public static string ReverseByStack(this string original)
{
Stack<char> stack = new Stack<char>();
foreach (char ch in original)
{
stack.Push(ch);
}
char[] c = new char[original.Length];
for (int i = 0; i < original.Length; i++)
{
c[i] = stack.Pop();
}
return new string(c);
}

1. 使用Array.Reverse方法

public static string ReverseByStringBuilder(this string original)
{
StringBuilder sb = new StringBuilder(original.Length);
for (int i = original.Length - 1; i >= 0; i--)
{
sb.Append(original[i]);
}
return sb.ToString();
}

在Array.Reverse内部,调用了非托管方法TrySZReverse,如果TrySZReverse不成功,实际上也是调用了类似ReverseByCharBuffer2的方法。

package string;

public class StringTest3 {
   public  static void main(String[] args)
   {
     String s="abcdefg";
       String s2="";
     char[] cs=s.toCharArray();
        for(int i=cs.length-1;i>=0;i--)
        {
         s2=s2+cs[i];
      }
     System.out.println("对字符串进行反转操作后为:"+s2);
       StringBuffer sb=new StringBuffer("abcdefg");
      StringBuffer sb2=sb.reverse();
        System.out.println("对StringBuffer进行反转操作后为:"+sb2);
  }

}

ReverseByCharBuffer使用了一个新的数组,而且遍历了字符数组的所有元素,因此时间和空间的开销都要大于ReverseByCharBuffer2。

public static string ReverseByCharBuffer(this string original)
{
char[] c = original.ToCharArray();
int l = original.Length;
char[] o = new char[l];
for (int i = 0; i < l ; i++)
{
o[i] = c[l - i - 1];
}
return new string(o);
}

但是委托开销大的弊病在这里一点也没有减少,以至于我做性能测试的时候导致系统假死甚至内存益处。
使用LINQ

转自:

2. 使用字符缓存

当然,聪明的同学们一定会发现不必对这个字符数组进行完全遍历,通常情况下我们会只遍历一半

public static string ReverseByRecursive2(this string original)
{
Func<string, string> f = null;
f = s => s.Length > 0 ? f(s.Substring(1)) + s[0] : string.Empty;
return f(original);
}

7. 使用递归

在面试或笔试中,往往要求不用任何类库方法,那么有朋友大概会使用类似下面这样的循环方法

8. 使用委托,还可以使代码变得更加简洁

return original;
}
}

本文由9159.com发布于编程,转载请注明出处:那么有朋友大概会使用类似下面这样的循环方法

关键词: