Leetcode 刷题笔记-Leetcode 101 第9章 数学问题

Leetcode 刷题笔记-Leetcode 101 第9章 数学问题

数学问题

公倍数与公因数

利用辗转相除法求得两个数的最大公因数，将两个数相乘再除以最大公因数即可得到最小公倍数

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

进一步也可以通过扩展欧几里得算法在求得 a和 b最大公因数的同时，也得到它们的系数 x和 y，从而使 ax + by = 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;
}

质数

Leetcode 204

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

class Solution {
public:
    int countPrimes(int n) {
        if(n <= 2){
            return 0;
        }
        vector<bool> nums(n,true);
        for(int i=2;i<n;++i){
            if(nums[i] == true){
                for(int j=2*i;j<n;j += i){
                    nums[j] = false;
                }
            }
        }
        return accumulate(nums.begin(),nums.end(),0) - 2;
    }
};

分析：使用埃拉托斯特尼筛法即可。

错误：有点忘记算法了。

数字处理

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

class Solution {
public:
    string convertToBase7(int num) {
        int sign = 0;
        if(num < 0){
            num = -num;
            sign = 1;
        }
        if(num == 0){
            return "0";
        }
        string result = "";
        while(num/7){
            char c = num%7 + '0';
            result =  c + result;
            num /= 7;
        }
        if(num != 0){
            char b = '0' + num;
            result =  b + result;
        }
        if(sign == 1){
            return '-' + result;
        }
        return result;
    }
};

分析：直接进制转换就行，注意进制转换的时候用十进制进行过渡比较方便。

错误：磕磕绊绊调通了。

Leetcode 172

给定一个整数 n ，返回 n! 结果中尾随零的数量。

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

分析：每个尾部的0由2*5 = 10而来，因此我们可以把阶乘的每一个元素拆成质数相乘，统计有多少个2和5。明显的，质因子2的数量远多于质因子5的数量，因此我们可以只统计阶乘结果里有多少个质因子5。

错误：没想到这么好的思路

Leetcode 415

给定两个字符串形式的非负整数 num1 和 num2 ，计算它们的和并同样以字符串形式返回。

class Solution {
public:
    string addStrings(string num1, string num2) {
        int n1 = num1.size();
        int n2 = num2.size();
        --n1;
        --n2;
        string result = "";
        int cnt = 0;
        while(n1 >= 0 && n2 >= 0){
            int temp = num1[n1] - '0' + num2[n2] - '0' + cnt;
            if(temp >= 10){
                cnt = 1;
            }
            else{
                cnt = 0;
            }
            char c = temp%10 + '0';
            result = c + result;
            --n1;
            --n2;
        }
        while(n1 >= 0){
            int temp = num1[n1] - '0' + cnt;
            if(temp >= 10){
                cnt = 1;
            }
            else{
                cnt = 0;
            }
            char c = temp%10 + '0';
            result = c + result;
            --n1;
        }
        while(n2 >= 0){
            int temp = num2[n2] - '0' + cnt;
            if(temp >= 10){
                cnt = 1;
            }
            else{
                cnt = 0;
            }
            char c = temp%10 + '0';
            result = c + result;
            --n2;
        }
        if(cnt == 1){
            return '1' + result;
        }
        return result;
    }
};

分析：大数相加，没什么新的东西

一遍AC

Leetcode 326

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false

class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n == 1){
            return true;
        }
        for(long long i=3;i<INT_MAX;i*=3){
            if(i == n){
                return true;
            }
        }
        return false;
    }
};

分析：比较简单，有更好的解法，需要数学能力

错误：n=1没有考虑

随机与取样

Leetcode 384

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

class Solution {
public:
    Solution(vector<int>& nums) {
        this->nums = nums;
        this->original.resize(nums.size());
        copy(nums.begin(), nums.end(), original.begin());
    }
  
    vector<int> reset() {
        copy(original.begin(), original.end(), nums.begin());
        return nums;
    }
  
    vector<int> shuffle() {
        if (nums.empty()) return {};
        vector<int> shuffled(nums);
        int n = nums.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;
    }
private:
    vector<int> nums;
    vector<int> original;
};

分析：经典的Fisher-Yates洗牌算法，原理是通过随机交换位置来实现随机打乱，有正向和反向两种写法

错误：类什么的还是不太会写

Leetcode 528

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

class Solution {
    vector<int> W;
public:
    Solution(vector<int>& w) {
        partial_sum(w.begin(), w.end(), back_inserter(W));
    }
  
    int pickIndex() {
        int pos = rand() % W.back();
        return upper_bound(W.begin(), W.end(), pos) - W.begin();
    }
};

分析：我们可以先使用 partial_sum求前缀和（即到每个位置为止之前所有数字的和），这个结果对于正整数数组是单调递增的。每当需要采样时，我们可以先随机产生一个数字，然后使用二分法查找其在前缀和中的位置，以模拟加权采样的过程。

错误：没思路

Leetcode 382

给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点被选中的概率一样 。

