devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

LeetCode力扣刷题——巧解数学问题_数学对于leetcode

作者：从前慢现在也慢 | 2024-08-22 18:36:31

赞

踩

数学对于leetcode

数论

一、引言

        对于 LeetCode 上数量不少的数学题，我们尽量将其按照类型划分讲解。然而很多数学题的解法并不通用，我们也很难在几道题里把所有的套路讲清楚，因此我们只选择了几道经典或是典型的题目，供大家参考。

二、经典问题

1. 公倍数与公因数

        利用辗转相除法（欧几里得算法），我们可以很方便地求得两个数的最大公因数（greatest common divisor ， gcd ）；将两个数相乘再除以最大公因数即可得到最小公倍数（least common multiple, lcm ）。 
  1. int gcd(int a, int b){
  2.     return b == 0? a: gcd(b, a%b);
  3. }
  4. int lcm(int a, int b){
  5.     return a / gcd(a, b) * b;
  6. }

         进一步地，我们也可以通过扩展欧几里得算法（extended gcd）在求得 a 和 b 最大公因数的同时，也得到它们的系数 x 和 y，从而使 ax + by = gcd(a, b)。

  1. int xGCD(int a,int b, int &x, int &y){
  2.     if(!b){
  3.         x = 1, y = 0;
  4.         return a;
  5.     }
  6.     int x1, y1,;
  7.     int gcd = xGCD(b, a%b, x1, y1);
  8.     x = y1, y = x1 - (a / b) * y1;
  9.     return gcd;
  10. }

2. 质数

        质数又称素数，指的是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然 数。值得注意的是，每一个数都可以分解成质数的乘积。
        埃拉托斯特尼筛法（Sieve of Eratosthenes ，简称埃氏筛法）是非常常用的，判断一个整数是否是质数的方法。并且它可以在判断一个整数 n 时，同时判断所小于 n 的整数，因此非常适合这道题。其原理也十分易懂：从 1 到 n 遍历，假设当前遍历到 m ，则把所有小于 n 的、且是 m 的倍数的整数标为和数；遍历完成后，没有被标为和数的数字即为质数。

204. 计数质数

204. Count Primes

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

  1. class Solution {
  2. public:
  3.     int countPrimes(int n) {
  4.         if(n <= 2)  return 0;
  5.         vector<bool> prime(n, true);
  6.         int count = n - 2;
  7.         for(int i=2; i<n; ++i){
  8.             if(prime[i]){
  9.                 for(int j=2*i; j<n; j+=i){
  10.                     if(prime[j]){
  11.                         prime[j] = false;
  12.                         --count;
  13.                     }
  14.                 }
  15.             }
  16.         }
  17.         return count;
  18.     }
  19. };
        利用质数的一些性质，我们可以进一步优化该算法。 
  1. class Solution {
  2. public:
  3.     int countPrimes(int n) {
  4.         if(n <= 2)  return 0;
  5.         vector<bool> prime(n, true);
  6.         int count = n / 2; // 所有的偶数一定不是质数
  7.         int i = 3, sqrtn = sqrt(n);
  8.         while(i <= sqrtn){ // 最小质因子一定小于等于开方数
  9.             for(int j=i*i; j<n; j+=2*i){ // 避免偶数和重复遍历
  10.                 if(prime[j]){
  11.                     prime[j] = false;
  12.                     --count;
  13.                 }
  14.             }
  15.             do{
  16.                 i += 2;
  17.             }while(i <= sqrtn && !prime[i]); // 避免偶数和重复遍历
  18.         }
  19.         return count;
  20.     }
  21. };

3. 数字处理

504. 七进制数

504. Base 7

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

        进制转换类型的题，通常是利用除法和取模（mod ）来进行计算，同时也要注意一些细节，如 负数和零。如果输出是数字类型而非字符串，则也需要考虑是否会超出整数上下界。 
  1. class Solution {
  2. public:
  3.     string convertToBase7(int num) {
  4.         if(num == 0)    return "0";
  5.         bool is_negative = num < 0;
  6.         if(is_negative) num = -num;
  7.         string ans;
  8.         while(num){
  9.             int a = num / 7, b = num % 7;
  10.             ans = to_string(b) + ans;
  11.             num = a;
  12.         }
  13.         return is_negative? "-" + ans: ans;
  14.     }
  15. };

