LeetCode刷题笔记(七): 数学问题

一、最大公约数和最小公倍数

这个没什么好说的，辗转相除法：

int gcd(int a, int b) { 
    return b == 0 ? a : gcd(b, a % b); 
}

int lcm(int a, int b) { 
    return a * b / gcd(a, b); 
}

也可以通过扩展欧几里得算法(extended gcd)在求得a和b最大公因数的同时，也得到它们的系数x和y，从而使ax+by=gcd(a, b)，也就是贝祖等式。

int xGCD(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int x_inner, y_inner;
    int gcd = xGCD(b, a % b, x_inner, y_inner);
    x = y_inner, y = x_inner - (a / b) * y_inner;
    return gcd;
}

二、质数

题目：计数质数
给定整数n，返回所有小于非负整数n的质数的数量。

解答：

class Solution {
public:
    int countPrimes(int n) {
        vector<bool> prime(n, true);
        int count = 0;
        if (n > 2) ++count;
        for (int i = 3; i < n; i += 2) {
            if (prime[i]) ++count;
            for (int j = 2 * i; j < n; j += i) {
                prime[j] = false;
            }
        }
        return count;
    }
};

提示：埃拉托斯特尼筛法(Sieve of Eratosthenes，简称埃氏筛法)是非常常用的，判断一个整数是否是质数的方法。并且它可以在判断一个整数n时，同时判断所小于n的整数，因此非常适合这道题。其原理也十分易懂：从1到n遍历，假设当前遍历到m，则把所有小于n的、且是m的倍数的整数标为和数；遍历完成后，没有被标为和数的数字即为质数。

三、数字处理

题目一：七进制数
给定一个整数num，将其转化为7进制，并以字符串形式输出。

解答：

class Solution {
public:
    string convertToBase7(int num) {
        if (num == 0) return "0";
        bool isNegative = num < 0;
        string res = "";
        num = isNegative ? -num : num;
        while (num > 0) {
            res.push_back(num % 7 + '0');
            num /= 7;
        }
        reverse(res.begin(), res.end());
        return isNegative ? "-" + res : res;
    }
};

提示：简单题，正常的模进制除进制。

题目二：阶乘后的零
给定一个非负整数，判断它的阶乘结果的结尾有几个0。

解答：

class Solution {
public:
    int trailingZeroes(int n) {
        int count = 0;
        while (n > 0) {
            n /= 5;
            count += n;
        }
        return count;
    }
};

提示：就是算有多少个2*5，然而2的数量肯定远多于5，所以只需要算5的数量。

题目三：字符串相加
给定两个由数字组成的字符串，求它们相加的结果。

解答：

class Solution {
public:
    string addStrings(string num1, string num2) {
        int minus = num1.length() - num2.length();
        if (minus < 0) {
            for (int i = 0; i < -minus; ++i)
                num1 = "0" + num1;
        } else {
            for (int i = 0; i < minus; ++i)
                num2 = "0" + num2;
        }
        int len = minus < 0 ? num2.length() : num1.length();
        string res;
        bool c = false;
        while (len > 0) {
            int temp1 = num1[len - 1] - '0';
            int temp2 = num2[len - 1] - '0';
            int add = temp1 + temp2 + c;
            if (add >= 10) {
                c = true;
                res.push_back(add - 10 + '0');
            } else {
                res.push_back(add + '0');
                c = false;
            }
            len--;
        }
        if (c) res.push_back(c + '0');
        reverse(res.begin(), res.end());
        return res;
    }
};

提示：注意进位。

题目四：3的幂
判断一个数字是否是 3 的次方。

解答：

class Solution {
public:
    bool isPowerOfThree(int n) {
        if (n <= 0) return false;
        while (n > 1) {
            int mod = n % 3;
            if (mod != 0) return false;
            n /= 3;
        }
        return true;
    }
};

提示：注意有小于等于零的情况。

题目五：Pow[x, n]
计算x的n次方。

