5. 1898.可移除字符的最大数目(中等,学习判断子序列)
1898. 可移除字符的最大数目 - 力扣（LeetCode）
思想
1.给你两个字符串 s 和 p ，其中 p 是 s 的一个 子序列 。同时，给你一个元素 互不相同 且下标 从 0 开始 计数的整数数组 removable ，该数组是 s 中下标的一个子集（s 的下标也 从 0 开始 计数）。
请你找出一个整数 k（0 <= k <= removable.length），选出 removable 中的 前 k 个下标，然后从 s 中移除这些下标对应的 k 个字符。整数 k 需满足：在执行完上述步骤后， p 仍然是 s 的一个 子序列 。更正式的解释是，对于每个 0 <= i < k ，先标记出位于 s[removable[i]] 的字符，接着移除所有标记过的字符，然后检查 p 是否仍然是 s 的一个子序列。
返回你可以找出的 最大 k ，满足在移除字符后 p 仍然是 s 的一个子序列。
字符串的一个 子序列 是一个由原字符串生成的新字符串，生成过程中可能会移除原字符串中的一些字符（也可能不移除）但不改变剩余字符之间的相对顺序。
2.单调性检验:k越大，越不可能满足条件，所以存在一个最大的k，而如果此时的k满足条件，说明删除这k个元素p依旧是子序列，而删除小于k个元素不影响p是子序列，所以满足单调性
3.学习如何写check函数，即删除元素判断p是不是子序列:
(1)用数组 state 来维护 s 中的每个字符是否被删除，其中 1 代表未删除，0 代表已删除
(2)判断 p 是否为 s 的子序列，可以用双指针的方法从左至右贪心匹配两个子序列的相同字符。在遍历到 s[i] 时，我们需要在 state 中检查该字符是否被删除以决定是否应当尝试匹配。
代码
c++:
class Solution {
public:
bool check(string s, string p, vector<int>& removable, int mid) {
int ns = s.size(), np = p.size(), n = removable.size();
vector<bool> state(ns, false);
for (int i = 0; i < mid; ++i)
state[removable[i]] = true;
int j = 0;
for (int i = 0; i < ns; ++i) {
// 未移除且匹配则++j
if (!state[i] && s[i] == p[j]) {
++j;
if (j == np)
return true; // 是子序列
}
}
return false;
}
int maximumRemovals(string s, string p, vector<int>& removable) {
int n = removable.size();
int left = 0, right = n;
int res = 0;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (check(s, p, removable, mid)) {
res = mid;
left = mid + 1;
} else
right = mid - 1;
}
return res;
}
};
6. 1642.可以达到的最远建筑(中等)
1642. 可以到达的最远建筑 - 力扣（LeetCode）
思想
1.给你一个整数数组 heights ，表示建筑物的高度。另有一些砖块 bricks 和梯子 ladders 。
你从建筑物 0 开始旅程，不断向后面的建筑物移动，期间可能会用到砖块或梯子。
当从建筑物 i 移动到建筑物 i+1（下标 从 0 开始 ）时：
- 如果当前建筑物的高度 大于或等于 下一建筑物的高度，则不需要梯子或砖块
- 如果当前建筑的高度 小于 下一个建筑的高度，您可以使用 一架梯子 或
(h[i+1] - h[i])个砖块
如果以最佳方式使用给定的梯子和砖块，返回你可以到达的最远建筑物的下标（下标 从 0 开始 ）。
2.单调性检验:最远建筑物下标越大，越不容易满足条件，而如果一个下标满足条件，小于它的下标也一定能到达，满足单调性
3.我的思想:
利用贪心策略，将高度差数组排序，将小的高度差累加不超过砖块数，剩余更大的高度差用梯子，因为梯子可以替代一次任意高度差，可以当做无穷大
4.还有优先队列+贪心的思想之后再写1642. 可以到达的最远建筑 - 力扣（LeetCode）
代码
c++:
class Solution {
public:
bool check(vector<int>& heights, int bricks, int ladders, int mid) {
int n = heights.size();
//[0,mid]
vector<int> cnt;
for (int i = 0; i < mid; ++i) {
// mid可能为n-1,得确保i+1<n合法
if (i + 1 < n && heights[i] < heights[i + 1])
cnt.emplace_back(heights[i + 1] - heights[i]);
}
sort(cnt.begin(), cnt.end());
int m = cnt.size();
int id = 0;
int sum = 0;
while (id < m && cnt[id] + sum <= bricks) {
sum += cnt[id];
++id;
}
if (id == m)
return true;
//[0,id)用砖块,[id,m)共m-id个梯子
if (m - id <= ladders)
return true;
else
return false;
}
int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
check(heights, bricks, ladders, 6);
int n = heights.size();
int left = 0, right = n - 1;
int res = 0;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (check(heights, bricks, ladders, mid)) {
res = mid;
left = mid + 1;
} else
right = mid - 1;
}
return res;
}
};
7. 2861.最大合金数(中等,学习right范围)
思想
1.假设你是一家合金制造公司的老板，你的公司使用多种金属来制造合金。现在共有 n 种不同类型的金属可以使用，并且你可以使用 k 台机器来制造合金。每台机器都需要特定数量的每种金属来创建合金。
对于第 i 台机器而言，创建合金需要 composition[i][j] 份 j 类型金属。最初，你拥有 stock[i] 份 i 类型金属，而每购入一份 i 类型金属需要花费 cost[i] 的金钱。
给你整数 n、k、budget，下标从 1 开始的二维数组 composition，两个下标从 1 开始的数组 stock 和 cost，请你在预算不超过 budget 金钱的前提下，最大化 公司制造合金的数量。
所有合金都需要由同一台机器制造。
返回公司可以制造的最大合金数。
2.所有合金都需要由同一台机器制造这个条件跟3. 2982.找出出现至少三次的最长特殊子字符串II类似，都是先遍历字符或机器，再二分
3.单调性检验:合金数越大，越不能满足条件，而一旦一个合金数满足条件，小于该值的合金也一定满足条件，满足单调性
4.注意:乘法前面乘个1LL防止溢出(最重要)(卡在这)
5,优化left和right范围:
(1)left:因为是每台机器取最多，所以left可以直接从当前合金最大值res开始，避免很多判断
(2)right考虑特殊情况粗略估计:假设composition[i][j]和cost[j]都取1(对合金数负影响，这里无需求最小值，太麻烦),但是stock要取最小值，而不是最大值，因为短板效应导致，所以(right*1-min(stock))*1=buget,得到right取min(stock)+buget,其实1e9也可以，但是之前一直没乘1LL导致溢出过不去
代码
c++:
class Solution {
public:
bool check(int n, int budget, vector<int>& compositioni, vector<int>& stock,
vector<int>& cost, int mid) {
long long sum = 0;
for (int i = 0; i < n; ++i) {
// 乘1LL防止溢出
if (stock[i] < 1LL * compositioni[i] * mid)
sum += (1LL * compositioni[i] * mid - stock[i]) * cost[i];
if (sum > (long long)budget)
return false;
}
return true;
}
int maxNumberOfAlloys(int n, int k, int budget,
vector<vector<int>>& composition, vector<int>& stock,
vector<int>& cost) {
int res = 0;
// 第i台机器
for (int i = 0; i < k; ++i) {
int mins = INT_MAX;
for (int j = 0; j < n; ++j) {
mins = min(mins, stock[j]);
}
// 确定right值
int left = res, right = mins + budget;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (check(n, budget, composition[i], stock, cost, mid)) {
res = max(res, mid);
left = mid + 1;
} else
right = mid - 1;
}
}
return res;
}
};