172. 阶乘后的零

172. Factorial Trailing Zeroes

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

        提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

        每个尾部的 0 由 2 × 5 = 10 而来，因此我们可以把阶乘的每一个元素拆成质数相乘，统计有多少个 2 和 5 。明显的，质因子 2 的数量远多于质因子 5 的数量，因此我们可以只统计阶乘结果里有多少个质因子 5 。 
  1. class Solution {
  2. public:
  3.     int trailingZeroes(int n) {
  4.         if(n == 0)  return 0;
  5.         return n / 5 + trailingZeroes(n / 5); 
  6.     }
  7. };

415. 字符串相加

415. Add Strings

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

        你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

  1. class Solution {
  2. public:
  3.     string addStrings(string num1, string num2) {
  4.         string output("");
  5.         reverse(num1.begin(), num1.end());
  6.         reverse(num2.begin(), num2.end());
  7.         int onelen = num1.length(), twolen = num2.length();
  8.         if(onelen <= twolen){
  9.             swap(num1, num2);
  10.             swap(onelen, twolen);
  11.         }
  12.         int addbit = 0;
  13.         for(int i=0; i<twolen; ++i){
  14.             int cur_sum = (num1[i] - '0') + (num2[i] - '0') + addbit;
  15.             output += to_string((cur_sum) % 10);
  16.             addbit = cur_sum < 10? 0: 1;
  17.         }
  18.         for(int i=twolen; i<onelen; ++i){
  19.             int cur_sum = (num1[i] - '0') + addbit;
  20.             output += to_string((cur_sum) % 10);
  21.             addbit = cur_sum < 10? 0: 1;
  22.         }
  23.         if(addbit){
  24.             output += "1";
  25.         }
  26.         reverse(output.begin(), output.end());
  27.         return output;
  28.     }
  29. };

326. 3 的幂

326. Power of Three

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

        整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3^x

        有两种方法，一种是利用对数。设 log_{3}^{n} = m ，如果 n 是 3 的整数次方，那么 m 一定是整数。 
  1. class Solution {
  2. public:
  3.     bool isPowerOfThree(int n) {
  4.         return fmod(log10(n) / log10(3), 1) == 0;
  5.     }
  6. };
        另一种方法是，因为在 int 范围内 3 的最大次方是 3^ 19 = 1162261467 ，如果 n 是 3 的整数次方，那么 1162261467 除以 n 的余数一定是零；反之亦然。 
  1. class Solution {
  2. public:
  3.     bool isPowerOfThree(int n) {
  4.         return n > 0 && 1162261467 % n == 0;
  5.     }
  6. };

4. 随即与取样

384. 打乱数组

384. Shuffle an Array

        给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。

实现 Solution class:

        Solution(int[] nums) 使用整数数组 nums 初始化对象
        int[] reset() 重设数组到它的初始状态并返回
        int[] shuffle() 返回数组随机打乱后的结果

        我们采用经典的 Fisher-Yates 洗牌算法，原理是通过随机交换位置来实现随机打乱，有正向和反向两种写法，且实现非常方便。注意这里“reset ”函数以及类的构造函数的实现细节。 
  1. class Solution {
  2. public:
  3.     vector<int> origin;
  4.     Solution(vector<int>& nums): origin(std::move(nums)) {
  5.  
  6.     }
  7.     
  8.     vector<int> reset() {
  9.         return origin;
  10.     }
  11.     
  12.     vector<int> shuffle() {
  13.         if(origin.empty())  return {};
  14.         vector<int> shuffled(origin);
  15.         int n = origin.size();
  16.         //反向洗牌
  17.         for(int i=n-1; i>=0; --i){
  18.             swap(shuffled[i], shuffled[rand() % (i + 1)]);
  19.         }
  20.         //正向洗牌
  21.         // for(int i=0; i<n; ++i){
  22.         //     int pos = rand() % (n - i);
  23.         //     swap(shuffled[i], shuffled[i + pos]);
  24.         // }
  25.         return shuffled;
  26.     }
  27. };
  28.  
  29. /**
  30.  * Your Solution object will be instantiated and called as such:
  31.  * Solution* obj = new Solution(nums);
  32.  * vector<int> param_1 = obj->reset();
  33.  * vector<int> param_2 = obj->shuffle();
  34.  */

