二分查找
34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
class Solution {
public int[] searchRange(int[] nums, int target) {
int length=nums.length;
if (length == 0) return new int[]{-1, -1};
int[] res = new int[2];
int left=0, right=length-1;
int mid=0;
while(left <= right) {
mid = (right-left)/2+left;
if (nums[mid] == target) {
break;
} else if (nums[mid] > target) {
right = mid-1;
} else {
left = mid + 1;
}
}
if (nums[mid] != target) {
return new int[]{-1, -1};
} else {
left=mid;right=mid;
while (left>0 && nums[left-1]==target) {
left--;
}
while (right<length-1 && nums[right+1]==target) {
right++;
}
res[0] = left;
res[1] = right;
}
return res;
}
}35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
class Solution {
public int searchInsert(int[] nums, int target) {
return findFirst1(nums, target);
}
public int findFirst1(int[] nums, int target) {
int left = 0, right = nums.length-1;
int mid;
while (left <= right) {
mid = (right - left) / 2 + left;
if (nums[mid] == target){
if (mid==0 || nums[mid-1] < nums[mid])
return mid;
}
if (nums[mid] == target) {
right = mid - 1;
} else if (nums[mid] > target){
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
}704. 二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
class Solution {
public int search(int[] nums, int target) {
return binarySearch(nums, target);
}
public int binarySearch(int[] nums, int target) {
int left=0, right=nums.length-1;
int mid=0;
while (left <= right) {
mid = (right-left)/2 + left;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid-1;
} else {
left = mid+1;
}
}
return -1;
}
}744. 寻找比目标字母大的最小字母
给你一个字符数组 letters，该数组按非递减顺序排序，以及一个字符 target。letters 里至少有两个不同的字符。
返回 letters 中大于 target 的最小的字符。如果不存在这样的字符，则返回 letters 的第一个字符。
class Solution {
public char nextGreatestLetter(char[] letters, char target) {
int length = letters.length;
int pos=binarySerachChar(letters, target);
// System.out.println(pos);
if (letters[pos] > target) {
return letters[pos];
} else return letters[(pos+1) % length];
}
public int binarySerachChar(char[] letters, char target) {
int left=0, right=letters.length-1;
int mid=0;
while (left <= right) {
mid = (right-left)/2 + left;
if (letters[mid] == target) {
if (mid == letters.length-1 || letters[mid] < letters[mid+1])
return mid;
}
if (letters[mid] == target) {
left = mid+1;
} else if (letters[mid] > target) {
right = mid-1;
} else {
left = mid+1;
}
}
return mid;
}
}1385. 两个数组间的距离值
给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。
「距离值」 定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。
class Solution {
public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
Arrays.sort(arr2);
Arrays.sort(arr1);
int m=arr1.length, n=arr2.length;
int p=0;
//找到一个大于arr[0]
for(int i=0; i<n; i++) {
if (arr2[i] > arr1[0]) {
p=i;
break;
}
}
int res=0;
for (int i=0; i<m; i++) {
while (p<n && arr2[p] < arr1[i]) {
p++;
}
if ((p>0 && arr1[i]-arr2[p-1] <= d) || (p<n && arr2[p]-arr1[i] <= d)) {
continue;
}
res++;
}
return res;
}
}2529. 正整数和负整数的最大计数
给你一个按 非递减顺序 排列的数组 nums ，返回正整数数目和负整数数目中的最大值。
换句话讲，如果
nums中正整数的数目是pos，而负整数的数目是neg，返回pos和neg二者中的最大值。
注意：0 既不是正整数也不是负整数。
class Solution {
public int maximumCount(int[] nums) {
// System.out.println(findNeg(nums));
// System.out.println(findPos(nums));
int pos = nums[nums.length-1] == 0 ? nums.length : findPos(nums);
int neg = nums[0] == 0 ? -1 : findNeg(nums);
return Math.max(neg + 1, nums.length-pos);
}
public int findPos(int[] nums) {
int left=0, right=nums.length-1;
int mid=0;
while (left <= right) {
mid = (right-left)/2 + left;
if (mid > 0 && nums[mid-1] <= 0 && nums[mid] > 0) {
return mid;
} else if (nums[mid] <= 0) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return 0;
}
public int findNeg(int[] nums) {
int left=0, right=nums.length-1;
int mid=0;
while (left <= right) {
mid = (right-left)/2 + left;
if (mid < nums.length-1 && nums[mid] < 0 && nums[mid+1] >= 0) {
return mid;
} else if (nums[mid] < 0) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return nums.length-1;
}
}2300. 咒语和药水的成功对数
给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。
同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。
请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。
class Solution {
public int[] successfulPairs(int[] spells, int[] potions, long success) {
Arrays.sort(potions);
int N = spells.length;
int M = potions.length;
int[] ans = new int[N];
for (int i = 0; i < N; i++) {
int l = 0;
int r = M - 1;
int min = -1;
while (l <= r) {
int m = (l + r) >>> 1;
if ((long) potions[m] * spells[i] >= success) {
min = m;
r = m - 1;
} else {
l = m + 1;
}
}
if (min != -1) {
ans[i] = M - min;
}
}
return ans;
}
}2389. 和有限的最长子序列
给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。
返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度 。
子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。
class Solution {
public int[] answerQueries(int[] nums, int[] queries) {
Arrays.sort(nums);
int length=nums.length;
int[] sum = new int[length];
sum[0] = nums[0];
for (int i=1; i<length; i++) {
sum[i] = nums[i] + sum[i-1];
}
int qlength=queries.length;
int[] ans=new int[qlength];
for (int i=0; i<qlength; i++) {
int left=0, right=length-1;
int mid=0;
int min=0;
while(left <= right) {
mid = (right-left)/2 + left;
if (sum[mid] == queries[i]) {
min = mid+1;
break;
} else if (sum[mid] > queries[i]) {
right = mid-1;
} else {
left = mid + 1;
min=mid+1;
}
}
ans[i] = min;
}
return ans;
}
}定义一个函数 f(s)，统计 s 中（按字典序比较）最小字母的出现频次 ，其中 s 是一个非空字符串。
例如，若 s = "dcce"，那么 f(s) = 2，因为字典序最小字母是 "c"，它出现了 2 次。
现在，给你两个字符串数组待查表 queries 和词汇表 words 。对于每次查询 queries[i] ，需统计 words 中满足 f(queries[i]) < f(W) 的 词的数目 ，W 表示词汇表 words 中的每个词。
请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是第 i 次查询的结果。
class Solution {
public int[] numSmallerByFrequency(String[] queries, String[] words) {
int length = queries.length, wordLen=words.length;
int[] numQueries = new int[length];
int[] numWords = new int[wordLen];
for (int i=0; i<length; i++) {
numQueries[i] = f(queries[i]);
// System.out.print(numQueries[i] + " ");
}
// System.out.println();
for (int i=0; i<wordLen; i++) {
numWords[i] = f(words[i]);
// System.out.print(numWords[i] + " ");
}
Arrays.sort(numWords);
int[] ans = new int[length];
for (int i=0; i<length; i++) {
int left=0, right=wordLen-1;
int mid=0;
while(left <= right) {
mid=(right-left)/2 + left;
// if (mid > 0 && numWords[mid-1] <= numQueries[i] && numWords[mid] > numQueries[i]) {
// break;
// }
if (numWords[mid] > numQueries[i]) {
right = mid-1;
} else {
left = mid+1;
}
}
ans[i]= wordLen-left;
}
return ans;
}
public int f(String s) {
char[] tmp = s.toCharArray();
Arrays.sort(tmp);
int count=1, index=1;
while (index < tmp.length && tmp[index] == tmp[index-1]) {
count++;
index++;
}
return count;
}
}2080. 区间内查询数字的频率
请你设计一个数据结构，它能求出给定子数组内一个给定值的 频率 。
子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。
请你实现 RangeFreqQuery 类：
RangeFreqQuery(int[] arr)用下标从 0 开始的整数数组arr构造一个类的实例。int query(int left, int right, int value)返回子数组arr[left...right]中value的 频率 。
一个 子数组 指的是数组中一段连续的元素。arr[left...right] 指的是 nums 中包含下标 left 和 right 在内 的中间一段连续元素。
class RangeFreqQuery {
int[] array;
Map<Integer, List<Integer>> map;
public RangeFreqQuery(int[] arr) {
array = arr;
map = new HashMap<>();
for (int i=0; i<arr.length; i++) {
int num=arr[i];
if (!map.containsKey(num)) {
List list = new ArrayList<>();
list.add(i);
map.put(num, list);
} else {
List list = map.get(num);
list.add(i);
map.put(num, list);
}
}
}
public int query(int left, int right, int value) {
int count=0;
if (!map.containsKey(value)) return 0;
List<Integer> list = map.get(value);
int l=0, r=list.size()-1;
int mid=0;
while (l<=r) {
mid = (r-l)/2 + l;
if (list.get(mid) >= left) {
r = mid-1;
} else {
l = mid+1;
}
}
count = l;
// System.out.println(count);
l=0; r=list.size()-1;
while (l<=r) {
mid = (r-l)/2 + l;
if (list.get(mid) > right) {
r = mid-1;
} else {
l = mid+1;
}
}
// System.out.println(l);
return l-count;
}
}
/**
* Your RangeFreqQuery object will be instantiated and called as such:
* RangeFreqQuery obj = new RangeFreqQuery(arr);
* int param_1 = obj.query(left,right,value);
*/2563. 统计公平数对的数目
给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。
如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：
0 <= i < j < n，且lower <= nums[i] + nums[j] <= upper
class Solution {
public long countFairPairs(int[] nums, int lower, int upper) {
Arrays.sort(nums);
long cnt=0;
int index=0;
while (index < nums.length) {
int left=findLower(nums, lower-nums[index], index+1, nums.length-1);
int right=findUpper(nums, upper-nums[index], index+1, nums.length-1);
// System.out.println(left + " " + right);
if(right < nums.length && nums[right] == upper-nums[index]) cnt++;
cnt += right-left;
index++;
}
return cnt;
}
public int findUpper(int[] nums, int target, int left, int right) {
int mid=0;
while (left <= right) {
mid = (right-left)/2 + left;
if (nums[mid] == target) {
if (mid == nums.length-1 || mid < nums.length-1 && nums[mid+1] > nums[mid])
return mid;
}
if (nums[mid] == target) {
left = mid + 1;
}
else if (nums[mid] > target) {
right = mid-1;
} else {
left = mid+1;
}
}
return left;
}
public int findLower(int[] nums, int target, int left, int right) {
int mid=0;
while (left <= right) {
mid = (right-left)/2 + left;
if (nums[mid] == target) {
if (mid == nums.length-1 || mid < nums.length-1 && nums[mid+1] > nums[mid])
return mid;
}
if (nums[mid] == target) {
right = mid-1;
}
else if (nums[mid] >= target) {
right = mid-1;
} else {
left = mid+1;
}
}
return left;
}
}2856. 删除数对后的最小数组长度
给你一个下标从 0 开始的 非递减 整数数组 nums 。
你可以执行以下操作任意次：
选择 两个 下标
i和j，满足nums[i] < nums[j]。将
nums中下标在i和j处的元素删除。剩余元素按照原来的顺序组成新的数组，下标也重新从 0 开始编号。
请你返回一个整数，表示执行以上操作任意次后（可以执行 0 次），nums 数组的 最小 数组长度。
class Solution {
public int minLengthAfterRemovals(List<Integer> nums) {
Map<Integer, Integer> map = new HashMap<>();
int max=0;
for (Integer num : nums) {
if (!map.containsKey(num)) {
max = Math.max(max, 1);
map.put(num, 1);
} else {
int n = map.get(num) + 1;
max = Math.max(max, n);
map.put(num, map.get(num) + 1);
}
}
int n = nums.size();
if (n % 2 == 0) return max <= n/2 ? 0 : max-(n-max);
return max <= n/2 ? 1 : max-(n-max);
}
}981. 基于时间的键值存储
设计一个基于时间的键值数据结构，该结构可以在不同时间戳存储对应同一个键的多个值，并针对特定时间戳检索键对应的值。
实现 TimeMap 类：
TimeMap()初始化数据结构对象void set(String key, String value, int timestamp)存储给定时间戳timestamp时的键key和值value。String get(String key, int timestamp)返回一个值，该值在之前调用了set，其中timestamp_prev <= timestamp。如果有多个这样的值，它将返回与最大timestamp_prev关联的值。如果没有值，则返回空字符串（""）。
class LinkValue {
String value;
int timestamp;
public LinkValue() {}
public LinkValue(String value, int timestamp) {
this.value = value;
this.timestamp = timestamp;
}
}
class TimeMap {
Map<String, List<LinkValue>> map=new HashMap<>();;
public TimeMap() {
}
public void set(String key, String value, int timestamp) {
LinkValue linkValue = new LinkValue(value, timestamp);
if (!map.containsKey(key)) {
List<LinkValue> list = new ArrayList<>();
list.add(linkValue);
map.put(key, list);
} else {
List list=map.get(key);
list.add(linkValue);
map.put(key, list);
}
}
public String get(String key, int timestamp) {
if (!map.containsKey(key) || map.get(key).get(0).timestamp > timestamp) {
return "";
} else {
List<LinkValue> list=map.get(key);
int left=0, right=list.size()-1;
while (left <= right) {
int mid=(right-left)/2 + left;
LinkValue tmp = list.get(mid);
if (tmp.timestamp == timestamp) return tmp.value;
else if (tmp.timestamp < timestamp) {
left = mid + 1;
} else {
right = mid - 1;
}
}
LinkValue tmp1 = list.get(right);
return tmp1.value;
}
}
}
/**
* Your TimeMap object will be instantiated and called as such:
* TimeMap obj = new TimeMap();
* obj.set(key,value,timestamp);
* String param_2 = obj.get(key,timestamp);
*/1146. 快照数组
实现支持下列接口的「快照数组」- SnapshotArray：
SnapshotArray(int length)- 初始化一个与指定长度相等的 类数组 的数据结构。初始时，每个元素都等于 0。void set(index, val)- 会将指定索引index处的元素设置为val。int snap()- 获取该数组的快照，并返回快照的编号snap_id（快照号是调用snap()的总次数减去1）。int get(index, snap_id)- 根据指定的snap_id选择快照，并返回该快照指定索引index的值。
class SnapshotArray {
private int snapId;
private Map<Integer, TreeMap<Integer, Integer>> map;
public SnapshotArray(int length) {
snapId = 0;
map = new HashMap<>();
for (int i = 0; i < length; i++) {
map.put(i, new TreeMap<>());
map.get(i).put(0, 0); // 初始化每个元素的初始值为 0，在 snap 0 时。
}
}
public void set(int index, int val) {
map.get(index).put(snapId, val);
}
public int snap() {
return snapId++;
}
public int get(int index, int snap_id) {
// 查找给定 snap_id 的值，如果不存在则找到小于或等于 snap_id 的最大快照值
return map.get(index).floorEntry(snap_id).getValue();
}
}658. 找到 K 个最接近的元素
给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足：
|a - x| < |b - x|或者|a - x| == |b - x|且a < b
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
Arrays.sort(arr);
List<Integer> list = new ArrayList<>();
int pos=find(arr, x);
System.out.println(pos);
int left=pos-1, right=pos;
int i=0;
while(i < k) {
if (left < 0) {
while (i < k) {
right++;
i++;
}
break;
}
if (right == arr.length) {
while (i < k) {
left--;
i++;
}
break;
}
int num1=arr[left], num2=arr[right];
if (Math.abs(x-num1) <= Math.abs(x-num2)) {
left--;
} else {
right++;
}
i++;
}
for (int j=left+1; j<=right-1; j++) {
list.add(arr[j]);
}
return list;
}
//找到第一个大于等于x的位置
public int find(int[] arr, int x) {
int left=0, right=arr.length-1;
int mid=0;
while (left<right) {
mid=(right-left)/2+left;
if (arr[mid] >= x) {
right = mid;
} else {
left = mid+1;
}
}
return left;
}
}1818. 绝对差值和
给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。
数组 nums1 和 nums2 的 绝对差值和 定义为所有 |nums1[i] - nums2[i]|（0 <= i < n）的 总和（下标从 0 开始）。
你可以选用 nums1 中的 任意一个 元素来替换 nums1 中的 至多 一个元素，以 最小化 绝对差值和。
在替换数组 nums1 中最多一个元素 之后 ，返回最小绝对差值和。因为答案可能很大，所以需要对 109 + 7 取余 后返回。
|x| 定义为：
如果
x >= 0，值为x，或者如果
x <= 0，值为-x
class Solution {
public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
long sum = 0;
int max = 0;
int length = nums1.length;
int[] sorted = nums1.clone();
Arrays.sort(sorted); // 排序后的 nums1 用于二分查找
for (int i = 0; i < length; i++) {
int gap = Math.abs(nums1[i] - nums2[i]); // 当前差值
int pos = find(sorted, nums2[i]); // 找到第一个大于等于 nums2[i] 的位置
// 初始最小差值为与 nums2[i] 最近的 sorted[pos] 的差值
int minGap = Integer.MAX_VALUE;
// 检查 pos-1 是否有效，并计算与 nums2[i] 的差值
if (pos > 0) {
minGap = Math.min(minGap, Math.abs(sorted[pos - 1] - nums2[i]));
}
// 检查 pos+1 是否有效，并计算与 nums2[i] 的差值
if (pos < length) {
minGap = Math.min(minGap, Math.abs(sorted[pos] - nums2[i]));
}
// 更新最大减少的差值
max = Math.max(max, gap - minGap);
sum += gap;
}
return (int)((sum - max) % 1000000007);
}
public int find(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (right - left) / 2 + left;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left; // left 是第一个大于等于 target 的位置
}
}二分答案：求最小
1283. 使结果不超过阈值的最小除数
给你一个整数数组 nums 和一个正整数 threshold ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。
请你找出能够使上述结果小于等于阈值 threshold 的除数中 最小 的那个。
每个数除以除数后都向上取整，比方说 7/3 = 3 ， 10/2 = 5 。
题目保证一定有解。
class Solution {
public int smallestDivisor(int[] nums, int threshold) {
int max=0;
int length=nums.length;
for (int num : nums) {
max = Math.max(num, max);
}
long left=1, right=max+1;
// System.out.println(left + " " +right);
while (left <= right) {
long mid = (right-left)/2+left;
if (!check(nums, threshold, mid)) {
left = mid + 1;
} else {
right = mid-1;
}
}
return (int)left;
}
public boolean check(int[] nums, int threshold, long divide) {
long sum=0;
for (int num : nums) {
sum += (int)(Math.ceil(num*1.0/divide));
}
// System.out.println(divide + " " + sum);
if (sum > threshold) return false;
return true;
}
}2187. 完成旅途的最少时间
给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟**旅途** 所需要花费的时间。
每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。
给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。
class Solution {
public long minimumTime(int[] time, int totalTrips) {
Arrays.sort(time);
long min=1, max=(long)totalTrips*time[0];
long mid=1;
long ans=max;
// System.out.println(min + " " + max);
while (min < max) {
mid = (max-min)/2 + min;
if (check(time, mid, totalTrips)) {
ans = Math.min(ans, mid);
max=mid;
} else {
min=mid+1;
}
}
return ans;
}
public boolean check(int[] time, long cur, int totalTrips) {
long cnt=0;
for (int t : time) {
cnt += (long)(cur/t);
}
// System.out.println(cur);
// System.out.println(cnt);
return cnt >= totalTrips;
}
}1870. 准时到达的列车最小时速
给你一个浮点数 hour ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 n 趟列车。另给你一个长度为 n 的整数数组 dist ，其中 dist[i] 表示第 i 趟列车的行驶距离（单位是千米）。
每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。
例如，第
1趟列车需要1.5小时，那你必须再等待0.5小时，搭乘在第 2 小时发车的第2趟列车。
返回能满足你准时到达办公室所要求全部列车的 最小正整数 时速（单位：千米每小时），如果无法准时到达，则返回 -1 。
生成的测试用例保证答案不超过 107 ，且 hour 的 小数点后最多存在两位数字 。
class Solution {
public int minSpeedOnTime(int[] dist, double hour) {
int n=dist.length;
int left=1, right=Integer.MIN_VALUE;
for(int d : dist) {
right = Math.max(d, right);
}
right = right * 100;
int mid=0;
int ans=right;
boolean valid=false;
while (left <= right) {
mid = (right-left)/2 + left;
if (check(dist, mid, hour)) {
valid = true;
ans = Math.min(ans, mid);
right = mid-1;
} else {
left=mid+1;
}
}
return valid ? ans : -1;
}
public boolean check(int[] dist, int speed, double hour) {
double cnt=0;
for (int i=0; i<dist.length-1; i++) {
cnt += Math.ceil(dist[i] * 1.0 / speed);
}
cnt += dist[dist.length-1] *1.0/speed;
// System.out.println(speed + " " + cnt);
return cnt <= hour;
}
}1011. 在 D 天内送达包裹的能力
传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。
class Solution {
public int shipWithinDays(int[] weights, int days) {
int length=weights.length;
int left=1, right=0;
for(int weight : weights) {
right = Math.max(weight, right);
}
right = right * length / days*2;
int mid=0;
int ans=right;
// System.out.println(left + " " + right);
while (left < right) {
mid=(right-left)/2+left;
if (check(weights, mid, days)) {
ans = Math.min(ans, mid);
right = mid;
} else {
left = mid+1;
}
}
return ans;
}
public boolean check(int[] weights, int hold, int days) {
int cur=0;
int cnt=1;
for (int i=0; i<weights.length; i++) {
if (weights[i] > hold) {
return false;
}
if (cur + weights[i] > hold) {
cur = weights[i];
cnt++;
} else {
cur += weights[i];
}
}
// System.out.println(hold + " " + cnt);
return days >= cnt;
}
}875. 爱吃香蕉的珂珂
珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。
珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int left=1, right=0;
for (int pile : piles) {
right=Math.max(right, pile);
}
int mid = 0;
int ans = right;
while (left<right) {
mid=(right-left)/2+left;
if (check(piles, mid, h)) {
ans=Math.min(ans, mid);
right=mid;
} else {
left=mid+1;
}
}
return ans;
}
public boolean check(int[] piles, int eat, int h) {
int cnt=0;
for (int i=0; i<piles.length; i++) {
cnt += (piles[i] + eat - 1) / eat;
}
return cnt <= h;
}
}475. 供暖器
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。
现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。
注意：所有供暖器 heaters 都遵循你的半径标准，加热的半径也一样。
class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int n=houses.length;
int m=heaters.length;
int left=0, right=Math.max(houses[n-1]-houses[0], heaters[m-1]-houses[0]);
int mid=0, ans=right;
while (left < right) {
mid=(right-left)/2+left;
if (check(houses, heaters, mid)) {
right = mid;
ans = Math.min(ans, mid);
} else {
left = mid + 1;
}
}
return ans;
}
public boolean check(int[] houses, int[] heaters, int radius) {
int i=0, j=0;
while (i<houses.length && j<heaters.length) {
if (houses[i] >= heaters[j]-radius && houses[i] <= heaters[j]+radius) {
i++;
} else {
j++;
}
}
if (i<houses.length) return false;
return true;
}
}2594. 修车的最少时间
给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。
同时给你一个整数 cars ，表示总共需要修理的汽车数目。
请你返回修理所有汽车 最少 需要多少时间。
注意：所有机械工可以同时修理汽车。
class Solution {
public long repairCars(int[] ranks, int cars) {
long left=1, right=Integer.MAX_VALUE;
for(int rank : ranks) {
right=Math.min(rank, right);
}
right = right*cars;
long mid=0, ans=right;
// System.out.println(left + " " + right);
while(left<right) {
mid=(right-left)/2+left;
if (check(ranks, cars, mid)) {
ans = Math.min(ans, mid);
right=mid;
} else {
left=mid+1;
}
}
return ans;
}
public boolean check(int[] ranks, int cars, long time) {
long cnt=0;
for (int rank : ranks) {
cnt += (int) Math.sqrt(time/rank);
}
// System.out.println(time + " " + cnt);
return cnt >= cars;
}
}1482. 制作 m 束花所需的最少天数
给你一个整数数组 bloomDay，以及两个整数 m 和 k 。
现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。
花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。
请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。
class Solution {
public int minDays(int[] bloomDay, int m, int k) {
int n=bloomDay.length;
if (n < m * k) return -1;
int left=1, right=0;
for (int d : bloomDay) {
right = Math.max(right, d);
}
right++;
int mid=0, ans=right;
boolean isChecked=false;
// System.out.println(left + " " + right);
while (left<right) {
mid=(right-left)/2+left;
if (check(bloomDay, m, k, mid)) {
right=mid;
ans=Math.min(ans, mid);
} else {
left=mid+1;
}
}
return isChecked ? ans : -1;
}
public boolean check(int[] bloomDay, int m, int k, int days) {
int cnt=0;
int cur=0;
for (int i=0; i<bloomDay.length; i++) {
if (bloomDay[i] <= days) {
cur++;
} else {
cur = 0;
}
if (cur == k) {
cnt++;
cur=0;
}
}
// System.out.println(days + " " + cnt);
return cnt >= m;
}
}二分答案：求最大
275. H 指数 II
给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。
h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）至少 有 h 篇论文分别被引用了至少 h 次。
请你设计并实现对数时间复杂度的算法解决此问题。
class Solution {
public int hIndex(int[] citations) {
int n = citations.length;
int left = 0, right = n-1;
int answer = citations[n-1];
int mid;
int citation=0;
int count=0;
int max = 0;
while (left <= right) {
mid = (left + right)/2;
citation = citations[mid]; //引用数
count = n-mid; //篇数
// System.out.println(count + " " + citation);
if (count <= citation) {
max = Math.max(max, count);
right = mid-1;
} else if (count > citation) {
left = mid + 1;
}
}
// System.out.println(left + " " + right);
// System.out.println(citation + " " + count);
return max;
}
}2226. 每个小孩最多能分到多少糖果
给你一个 下标从 0 开始 的整数数组 candies 。数组中的每个元素表示大小为 candies[i] 的一堆糖果。你可以将每堆糖果分成任意数量的 子堆 ，但 无法 再将两堆合并到一起。
另给你一个整数 k 。你需要将这些糖果分配给 k 个小孩，使每个小孩分到 相同 数量的糖果。每个小孩可以拿走 至多一堆 糖果，有些糖果可能会不被分配。
返回每个小孩可以拿走的 最大糖果数目 。
class Solution {
public int maximumCandies(int[] candies, long k) {
long sum=0;
int n=candies.length;
int left=1, right=1;
for (int candy : candies) {
right=Math.max(candy, right);
sum += candy;
}
if (sum < k) return 0;
int mid=0, ans=1;
while(left<=right) {
mid=(right-left)/2+left;
if (check(candies, k, mid)) {
left=mid+1;
ans=Math.max(ans, mid);
} else {
right=mid-1;
}
}
return ans;
}
public boolean check(int[] candies, long k, int num) {
long cnt=0;
for (int candy : candies) {
cnt += candy/num;
}
return cnt>=k;
}
}2982. 找出出现至少三次的最长特殊子字符串 II
给你一个仅由小写英文字母组成的字符串 s 。
如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。
返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。
子字符串 是字符串中的一个连续 非空 字符序列。
class Solution {
public int maximumLength(String s) {
List<Integer>[] lists = new ArrayList[26];
for (int i = 0; i < lists.length; i++) {
lists[i] = new ArrayList<>(); // 直接通过索引访问并初始化
}
char[] chars = s.toCharArray();
int n=s.length();
int cnt=0;
for (int i=0; i<n; i++) {
cnt++;
if (i==n-1 || chars[i] != chars[i+1]) {
lists[chars[i]-'a'].add(cnt);
cnt=0;
}
}
int ans=0;
for (List<Integer> list : lists) {
if (list.isEmpty()) continue;
Collections.sort(list, Collections.reverseOrder());
list.add(0);
list.add(0);
ans = Math.max(ans,Math.max(list.get(0)-2, Math.max(Math.min(list.get(0)-1, list.get(1)), list.get(2))));
}
return ans==0 ? -1 : ans;
}
}2576. 求出最多标记下标
给你一个下标从 0 开始的整数数组 nums 。
一开始，所有下标都没有被标记。你可以执行以下操作任意次：
选择两个 互不相同且未标记 的下标
i和j，满足2 * nums[i] <= nums[j]，标记下标i和j。
请你执行上述操作任意次，返回 nums 中最多可以标记的下标数目。
class Solution {
public int maxNumOfMarkedIndices(int[] nums) {
Arrays.sort(nums); // 先对数组进行排序
int res = 0;
int length = nums.length;
int fast = length / 2 - 1, slow = length - 1; // fast 从中间开始，slow 从末尾开始
// 使用双指针遍历数组
while (fast >= 0 && slow >= length / 2) {
if (nums[fast] * 2 <= nums[slow]) { // 如果满足条件
res += 2; // 成对的元素计数
slow--; // slow 移动到下一个位置
}
fast--; // fast 移动到下一个位置
}
return res; // 返回被标记的元素数量
}
}1898. 可移除字符的最大数目
给你两个字符串 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 的一个子序列。
字符串的一个 子序列 是一个由原字符串生成的新字符串，生成过程中可能会移除原字符串中的一些字符（也可能不移除）但不改变剩余字符之间的相对顺序。
class Solution {
public int maximumRemovals(String s, String p, int[] removable) {
int length1=s.length(), length2=p.length();
int i=length1-1, j=length2-1;
for (; i>=0; i--) {
if (j <0) break;
if (s.charAt(i) == p.charAt(j)) {
j--;
}
}
System.out.println(j + " " + i);
for (int k=0; k<removable.length; k++) {
if (removable[k] < i) {
return k;
}
}
return -1;
}
}最小化最大值
410. 分割数组的最大值
给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组。
设计一个算法使得这 k 个子数组各自和的最大值最小。
class Solution {
public int splitArray(int[] nums, int k) {
int n=nums.length;
int left=-1, right=0;
for (int num:nums) {
right+=num;
}
int mid=0, ans=right;
// System.out.println(left + " " + right);
while (left<=right) {
mid=(right-left)/2+left;
if (check(nums, k, mid)) {
right=mid-1;
ans=Math.min(ans, mid);
}else{
left=mid+1;
}
}
return ans;
}
public boolean check(int[] nums, int k, int max) {
int cur=0;
int cnt=1;
// System.out.println(max);
for (int i=0; i<nums.length; i++) {
if (nums[i] > max) return false;
if (nums[i] + cur <= max) {
cur=nums[i]+cur;
} else {
cur=nums[i];
cnt++;
}
if (cnt > k) return false;
}
return cur<=max && cnt<=k;
}
}2064. 分配给商店的最多商品的最小值
给你一个整数 n ，表示有 n 间零售商店。总共有 m 种产品，每种产品的数目用一个下标从 0 开始的整数数组 quantities 表示，其中 quantities[i] 表示第 i 种商品的数目。
你需要将 所有商品 分配到零售商店，并遵守这些规则：
一间商店 至多 只能有 一种商品 ，但一间商店拥有的商品数目可以为 任意 件。
分配后，每间商店都会被分配一定数目的商品（可能为
0件）。用x表示所有商店中分配商品数目的最大值，你希望x越小越好。也就是说，你想 最小化 分配给任意商店商品数目的 最大值 。
请你返回最小的可能的 x 。
class Solution {
public int minimizedMaximum(int n, int[] quantities) {
int length=quantities.length;
int left=0, right=0;
for (int num:quantities) {
right=Math.max(right, num);
}
int mid=0, ans=right;
while(left<=right) {
mid=(right-left)/2+left;
if (check(n, quantities, mid)) {
right=mid-1;
ans=Math.min(ans, mid);
} else {
left=mid+1;
}
}
return ans;
}
public boolean check(int n, int[] quantities, int max) {
int cnt=0;
for (int num:quantities) {
cnt += Math.ceil(num * 1.0 / max);
}
return cnt <= n;
}
}1760. 袋子里最少数目的球
给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。
你可以进行如下操作至多 maxOperations 次：
选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有
正整数
个球。
比方说，一个袋子里有
5个球，你可以把它们分到两个新袋子里，分别有1个和4个球，或者分别有2个和3个球。
你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。
请你返回进行上述操作后的最小开销。
class Solution {
public int minimumSize(int[] nums, int maxOperations) {
int left=1, right=0;
for(int num : nums) {
right=Math.max(right, num);
}
int mid=0, ans=right;
while(left<=right) {
mid=(right-left)/2+left;
if(check(nums, maxOperations, mid)) {
right=mid-1;
ans=Math.min(ans, mid);
} else {
left=mid+1;
}
}
return ans;
}
public boolean check(int[] nums, int maxOperations, int balls) {
int cnt=0;
for (int num : nums) {
if (num > balls) {
cnt += Math.ceil(num * 1.0 / balls)-1;
}
}
return cnt <= maxOperations;
}
}2439. 最小化数组中的最大值
给你一个下标从 0 开始的数组 nums ，它含有 n 个非负整数。
每一步操作中，你需要：
选择一个满足
1 <= i < n的整数i，且nums[i] > 0。将
nums[i]减 1 。将
nums[i - 1]加 1 。
你可以对数组执行 任意 次上述操作，请你返回可以得到的 nums 数组中 最大值 最小 为多少。
class Solution {
public int minimizeArrayValue(int[] nums) {
int n=nums.length;
int left=1, right=0;
for (int num:nums) {
right=Math.max(right, num);
}
int mid=0, ans=right;
while (left<=right) {
mid=(right-left)/2+left;
if (check(nums, mid)) {
right=mid-1;
ans=Math.min(ans, mid);
} else {
left=mid+1;
}
}
return ans;
}
public boolean check(int[] nums, int threshold) {
int n=nums.length;
long extra=0;
for (int i=0; i<n; i++) {
if (i==0 && nums[i] > threshold) return false;
if (nums[i] <= threshold) {
extra += threshold-nums[i];
} else {
extra -= nums[i]-threshold;
if (extra < 0) return false;
}
}
return true;
}
}