牛客网刷题——斩获offer

牛客网刷题——斩获offer

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

文章目录

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

一、 随机数组

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

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。
牛客网刷题——斩获offer
牛客网刷题——斩获offer

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 个数,使得乘积最大,返回这个乘积。
牛客网刷题——斩获offer
我们先对数组进行排序,然后就上面两个情况的数的大小,因为数组是升序的,从小到大,最大的两个负数乘积就在数组的最前面,最大的三个正数就在数组的最后面,比较两个数即可。

  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));
    }

版权声明:程序员胖胖胖虎阿 发表于 2022年9月1日 上午3:08。
转载请注明:牛客网刷题——斩获offer | 胖虎的工具箱-编程导航

相关文章

暂无评论

暂无评论...