手摇算法

一，算法描述

f为翻转映射 1. 假设AB要翻转成BA，

f(f(A)f(B))=f(f(B))f(f(A))=BA

2. 假设ABC要翻转成CBA，f为翻转映射

f【f(A)f(B)f(C)】=f(f(C))f(f(B))f(f(A))=CBA

还是觉得叫翻手掌算法比较形象…… 跟着我左手右手一个慢动作 各自180°翻转 右手左手慢动作重播 整体180°翻转

二，算法应用

1. 翻转字符串

i come from china.反转成china. come from i 中间可能有多个空格

private static String reverseString1(String string) { if (string==null||string.length()==0){ return string; } char[] array=string.toCharArray(); int start=0; int end=array.length-1; while (array[start]!=' '){ start++; } while (array[end]!=' '){ end--; } //[0,start-1]之间的元素是第一个单词，[end+1,array.length-1]是第二个单词 //现在的结构是ABC，需要变成CBA,定义f为翻转映射，f【f(A)f(B)f(C)】=f(f(C))f(f(B))f(f(A))=CBA reverse(array,0,start-1); reverse(array,start,end); reverse(array,end+1,array.length-1); reverse(array,0,array.length-1); return String.valueOf(array); } public static void reverse(char[] array,int start,int end){ while (start<=end){ swap(array,start++,end--); } } private static void swap(char[] array, int i, int j) { char temp=array[i]; array[i]=array[j]; array[j]=temp; }

2. 原地归并

http://blog.csdn.net/shuxiangxingkong/article/details/17614195