07数字处理问题
# 07 数字处理问题
# 238 除自身以外数组的乘积 (opens new window)
给定一个长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
输入一个数组,输出一个数组,其中每个元素数值为除本身之外所有元素的乘积
输入: [1,2,3,4] 输出: [24,12,8,6]
解析:
本题与135题分糖果相似,可以先从左到右计算当前元素左侧所有元素的乘积,然后从右到左计算当前元素右侧所有元素的乘积,再将两个元素乘积相乘得到最终结果。
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int len = nums.size();
vector<int> output(len,1);
vector<int> L(len,1);
vector<int> R(len,1);
for(int i=1;i<len;++i){
L[i] = L[i-1] * nums[i-1];
}
for(int i=len-2;i>=0;--i){
R[i] = R[i+1] * nums[i+1];
output[i] = L[i]*R[i];
}
output[len-1] = L[len-1];
return output;
}
};
进一步优化空间复杂的,在从左和从右扫描中,用一个全局变量记录 i 之前或 i 之后所有元素的乘积
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int len = nums.size();
vector<int> output(len,1);
int product = nums[0];
for(int i=1;i<len;++i){
output[i] = product;
product *= nums[i]; // 记录从开头到当前位置中所有元素的乘积
}
product = nums[len-1];
for(int i=len-2;i>=0;--i){
output[i] *= product;
product *= nums[i];// 记录从结尾到当前位置中所有元素的乘积
}
return output;
}
};
# 326 3的幂 (opens new window)
判断一个数字是否是 3 的次方。
输入一个整数,输出一个布尔值。
Input: n = 27 Output: true
解析:
第一种方式是使用对数函数以3为底的对数函数,如果 n 是 3 的次方那么其值应该为整数。math库中提供了以 e 为底的log()
和以10为底的log10()
,根据换底公式有log3(n) = log10(n)/log10(3)
。
$$
log_a^b = log_c^b / log_c^a
$$
class Solution {
public:
bool isPowerOfThree(int n) {
if(n == 0) return false;
double m = log10(n) / log10(3);
// fmod(double x, double y) 用于计算浮点数取模
return fmod(m,1) == 0;
}
};
另一中方式因为在 int 范围内 3 的最大次方是 3^19 = 1162261467,如果 n 是 3 的整数次方,那么 1162261467 除以 n 的余数一定是零;反之亦然。
class Solution {
public:
bool isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}
};
上次更新: 2023/11/19, 12:55:48