编写一个函数，作用是把一个char组成的字符串循环右移n个

例如，"abcdef"循环右移2个就变为"efabcd"

popo实现了一个，不过需要O(n)的额外空间
程序：
void LoopMove(char * pStr,int steps)
{
int len = strlen(pStr);
char *s = new char[len+1];
int count = 0;
char *temp = pStr;
while (*pStr)
{
s[(count+steps)%len] = *pStr;
pStr++;
count++;
}
s[len] = '\0';
strcpy(temp,s);
delete []s;
}


最近想出了个空间为O(1)，时间为O(n)的算法
就是只通过数组指针移动和交换来实现

int LoopMove2(char *p, int i, int t, int s, int m){
int n = strlen(p);
int j = (i+m)%n;
if(t == j) return 0;
p[s] = p[j];
p[j] = p[t];
LoopMove2(p, j, s, t,m);
}

使用方法是
如果要右移2位就调用
LoopMove2(p,0,0,-1,2);

基本思想是：
如果数组X有n个元素，要右移m个位置
申请一个临时变量，设它为数组上的X[-1]
对于数组中的Xi，要把它一次性移到它的最终位置，这个位置是j=(i+m)%n,那么首先把Xj移到X[-1],然后把X[i]移到X[j],接下来一次性移动Xj到它的最终位置(j+m)%n,此时临时变量为X[i],要移动的元素是Xj，并且Xj的值在X[-1]位置上。
由此定义LoopMove2函数，它参数的含义是
i：此步要移动的元素Xi
t：当前元素Xi的值在数组上的位置
s：临时变量在数组上的位置
m：右移的位数

最终移动的终止条件是：
当前元素Xi的值在数组上的位置＝＝Xi要移向的最终位置

这个程序中使用了数组的-1处作为临时变量的位置，主要是想把程序写得简单些
当然这样会带来一些问题，但作为说明性的例子就暂不考虑了。
gmail id: yichao.zhang
欢迎和各位讨论算法

Google 面试第一题解法

Solve this cryptic equation, realizing of course that values for M and E could be interchanged. No leading zeros are allowed.

WWWDOT - GOOGLE = DOTCOM

思路：
穷举法，式子中共有9个不同的字母，数字0－9有10个，因此就从10个数字中任取9个，排成一列，这样分别对应了式子中的字母。
然后判断当前取出的这9个数，是否满足条件。本程序中用check2 函数判断，另外需要考虑WE是可以互换，但不可以相同

答案：只有两组解
777589 - 188103 = 589486
777589 - 188106 = 589483

程序：
Perm1.java
package org.chao.perm;

public class Perm1 {
public static void main(String[] args) {
int size = 9;
int[] a = new int[size];
int all = 10;
check(a,all,size,0);
}

private static void check(int[] a, int all, int size, int depth) {
if(size == depth){
check2(a);
}
for(int i=0; i<all; i++){
int j = 0;
for(;j<depth;j++){
if(a[j] == i){
break;
}
}
if(j==depth && depth<size){
a[depth]=i;
check(a,all, size,depth+1);
}
}
}

private static void check2(int[] a) {
//WWWDOT - GOOGLE = DOTCOM
//w0/6 d1 o2 t3 g4 l5 e6/0 c7 m8
int s1 = a[0]*111000+a[1]*100+a[2]*10+a[3];
int s2 = a[4]*100100+a[2]*11000+a[5]*10+a[6];
int s3 = a[1]*100000+a[2]*10010+a[3]*1000+a[7]*100+a[8];
if(s1-s2 == s3){
System.out.println(s1+" - "+s2+" = "+s3);
}
s1 = a[6]*111000+a[1]*100+a[3]*10+a[4];
s2 = a[4]*100100+a[2]*11000+a[5]*10+a[0];
s3 = a[1]*100000+a[2]*10010+a[3]*1000+a[7]*100+a[8];
if(s1-s2 == s3){
System.out.println(s1+" - "+s2+" = "+s3);
}
}
}


对上面程序的一点改进：
改进部分：如何从10个数字中取出9个排成一列
上面例子中每次递归都要做depth判断来排除已经选用的数字
下面这个程序则不需要判断

程序：
Perm2.java
package org.chao.perm;
public class Perm2 {
public static void main(String[] args) {
int num[] = { 0,1,2,3,4,5,6,7,8,9 };
int n=num.length;
generate(num, n-1);
}
private static void generate(int[] num, int n) {
if (n == 0) {
//打印出num;
} else {
for (int i = 0; i <= n; i++) {
swap(num,i,n-1);
generate(num, n - 1);
swap(num,i,n-1);
}
}
}
private static void swap(int[] num, int i, int j) {
int tmp = num[i];
num[i] = num[j];
num[j] = tmp;
}
}