算法思想.md

算法思想

链表类

Floyd 判圈算法/龟兔赛跑算法

使用两个指针slow和fast。两个指针开始时均在头节点处，slow指针（龟）一次向后移动一个一步，fast指针（兔）一次向后移动两步。若存在环，则slow和fast必能相遇；反之若slow到达链表尾时两个指针仍不能相遇，则不存在环。

数学类

欧几里得算法/辗转相除法

/**
 * 欧几里得算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法。
 * 扩展欧几里得算法可用于RSA加密等领域。
 * 假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：
 * 1997 / 615 = 3 (余 152)
 * 615 / 152 = 4(余7)
 * 152 / 7 = 21(余5)
 * 7 / 5 = 1 (余2)
 * 5 / 2 = 2 (余1)
 * 2 / 1 = 2 (余0)
 * 至此，最大公约数为1
 * 以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。
 */
int gcd(int m,int n)
{   if(n == 0){
        return m; 
    }
    int r = m%n;
    return gcd(n,r);
}

利用Math.log10计算数字位数

int x = 102333;
int n = (int)(Math.log10(x)+1);//6

巴什博奕

只有一堆n个物品,两个人轮流从这堆物品中取物,规定每次至少取1个,最多取m个.最后取光者得胜：

n%(m+1)!=0时，先手总是会赢的