牛客笔试强训

本文主要是介绍牛客笔试强训，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

牛客AB33.相差不超过k的最多数 (滑动窗口)

 和之前那个空调吹风属于一道题的类型，当然滑动窗口,最大值-最小值，然后<=p即可

也可以双指针来取寻找最大值和最小值

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int k = in.nextInt();int[]a=new int[n];for(int i=0;i<n;i++){a[i]=in.nextInt();}Arrays.sort(a);int left=0;int right=0;int count=0;while(right<n){while(a[right]-a[left]>k){left++;}if(a[right]-a[left]<=k){count=Math.max(count,right-left+1);}right++;}System.out.print(count);}
}

二分，注意的是要确认，二分对应的界限，左端点是left+(right-left)/2,右端点是left+(right-left+1)/2。为什么是这两个情况，因为小于等于，和大于等于啥的要求不一样，如果左端点不+1，这样她就是两个相同的里面左边的那个，反之就是右边的那个 

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int n = in.nextInt();int count = 1;int k = in.nextInt();int[]a = new int[n];for (int i = 0; i < n; i++) {a[i] = in.nextInt();}Arrays.sort(a);for (int i = 0; i < n; i++) {int x = Math.max(a[i] - k, 1);int left = 0;int right = n - 1;while (left < right) {int mid = left + (right - left) / 2;if (a[mid] >= x) {right = mid;} else {left = mid + 1;}}int l = left;left = 0;right = n - 1;x = Math.max(a[l] + k, 1);while (left < right) {int mid = left + (right - left + 1) / 2;if (a[mid] > x) {right = mid - 1;} else {left = mid;}}count = Math.max(count, right - l + 1);}System.out.print(count);}
}

 牛客.DP最长公共子序列

动态规划，只要前面出来了，代码好写

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别        int n= in.nextInt();int m= in.nextInt();String aa=in.next();char[]a=aa.toCharArray();String bb=in.next();char[]b=bb.toCharArray();//s1中[0,i]区间以及s2中[0,j]区间中，所有子序列里面，最长的公共子序列长度int max=0;int[][]dp=new int[n+1][m+1];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i-1]==b[j-1]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);}max=Math.max(dp[i][j],max);}}
System.out.println(max);}
}

牛客.春游

模拟，贪心，有点微微像蓝桥杯的食堂，但是情况比食堂会简单一点

import java.util.*;
public class Main{public static void main(String[]args){Scanner in=new Scanner(System.in);int T=in.nextInt();for(int i=0;i<T;i++){long n=in.nextLong();long a=in.nextLong();long b=in.nextLong();long ret=0;if(n<=2){ret=Math.min(a,b);}else{if(3*a<2*b){ret=n/2*a;if(n%2==1){  if(2*a<b){ret+=a;}else{ret+=b-a;}}}else {ret=n/3*b;if(n%3==2){ret+=Math.min(a,Math.min(b,3*a-b));}else if(n%3==1){ret+=Math.min(a,Math.min(b,2*a-b));}}   }System.out.println(ret);}}
}

牛客.活动安排(贪心)

我们应该选择右端点较小的作为基准,当我面临这种重叠的时候，.

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n=in.nextInt();int[][]arr=new int[n][2];for(int i=0;i<n;i++){arr[i][0]=in.nextInt();arr[i][1]=in.nextInt();}Arrays.sort(arr,(x,y)->{return x[0]<=y[0] ?-1:1;});int ret=0;int r=arr[0][1];for(int i=1;i<n;i++){if(arr[i][0]<r){r=Math.min(arr[i][1],r);}else{ret++;r=arr[i][1];}}System.out.println(ret+1);}
}

这篇关于牛客笔试强训的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---