528. 按权重随机选择

528. Random Pick with Weight

        给你一个 下标从 0 开始 的正整数数组 w ，其中 w[i] 代表第 i 个下标的权重。

        请你实现一个函数 pickIndex ，它可以 随机地 从范围 [0, w.length - 1] 内（含 0 和 w.length - 1）选出并返回一个下标。选取下标 i 的 概率 为 w[i] / sum(w) 。

        例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

        我们可以先使用 partial_sum 求前缀和（即到每个位置为止之前所有数字的和），这个结果对于正整数数组是单调递增的。每当需要采样时，我们可以先随机产生一个数字，然后使用二分法查找其在前缀和中的位置，以模拟加权采样的过程。这里的二分法可以用 lower_bound 实现。
        以样例为例，权重数组[1,3] 的前缀和为 [1,4] 。如果我们随机生成的数字为 1 ，那么 lower_bound 返回的位置为 0 ；如果我们随机生成的数字是 2 、 3 、 4 ，那么 lower_bound 返回的位置为 1 。
        关于前缀和的更多技巧，我们将在接下来的章节中继续深入讲解。 
  1. class Solution {
  2. public:
  3.     vector<int> sums;
  4.     Solution(vector<int>& w): sums(std::move(w)) {
  5.         partial_sum(sums.begin(), sums.end(), sums.begin());
  6.     }
  7.     
  8.     int pickIndex() {
  9.         int pos = (rand() % sums.back()) + 1;
  10.         return lower_bound(sums.begin(), sums.end(), pos) - sums.begin();
  11.     }
  12. };
  13.  
  14. /**
  15.  * Your Solution object will be instantiated and called as such:
  16.  * Solution* obj = new Solution(w);
  17.  * int param_1 = obj->pickIndex();
  18.  */

382. 链表随机节点

382. Linked List Random Node

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

实现 Solution 类：

        Solution(ListNode head) 使用整数数组初始化对象。
        int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。

        不同于数组，在未遍历完链表前，我们无法知道链表的总长度。这里我们就可以使用水库采样：遍历一次链表，在遍历到第 m 个节点时，有 \frac{1}{m}  的概率选择这个节点覆盖掉之前的节点选择。
        我们提供一个简单的，对于水库算法随机性的证明。对于长度为 n 的链表的第 m 个节点，最 后被采样的充要条件是它被选择，且之后的节点都没有被选择。这种情况发生的概率为   \frac{1}{m}\times\frac{m}{m+1}\times\frac{m+1}{m+2}\times...\times\frac{n-1}{n} = \frac{1}{n}  。因此每个点都有均等的概率被选择。 
  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* head;
  14.     Solution(ListNode* n): head(n) {
  15.  
  16.     }
  17.     
  18.     int getRandom() {
  19.         int ans = head->val;
  20.         ListNode* node = head->next;
  21.         int i = 2;
  22.         while(node){
  23.             if((rand() % i) == 0){
  24.                 ans = node->val;
  25.             }
  26.             ++i;
  27.             node = node->next;
  28.         }
  29.         return ans;
  30.     }
  31. };
  32.  
  33. /**
  34.  * Your Solution object will be instantiated and called as such:
  35.  * Solution* obj = new Solution(head);
  36.  * int param_1 = obj->getRandom();
  37.  */

三、巩固练习

168. Excel表列名称

168. Excel Sheet Column Title

67. 二进制求和

67. Add Binary

238. 除自身以外数组的乘积

238. Product of Array Except Self

462. 最小操作次数使数组元素相等 II

462. Minimum Moves to Equal Array Elements II

169. 多数元素

169. Majority Element

470. 用 Rand7() 实现 Rand10()

470. Implement Rand10() Using Rand7()

202. 快乐数

202. Happy Number

欢迎大家共同学习和纠正指教

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/1017551
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号