个人主页:熬夜磕代码丶
作品专栏: java se
我变秃了,也变强了
给大家介绍一款程序员必备刷题平台——牛客网
点击注册一起刷题收获大厂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。
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 个数,使得乘积最大,返回这个乘积。
我们先对数组进行排序,然后就上面两个情况的数的大小,因为数组是升序的,从小到大,最大的两个负数乘积就在数组的最前面,最大的三个正数就在数组的最后面,比较两个数即可。
- 没有正数,当然负数越小乘积越大,即排序后数组的最后三个数,零大于负数
- 没有负数,数越大乘积越大,即排序后数组的最后三个数
- 一个负数,排序后的最后三个数乘积最大
- 一个正数,即开头的第一个情况。
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));
}
相关文章
暂无评论...