LeetCode热题100：前缀和 差分

摘要

题目	知识点
56. 合并区间 - 力扣（LeetCode）	差分，排序
238. 除自身以外数组的乘积 - 力扣（LeetCode）	前缀和

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

1）差分

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
	vector<vector<int>> merge(vector<vector<int>>& v) {
		vector<int > diff(20010);
		vector<vector<int> > ans;
		// 对于[1,2], [3,4]的情况，本题需要分别输出。
		// 通过对每个区间[L,R]*2，分隔2个区间
		for(int i = 0 ; i < v.size() ; i ++){
			int l = v[i][0]*2;
			int r = v[i][1]*2;
			diff[l]++;
			diff[r+1]--;
		}
		for(int i = 1 ; i < diff.size() ; i ++){
			diff[i] += diff[i-1];
		}
		for(int i = 0 ; i < diff.size() ; i++){
			if(diff[i] != 0){
				int j = i+1;
				while(diff[j] != 0) j++;
				ans.push_back({i/2, (j-1)/2});
				i = j;
				continue;
			}
		}
		return ans;
	}
};

2）排序

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
	vector<vector<int>> merge(vector<vector<int>>& v) {
		vector<vector<int>> ans;
		sort(v.begin(), v.end());
        // 排序后，记录重叠数组即可
		int l = v[0][0], r = v[0][1];
		for(int i = 1 ; i < v.size() ; i ++){
			if(v[i][0] <= r){
				r = max(r, v[i][1]);
			}else{
				ans.push_back({l, r});
				l = v[i][0]; r = v[i][1];
			}
		}
		ans.push_back({l, r});
		return ans;
	}
};

除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
	vector<int> productExceptSelf(vector<int>& nums) {
		vector<int > pre(nums.size()), back(nums.size());
		vector<int > ans;
		for(int i = 0 ; i < nums.size() ; i ++){
			if(i == 0) pre[i] = nums[i];
			else pre[i] = nums[i]*pre[i-1];
		}
		for(int i = nums.size()-1 ; i >= 0 ; i --){
			if(i == nums.size()-1) back[i] = nums[i];
			else back[i] = nums[i]*back[i+1];
		}
		for(int i = 0 ; i < nums.size() ; i ++){
			int l = i == 0 ? 1 : pre[i-1];
			int r = i == nums.size()-1 ? 1 : back[i+1];
			ans.push_back(l*r);
		}
		return ans;
	}
};