许昌哪个网站做苗木,南沙高端网站建设,自己做网站难吗,新公司起名大全免费题目链接
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 题目解析 使用前缀和进行解决该题#xff0c;只不过与之前前缀和不同的是这个题目计算前缀和的时候不需要计算当前元素#xff0c;也就是当前位置前缀和的值其实是不包含当前元素的前缀和。…题目链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台 题目解析 使用前缀和进行解决该题只不过与之前前缀和不同的是这个题目计算前缀和的时候不需要计算当前元素也就是当前位置前缀和的值其实是不包含当前元素的前缀和。 我们算出该位置的前缀和(不包含当前元素)后缀和(不包含当前元素)。然后再相乘。 解题方法 法一我们直接定义三个数组一个记录最终结果一个计算前缀和一个计算后缀和。 法二只需要定义一个数组先计算前缀和然后使用一个变量记录后缀和与之相乘只需要遍历的过程中乘上后缀和即可。 代码
法一
class Solution
{
public:vectorint productExceptSelf(vectorint nums) {int nnums.size();vectorint answer(n),answer_front(n),answer_tail(n);answer_front[0]nums[0];answer_tail[n-1]nums[n-1];for(int i1;in;i){answer_front[i]answer_front[i-1]*nums[i];}for(int in-2;i0;i--){answer_tail[i]answer_tail[i1]*nums[i];}for(int i0;in;i){// 注意处理第一个元素与第二个元素if(i0)answer[i]answer_tail[i1];else if(in-1)answer[i]answer_front[n-2];else answer[i]answer_front[i-1]*answer_tail[i1];}return answer;}
};
法二
class Solution
{
public:vectorint productExceptSelf(vectorint nums) {int nnums.size();vectorint ret(n);// 先算前缀和// 第一个前缀和设为1目的是为了不影响后面数据的计算ret[0]1;// 需要注意的是我们所计算的前缀和是不包含自身的for(int i1;in;i)// 当前位置的前缀和等于上一个数的前缀和*上一个数组的元素ret[i]ret[i-1]*nums[i-1];// 再计算后缀和// 使用k来记录后缀和设为1为了不影响前边的后缀和数据int k1;for(int in-2;i0;i--){// 每次遍历都及时更新kk*nums[i1];// 更新ret[i]ret[i]ret[i]*k;}// 此时数组ret中的元素就是当前元素的前缀和*后缀和return ret;}
};