class Solution {
    vector<int> arr;
public:
    Solution(ListNode* head) {
        while (head) {
            arr.emplace_back(head->val);
            head = head->next;
        }
    }
  
    int getRandom() {
        return arr[rand() % arr.size()];
    }
};

分析：用一个数组记录链表中的所有结点值，然后随机输出即可。

错误：思路简单就是不会写

练习

Leetcode 168

给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。

class Solution {
public:
    string convertToTitle(int columnNumber) {
        string ans;
        while (columnNumber > 0) {
            int a0 = (columnNumber - 1) % 26 + 1;
            ans += a0 - 1 + 'A';
            columnNumber = (columnNumber - a0) / 26;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

分析：进制转换的变形题

错误：减法操作没想好

Leetcode 67

给你两个二进制字符串，返回它们的和（用二进制表示）。

class Solution {
public:
    string addBinary(string a, string b) {
        int a_size = a.size();
        int b_size = b.size();
        --a_size;
        --b_size;
        int cnt = 0;
        int sign;
        string result = "";
        while(a_size >= 0 && b_size >= 0){
            sign = a[a_size] - '0' + b[b_size] - '0' + cnt;
            if(sign == 0){
                result = "0" + result;
                cnt = 0;
            }
            else if(sign == 1){
                result = "1" + result;
                cnt = 0;
            }
            else if(sign == 2){
                result = "0" + result;
                cnt = 1;
            }
            else if(sign == 3){
                result = "1" + result;
                cnt = 1;
            }
            --a_size;
            --b_size;
        }
        while(a_size >= 0){
            sign = a[a_size] - '0' + cnt;
            if(sign == 0){
                result = "0" + result;
                cnt = 0;
            }
            else if(sign == 1){
                result = "1" + result;
                cnt = 0;
            }
            else if(sign == 2){
                result = "0" + result;
                cnt = 1;
            }
            else if(sign == 3){
                result = "1" + result;
                cnt = 1;
            }
            --a_size;
        }
        while(b_size >= 0){
            sign = b[b_size] - '0' + cnt;
            if(sign == 0){
                result = "0" + result;
                cnt = 0;
            }
            else if(sign == 1){
                result = "1" + result;
                cnt = 0;
            }
            else if(sign == 2){
                result = "0" + result;
                cnt = 1;
            }
            else if(sign == 3){
                result = "1" + result;
                cnt = 1;
            }
            --b_size;
        }
        if(cnt == 1){
            result = "1" + result;
        }
        return result;
    }
};

分析：还是大数加法

错误：忘记了，应该没什么错误

Leetcode 238

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

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n);
        vector<int> right(n);
        int start = 1;
        left[0] = start;
        for(int i=1;i<n;++i){
            left[i] = start * nums[i-1];
            start = left[i];
        }
        int end = 1;
        right[n-1] = end;
        for(int i=n-2;i>=0;--i){
            right[i] = end * nums[i+1];
            end = right[i];
        }
        vector<int> result(n);
        for(int i=0;i<n;++i){
            result[i] = left[i] * right[i];
        }
        return result;
    }
};

分析：前缀积+后缀积

错误：看了一下思路，后面自己想通了实现了

Leetcode 462

给你一个长度为 n 的整数数组 nums ，返回使所有数组元素相等需要的最少移动数。在一步操作中，你可以使数组中的一个元素加 1 或者减 1 。

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

分析：如果仅仅考虑最大的数字和最小的数字，那么这个数字一定在这两个数字中间，去除掉后这个数字也一定在次大的和次小的数字之间。因此是中位数

错误：思路不对，开始想成平均数了

Leetcode 169

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

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

分析：Boyer-Moore 算法：维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：如果 x 与 candidate 相等，那么计数器 count 的值增加 1；如果 x 与 candidate 不等，那么计数器 count 的值减少 1。在遍历完成后，candidate 即为整个数组的众数。

错误：算法想的不太好，没有想到最优的解法。

Leetcode 470

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。

class Solution {
public:
    int rand10() {
        int row, col, idx;
        do {
            row = rand7();
            col = rand7();
            idx = col + (row - 1) * 7;
        } while (idx > 40);
        return 1 + (idx - 1) % 10;
    }
};

分析：调用两次rand7()，找到一些等概率的数字，然后拒绝掉另外的数字。

错误：想当然认为是直接乘法了。

Leetcode 202

编写一个算法来判断一个数 n 是不是快乐数。

class Solution {
public:
    bool isHappy(int n) {
        int sum = 6;
        while(sum--){
            string s = to_string(n);
            int t = 0;
            for(int i=0;i<s.size();++i){
                t += (s[i] - '0') * (s[i] - '0');
            }
            if(t == 1){
                return true;
            }
            n = t;
        }
        return false;
    }
};

分析：看看会不会跳出循环

一遍AC，但是解法不够好，后面要用更好的方法进行尝试。

总结

数学问题需要有数学基础，一般面试中应该用的比较少，有些问题还是挺有意思的。