解答：

class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) return 1;
        double res = 1.0, base = x;
        bool isNegative = (n < 0);
        if (isNegative) {
            if (n == INT_MIN) {
                res *= x;
                ++n;
            }
            n = -n;
        }
        while (n > 0) {
            if (n & 1 == 1) res *= base;
            base *= base;
            n >>= 1;
        }
        return isNegative ? 1 / res : res;
    }
};

提示：是一个值得记住的快速幂算法，理解位运算的含义。

四、随机与取样

题目一：打乱数组
给定一个数组，要求实现两个指令函数。第一个函数“shuﬄe”可以随机打乱这个数组，第二个函数“reset”可以恢复原来的顺序。

解答：

class Solution {
private:
    vector<int> myNums;

public:
    Solution(vector<int>& nums) {
        myNums = vector<int>(nums.begin(), nums.end());
    }
  
    vector<int> reset() {
        return myNums;
    }

    vector<int> shuffle() {
        vector<int> randNums = vector<int>(myNums.begin(), myNums.end());
        int size = randNums.size();
        // 从后往前打乱
        for (int i = size - 1; i >= 0; --i) {
            swap(randNums[i], randNums[rand() % (i + 1)]);
        }
        // 从前往后打乱
        // for (int i = 0; i < n; ++i) {
        // int pos = rand() % (n - i);
        // swap((randNums[i], randNums[i+pos]);
        // }
        return randNums;
    }
};

提示：其实就是后面交换前面不重复的，前面交换后面不重复的。

题目二：按权重随机选择
给定一个数组，数组每个位置的值表示该位置的权重，要求按照权重的概率去随机采样。

解答：

class Solution {
private:
    vector<int> myW;

public:
    Solution(vector<int>& w) {
        myW = vector<int>(w.begin(), w.end());
        for (int i = 1; i < myW.size(); ++i) {
            myW[i] += myW[i - 1];
        }
    }

    int pickIndex() {
        int target = rand() % myW.back() + 1;
        int low = 0, high = myW.size();
        while (low < high) {
            int mid = (low + high) >> 1;
            if (myW[mid] < target) low = mid + 1;
            else high = mid;
        }
        return low;
    }
};

提示：利用前缀和来做，在[num[i-1]+1, num[i]]之中的随机数相当于采样的第i个值。

题目三：链表随机节点
给定一个单向链表，要求设计一个算法，可以随机取得其中的一个数字。

解答：

// struct ListNode {
//     int val;
//     ListNode *next;
//     ListNode() : val(0), next(nullptr) {}
//     ListNode(int x) : val(x), next(nullptr) {}
//     ListNode(int x, ListNode *next) : val(x), next(next) {}
// };
//
class Solution {
private:
    ListNode* myList;

public:
    Solution(ListNode* head) {
        myList = head;
    }

    int getRandom() {
        ListNode* node = myList;
        int res = node->val;
        node = node->next;
        int i = 2;
        while (node != nullptr) {
            if (rand() % i == 0) res = node->val;
            node = node->next;
            ++i;
        }
        return res;
    }
};

提示：使用的核心思想是水库采样，在未遍历完链表前，我们无法知道链表的总长度。这里我们就可以使用水库采样：遍历一次链表，在遍历到第m个节点时，有1/m的概率选择这个节点覆盖掉之前的节点选择。提供一个简单的，对于水库算法随机性的证明。对于长度为n的链表的第m个节点，最后被采样的充要条件是它被选择，且之后的节点都没有被选择。这种情况发生的概率为1/m*m/(m+1)*(m+1)/(m+2)*…*(n-2)/(n-1)*(n-1)/n=1/n因此每个点都有均等的概率被选择。
另一种方法是用数组进行初始化，因为很简单就不展示了。

五、练习

题目一：Excel 表列名称
给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。
例如：A -> 1, B -> 2, C -> 3, Z -> 26, AA -> 27, AB -> 28

