LC101の8. 数学

title: LC101の8. 数学
date: ‘2021-07-20 09:50:06’
tags: [数学]
categories:

• 动手敲敲
• 算法刷题

公倍数与公因数

辗转相除法

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);
}

扩展欧几里得

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

质数

204. 计数质数

埃氏筛

int countPrimes(int n) {
    vector<int> isPrime(n, 1);
    int ans = 0;
    for (int i = 2; i < n; ++i) {
        if (isPrime[i]) {
            ans += 1;
            if ((long long)i * i < n) {
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = 0;
                }
            }
        }
    }
    return ans;
}

数字处理

504. 七进制数

string convertToBase7(int num) {
    bool flag = false;
    string ans = "";
    if(num < 0){
        num = -num;
        flag = true;
    }
    do{
        ans += to_string(num % 7);
        num /= 7;
    }while(num);
    reverse(ans.begin(), ans.end());
    return flag? "-" + ans: ans;
}

172. 阶乘后的零

int trailingZeroes(int n) {
    int ans = 0;
    for (int i = 5; i <= n; i += 5) {
        for (int x = i; x % 5 == 0; x /= 5) {
            ++ans;
        }
    }
    return ans;
}

415. 字符串相加

string addStrings(string num1, string num2) {
    int i = num1.length() - 1, j = num2.length() - 1, add = 0;
    string ans = "";
    while (i >= 0 || j >= 0 || add != 0) {
        int x = i >= 0 ? num1[i] - '0' : 0;
        int y = j >= 0 ? num2[j] - '0' : 0;
        int result = x + y + add;
        ans.push_back('0' + result % 10);
        add = result / 10;
        i --;
        j --;
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

326. 3 的幂

bool isPowerOfThree(int n) {
    while (n && n % 3 == 0) {
        n /= 3;
    }
    return n == 1;
}

随机与取样

384. 打乱数组

经典的 Fisher-Yates 洗牌算法，原理是通过随机交换位置来实现随机打乱。

class Solution {
    vector<int> origin;
public:
    Solution(vector<int> nums): origin(std::move(nums)) {}
    vector<int> reset() {
        return origin;
    }
    vector<int> shuffle() {
    if (origin.empty()) return {};
    vector<int> shuffled(origin);
    int n = origin.size();
    // 可以使用反向或者正向洗牌，效果相同。
    // 反向洗牌：
    for (int i = n - 1; i >= 0; --i) {
        swap(shuffled[i], shuffled[rand() % (i + 1)]);
    }
    // 正向洗牌：
    // for (int i = 0; i < n; ++i) {
    // int pos = rand() % (n - i);
    // swap(shuffled[i], shuffled[i+pos]);
    // }
    return shuffled;
    }
};

528. 按权重随机选择

题目大意：按权重随机返回数字

class Solution {
    vector<int> sums;
public:
    Solution(vector<int> weights): sums(std::move(weights)) {
        partial_sum(sums.begin(), sums.end(), sums.begin());
    }
    int pickIndex() {
        int pos = (rand() % sums.back()) + 1;
        return lower_bound(sums.begin(), sums.end(), pos) - sums.begin();
    }
};

382. 链表随机节点

题目大意：随机返回链表的一个节点

class Solution {
ListNode* head;
    public:
    Solution(ListNode* n): head(n) {}
    int getRandom() {
        int ans = head->val;
        ListNode* node = head->next;
        int i = 2;
        while (node) {
            if ((rand() % i) == 0) {
            ans = node->val;
            }
            ++i;
            node = node->next;
        }
        return ans;
    }
};

练习