wordpress 全站不刷新,建筑论坛网站,浏览器最新大全,生鲜网站建设费用1964. 找出到每个位置为止最长的有效障碍赛跑路线
你打算构建一些障碍赛跑路线。给你一个 下标从 0 开始 的整数数组 obstacles #xff0c;数组长度为 n #xff0c;其中 obstacles[i] 表示第 i 个障碍的高度。
对于每个介于 0 和 n - 1 之间#xff08;包含 0 和 n - 1数组长度为 n 其中 obstacles[i] 表示第 i 个障碍的高度。
对于每个介于 0 和 n - 1 之间包含 0 和 n - 1的下标 i 在满足下述条件的前提下请你找出 obstacles 能构成的最长障碍路线的长度
你可以选择下标介于 0 到 i 之间包含 0 和 i的任意个障碍。在这条路线中必须包含第 i 个障碍。你必须按障碍在 obstacles 中的 出现顺序 布置这些障碍。除第一个障碍外路线中每个障碍的高度都必须和前一个障碍 相同 或者 更高
返回长度为 n 的答案数组 ans 其中 ans[i] 是上面所述的下标 i 对应的最长障碍赛跑路线的长度。
数据范围
n obstacles.length1 n 1051 obstacles[i] 107
分析
本题数据范围比较大因此不能使用n方做法采用贪心二分的方法用q数组记录所有长度为i的最长非递减子序列中的最小值这样可以尽可能多的构造非递减子序列例如原数组为1232
q[1]q[1,2]q[1,2,3]2找到第一个大于2的下标并将其替换q[1,2,2]此时替换的位置就是最长序列的长度
代码
class Solution {
public:const static int N 1e5 5;int dp[N]; int q[N], tt -1;void print() {for(int i 0; i tt; i ) cout q[i] ;cout endl;}vectorint longestObstacleCourseAtEachPosition(vectorint obstacles) {int n obstacles.size();vectorint res;res.resize(n);for(int i 0; i n; i ) {if(tt -1 || obstacles[i] q[tt]) {q[ tt] obstacles[i];res[i] tt 1;}else { int pos upper_bound(q, q tt, obstacles[i]) - q;res[i] pos 1;q[pos] obstacles[i];}}return res;}
};2111. 使数组 K 递增的最少操作次数
给你一个下标从 0 开始包含 n 个正整数的数组 arr 和一个正整数 k 。
如果对于每个满足 k i n-1 的下标 i 都有 arr[i-k] arr[i] 那么我们称 arr 是 K 递增 的。
比方说arr [4, 1, 5, 2, 6, 2] 对于 k 2 是 K 递增的因为 arr[0] arr[2] (4 5)arr[1] arr[3] (1 2)arr[2] arr[4] (5 6)arr[3] arr[5] (2 2)
但是相同的数组 arr 对于 k 1 不是 K 递增的因为 arr[0] arr[1]对于 k 3 也不是 K 递增的因为 arr[0] arr[3] 。 每一次 操作 中你可以选择一个下标 i 并将 arr[i] 改成任意 正整数。
请你返回对于给定的 k 使数组变成 K 递增的 最少操作次数 。
数据范围
1 arr.length 1051 arr[i], k arr.length
分析
实际就是将原数组拆分为k个子数组对每个子数组求他的最长非递减子序列然后对于非递减子序列的元素就是最优的需要修改的统计一下即可这里求最长非递减子序列也是通过上题的贪心二分计算
代码
class Solution {
public:const static int N 1e5 5;int dp[N];int q[N], tt -1;void print() {for(int i 0; i tt; i ) cout q[tt] ;cout endl;}int kIncreasing(vectorint arr, int k) {int res 0;int n arr.size();for(int i 0; i k - 1; i ) {tt -1;int cnt 0;for(int j i; j n; j k) {cnt ;if(tt -1 || arr[j] q[tt]) q[ tt] arr[j];else {int pos upper_bound(q, q tt, arr[j]) - q;q[pos] arr[j];}}res cnt - (tt 1);}return res;}
};1626. 无矛盾的最佳球队
假设你是球队的经理。对于即将到来的锦标赛你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。
然而球队中的矛盾会限制球员的发挥所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员则存在矛盾。同龄球员之间不会发生矛盾。
给你两个列表 scores 和 ages其中每组 scores[i] 和 ages[i] 表示第 i 名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数
数据范围
1 scores.length, ages.length 1000scores.length ages.length scores[i] 1061 ages[i] 1000
分析
首先将球员先按照年龄排序再按照分数从小到大排序令dp[i]表示选择第i个球员的最大分数状态转移如下 d p [ i ] m a x ( d p [ i ] , d p [ j ] s c o r e [ i ] ) dp[i]max(dp[i],dp[j]score[i]) dp[i]max(dp[i],dp[j]score[i])
代码
class Solution {
public:const static int N 1005;int dp[N], agedp[N];struct node_ {int score, age;friend bool operator (const node_ a, const node_ b) {if(a.age b.age) return a.score b.score;return a.age b.age;}};vectornode_ nodes;int bestTeamScore(vectorint scores, vectorint ages) {int n ages.size();for(int i 0; i n; i ) {nodes.push_back({scores[i], ages[i]});}sort(nodes.begin(), nodes.end());for(int i 0; i n; i ) {dp[i] nodes[i].score;for(int j 0; j i; j ) {if(nodes[j].score nodes[i].score) dp[i] max(dp[i], dp[j] nodes[i].score);}}int res 0;for(int i 0; i n; i ) res max(res, dp[i]);return res;}
};54. 俄罗斯套娃信封问题
给你一个二维整数数组 envelopes 其中 envelopes[i] [wi, hi] 表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候这个信封就可以放进另一个信封里如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封即可以把一个信封放到另一个信封里面。
注意不允许旋转信封。
数据范围
1 envelopes.length 105envelopes[i].length 21 wi, hi 105
分析
先按w升序再按h降序按h降序保证了w相同的信封只能选一个然后对h求最长上升子序列就行此时就满足h递增且w递增
代码
class Solution {
public:const static int N 1e5 5;struct node_ {int a, b;friend bool operator (const node_ a, const node_ b) {if(a.a b.a) return a.b b.b;return a.a b.a;}};int n;node_ q[N];int tt -1;vectornode_ envelopes;int find(node_ x) {int l 0, r tt;while(l r) {int mid (l r) 1;if(q[mid].b x.b) l mid 1;else r mid;}return l;}int maxEnvelopes(vectorvectorint envs) {n envs.size();for(int i 0; i n; i ) envelopes.push_back({envs[i][0], envs[i][1]});sort(envelopes.begin(), envelopes.end());for(int i 0; i n; i ) {int a envelopes[i].a, b envelopes[i].b;if(tt -1 || b q[tt].b) q[ tt] {a, b};else {int pos find({a, b});q[pos] {a, b};}}return tt 1;}
};