解答：

class Solution {
public:
    string convertToTitle(int columnNumber) {
        string res;
        while (columnNumber > 0) {
            int temp = columnNumber % 26;
            if (temp == 0) {
                res.push_back('Z');
                columnNumber = columnNumber / 26 - 1;
                continue;
            }
            res.push_back(temp + 'A' - 1);
            columnNumber /= 26;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

提示：Z相当于十进制中的10，所以处理的时候要注意单独处理。

题目二：除自身以外数组的乘积
给你一个整数数组nums，返回数组answer，其中answer[i]等于nums中除nums[i]之外其余各元素的乘积。

解答：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int size = nums.size();
        vector<int> res(size, 1);
        int temp = nums[0];
        for (int i = 1; i < size; ++i) {
            res[i] *= temp;
            temp *= nums[i];
        }
        temp = nums[size - 1];
        for (int i = size - 2; i >= 0; --i) {
            res[i] *= temp;
            temp *= nums[i];
        }
        return res;
    }
};

提示：我很喜欢的一道题，仔细思考如何才能乘到前缀和后缀。

题目三：最小操作次数使数组元素相等 II
给你一个长度为n的整数数组nums，返回使所有数组元素相等需要的最小操作数。在一次操作中，你可以使数组中的一个元素加1或者减1。

解答：

class Solution {
public:
    int minMoves2(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        int median = nums[nums.size() / 2];
        int moves = 0;
        for (int num : nums) {
            moves += abs(num - median);
        }
        return moves;
    }
};

提示：并不是很难的一道题，就是找中位数即可，你也可以通过快速选择来完成这道题。

题目四：多数元素
给定一个大小为n的数组nums，返回其中的多数元素。多数元素是指在数组中出现次数大于⌊n/2⌋的元素。

解答：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int k = 0, cand = 0;
        for (int num : nums) {
            if (k == 0) {
                k = 1;
                cand = num;
            } else {
                if (num == cand) ++k;
                else k--;
            }
        }
        return cand;
    }
};

提示：使用的核心思想是Boyer-Moore Majority Vote算法，可以自行上网查询该算法的思想，简单的理解就是不同的票会相互”抵消”。

题目五：用 Rand7() 实现 Rand10()
给定方法rand7可生成[1,7]范围内的均匀随机整数，试写一个方法rand10生成[1,10]范围内的均匀随机整数。

解答：

// int rand7();
class Solution {
public:
    int rand10() {
        while (1) {
            int i = (rand7() - 1) * 7;
            int j = rand7();
            int sum = i + j;
            if (sum <= 40) return sum % 10 + 1;
        }
    }
};

提示：不能简单地使用rand7()%4+rand7()，首先rand7()%4生成的数概率就不相同，其次这样相加出来的数概率也不相同，比如2只能为1+1，而3可以为2+1或者1+2，这里必须要乘以7的原因也在于此，这样才能生成均匀的[1, 49]，而如果值大于40的话，因为会影响概率，所以需要拒绝采样。

题目六：快乐数
编写一个算法来判断一个数n是不是快乐数。
「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为1，也可能是无限循环但始终变不到 1。
如果这个过程结果为1，那么这个数就是快乐数。

解答：

class Solution {
public: 
    int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }

    bool IsHappy(int n) {
        int slowRunner = n;
        int fastRunner = getNext(n);
        while (fastRunner != 1 && slowRunner != fastRunner) {
            slowRunner = getNext(slowRunner);
            fastRunner = getNext(getNext(fastRunner));
        }
        return fastRunner == 1;
    }
}

解答二(逃课解法)：

class Solution {
public:
    bool isHappy(int n) {
        int last = 0;
        int i = 10;
        while (i--) {
            last = n;
            int temp = 0;
            while (n > 0) {
                int num = n % 10;
                temp += (num * num);
                n /= 10;
            }
            n = temp;
            if (last == n) return true;
        }
        return false;
    }
};