一、问题描述
给定一个包含正数，负数和零的无序数组，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)
package com.pdd;
import java.util.Scanner;
public class Demo1 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
long [] arr=new long[n];
//给数组赋值
for(int i=0;i<n;i++) {
arr[i]=sc.nextLong();
}
//新建一个函数，查找最大值
System.out.println(getMaxMul(arr));
}
private static long getMaxMul(long[] arr) {
int n=arr.length;
//找出最大的max1，max2，max3 和最小的min1,min2
long max1=0;
long max2=0;
long max3=0;
long min1=0;
long min2=0;
for(int i=0;i<n;i++) {
if (arr[i]>max1) {
max3=max2;
max2=max1;
max1=arr[i];
}else if (arr[i]>max2) {
max3=max2;
max2=arr[i];
}else if (arr[i]>max3) {
max3=arr[i];
}
if (arr[i]<min1) {
min2=min1;
min1=arr[i];
}else if (arr[i]<min2) {
min2=arr[i];
}
}
return (max1*max2*max3)>(max1*min1*min2)?(max1*max2*max3):(max1*min1*min2);
}
}
二、问题描述
有两个用字符串表示的非常大的大整数,算出他们的乘积，也是用字符串表示。不能用系统自带的大整数类型
package com.pdd;
import java.util.Scanner;
public class Demo2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str1 = sc.next();
String str2 = sc.next();
String res;
if (str1 == null || str2 == null) {
res=null;
}
if (str1.charAt(0)=='0'||str2.charAt(0)=='0') {
res=""+'0';
}
res= multiply(str1,str2);
System.out.println(res);
}
private static String multiply(String str1, String str2) {
//1.将字符串反转
String num1=new StringBuffer(str1).reverse().toString();
String num2=new StringBuffer(str2).reverse().toString();
int n1Length=num1.length();
int n2Length=num2.length();
//2.建立一个数组保存结果，该结果最长为n1Length+n2Length
int [] arr=new int [n1Length+n2Length];
for(int i=0;i<n1Length;i++) {
for(int j=0;j<n2Length;j++) {
arr[i+j]+=(num1.charAt(i)-'0')*(num2.charAt(j)-'0');
}
}
StringBuffer sBuffer=new StringBuffer();
for(int i=0;i<arr.length;i++) {
int curBit=arr[i]%10;
int postCur=arr[i]/10;
if (i+1<arr.length) {
arr[i+1]+=postCur;
}
sBuffer.insert(i, curBit);
}
if (sBuffer.reverse().charAt(0)=='0') {
sBuffer.deleteCharAt(0);
}
return sBuffer.toString();
}
}
三、问题描述
给定一个数组 A[1....N] ，如何快速创建一个数组B[1...N]，时间复杂度要求在 O(n);A[1....N] -> B[1....N]的规则如下：
B[i] = A[1]*A[2]....A[N]/A[i]; 要求不使用除法
算法：两次扫描数组 ， 一次从前往后扫描，一次从后往前扫描
一次扫描: 从前往后
P[1] = 1;
P[i] = P[i-1] * A[i-1];
........ i>=2 && i=<N
二次扫描: 从后往前
Q[N] = 1;
Q[i] = Q[i+1] * A[i+1];
.....
( i>=1 i < N )
B[i] = P[i] + Q[i];
using namespace std;
int A[5] = {1,2,3,4,5};
int B[5],P[5],Q[5] ;
int main()
{
int i=1;
int j=3;
P[0] = 1;
Q[4] = 1;
for(;i<5&&j>=0;i++,j--)
{
P[i] = P[i-1]*A[i-1];
Q[j] = Q[j+1]*A[j+1];
}
for(i=0;i<5;i++)
{
B[i] = P[i]*Q[i];
cout<<B[i]<<" ";
}
cout<<endl;
return 0;
}
如果你是准大二，大三，研一，研二
你也想进击互联网名企，
8月8号西部开源名企直通课，我们等你。
如果你即将大四或研三，遇事不要慌，
8月8号西开报个班，优质offer等你拿
