二分系列(二分答案最大值)9/15.16
一、找出出现至少三次的最长特殊子序列
题意:
给你一个仅由小写英文字母组成的字符串 s
。
如果一个字符串仅由单一字符组成,那么它被称为 特殊 字符串。例如,字符串 "abc"
不是特殊字符串,而字符串 "ddd"
、"zz"
和 "f"
是特殊字符串。
返回在 s
中出现 至少三次 的 最长特殊子字符串 的长度,如果不存在出现至少三次的特殊子字符串,则返回 -1
。
思路:
仍然使用二分答案的思路。
1.确定答案的范围区间,这里粗略的判断为0->str.length()
2.对答案进行二分查找
3.写一个校验函数check(利用滑动窗口的思想):
滑动窗口里面是特殊子字符串,使用数组进行统计。以特殊子字符串中的字符-'a'作为下标。
boolean check(String str,int len){
int[] cnt=new int[26];
for(int i=0;i<str.length();i++){
int j=i+1;
while(j<str.length()&&str.charAt(i)==str.charAt(j))
j++;
int n=str.charAt(i)-'a';
cnt[n]+=Math.max(0,j-i+1-len);
if(cnt[n]>=3)return true;
i=j;
}
return false;
}
代码:
class Solution {
public int maximumLength(String s) {
int left=0;
int right=s.length()-1;
while(left<=right){
int mid=left+(right-left)/2;
if(check(s,mid)){
left=mid+1;
}else{
right=mid-1;
}
}
return right==0?-1:right;
}
public boolean check(String s,int len){
int[] cnt=new int[26];
for(int i=0;i<s.length();){
int j=i+1;
while(j<s.length()&&s.charAt(i)==s.charAt(j)){
j++;
}
int k=s.charAt(i)-'a';
cnt[k]+=Math.max(0,j-i-len+1);
if(cnt[k]>=3){
return true;
}
i=j;
}
return false;
}
}
二、求最多标记下标
给你一个下标从 0 开始的整数数组 nums
。一开始,所有下标都没有被标记。你可以执行以下操作任意次:
- 选择两个 互不相同且未标记 的下标
i
和j
,满足2 * nums[i] <= nums[j]
,标记下标i
和j
。
请你执行上述操作任意次,返回 nums
中最多可以标记的下标数目
思路:
题目中要我们求最多可以标记的下标数目。假设下标数目为x,那么排序后前x个数字一定符合x*2<=y;y是后x个数字。
_ _ _ x _ _ _ x_ _ _
因此我们选择二分法进行查找答案
1.答案的范围为(0,nums.length/2)
2.在范围里面进行二分
3.check()函数:
将数组排序之后,判断前x个元素对后x个元素是否满足条件
代码:
class Solution {
public int maxNumOfMarkedIndices(int[] nums) {
Arrays.sort(nums);
//如果二分的答案是满足题意的,那么排序后一定存在前mid个是一定小于后mid个的 牛
int left=0;
int right=nums.length/2;
while(left<=right){
int mid=left+(right-left)/2;//mid为对数
if(check(nums,mid)){
left=mid+1;
}else{
right=mid-1;
}
}
System.out.println("left:"+left+" right: "+right);
return right*2;
}
public boolean check(int[] nums,int mid){
int n=nums.length;
for(int i=0;i<mid;i++){
if(nums[i]*2>nums[n-mid+i])return false;
}
return true;
}
}
三、有界数组中指定下标处的最大值
给你三个正整数 n
、index
和 maxSum
。你需要构造一个同时满足下述所有条件的数组 nums
(下标 从 0 开始 计数):
nums.length == n
nums[i]
是 正整数 ,其中0 <= i < n
abs(nums[i] - nums[i+1]) <= 1
,其中0 <= i < n-1
nums
中所有元素之和不超过maxSum
nums[index]
的值被 最大化
返回你所构造的数组中的指定下标处的最大值!
思路:
二分最大值;
根据贪心:以index为中心,向两边依次-1,直到减到1为止。然后计算总和与maxSum作比较。
这里在求和的时候可能会超时。所以使用求和公式比较好。和为:(首项+末项)*项数/2
但是要检测左边是否减到1。
左边leftCount:index个元素。
如果mid-index>=1的,直接求和公式;
如果mid-index<1的,要计算有多少个1。leftCount-(mid-1); 前n项和:(mid-1+1)*(mid-1)/2+leftCount-(mid-1);
右边rightCount: n-index-1个元素
如果mid-rightCount>=1,直接求和公式
如果mid-rightCount<1,先计算多少个1,xxx
代码:
class Solution {
public int maxValue(int n, int index, int maxSum) {
int left=1;
int right=maxSum;
while(left<=right){
int mid=left+(right-left)/2;
if(check(n,index,maxSum,mid)){
left=mid+1;
}else{
right=mid-1;
}
}
return right;
}
public boolean check(int n,int index,int maxSum,int mid){
//左右两边各有多少个元素 然后用求和公式
int leftCount=index;
int rightCount=n-index-1;
//还要判断是否为1
long leftSum=0;
long rightSum=0;
if(mid>leftCount){
leftSum=(long)(mid-1+mid-leftCount)*leftCount/2;
}else{
leftSum=(long)(mid-1+1)*(mid-1)/2+leftCount-mid+1;
}
if(mid>rightCount){
rightSum=(long)(mid-rightCount+mid-1)*rightCount/2;
}else{
rightSum=(long)(mid-1+1)*(mid-1)/2+rightCount-mid+1;
}
long sum=leftSum+rightSum+mid;
return sum<=maxSum;
}
}
四、最大合金数
题意:
给你一批机器,及其它制作一块合金所需要的不同种类金属的个数。用List<List<Integer>> composition表示。eg:[[1,1,1],[1,1,10]] 。第一台机器制作一块合金,需要一块A金属、一块B金属、一块C金属。 第二台机器需要1 1 10;
然后每一种金属可能有库存,用stock[i]来表示;每一种金属也有cost[i],表示价格。
给你一个budget预算,请你给出可以制作的最大合金数。
思路:
二分答案。
1.首先找出答案的范围(1,100000000)
2.对答案进行二分
3.对每一种答案进行判断。假设x块合金:
我们对每一类机器所需要的各种种类的金属进行判断,如果仓库里面有,就不需要花钱;仓库里面没有需要花钱,看总花费是否<=预算。如果小于,返回true。表示该数量的合金是可以制作的。
代码:
class Solution {
public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
// n是合金的种类 k是机器数 budget是预算 stock最开始拥有的i类型金属 cost是花费
// 制造合金数目的范围是 0->
int max=0;
for(Integer num:stock){
max=Math.max(num,max);
}
long left=0;
long right=(long)budget+max;
while(left<=right){
long mid=left+(right-left)/2;
//System.out.println("left:"+left+" right:"+right+" ");
if(check(budget,composition,stock,cost,mid)){
left=mid+1;
}else{
right=mid-1;
}
}
return (int)right;
}
public boolean check(int budget,List<List<Integer>> composition,List<Integer> stock, List<Integer> cost,long mid){
for(List<Integer> compos:composition){
//对于每一个机器来进行讨论 我需要mid*
long totalCost=0;
for(int i=0;i<compos.size();i++){
long required=compos.get(i)*mid;
long own=stock.get(i);
if(own>=required)own-=required;
else{
long buy=required-own;
totalCost+=buy*cost.get(i);
}
}
if(totalCost<=budget){
return true;
}
}
return false;
}
}
原文地址:https://blog.csdn.net/2301_78191305/article/details/142280911
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!