Java算法之字符串反转分析

时间：2022-03-03 13:14:32



本文来自http://blog.csdn.net/liuxian13183/ ，引用必须注明出处！


在基本的工作内容开发中，算法不会显得那么重要，而在百万级别的时候，差距非常大，今天带大家研究下常见的字符串反转算法。

public class StringReverse {public static String reverse1(String orig) {
char[] s = orig.toCharArray();
int n = s.length - 1;
int halfLength = n / 2;
for (int i = 0; i <= halfLength; i++) {// 2分法+替换算法
char temp = s[i];
s[i] = s[n - i];
s[n - i] = temp;
}
return new String(s);
}

public static String reverse2(String s) {// 2分法+异或算法 
char[] str = s.toCharArray();
int begin = 0;
int end = s.length() - 1;
while (begin < end) {
str[begin] = (char) (str[begin] ^ str[end]);
str[end] = (char) (str[begin] ^ str[end]);
str[begin] = (char) (str[end] ^ str[begin]);
begin++;
end--;
}
return new String(str);
}

public static String reverse3(String s) {// jdk提供
return new StringBuffer(s).reverse().toString();
}

public static String reverse4(String s) {// 2分递归算法
int length = s.length();
if (length <= 1)
return s;
String left = s.substring(0, length / 2);
String right = s.substring(length / 2, length);
return reverse1(right) + reverse1(left);
}

public static String reverse5(String s) {// 傳統从后往前加
int length = s.length();
String reverse = "";
for (int i = 0; i < length; i++)
reverse = s.charAt(i) + reverse;
return reverse;
}

public static String reverse6(String s) {//傳統與5雷同
char[] array = s.toCharArray();
String reverse = "";
for (int i = array.length - 1; i >= 0; i--)
reverse += array[i];
return reverse;
}

public static String reverse7(String s) {// 利用栈先进后出的特性
char[] str = s.toCharArray();
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < str.length; i++)
stack.push(str[i]);
String reversed = "";
for (int i = 0; i < str.length; i++)
reversed += stack.pop();
return reversed;
}

public static void main(String[] args) {
String str = "hello world !";
int length = 10000000;
long curTime = System.currentTimeMillis();
for (int i = 0; i < length; i++) {
reverse1(str);
}
System.out.println("reverse1:" + (System.currentTimeMillis() - curTime));
curTime = System.currentTimeMillis();
for (int i = 0; i < length; i++) {
reverse2(str);
}
System.out.println("reverse2:" + (System.currentTimeMillis() - curTime));
curTime = System.currentTimeMillis();
for (int i = 0; i < length; i++) {
reverse3(str);
}
System.out.println("reverse3:" + (System.currentTimeMillis() - curTime));
curTime = System.currentTimeMillis();
for (int i = 0; i < length; i++) {
reverse4(str);
}
System.out.println("reverse4:" + (System.currentTimeMillis() - curTime));
curTime = System.currentTimeMillis();
for (int i = 0; i < length; i++) {
reverse5(str);
}
System.out.println("reverse5:" + (System.currentTimeMillis() - curTime));
curTime = System.currentTimeMillis();
for (int i = 0; i < length; i++) {
reverse6(str);
}
System.out.println("reverse6:" + (System.currentTimeMillis() - curTime));
curTime = System.currentTimeMillis();
for (int i = 0; i < length; i++) {
reverse7(str);
}
System.out.println("reverse7:" + (System.currentTimeMillis() - curTime));
}
}

Java算法之字符串反转分析

其他有趣的算法： 如赛马问题，25匹马，5个赛道，如何在不用工具的情况下，找到最快的5匹。问题可以简化为3匹马，3个赛道。 分A B C三组马，各赛一场，结果如下： A1 A2 A3 B1 B2 B3 C1 C2 C3 3场第1名赛一场，得出第1名 如果是A1，则A2跟B1和C1比1场，其他同理，找出第2名 如果是B1，则A2跟B2和C1比1场，其他同理，找出第3名 比赛结束，共需要6场 同理可算出，25匹马需要10场。 如运煤问题，3000吨煤，用载重1000吨的火车，从原点运往终点，路程1000公里，每公里消耗1吨煤，到终点时煤剩几何？ 粗略一算，第一种方案： 第一轮， 第1次，先拉1000吨到A，卸下500吨，返回，行程250公里 第2次，再拉1000吨到A，卸下500吨，返回，行程250公里，同理第三次 第3次后，A地剩下1500吨煤，行程250公里 第二轮 继续第4次，同上，到B地行程187.5公里，每次卸下375吨货物 两轮后，行程437.5公里，剩下货物750吨 第三轮 一次性运到，共剩余312.5吨 分析：由于第三轮每次只运750吨，运量未满，导致最终运送较少。 粗略一算，第二种方案： 第1次，先拉1000吨到A，卸下500吨，行程250公里，返回第2次，再拉1000吨到A，加上250吨满载，剩下250吨；走250公里到B，卸下250吨，总行程250公里，返回第3次，再拉1000吨到A，加上250吨满载；再走250公里到B，加上前两次剩下的共500吨，满载1000吨继续直行到终点，共剩余500吨分析：似乎比较完美，每次都是满载。粗略一算，第三种方案：
变下思路，将此题变成n千吨煤，可以走多少公里，即消耗多少那么1000吨走1000公里，2000吨由于中间要折回+第1次向前走共3次即1000*（1+1/3)公里，同理可得3000吨走1000*（1+1/3+1/5）公里，n千吨可走1000*（1+1/3+1/5+……+1/(2n-1)）公里那么3000公里剩余多少呢？前两句已经讲了3000吨可走的公里，每公里1吨，多出多少公里即多出多少吨即1000*（1+1/3+1/5）-1000=1600/3吨，即533.33吨。功夫不负有心人，这就是最终答案！



标签：

相关文章