每日算法刷题计划Day20 6.2:leetcode二分答案3道题，用时1h20min

9.3048.标记所有下标的最早秒数(中等)

3048. 标记所有下标的最早秒数 I - 力扣（LeetCode）

思想

1.给你两个下标从 1 开始的整数数组 nums 和 changeIndices ，数组的长度分别为 n 和 m 。
一开始，nums 中所有下标都是未标记的，你的任务是标记 nums 中 所有 下标。
从第 1 秒到第 m 秒（包括 第 m 秒），对于每一秒 s ，你可以执行以下操作 之一 ：

• 选择范围 [1, n] 中的一个下标 i ，并且将 nums[i] 减少 1 。
• 如果 nums[changeIndices[s]] 等于 0 ，标记 下标 changeIndices[s] 。
• 什么也不做。
  请你返回范围 [1, m] 中的一个整数，表示最优操作下，标记 nums 中 所有 下标的 最早秒数 ，如果无法标记所有下标，返回 -1 。
  2.单调性检验:秒数越少，越不可能标记nums中所有下标，所以存在一个最少秒数
  3.本题难点在于check函数怎么写，我的思路是changeIndices中下标i最后一次出现的位置（核心) 取消标记，只要之前的次数大于nums[i-1](因为i在[1,m])就能成功标记，所以需要记录下标-最后出现位置的数据结构，用map和vector<pair<int,int>>都可以，但要注意map只能按键排序，vector按first和second都行，但是最好直接记录最后出现的位置-下标
  4.学习别人思路:
  (1)也是记录i在chanegIndices最后一次出现的位置，但是直接用vector<int>存储即可，因为i属于[0,n),且无需像我那样一点要从最后找到第一次出现位置last[i]，直接顺序迭代更新即可，用后面的值覆盖前面的值
  (2)然后利用一个cnt变量记录可以消耗的值
• 是last[i],即判断cnt和nums[i]的大小
• 不是last[i],++cnt

代码

c++:

