先bb两句，科目三终于考完了，现在可以好好的学习(玩耍)了hh
1480.一维数组的动态和
给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i])。
请返回 nums 的动态和。
分析
求一次前缀和即可。
class Solution {
public:
vector<int> runningSum(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n);
ans[0] = nums[0];
for(int i = 1; i<n; i++) {
if(i)
ans[i] = ans[i-1] + nums[i];
}
return ans;
}
};
1481.不同整数的最少数目
给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。
分析
构造一个pair数组，second放数字本身，first放该数字出现的次数，根据pair的性质，在排序时，先比较first，如果first相同在比较second，排完序后，删除前面的数即可，优先删除数量少的数字肯定是对答案有利的。.
class Solution {
public:
int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
unordered_map<int,int> h;
for(int x: arr) h[x]++;
int ans = h.size();
vector<pair<int,int>> s;
for(auto it:h)
s.push_back(make_pair(it.second,it.first));
sort(s.begin(),s.end());
for(auto x: s){
if(k>=x.first){
k -= x.first;
ans--;
}else break;
}
return ans;
}
};
1482.制作m束花所需的最少天数
给你一个整数数组 bloomDay，以及两个整数 m 和 k 。
现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。
花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。
请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。
分析
二分答案，check函数判断在当前天数下是否可以制作出m束花。
class Solution {
public:
vector<int> a;
bool check(int x,int n,int m,int k){
int r = 0;
for(int i = 0; i<n; i++){
if(a[i] <= x){
int t = k;
while(i<n && a[i]<=x){
i++;
t--;
if(t == 0){
r++;
t = k;
}
}
}
}
return r>=m;
}
int minDays(vector<int>& bloomDay, int m, int k) {
int n = bloomDay.size();
if(m*k > n) return -1;
this->a = bloomDay;
int l = 1, r = 1e9;
while(l<r){
int mid = (l+r)>>1;
if(check(mid,n,m,k)) r = mid;
else l = mid+1;
}
//cout<<l<<endl;
if(check(l,n,m,k)) return l;
return -1;
}
};
1483.树节点的第k个祖先
给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。
请你设计并实现 getKthAncestor(int node, int k)函数，函数返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点，返回 -1 。
树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。
分析
DP, dp[i][j]表示节点 i 向上走2^j步，就有dp[i][j] = dp[dp[i][j-1]][j-1]，从根节点bfs一遍，预处理出dp数组。
class TreeAncestor {
public:
vector<vector<int>> dp; //dp[i][j] 表示节点i向上走2^j步
vector<vector<int>> g; //邻接表
TreeAncestor(int n, vector<int>& parent) {
dp = vector<vector<int>> (n,vector<int>(16,-1));
g = vector<vector<int>> (n);
int root = 0;
for(int i = 0; i<n; i++){
if(parent[i] == -1) root = i;
else g[parent[i]].push_back(i);
}
//宽搜，预处理出dp数组
queue<int> q;
q.push(root);
while(q.size()){
int t = q.front();
q.pop();
for(int x: g[t]){
dp[x][0] = t; //向上走一步走到自己的父节点
for(int j = 1; j<16; j++){
if(dp[x][j-1] != -1)
dp[x][j] = dp[dp[x][j-1]][j-1];
}
q.push(x);
}
}
}
int getKthAncestor(int node, int k) {
int ans = node;
for(int i = 0; i<16; i++){
if(k>>i&1){
ans = dp[ans][i];
if(ans == -1) return -1;
}
}
return ans;
}
};
/**
* Your TreeAncestor object will be instantiated and called as such:
* TreeAncestor* obj = new TreeAncestor(n, parent);
* int param_1 = obj->getKthAncestor(node,k);
*/
网友评论