每日算法刷题Day22 6.4:leetcode二分答案3道题，用时1h30min

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) {// 未移除且匹配则++jif (!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;} elseright = 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;elsereturn 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;} elseright = mid - 1;}return res;}
};

7. 2861.最大合金数(中等,学习right范围)

2861. 最大合金数 - 力扣（LeetCode）

思想

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;} elseright = mid - 1;}}return res;}
};