牛客网刷题——斩获offer

个人主页：熬夜磕代码丶
作品专栏: java se
我变秃了，也变强了
给大家介绍一款程序员必备刷题平台——牛客网
点击注册一起刷题收获大厂offer吧

文章目录

一、 随机数组

通过对数器生成一个随机长度，随机大小的数组

publicstaticint[]randomArray(int maxLen,int maxValue){intLen=(int)(Math.random()* maxLen);int[] arr =newint[Len];if(Len>0){
            arr[0]=(int)(Math.random()* maxValue);for(int i =1; i <Len; i++){do{
                    arr[i]=(int)(Math.random()* maxValue);}while(arr[i]== arr[i-1]);}}return arr;}```
    

二、 局部最小值

定义局部最小的概念。arr长度为1时，arr[0]是局部最小。arr的长度为N(N>1)时，如果arr[0] < arr[1]，那么arr[0]是局部最小；
如果arr[N-1]<arr[N-2],那么arr[N-1]是局部最小；如果0<i<N-1，既有arr[i] < arr[i-1]，又有arr[i] < arr[i + 1]，那么arr[i]是局部最小。给定无序数组arr,已知arr中任意两个相邻的数都不相等，只需要返回arr中任意一个局部最小出现的位置即可，如果不存在这个位置就输出-1。

importjava.util.*;publicclassMain{publicstaticintoneMinIndex(int[] arr){if(arr ==null|| arr.length ==0){return-1;}if(arr.length ==1){return0;}if(arr[0]< arr[1]){return0;}intN= arr.length;if(arr[N-1]< arr[N-2]){returnN-1;}intL=0;intR=N-1;int ans =-1;while(L<=R){int mid =(L+R)/2;if(arr[mid]< arr[mid-1]&& arr[mid]< arr[mid+1]){
                ans = mid;break;}if(arr[mid]> arr[mid-1]){R= mid -1;continue;}if(arr[mid]> arr[mid+1]){L= mid +1;continue;}}return ans;}publicstaticvoidmain(String[] args){Scanner scanner =newScanner(System.in);int n = scanner.nextInt();int[] arr =newint[n];while(scanner.hasNextInt()){for(int i =0;i < n;i++){
            arr[i]= scanner.nextInt();}}System.out.println(oneMinIndex(arr));}}

四、 三个数的最大乘积

给定一个长度为 nn 的无序数组 AA ，包含正数、负数和 0 ，请从中找出 3 个数，使得乘积最大，返回这个乘积。

我们先对数组进行排序，然后就上面两个情况的数的大小，因为数组是升序的，从小到大，最大的两个负数乘积就在数组的最前面，最大的三个正数就在数组的最后面，比较两个数即可。

1. 没有正数，当然负数越小乘积越大，即排序后数组的最后三个数，零大于负数
2. 没有负数，数越大乘积越大，即排序后数组的最后三个数
3. 一个负数，排序后的最后三个数乘积最大
4. 一个正数，即开头的第一个情况。

publiclong solve (int[]A){Arrays.sort(A);int n =A.length -1;returnMath.max((long)A[n]*A[n-1]*A[n-2],(long)A[0]*A[1]*A[n]);}

三、 阶乘累加

计算1！+2！+3！……+n！
方法1：暴力求解

publicstaticlongf1(int n){long ans =0;for(int i =1; i <= n; i++){
            ans +=factorial(i);}return ans;}publicstaticlongfactorial(int n){long ans =1;for(int i =1; i <= n; i++){
            ans *= i;}return ans;}publicstaticvoidmain(String[] args){//求阶乘之和Scanner scanner =newScanner(System.in);int n = scanner.nextInt();System.out.println(f1(n));}

方法二:迭代法

publicstaticlongf2(int n){long ans =0;long ret =1;for(int i =1; i <= n; i++){
            ret *= i;
            ans += ret;}return ans;}publicstaticvoidmain(String[] args){//求阶乘之和Scanner scanner =newScanner(System.in);int n = scanner.nextInt();System.out.println(f2(n));}