class Solution {
public:bool check(vector<int>& nums, vector<int>& changeIndices, int mid) {vector<pair<int, int>> v; // 最后位置-下标int n = nums.size(), m = changeIndices.size();for (int i = 1; i <= n; ++i) {int j = mid - 1;while (j >= 0 && changeIndices[j] != i)--j;if (j < 0)return false;v.emplace_back(j, i);}sort(v.begin(), v.end());int cnt = 0; // 用了几个for (const auto x : v) {int last = x.first, id = x.second;if (last - cnt < nums[id - 1])return false;cnt += nums[id - 1] + 1;}return true;}int earliestSecondToMarkIndices(vector<int>& nums,vector<int>& changeIndices) {int res = -1;int n = nums.size(), m = changeIndices.size();set<int> s;for (const int x : changeIndices)s.insert(x);if (s.size() < n)return -1;int left = 1, right = m;while (left <= right) {int mid = left + ((right - left) >> 1);if (check(nums, changeIndices, mid)) {res = mid;right = mid - 1;} elseleft = mid + 1;}return res;}
};

学习check函数:

bool check(vector<int>& nums, vector<int>& changeIndices, int mid) {int n = nums.size(), m = changeIndices.size();vector<int> lasti(n, -1); // 最后位置for (int i = 0; i < mid; ++i)lasti[changeIndices[i] - 1] = i;for (int i = 0; i < n; ++i) {if (lasti[i] == -1)return false;}int cnt = 0; // 可用几个for (int i = 0; i < mid; ++i) {int id = changeIndices[i] - 1;if (lasti[id] == i) {if (cnt < nums[id])return false;cnt -= nums[id];} else++cnt;}return true;
}

2.2 求最大

在练习时，请注意「求最小」和「求最大」的二分写法上的区别。
前面的「求最小」和二分查找求「排序数组中某元素的第一个位置」是类似的，按照红蓝染色法，左边是不满足要求的（红色），右边则是满足要求的（蓝色）。
「求最大」的题目则相反，左边是满足要求的（蓝色），右边是不满足要求的（红色）。这会导致二分写法和上面的「求最小」有一些区别。
以开区间二分为例：
求最小：check(mid) == true 时更新 right = mid，反之更新 left = mid，最后返回 right。
求最大：check(mid) == true 时更新 left = mid，反之更新 right = mid，最后返回 left。
对于开区间写法，简单来说 check(mid) == true 时更新的是谁，最后就返回谁。相比其他二分写法，开区间写法不需要思考加一减一等细节，推荐使用开区间写二分。

1.套路

c++:

class Solution {
public:bool check(vector<int>& citations, int mid) {}int hIndex(vector<int>& citations) {int res = 0;int n = citations.size();int left = 0, right = min(n, citations[n - 1]);while (left <= right) {int mid = left + ((right - left) >> 1);if (check(citations, mid)) {res = mid;left = mid + 1; // 还可能有更大的值满足条件} elseright = mid - 1;}return res;}
};

2.题目描述

1.给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 非降序排列。计算并返回该研究者的 h 指数(答案)。
h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）至少 有 h 篇论文分别被引用了至少 h 次(条件)。
2.给你一个 下标从 0 开始 的整数数组 candies 。数组中的每个元素表示大小为 candies[i] 的一堆糖果。你可以将每堆糖果分成任意数量的 子堆 ，但 无法 再将两堆合并到一起。
另给你一个整数 k 。你需要将这些糖果分配给 k 个小孩，使每个小孩分到 相同 数量的糖果(条件)。每个小孩可以拿走 至多一堆 糖果，有些糖果可能会不被分配。
返回每个小孩可以拿走的 最大糖果数目(答案) 。

3.学习经验

(1)求最大合法区间在右边，所以满足条件是left=mid+1,而求最小是right=mid-1

1. 275.H指数II

275. H 指数 II - 力扣（LeetCode）

思想

1.给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 非降序排列 。计算并返回该研究者的 h 指数。
h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）至少 有 h 篇论文分别被引用了至少 h 次。
2.单调性检验：若h越大，越不可能满足条件，但若h满足条件，小于h的值肯定满足条件，即至少有 h 篇论文分别被引用了至少h 次，那肯定有小于h 篇论文分别被引用了至少h 次，满足单调性
3.我的思想：是找到第一个大于mid的引用次数，然后判断文章数，但这样要花费时间找第一个大于mid的引用次数的下标
4.学习：可以直接假设文章数为mid，然后判断n-mid处的引用次数是否大于mid，O(1)的复杂度

代码

c++:

class Solution {
public:bool check(vector<int>& citations, int mid) {int n = citations.size();int i = 0;while (i < n && citations[i] < mid)++i;if (i == n)return false;if (n - i >= mid)return true;elsereturn false;}int hIndex(vector<int>& citations) {int res = 0;int n = citations.size();int left = 0, right = min(n, citations[n - 1]);while (left <= right) {int mid = left + ((right - left) >> 1);if (check(citations, mid)) {res = mid;left = mid + 1; // 还可能有更大的值满足条件} elseright = mid - 1;}return res;}
};

学习:

bool check(vector<int>& citations, int mid) {int n = citations.size();if (mid == 0 || citations[n - mid] >= mid) // mid有可能为0return true;elsereturn false;
}

2. 2226.每个小孩最多能分到多少糖果

2226. 每个小孩最多能分到多少糖果 - 力扣（LeetCode）

思想

1.给你一个 下标从 0 开始 的整数数组 candies 。数组中的每个元素表示大小为 candies[i] 的一堆糖果。你可以将每堆糖果分成任意数量的 子堆 ，但 无法 再将两堆合并到一起。
另给你一个整数 k 。你需要将这些糖果分配给 k 个小孩，使每个小孩分到 相同 数量的糖果。每个小孩可以拿走 至多一堆 糖果，有些糖果可能会不被分配。
返回每个小孩可以拿走的 最大糖果数目 。
2.单调性检验:糖果数目越大，越不能均分，所以存在一个最大糖果数目，且小于该糖果数目的值也一定满足条件，满足单调性
3.一个堆只能分一次子堆，就是商

代码

c++:

class Solution {
public:bool check(vector<int>& candies, long long k, long long mid) {if (mid == 0) // 注意下面除数不能为0return true;long long cnt = 0;for (const int x : candies) {cnt += (long long)x / mid;if (cnt >= k)return true;}return false;}int maximumCandies(vector<int>& candies, long long k) {int res = 0;long long sum = 0;for (const int x : candies)sum += x;if (sum < k)return 0;long long left = 0, right = sum / k;while (left <= right) {long long mid = left + ((right - left) >> 1);if (check(candies, k, mid)) {res = mid;left = mid + 1;} elseright = mid - 1;}return res;}
};