leetcode经典题目（5）--数学问题

1 计数质数

题目描述：统计所有小于非负整数 n 的质数的数量。 解题思路：如果遍历所有数值，判断每个数是否为质数，就会超时。这里使用埃拉托斯特尼筛法，每次找到一个素数时，将能被素数整除的数排除掉。使用一个数组isPrime，isPrime[i]表示是否为质数。如果找到一个质数，则将数组中该数的所有小于n的倍数位置的值置为false。

class Solution { public: int countPrimes(int n) { if (n <= 1) return 0; vector<bool> isPrime(n,true); isPrime[0] = false; isPrime[1] = false; int count = 0; for (int i = 2; i < n; i++){ if (isPrime[i]){//i是素数 count++; for (int j = 2 * i; j < n; j += i) isPrime[j] = false; } } return count; } };

2 最大公约数

2.1 辗转相除法

int gys(int a, int b){ if (a < b){ int tmp = b; b = a; a = b; } while (b != 0){ int tmp = a % b; a = b; b = tmp; } return a; }

两个数的最小公倍数等于两数乘积除以最大公约数。

2.2 使用位操作和减法求解最大公约数

bool isEven(int a){ return (a & 1) == 0; } int gcd(int a, int b){ if (a < b) return gcd(b,a); if (b == 0) return a; if (isEven(a) && isEven(b)) return 2 * gcd(a >> 1, b >> 1); else if (isEven(a) && !isEven(b)) return gcd(a >> 1, b); else if (!isEven(a) && isEven(b)) return gcd(a, b >> 1); else return gcd(b, a - b); }

3. 进制转换

3.1 7 进制（NO.504）

class Solution { public: string convertToBase7(int num) { if (num < 0) return '-' + convertToBase7(-1*num); if (num == 0) return "0"; string res; while (num != 0){ res.insert(res.begin(),num % 7 + 48); num = num / 7; } return res; } };

3.2 16 进制（NO.405）

题目描述：给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。 暴力解法：对于正数，直接对16求余数和商。对于负数，采用补码，首先求绝对值的16进制表示（注意位数不够时前面要补0），在对所有位取反得到反码，将最后一位加1得到补码。

class Solution { public: string toHex(int num) { if (num == 0) return "0"; if (num < 0){ string tmp = toHex(-1*num); while (tmp.size() < 8)//前面添加0补位 tmp.insert(tmp.begin(),'0'); for (char& c : tmp){//取反，得到反码 if ((c >= 'a' && c <= 'f') || (c >= '0' && c <= '5')) c = 150 - c; else c = 111 - c; } //末尾加1 int key = 1; for (int i = tmp.size() - 1; i >= 0; i--){ if (key == 1){ if (tmp[i] == 57){ tmp[i] = 'a'; key = 0; } if (tmp[i] == 'f') tmp[i] = '0'; else{ tmp[i] += key; key = 0; } } } return tmp; } string res;//处理正数 while(num != 0){ int r = num % 16; if (r < 10) res.insert(res.begin(),r + 48); else res.insert(res.begin(),r + 87); num = num / 16; } return res; } };

核心思想：使用位运算，每4位，对应1位16进制数字。 （1）使用0xf(00…01111b)获取num的低4位。0x开头的数字是十六进制数字，后面跟的数字都要按照十六进制理解，0xf就是十六进制数字f，转换为10进制数字就是15. （2）">>"算数位移，其中正数右移左边补0，负数右移左边补1。位移运算并不能保证num==0，需要使用32位int保证（对应16进制小于等于8位）。如果num是正数，右移可以使num变为0，如果num是负数，右移会往前面添加1，所以右移num不会变为0.

class Solution { public: string toHex(int num) { if (num == 0) return "0"; string str = "0123456789abcdef"; string res; while (num && res.size() < 8){ res.insert(res.begin(),str[num & 0xf]); num >>= 4; } return res; } };

3.3 26进制-Excel表列名称（NO.168）

题目描述：给定一个正整数，返回它在 Excel 表中相对应的列名称。例如， 1 -> A … 26 -> Z 27 -> AA 28 -> AB … 解题思路：要注意26与Z对应，而n&=0。

class Solution { public: string convertToTitle(int n) { if (n == 0) return ""; string res; while (n){ if (n % 26 != 0){ res.insert(res.begin(),n % 26 + 64); n = n / 26; } else{//n是26的整数倍 res.insert(res.begin(),'Z'); n = n / 26 - 1; } } return res; } };

4. 阶乘

4.1 统计阶乘尾部有多少个 0（NO.172）

题目描述：给定一个整数 n，返回 n! 结果尾数中零的数量。 解题思路：尾部的 0 由 2 * 5 得来，2 的数量明显多于 5 的数量，因此只要统计有多少个 5 即可。对于一个数 N，它所包含 5 的个数为：$N/5+N/5^2+N/5^3+...$，其中 N/5 表示不大于 N 的数中 5 的倍数贡献一个 5，$N/5^2$ 表示不大于 N 的数中 $5^2$ 的倍数再贡献一个 5 。例如25贡献两个5，在5的倍数里面算了一次，在25的倍数里面又算了一次，共算了两次。

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

5. 字符串加法减法

5.1 二进制加法（NO.67）

题目描述：给你两个二进制字符串，返回它们的和（用二进制表示）。输入为 非空 字符串且只包含数字 1 和 0。

class Solution { public: string addBinary(string a, string b) { //首先将两个字符串的位数补齐 int maxSize = a.size() < b.size() ? b.size() : a.size(); while (a.size() < maxSize) a.insert(a.begin(),'0'); while (b.size() < maxSize) b.insert(b.begin(),'0'); int key = 0;//表示是否进位 string res; for (int i = a.size()-1; i >= 0; i--){ int tmp = a[i] - '0' + b[i] - '0' + key; if (tmp > 1){ res.insert(res.begin(),'0' + tmp -2); key = 1; } else{ res.insert(res.begin(),'0' + tmp); key = 0; } } if (key == 1) res.insert(res.begin(),'1'); return res; } };

5.2 字符串加法（NO.415）

题目描述：给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

class Solution { public: string addStrings(string num1, string num2) { int key = 0; int i = num1.size() - 1, j = num2.size() - 1; string res; while (i >= 0 || j >= 0 || key == 1){ int a = 0, b = 0; if (i >= 0){ a = num1[i] - '0'; i--; } if (j >= 0){ b = num2[j] - '0'; j--; } int tmp = a + b + key; if (tmp > 9){ tmp -= 10; key = 1; } else{ key = 0; } res.insert(res.begin(),tmp + '0'); } return res; } };

6. 相遇问题

6.1 改变数组元素使所有的数组元素都相等（NO.462）

题目描述：给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。 解题思路：这是个典型的相遇问题，移动距离最小的方式是所有元素都移动到中位数。理由如下：设 m 为中位数。a 和 b 是 m 两边的两个元素，且 b > a。要使 a 和 b 相等，它们总共移动的次数为 b - a，这个值等于 (b - m) + (m - a)，也就是把这两个数移动到中位数的移动次数。

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

7. 多数投票问题

7.1 数组中出现次数多于 n / 2 的元素

题目描述：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。 解法一：由于多数元素必存在，对原数组排序后，n/2位置的元素就是多数元素。

class Solution { public: int majorityElement(vector<int>& nums) { sort(nums.begin(),nums.end()); return nums[nums.size()/2]; } };

解法二：

8. 其他

8.1 平方数（NO.367）

题目描述： 给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。 解题思路：平方序列：1,4,9,16,…，间隔：3,5,7,…。间隔为等差数列，使用这个特性可以得到从 1 开始的平方序列。

class Solution { public: bool isPerfectSquare(int num) { int tmp = 1; while (num > 0){ num -= tmp; tmp += 2; } if (num == 0) return true; else return false; } };

8.2 3 的 n 次方（NO.326）

题目描述：定一个整数，写一个函数来判断它是否是 3 的幂次方。 解题思路：

class Solution { public: bool isPowerOfThree(int n) { int tmp = 1; while(tmp < n){ tmp *= 3;//可能会超出int型范围 } return tmp == n; } }; class Solution { public: bool isPowerOfThree(int n) { return n > 0 && (1162261467 % n == 0); } };

8.3 除自身以外数组的乘积（NO.238）

题目描述：给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。请不要使用除法，且在 O(n) 时间复杂度内完成此题。 解题思路：如果可以使用除法，则可求出数组中所有数字的乘积，再除以相应位置的元素。使用left[i]表示第i个数前面所有数的乘积。right[i]表示第i个数后面所有数的乘积。

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

8.4 三个数的最大乘积（NO.628）

题目描述：给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。 解题思路：数组中三个数的最大乘积，可能是最大的三个数的乘积（三个正数），也可能是最大数和最小的两个数的乘积（一正两负）。

class Solution { public: int maximumProduct(vector<int>& nums) { int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN, min1 = INT_MAX, min2 = INT_MAX; for (int n : nums){ if (n > max1){ max3 = max2; max2 = max1; max1 = n; } else if (n > max2){ max3 = max2; max2 = n; } else if (n > max3) max3 = n; if (n < min1){ min2 = min1; min1 = n; } else if (n < min2) min2 = n; } return max(max1*max2*max3,max1*min1*min2); } }; class Solution { public: int maximumProduct(vector<int>& nums) { int n = nums.size(); sort(nums.begin(),nums.end()); return max(nums[n-1]*nums[n-2]*nums[n-3],nums[n-1]*nums[0]*nums[1]); } };