LeetCode—数学
程序员文章站
2022-03-13 12:57:29
...
LeetCode—数学
素数分解
整除
最大公约数最小公倍数
1、生成素数序列
T204. Count Primes (Easy)
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)
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)
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)
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)
class Solution {
public:
int trailingZeroes(int n) {
int res = 0;
while (n) {
res += n / 5;
n /= 5;
}
return res;
}
};
字符串加法减法
1、二进制加法
T67. Add Binary (Easy)
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)
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)
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)
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)
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)
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)
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)
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]);
}
};