二分答案 能穿过矩阵的最后一天
能穿过矩阵的最后一天
即计算能穿过矩阵的最大天数 如果能穿过矩阵的最大天数是k
所有的小于k的天数也都能够穿过矩阵
二分区间为[0,row*col]
class Solution {
int[] dx={0,1,0,-1};
int[] dy={1,0,-1,0};
public int latestDayToCross(int row, int col, int[][] cells) {
//二分
int left=0;int right=row*col;
int[][] grid=new int[row][col];
while(left<right){
int mid=left+right+1>>1;
for(int i=0;i<row;i++){
Arrays.fill(grid[i],1);//1表示陆地,前mid天对应的cells变为0水
}
for(int i=0;i<mid;i++){
grid[cells[i][0]-1][cells[i][1]-1]=0;
}
if(check(grid)){
//修改二分区间
left=mid;
}else{
right=mid-1;
}
}
return left;
}
public boolean check(int[][] grid){
Queue<int[]> queue=new LinkedList<>();
//搜索
for(int j=0;j<grid[0].length;j++){
if(grid[0][j]==1){
queue.offer(new int[]{0,j});
//将对应的已经走过的位置修改,避免回头路,不需要bool[]
grid[0][j]=0;
}
}
while (!queue.isEmpty()) {
int[] node=queue.poll();
int x=node[0];int y=node[1];
if(x==grid.length-1){
return true;
}
for(int k=0;k<4;k++){
int a=x+dx[k];
int b=y+dy[k];
if(a>=0&&a<grid.length&&b>=0&&b<grid[0].length&&grid[a][b]!=0){
queue.offer(new int[]{a,b});
grid[a][b]=0;
}
}
}
return false;
}
}
寻找峰值
寻找峰值
二分数组不需要严格单调,寻找其中另一一个可行值
class Solution {
public int findPeakElement(int[] nums){
int left=0;int right=nums.length-1;int res=-1;
while (left < right) {
int mid=left+right>>1;
if (check(nums, mid)) {
right=mid;
}else{
left=mid+1;
}
}
return left;
}
public boolean check(int[] nums,int mid){
return nums[mid]>nums[mid+1]||mid==nums.length-1;
}
}
查找target所在的位置 初始化right=nums.length-1
查找第一个大于target位置 初始化right=nums.length
public int binarySearch(int[] nums,int target){
int left=0;int right=nums.length;
while(left<right){
int mid=left+right>>1;
if(nums[mid]>target){
right=mid;
}else{
left=mid+1;
}
}
return left;
}
二分大于target的第一个数
class Solution {
//预处理所有的
int max_n=100010;
int[] f=new int[max_n];
int MOD=1000000007;
public int numSubseq(int[] nums, int target) {
init();
//对于所有的最小元素
Arrays.sort(nums);
int res=0;
for(int i=0;i<nums.length&&nums[i]*2<=target;i++){
int maxv=target-nums[i];
int pos=binarySearch(nums,maxv)-1;
int contribute=(pos>=i)? f[pos-i]:0;
res=(res+contribute)%MOD;
}
return res;
}
//大于target第一个值
public int binarySearch(int[] nums,int target){
int left=0;int right=nums.length-1;
while(left<right){
int mid=left+right+1>>1;
if(nums[mid]>target){
right=mid;
}else{
left=mid+1;
}
}
return left;
}
public void init(){
f[0]=1;
for(int i=1;i<max_n;i++){
f[i]=(f[i-1]<<1)%MOD;
}
}
}
第k个最小的素数分数
第k个最小的素数分数
所有的素数分数结果为[0,1]
通过二分get(k)表示小于等于k的素数分数的个数,
实数二分,对于最后的结果计算距离最近的素数分数
class Solution {
double eps=1e-8;
int A,B;
public int[] kthSmallestPrimeFraction(int[] arr, int k) {
double left=0;double right=1;//所有的素数分数小于1,所以二分区间[0,1]
while ((right - left) > eps) {
double mid=(left+right)/2;
if(get(arr,mid)>=k){
right=mid;
}else{
left=mid;//实数域上的二分对应的left=mid
}
}
get(arr,right);
return new int[]{A,B};
}
public int get(int[] arr,double mid){
//表示小于等于mid的素数分数个数
int res=0;
for(int i=0,j=0;i<arr.length;i++){
while((double)arr[j+1]/arr[i]<=mid)j++;
if((double)arr[j]/arr[i]<=mid){
res+=j+1;
}
//计算最接近mid的素数分数
if(Math.abs((double)arr[j]/arr[i]-mid)<eps){
A=arr[j];
B=arr[i];
}
}
return res;
}
}
阶乘函数后k个零
阶乘函数后k个零
阶乘函数包含k个零的整数的个数
所有的零的个数,对应的10=2*5因子的个数最小值 ,假设对应的2因子个数为a;5因子个数为b Math.min(a,b)
[n/5]+[n/5/5]+[n/5/5/5]+[n/5/5/5/5]+…
对应n越大,包含的5因子非递减,通过二分的方式,前缀
cal(k)-cal(k-1);
其中cal(k):表示因子5的个数小于等于k个元素个数
class Solution {
public int preimageSizeFZF(int k) {
System.out.println(cal(-1)+"===="+cal(0));
return (int)(cal(k)-cal(k-1));
}
public long cal(int k){
long left=-1;long right=(long)1e18;
while (left < right) {
long mid=left+right+1>>1;
if(get(mid)<=k){
left=mid;
}else{
right=mid-1;
}
}
return left;
}
public long get(long k){
long res=0;
while(k!=0){
res+=k/5;
k/=5;
}
return res;
}
}