今日学习记录
1. 最大平均通过率leetcode.1792
关键词：贪心 优先队列
问题分析：
- 就是看谁增的多就给谁加,因为好学生加入必然增加通过率(除了 100%)
核心思路
- 记录增加的值,再把增加的值和对应的分子和分母放入堆中,谁增的多就给谁加,循环 e 次,取堆中最大的加
- 比较前后差 a/b>c/d 等同于 ad>bc
**最终代码：
double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
using dr = tuple<double,int,int>;
auto cam = [](const dr&a,const dr&b){
return get<0>(a) < get<0>(b);
};
priority_queue<dr,vector<dr>,decltype(cam)> pq;
for(auto &c:classes){
int a = c[0],b = c[1];
pq.emplace(1.0*(b-a)/(1LL*b*(b+1)),a,b);
}
while(extraStudents--){
auto [_,a,b] = pq.top();
pq.pop();
a++;
b++;
pq.emplace(1.0*(b-a)/(1LL*b*(b+1)),a,b);
}
double ans = 0;
int len = classes.size();
while(!pq.empty()){
auto [_,a,b] = pq.top();
pq.pop();
ans += 1.0*a/b;
}
return ans/len;
}学到的点：
- 用到之前学的东西了,不错
2. 统计镜子反射路径数目leetcode.3665
关键词：dfs 动态规划
问题分析：
- 就是一个图论上的 dfs,不同路径数,就是多了个镜面处理
核心思路
- 记忆化搜索,难就难在镜面处理,我们可以预先判断下一个点是否为镜面,但是发现在遇到镜面之后,还要判断上一个节点是从哪里来的,该节点不可能能进行逆操作,所以需要一个值来传递状态,那么设 k 为状态值 0 为下,1 为右
const int MOD = 1000000007;
int uniquePaths(vector<vector<int>>& grid) {
int n = grid.size(),m = grid[0].size();
vector moment(n,vector(m,vector<int>(2,-1)));
auto dfs = [&](this auto &&dfs,int r,int c,int k)->int{
if(r<0||r>=n||c<0||c>=m) return 0;
if(r==0&&c==0) return 1;
int& a = moment[r][c][k];
if(a!=-1) return a;
if(grid[r][c]==0) a = (dfs(r-1,c,0)+dfs(r,c-1,1))%MOD;
else if(k==1) a = dfs(r-1,c,0)%MOD;
else a = dfs(r,c-1,1)%MOD;
return a;
};
return dfs(n-1,m-1,0)%MOD;
}- 化为递推,上面的记忆化搜索是从底向上的,去掉了递,只有归,动态规划,状态方程的条件跟上一样
const int MOD = 1000000007;
int uniquePaths(vector<vector<int>>& grid) {
int n = grid.size(),m = grid[0].size();
vector f(n+1,vector(m+1,vector<int>(2)));
f[0][1] = {1,1};
//0下1右
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
if(grid[i][j]==0){
f[i+1][j+1][0] = (f[i][j+1][0]+f[i+1][j][1])%MOD;
f[i+1][j+1][1] = f[i+1][j+1][0];
}else{
f[i+1][j+1][0] = f[i+1][j][1];
f[i+1][j+1][1] = f[i][j+1][0];
}
}
}
return f[n][m][0];
}- 空间优化 最终代码：
学到的点： 1.