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