欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode—数学

程序员文章站 2022-03-13 12:57:29
...

LeetCode—数学

素数分解

整除

最大公约数最小公倍数

1、生成素数序列
T204. Count Primes (Easy)
LeetCode—数学

class Solution {
public:
    int countPrimes(int n) {
        int count = 0;
    //初始默认所有数为质数
    vector<bool> signs(n, true);
    for (int i = 2; i < n; i++) {
        if (signs[i]) {
            count++;
            for (int j = i + i; j < n; j += i) {
                //排除不是质数的数
                signs[j] = false;
            }
        }
    }
    return count;


    }
};

2、最大公约数

3、使用位操作和减法求解最大公约数
编程之美:2.7

进制转换

1、7 进制
T504. Base 7 (Easy)
LeetCode—数学

class Solution {
public:
    string convertToBase7(int num) {
        if(num == 0){
            return "0";
        }
        bool flag = true; //是否为正数
        if(num < 0){
            flag = false;
            num = -num;
        }
        string ans;
        while(num != 0){
            ans.push_back(char(num % 7 + '0'));
            num /= 7;
        }
        if(!flag){  //为负数
            ans.push_back('-');
        }
        reverse(ans.begin(), ans.end());    //反转字符串才为结果
        return ans;


    }
};

2、16 进制
T405. Convert a Number to Hexadecimal (Easy)
LeetCode—数学

class Solution {
public:
    string toHex(int num) {
        string res = "";
        for (int i = 0; num && i < 8; ++i) {
            int t = num & 0xf;
            if (t >= 10) res = char('a' + t - 10) + res;
            else res = char('0' + t) + res;
            num >>= 4;
        }
        return res.empty() ? "0" : res;

    }
};

3、26 进制
T168. Excel Sheet Column Title (Easy)
LeetCode—数学

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

    }
};

阶乘

1、统计阶乘尾部有多少个 0
T172. Factorial Trailing Zeroes (Easy)
LeetCode—数学

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

    }
};

字符串加法减法

1、二进制加法
T67. Add Binary (Easy)
LeetCode—数学

class Solution {
public:
    string addBinary(string a, string b) {
        string res = "";
        int m = a.size() - 1, n = b.size() - 1, carry = 0;
        while (m >= 0 || n >= 0) {
            int p = m >= 0 ? a[m--] - '0' : 0;
            int q = n >= 0 ? b[n--] - '0' : 0;
            int sum = p + q + carry;
            res = to_string(sum % 2) + res;
            carry = sum / 2;
        }
        return carry == 1 ? "1" + res : res;
        
    }
};

2、字符串加法
T415. Add Strings (Easy)
LeetCode—数学

class Solution {
public:
    string addStrings(string num1, string num2) {
        string res = "";
        int m = num1.size(), n = num2.size(), i = m - 1, j = n - 1, carry = 0;
        while (i >= 0 || j >= 0) {
            int a = i >= 0 ? num1[i--] - '0' : 0;
            int b = j >= 0 ? num2[j--] - '0' : 0;
            int sum = a + b + carry;
            res.insert(res.begin(), sum % 10 + '0');
            carry = sum / 10;
        }
        return carry ? "1" + res : res;

    }
};

相遇问题

1、改变数组元素使所有的数组元素都相等
T462. Minimum Moves to Equal Array Elements II (Medium)
LeetCode—数学

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        int res = 0, i = 0, j = (int)nums.size() - 1;
        sort(nums.begin(), nums.end());
        while (i < j) {
            res += nums[j--] - nums[i++];
        }
        return res;

    }
};

多数投票问题

1、数组中出现次数多于 n / 2 的元素
T169. Majority Element (Easy)
LeetCode—数学

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

其它

1、平方数
T367. Valid Perfect Square (Easy)
LeetCode—数学

class Solution {
public:
    bool isPerfectSquare(int num) {
       int i = 1;
        while (num > 0) {
            num -= i;
            i += 2;
        }
        return num == 0;

    }
};

2、3 的 n 次方
T326. Power of Three (Easy)
LeetCode—数学

class Solution {
public:
    bool isPowerOfThree(int n) {
        return (n > 0 && int(log10(n) / log10(3)) - log10(n) / log10(3) == 0);

    }
};

3、乘积数组
T238. Product of Array Except Self (Medium)
LeetCode—数学

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

    }
};

4、找出数组中的乘积最大的三个数
T628. Maximum Product of Three Numbers (Easy)
LeetCode—数学

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int p = nums[0] * nums[1] * nums[n - 1];
        return max(p, nums[n - 1] * nums[n - 2] * nums[n - 3]);

    }
};