牛牛浇树题解
100分解法
比较基础的一个差分题。可以选择离散化m个区间去差分，时间复杂度o(mlogm)，空间复杂度o(m)。当然，由于本题n较小，也可以不进行差分，时间复杂度o(n)，空间复杂度o(n)。
讲一下具体的思路。首先如果我们每棵树都没有浇水的话，m天后每棵树高度都为m。如果m是奇数的话，我们找到浇水次数为偶数的树的个数即可，反之找到浇水次数奇数的树个数即可，统计这一件事就需要用到差分。对于每个区间，我们可以在l[i]打上一个+1的标志，在r[i]打上一个-1的标志，然后用sum一边遍历数组一边记录数组的前缀和，在某一棵树的位置sum的值就是这棵树浇水的次数，统计一下其中奇数偶数的个数即可。下面给出不离散化的代码：
int a[20000005];
class Solution {
public:
/**
* 返回m天后高度为奇数的树的数量
* @param n int整型
* @param m int整型
* @param l int整型vector
* @param r int整型vector
* @return int整型
*/
int oddnumber(int n, int m, vector<int>& l, vector<int>& r) {
// write code here
for(int i=0;i<m;i++)a[l[i]]++,a[r[i]+1]--;
int ans=0,sum=0;
for(int i=1;i<=n;i++)
{
sum+=a[i];
if(sum%2)ans++;
}
if(m%2)return n-ans;
return ans;
}
};
查看8道真题和解析