今日学习记录
1. 需要教语言的最少人数leetcode.1733
关键词：枚举 哈希表
问题分析：
- 就是看互为朋友的人是否会相同的语言
- 只能教一种语言
- 求要教的人的最少数
核心思路
- 遍历朋友数组,看有哪些组的朋友需要被教,怎么比较,提前用数组记录每个人会哪些语言,在比较时只看第二个人会不会第一个人的语言,记录完后枚举所有可能的语言,再比较看谁要被教,记录最小的人数即为答案
思维扩展
这样更简单,就是遇到不同就加一**最终代码：
int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
//不就是谁会哪几种语言嘛
int len = languages.size();
vector arr(len,vector<bool>(n+1,false));
for(int i = 0;i<len;i++){
for(int x:languages[i]){
arr[i][x] = true;
}
}
vector<pair<int,int>> temp;
for(auto &d:friendships){
int u = d[0]-1,v = d[1]-1;
bool ok = false;
for(int x:languages[u]){
if(arr[v][x]){
ok = true;
break;
}
}
if(!ok) temp.emplace_back(u,v);
}
int ans = len;
for(int k= 1;k<=n;k++){
unordered_set<int> st;
for(auto [u,v]:temp){
//要学习的人,而不是要学习的语言,因为如果两个人都不会,都要学习,而不是只一一个学
if(!arr[u][k]) st.insert(u);
if(!arr[v][k]) st.insert(v);
}
ans = min(ans,(int)st.size());
}
return ans;
}学到的点：
- 枚举技巧
2. 制作 m 束花所需的最少天数leetcode.1482
关键词：二分答案
问题分析：
- 要等 n 天后其中的一部分花才开,要收集 m 束花,每束花都要花园中的连续 k 个花制成
核心思路
- 如果从第一天开始看,每次增加花开的数量,但是要每次都去遍历数组查看是否能制成花,直接使用双指针做,实现比较简单,那我直接说让天数无限大,那么所有的花都开了,我可以放心去收集花,一定能做成 m 束花,可是我要找到最小的天数来收集,这里就可以发现单调关系了,天数越小花越少,符合答案就越少,天数越大,花开的越多符合答案就越多,找到单调关系直接使用二分答案
- 双指针求分组长度为 m 的总数
- 特判,直接返回-1
最终代码：
int minDays(vector<int>& bloomDay, int m, int k) {
int n = bloomDay.size();
if(n<(long long)m*k) return -1;
auto check = [&](int mid)->bool{
int ans = 0;
for(int l = 0;l<n;l++){
int sum = 0;
for(int r = l;r<l+k&&r<n;r++){
if(mid<bloomDay[r]){
l = r;
break;
}
sum++;
if(sum==k){
ans++;
if(ans>=m) return true;
l = r;
break;
}
}
}
return false;
};
int left = 0,right = 1e9;
while(left<right){
int mid = left+(right-left)/2;
if(check(mid)) right = mid;
else left = mid+1;
}
return right;
}学到的点： 1.