Java算法之字符串反转分析

简介: 本文来自http://blog.csdn.net/liuxian13183/ ,引用必须注明出处! 在基本的工作内容开发中,算法不会显得那么重要,而在百万级别的时候,差距非常大,今天带大家研究下常见的字符串反转算法。



本文来自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));
	}
}


其他有趣的算法:
如赛马问题,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吨运两次,向前3次向后2次,向前只能多走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吨。功夫不负有心人,这就是最终答案!






目录
相关文章
|
21天前
|
编解码 算法 定位技术
GEE时序——利用sentinel-2(哨兵-2)数据进行地表物候学分析(时间序列平滑法估算和非平滑算法代码)
GEE时序——利用sentinel-2(哨兵-2)数据进行地表物候学分析(时间序列平滑法估算和非平滑算法代码)
29 3
|
1天前
|
存储 算法 安全
【国密算法】国密算法在Java中的实践
【国密算法】国密算法在Java中的实践
|
3天前
|
存储 前端开发 算法
加密算法在网络通信中的应用及优势分析
本文将探讨加密算法在网络通信中的重要性,以及不同加密算法的应用和优势。通过对前端、后端、Java、Python、C、PHP、Go等多种技术的分析,我们将了解在日益增长的网络威胁下,加密算法对于确保数据安全和隐私保护的必要性。
|
3天前
|
算法
某圈app算法分析
某圈app算法分析
6 0
|
3天前
|
算法 安全 数据安全/隐私保护
某影视APP算法逆向分析
某影视APP算法逆向分析
5 0
|
6天前
|
前端开发 JavaScript Java
利用Java Web技术实现实时通信系统的案例分析
利用Java Web技术实现实时通信系统的案例分析
|
6天前
|
算法 安全 前端开发
Java Queue接口及其常用实现类分析
Java Queue接口及其常用实现类分析
|
6天前
|
存储 算法 搜索推荐
Java中的数据结构与算法解析
Java中的数据结构与算法解析
|
6天前
|
算法 数据挖掘 数据安全/隐私保护
某合伙人app算法分析
某合伙人app算法分析
5 0
|
8天前
|
Java
Java字符串转整数的超简单方法!
Java字符串转整数的超简单方法!
20 0

相关产品