[解决方案报告] 算法 100 讲零（第 29 讲）容忍原则
目录
零、写在前面
一、主要知识点
1.容斥原理
二、课后习题
509. 斐波那契数
920. 播放列表的数量
1782. 统计点对的数目
写在最后
零、写在前面
今天是打卡的第29天，今天好累，不过这题的难度直接给我从困的状态泼醒了，这也太难了点吧，我足足肝了三个小时，太可怕了，知识点在：
《算法零基础100讲》(第29讲) 容斥原理https://blog.****.net/WhereIsHeroFrom/article/details/120875965
https://blog.****.net/WhereIsHeroFrom/article/details/120875965
一、主要知识点
1.容斥原理
其实很简单的，就是多减的就加回来，多加的就减下去，就好了。
二、课后习题
509. 斐波那契数
1201. 丑数 III
https://leetcode-cn.com/problems/ugly-number-iii/
题目描述
给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。
丑数是可以被 a 或 b 或 c 整除的 正整数 。
思路
第n个丑数一定是满足下列式子的值 我们用二分去找到这个值就好了。。
int gcd(int a,int b){ //最大公约数 if(a == 0) return b ; return gcd(b%a,a); } long long gcm(long long a, long long b){ //最好输入就是长整型 不然会溢出哦 return (a*b)/gcd(a,b); } bool check(int n,int a,int b,int c,long long mid){//判断是否满足 if((mid/a+mid/b+mid/c-mid/gcm(a,b)-mid/gcm(a,c)-mid/gcm(b,c)+mid/gcm(gcm(a,b),c))>=n) return true; return false; } int min(int a,int b){return a < b ? a : b;}//返回最小值 int nthUglyNumber(int n, int a, int b, int c){ long long left = 0,right = n*min(min(a,b),c); while(left < right){ //二分查找满足条件的解 int mid = left +(right - left)/2; if(check(n,a,b,c,mid)) right = mid; else left = mid+1; } return right; }
920. 播放列表的数量
920. 播放列表的数量
https://leetcode-cn.com/problems/number-of-music-playlists/
题目描述
你的音乐播放器里有 N 首不同的歌，在旅途中，你的旅伴想要听 L 首歌（不一定不同，即，允许歌曲重复）。请你为她按如下规则创建一个播放列表：
每首歌至少播放一次。
一首歌只有在其他 K 首歌播放完之后才能再次播放。
返回可以满足要求的播放列表的数量。由于答案可能非常大，请返回它模 10^9 + 7 的结果。
思路
考虑最后一首歌的情况，只有两种
一种是之前播放过 播放过那么就只能是之前的 j-k其中j表示之前的歌曲数目 但是不能小于0
一种是之前没播放过 没播放过的 那么可以选的有 n-j 种 其中j为之前播放过的数目
有递推式
int max(int a,int b){ return a>b?a:b; } int numMusicPlaylists(int n, int goal, int k){ int mod = 1000000007; long long ans[goal+1][n+1]; memset(ans,0,sizeof(ans)); ans[0][0] = 1; //初始值 for(int i = 1;i<=goal;i++) for(int j = 1;j<=n;j++){ ans[i][j] = ans[i-1][j-1]*(n - j + 1) +ans[i-1][j]*max(j-k,0);//递推 ans[i][j] %= mod; } return ans[goal][n]; }
1782. 统计点对的数目
1782. 统计点对的数目
https://leetcode-cn.com/problems/count-pairs-of-nodes/
题目描述
给你一个无向图，无向图由整数 n ，表示图中节点的数目，和 edges 组成，其中 edges[i] = [ui, vi] 表示 ui 和 vi 之间有一条无向边。同时给你一个代表查询的整数数组 queries 。
第 j 个查询的答案是满足如下条件的点对 (a, b) 的数目：
a < b
cnt 是与 a 或者 b 相连的边的数目，且 cnt 严格大于 queries[j] 。
请你返回一个数组 answers ，其中 answers.length == queries.length 且 answers[j] 是第 j 个查询的答案。
请注意，图中可能会有 重复边 。
思路
最容易想到的方式就是记录所有的边信息，搞一个邻接矩阵，然后进行统计。但是 会超时。
为了加速，为了加速，一切都是为了加速。一开始会记录有哪些边，并且记录相应的权重。
接下来统计的时候
1.先统计任意两个顶点的边和大于所给值的 (这里的任意性才有加速的可能)
2.遍历所有边看其两个端点的和是否大于所给值的同时不符合要求 结果数量就要减少
其中为了计算两个顶点和大于给定值 用了双指针，就要预先对数据进行排序。这里复杂度大概就是 n+logn的快排复杂度。不过也同时增加了排序的空间消耗，需要对数据进行备份。排序之后所保存的hash映射就会丢失。
然后遍历所有边也就是m的复杂度。这道题卡时间太狠了。导致我一开始不能好好的初始化我的邻接矩阵，那我的思路就是，先遍历边 哪些边有值我再初始化哪些。
整道题的思路都是n^2的复杂度肯定比m的复杂度高，所有的一切全是围绕着遍历边进行复杂度的降低。
int cmp(int *a, int * b){ return *a > *b; } int hash[400000001]; //邻接矩阵 int* countPairs(int n, int** edges, int edgesSize, int* edgesColSize, int* queries, int queriesSize, int* returnSize){ if(queriesSize == 0) {*returnSize = 0;return NULL;} *returnSize = queriesSize; int *ans = malloc(sizeof(int)*queriesSize); int stacke[edgesSize],stackesize = 0,hashp[n+1],hashsort[n+1];//边表 节点表 memset(hashp,0,sizeof(hashp));memset(hashsort,0,sizeof(hashsort)); for(int i = 0;i < edgesSize;i++){ //hash表的初始化！ int temp; if(edges[i][0] > edges[i][1]) temp = edges[i][1]*n+edges[i][0]-1; else temp = edges[i][0]*n+edges[i][1] - 1; hash[temp]=0; } for(int i = 0;i < edgesSize;i++){ //利用hash表统计每条边的权重 加快速度 int temp,j; hashp[edges[i][0]] ++;hashsort[edges[i][0]] ++; hashp[edges[i][1]] ++;hashsort[edges[i][1]] ++; if(edges[i][0] > edges[i][1]) temp = edges[i][1]*n+edges[i][0]-1; else temp = edges[i][0]*n+edges[i][1] - 1; if(!hash[temp]) stacke[stackesize++] = temp; hash[temp]++; } qsort(hashsort,sizeof(hashsort)/sizeof(int),sizeof(int),cmp); int anssize= 0; for(int i = 0;i < queriesSize;i++){ int temp = 0,low = 1,high = n;//节点数字从1-n while(low < n){ //双指针求和为k的元素个数 while(high > 1 && hashsort[low] + hashsort[high] > queries[i]) high--; temp += (n - (low >high ?low:high)); low++; } if(temp == 0) {ans[anssize++] = 0;continue;}//提前继续 加速 for(int k = 0;k < stackesize;k++){ //统计边的影响 int p = stacke[k]/n,q = stacke[k]%n+1; if(hashp[p] + hashp[q] > queries[i] && hashp[p] + hashp[q] <= queries[i] + hash[stacke[k]]) temp--; } ans[anssize++] = temp; //结果返回 } return ans; }
放个图庆祝一下过分么？
写在最后
多刷题，多刷题才知道怎么写，万人千题，集万人之势乘万人之事情，这过程中必然有很多人下车，希望在看我文章的各位，可以一起当最强的人！