每日算法刷题Day23 6.5:leetcode二分答案3道题，用时1h40min(有点慢)

8. 3007.价值和小于等于K的最大数字(中等，学习,太难，先过)

3007. 价值和小于等于 K 的最大数字 - 力扣（LeetCode）

思想

1.给你一个整数 k 和一个整数 x 。整数 num 的价值是它的二进制表示中在 x，2x，3x 等位置处 设置位 的数目（从最低有效位开始）。num 的 累加价值 是从 1 到 num 的数字的 总 价值。如果 num 的累加价值小于或等于 k 则被认为是 廉价 的。
请你返回 最大 的廉价数字。
2.单调性检验:廉价数字越大，累加价值越容易超过k,所以存在一个最大廉价数字，若此时廉价数字符合条件，小于它的廉价数字也一定符合条件
3.我的想法是可以用二分，但是对于每个mid还要单独再算一遍累加价值会很慢，而如果储存在数组里面也会很耗空间，所以采用遍历res自增写，会超时
4.学习:
(1)数位dp，先不考虑
(2)数学公式
(3)试填法(逐位构造)

代码

c++:
1.我的代码

class Solution {
public:long long cal(long long val, int x) {long long cnt = 0; // 位数long long res = 0;while (val) {++cnt;if (cnt % x == 0 && val & 1) {++res;}val = val >> 1;}return res;}long long findMaximumNumber(long long k, int x) {long long res = 1;long long sum = 0;while (sum + cal(res, x) <= k) {sum += cal(res, x);++res;}return res - 1;}
};

9. LCP 78.城墙防线(中等)

LCP 78. 城墙防线 - 力扣（LeetCode）

思想

1.在探险营地间，小扣意外发现了一片城墙遗迹，在探索期间，却不巧遇到迁徙中的兽群向他迎面冲来。情急之下小扣吹响了他的苍蓝笛，随着笛声响起，遗迹中的城墙逐渐发生了横向膨胀。 已知 rampart[i] = [x,y] 表示第 i 段城墙的初始所在区间。当城墙发生膨胀时，将遵循以下规则：

• 所有的城墙会同时膨胀相等的长度；
• 每个城墙可以向左、向右或向两个方向膨胀。
  小扣为了确保自身的安全，需要在所有城墙均无重叠的情况下，让城墙尽可能的膨胀。请返回城墙可以膨胀的 最大值 。
  注意：
• 初始情况下，所有城墙均不重叠，且 rampart 中的元素升序排列；
• 两侧的城墙可以向外无限膨胀。
  2.单调性检验:膨胀值越大，越不容易满足条件，所以存在一个最大膨胀值，而一旦一个膨胀值满足条件，比它小的值一定可以膨胀，符合单调性
  3.我的思想就是贪心，记录前一个城墙用了右侧多少个城墙，从而得出下一个城墙还剩多少个，然后向右拓展尽可能满足条件达到mid，直到循环结束或者有一个城墙没的用了

代码

c++:

class Solution {
public:bool check(vector<vector<int>>& rampart, int mid) {int n = rampart.size();vector<int> cnt(n, 0);int t = 0;                        // 前一个城墙用了多少for (int i = 1; i < n - 1; ++i) { //[1,n-2]int left = rampart[i][0] - rampart[i - 1][1] - t;if (left >= mid) {t = 0;continue;}int right = rampart[i + 1][0] - rampart[i][1];if (left + right < mid)return false;else {t = mid - left;}}return true;}int rampartDefensiveLine(vector<vector<int>>& rampart) {int res = 0;int left = 0, right = 1e9;while (left <= right) {int mid = left + ((right - left) >> 1);if (check(rampart, mid)) {res = mid;left = mid + 1;} elseright = mid - 1;}return res;}
};

2.3 二分间接值

二分的不是答案，而是一个和答案有关的值（间接值）。

1.套路

c++:

2.题目描述

1.给你一个二维数组 points 和一个字符串 s ，其中 points[i] 表示第 i 个点的坐标，s[i] 表示第 i 个点的 标签 。
如果一个正方形的中心在 (0, 0) ，所有边都平行于坐标轴，且正方形内 不 存在标签相同的两个点，那么我们称这个正方形是 合法 的。
请你返回 合法正方形(条件) 中可以包含的 最多点数(答案,但是二分正方形边长)。
注意：

• 如果一个点位于正方形的边上或者在边以内，则认为该点位于正方形内。
• 正方形的边长可以为零。
  2.你有一些球的库存 inventory ，里面包含着不同颜色的球。一个顾客想要 任意颜色 总数为 orders 的球。
  这位顾客有一种特殊的方式衡量球的价值：每个球的价值是目前剩下的 同色球 的数目。比方说还剩下 6 个黄球，那么顾客买第一个黄球的时候该黄球的价值为 6 。这笔交易以后，只剩下 5 个黄球了，所以下一个黄球的价值为 5 （也就是球的价值随着顾客购买同色球是递减的）
  给你整数数组 inventory ，其中 inventory[i] 表示第 i 种颜色球一开始的数目。同时给你整数 orders ，表示顾客总共想买的球数目。你可以按照 任意顺序 卖球。
  请你返回**卖了 orders 个球(条件)**以后 最大 总价值之和(答案，但是二分最终球的最大价值)。由于答案可能会很大，请你返回答案对 109 + 7 取余数 的结果。

3.学习经验

(1)所求答案不好二分，因为不好在check函数中使用，可以间接地二分另一个值，与答案有一定函数关系，最终常数时间求解即可(思考是在二分过程中求解还是二分结束后求解)
(2)可以是一个阈值

1. 3143.正方形中的最多点数(中等)

3143. 正方形中的最多点数 - 力扣（LeetCode）

思想

1.给你一个二维数组 points 和一个字符串 s ，其中 points[i] 表示第 i 个点的坐标，s[i] 表示第 i 个点的 标签 。
如果一个正方形的中心在 (0, 0) ，所有边都平行于坐标轴，且正方形内 不 存在标签相同的两个点，那么我们称这个正方形是 合法 的。
请你返回 合法 正方形中可以包含的 最多 点数。
注意：

• 如果一个点位于正方形的边上或者在边以内，则认为该点位于正方形内。
• 正方形的边长可以为零。
  2.单调性检验:正方形边长越大，点数越多，越不容易合法，所以存在一个最大正方形边长，而一旦这个正方形边长满足条件，更小的也一定满足条件，符合单调性
  3.用哈希表记录标签即可
  4.答案是最多点数，但是二分最多点数不好判断，要计算距离，所以二分正方形边长然后在check里面更新点数res即可

代码

c++:

class Solution {
public:bool check(vector<vector<int>>& points, string s, int mid, int& res) {int n = points.size();unordered_map<char, int> mp;for (int i = 0; i < n; ++i) {int x = points[i][0], y = points[i][1];if (abs(x) <= mid && abs(y) <= mid) {++mp[s[i]];if (mp[s[i]] > 1)return false;}}res = max(res, (int)mp.size());return true;}int maxPointsInsideSquare(vector<vector<int>>& points, string s) {int n = points.size();int res = 0;int maxval = INT_MAX;for (const auto x : points) {maxval = max({maxval, abs(x[0]), abs(x[1])});}long long left = 0, right = maxval;while (left <= right) {long long mid = left + ((right - left) >> 1);if (check(points, s, mid, res)) {left = mid + 1;} elseright = mid - 1;}return res;}
};

2. 1648.销售价值减少的颜色球(中等,重点学习思想)

1648. 销售价值减少的颜色球 - 力扣（LeetCode）

思想

1.你有一些球的库存 inventory ，里面包含着不同颜色的球。一个顾客想要 任意颜色 总数为 orders 的球。
这位顾客有一种特殊的方式衡量球的价值：每个球的价值是目前剩下的 同色球 的数目。比方说还剩下 6 个黄球，那么顾客买第一个黄球的时候该黄球的价值为 6 。这笔交易以后，只剩下 5 个黄球了，所以下一个黄球的价值为 5 （也就是球的价值随着顾客购买同色球是递减的）
给你整数数组 inventory ，其中 inventory[i] 表示第 i 种颜色球一开始的数目。同时给你整数 orders ，表示顾客总共想买的球数目。你可以按照 任意顺序 卖球。
请你返回卖了 orders 个球以后 最大 总价值之和。由于答案可能会很大，请你返回答案对 109 + 7 取余数 的结果。
2.这道题二分查找的是卖了orders个球后总的球的最大价值，即一个阈值k,即

• 所有数量>x的球一定会减小到x，用等差数列求和求价值
• orders仍有剩余，剩余的一定以价值x卖出(因为是个阈值)
  而这个阈值越小，卖的球越多，越不容易满足条件，所以存在一个最小值，而一旦这个阈值满足条件，大于它的值一定满足条件
  3.二分得到阈值k，答案在二分结束后单独求，而不是在二分里面求解

代码

c++:

class Solution {
public:bool check(vector<int>& inventory, int orders, int mid) {int cnt = 0;for (const int x : inventory) {if (x > mid) {cnt += x - mid;if (cnt > orders)return false;}}return true;}int maxProfit(vector<int>& inventory, int orders) {long long mod = 1e9 + 7;int n = inventory.size();int maxval = INT_MIN;for (const int x : inventory)maxval = max(maxval, x);int left = 0, right = maxval;int k = 0;while (left <= right) {int mid = left + ((right - left) >> 1);if (check(inventory, orders, mid)) {right = mid - 1; // 找更小的k = mid;} elseleft = mid + 1;}// 找到阈值求解reslong long res = 0, sum = 0;for (const int x : inventory) {if (x > k) {// x,卖x-k个,到k+1res = (res + 1LL * (x + k + 1) * (x - k) / 2) % mod;sum += x - k;}}// 剩余的if (sum < orders)res = (res + 1LL * (orders - sum) * k) % mod;return res;}
};