leetcode中数学相关算法

1、不用加减乘除实现加法运算

link: https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/

class Solution {
    public int add(int a, int b) {
        while(b != 0) { // 当进位为 0 时跳出
            int c = (a & b) << 1;  // c = 进位
            a ^= b; // a = 非进位和
            b = c; // b = 进位
        }
        return a;
    }
}

2、求最大公约数

class Solution {
    public int gcd(int a, int b) {
        // 递归算法
        // if (b == 0) {
        //     return a;
        // }
        // return gcd(b, a % b);

        // 非递归算法
        while(b != 0){
            int tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }
}

3、圆圈中最后剩下的数字（约瑟夫环问题）

link：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/

class Solution {
    public int lastRemaining(int n, int m) {
        // 递归算法
        // return func(n, m);

        // 非递归算法
        int f = 0;
        for (int i = 2; i != n + 1; ++i) {
            f = (m + f) % i;
        }
        return f;
    }

    // 递归算法，状态转移方程：f(n, m) = (f(n-1, m) + m) % n
    public int func(int n, int m) {
        if (n == 1) {
            return 0;
        }
        int x = f(n - 1, m);
        return (m + x) % n;
    }

}