数学题：实现

0263. 丑数 (opens new window)

题目

编写一个程序判断给定的数是否为丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

解析

将质因数除去后判断结果是否为 1 即可。

代码

class Solution {
public:
    bool isUgly(int n) {
        if (n == 0) {
            return false;
        }
        while (n % 2 == 0) n /= 2;
        while (n % 3 == 0) n /= 3;
        while (n % 5 == 0) n /= 5;

        return n == 1;
    }
};

0264. 丑数 II (opens new window)

题目

编写一个程序，找出第 n 个丑数。

丑数就是质因数只包含 2, 3, 5 的正整数。

解析

使用三个指针 i2、i3、i5，标记所指向丑数要乘以的因子。

算法很简单：在 nums[i2] * 2、nums[i3] * 3 和 nums[i5] * 5 中选出最小的丑数并添加到数组中。并将该丑数对应的因子指针往前走一步。重复该步骤直到计算完 n 个丑数。

代码

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> nums(n, 1);
        int i2 = 0, i3 = 0, i5 = 0;
        for (int i = 1; i < n; i ++) {
            nums[i] = min(min(nums[i2] * 2, nums[i3] * 3), nums[i5] * 5);
            if (nums[i] == nums[i2] * 2) i2 ++;
            if (nums[i] == nums[i3] * 3) i3 ++;
            if (nums[i] == nums[i5] * 5) i5 ++;
        }
        return nums[n - 1];
    }
};

0412. Fizz Buzz (opens new window)

题目

写一个程序，输出从 1 到 n 数字的字符串表示。

1. 如果 n 是 3 的倍数，输出“Fizz”；
2. 如果 n 是 5 的倍数，输出“Buzz”；
3. 如果 n 同时是 3 和 5 的倍数，输出 “FizzBuzz”。

解析

按要求实现即可，判断顺序需要注意一下。

代码

class Solution {
public:
    vector<string> fizzBuzz(int n) {
        vector<string> ans;
        for (int i = 1; i <= n; i ++) {
            if (i % 3 == 0 && i % 5 == 0) {
                ans.push_back("FizzBuzz");
            } else if (i % 3 == 0) {
                ans.push_back("Fizz");
            } else if (i % 5 == 0) {
                ans.push_back("Buzz");
            } else {
                ans.push_back(to_string(i));
            }
        }
        return ans;
    }
};

0453. 最小操作次数使数组元素相等 (opens new window)

题目

给定一个长度为 n 的非空整数数组，每次操作将会使 n - 1 个元素增加 1。找出让数组所有元素相等的最小操作次数。

解析

将 n - 1 个元素增加 1，等价于将 1 个元素减少 1，因为我们只对元素的相对大小感兴趣。

因此，该问题简化为需要进行的减法次数。只需计算出数组的最小值，然后统计所有元素与最小值的差的和即可。

代码

class Solution {
public:
    int minMoves(vector<int>& nums) {
        int min_num = INT_MAX;
        for (int i = 0; i < nums.size(); i ++) {
            if (nums[i] < min_num) {
                min_num = nums[i];
            }
        }

        int ans = 0;
        for (int i = 0; i < nums.size(); i ++) {
            ans += nums[i] - min_num;
        }
        return ans;
    }
};

0592. 分数加减运算 (opens new window)

题目

给定一个表示分数加减运算表达式的字符串，你需要返回一个字符串形式的计算结果。 这个结果应该是不可约分的分数，即最简分数。 如果最终结果是一个整数，例如 2，你需要将它转换成分数形式，其分母为 1。所以在上述例子中, 2 应该被转换为 2/1。

解析

首先进行通分，分子求和，然后再根据分子和与分母的最大公约数进行约分即可。

代码

class Solution {
public:
    string fractionAddition(string expression) {
        istringstream in(expression);
        int A = 0, B = 1, a, b;
        char _;
        while (in >> a >> _ >> b) {
            A = A * b + B * a;
            B = B * b;
            int g = abs(__gcd(A, B));
            A /= g;
            B /= g;
        }
        return to_string(A) + '/' + to_string(B);
    }
};