牛客网刷题——斩获offer

蔚落 2023-09-28 21:31 16阅读 0赞

![在这里插入图片描述][36eb29614ae640788a61d0dff3d77580.gif_pic_center]

>  个人主页：[熬夜磕代码丶][Link 1]  
>  作品专栏: [java se][]  
>  我变秃了，也变强了  
> 给大家介绍一款程序员必备刷题平台——牛客网  
> [点击注册一起刷题收获大厂offer吧][offer]  
> ![在这里插入图片描述][93dcd6e82b1e476b860895df59e8b213.png]

#### 文章目录 ####

*  一、 随机数组
 *  二、 局部最小值
 *  四、 三个数的最大乘积
 *  三、 阶乘累加

## 一、 随机数组 ##

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

public static int[] randomArray(int maxLen,int maxValue) {
        
            int Len = (int)(Math.random() * maxLen);
            int[] arr = new int[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。  
![在这里插入图片描述][3b5471d4c55b466f9623d7764f22094b.png]  
![在这里插入图片描述][cabc4b1bd6b045b4bd302431eba7068c.png]

import java.util.*;
    public class Main{
        
        public static int oneMinIndex(int[] arr) {
        
            if(arr == null || arr.length == 0) {
        
                return -1;
            }
            if(arr.length == 1) {
        
                return 0;
            }
    
            if(arr[0] < arr[1]) {
        
                return 0;
            }
            int N = arr.length;
            if(arr[N-1] < arr[N-2]) {
        
                return N-1;
            }
            int L = 0;
            int R = 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;
        }
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            int[] arr = new int[n];
            while(scanner.hasNextInt())
            {
        
                for(int i = 0;i < n;i++) {
        
                arr[i] = scanner.nextInt();
            }
            }
            System.out.println(oneMinIndex(arr));
        }
    }

## 四、 三个数的最大乘积 ##

给定一个长度为 nn 的无序数组 AA ，包含正数、负数和 0 ，请从中找出 3 个数，使得乘积最大，返回这个乘积。  
![在这里插入图片描述][c8c058bca1054e1a816456a5b389ce45.png]  
我们先对数组进行排序，然后就上面两个情况的数的大小，因为数组是升序的，从小到大，最大的两个负数乘积就在数组的最前面，最大的三个正数就在数组的最后面，比较两个数即可。

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

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

## 三、 阶乘累加 ##

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

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

**方法二:迭代法**

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

[36eb29614ae640788a61d0dff3d77580.gif_pic_center]: https://img-blog.csdnimg.cn/36eb29614ae640788a61d0dff3d77580.gif#pic_center
[Link 1]: https://blog.csdn.net/buhuisuanfa?spm=1018.2226.3001.5343
[java se]: https://blog.csdn.net/buhuisuanfa/category_11932688.html?spm=1001.2014.3001.5482
[offer]: https://www.nowcoder.com/link/pc_csdncpt_bhsf_jzsf
[93dcd6e82b1e476b860895df59e8b213.png]: https://img-blog.csdnimg.cn/93dcd6e82b1e476b860895df59e8b213.png
[3b5471d4c55b466f9623d7764f22094b.png]: https://img-blog.csdnimg.cn/3b5471d4c55b466f9623d7764f22094b.png
[cabc4b1bd6b045b4bd302431eba7068c.png]: https://img-blog.csdnimg.cn/cabc4b1bd6b045b4bd302431eba7068c.png
[c8c058bca1054e1a816456a5b389ce45.png]: https://img-blog.csdnimg.cn/c8c058bca1054e1a816456a5b389ce45.png