card shuffler - Google Interview

card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡片的下一个位置
e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是ABCDE，43210的话下个卡片位置是EDCBA。
问给定一个shuffle array，不断用这个array去shuffle，能否得到最初的card deck，能得话要多少次。

https://hellosmallworld123.wordpress.com/2015/07/23/

我能想到的做法是一个一个的字母找，看多少次能回到原来的位置（或者不能回到原来的位置），记录这个次数为t[i], 然后求所有t[i]的LCM最小公倍数,
求最小公倍数的方法是先求最大公约数（用辗转相除法），然后再用a*b/gcd(a,b) 求最小公倍数。
X.

public int cardShuffler(int[] cards, int[] shuffle) {
int[] steps = new int [cards.length];
for(int i=0; i<cards.length; i++) {
steps[i] = stepsBack(i, shuffle);
if (steps[i] == -1)
return -1;
}
return LCM(steps);
}

private int stepsBack(int start, int[] shuffle) {
int i = start;
int res = 0;
Set visited = new HashSet();
do {
i = shuffle[i];
if (visited.contains(i))
return -1;
visited.add(i);
res++;
} while(i != start);
return res;
}

private int LCM(int[] steps) {
int res = steps[0];
for(int i=1; i<steps.length; i++) {
res = res*steps[i]/GCD(res, steps[i]);
}
return res;
}

private int GCD(int a, int b) {
int n1 = Math.max(a,b);
int n2 = Math.min(a,b);
while(n1%n2 != 0) {
int tmp = n1%n2;
n1 = n2;
n2 = tmp;
}
return n2;
}

http://shibaili.blogspot.com/2015/07/google-interview-questions-4.html
O(n), 对shuffle里面的每一个点都走一遍，最后走回起始点，走过的路径全部mark起来，记录count。mark过的可以直接跳过

最后取所以count的最小公约数即可 

int getSmallest(int i, int j) {

    for (int s = 1; s <= j; s++) {

        if (s * i % j == 0) return s * i;

    }

}

 

int jumpBack(vector<int> &shuffle) {

    vector<int> visit(shuffle.size(),-1);

    int count = 0, preCount = 1;

    for (int i = 0; i < shuffle.size(); i++) {

        count = 0;

        int index = i;

        while (visit[index] == -1) {

            count++;

            visit[index] = shuffle[i];

            index = shuffle[index];

            if (visit[index] != -1 && visit[index] != visit[i]) return -1;

        }

        if (count != 0) preCount = getSmallest(count,preCount);   

                

    }

     

    return preCount;

}