遇到一个测试题，有没有大佬能够帮忙优化解决呀？

//爱德华有1个包含N个整数的数组A，他定义1个数组的美丽值为数组中所有不同整数的和。现在爱德华想知道数组A的所有连续子序列的美丽值之和。
//楼主很笨，用了一个很傻的方法，每次都遍历一遍，时间复杂度都达到O（N^4）了，能不能帮助楼主想个好办法呢？
//测试用例：
//1, 1, 2 => 11
//1, 2 => 6
//1，2，3，3 => 37

package 测试;

public class Test1 {

public static void main(String[] args) {
int arr[] = { 1,1,3,3 };
System.out.println(beauty_of_array(arr));
}

/*
* 实现代码：Java
* 该函数用于计算数组中所有连续子序列的美丽值之和
*/
private static int beauty_of_array(int[] array) {
// 数组的长度
int length = array.length;
// 如果输入的数组不合法，返回0，表示没有美丽值
if (array == null || length <= 0)
return 0;

// 用于统计美丽值的总和
int beautyValue = 0;

// 统计所有可能存在的子序列的和
while (length > 0) {
beautyValue = beauty_of_array(array, length);
length--;
}
return beautyValue;
}

/*
* 该函数用于统计连续的n个数作为一个子序列可得到的美丽值之和
*/
private static int beauty_of_array(int array[], int count) {
// 如果已经把所有的子串都统计完毕，则不用再进行递归，返回0退出
if (count <= 0)
return 0;

// 用于记录美丽值
int beautyValue = 0;
// 用于存放数组的长度
int length = array.length;
// 用于储存子串的数量
int num = length - count 1;
// 循环时的计数器
int i = 0, j = 0, k = 1;
// 用于记录当前子串是否存在相同的其他子串
boolean exsist = false;

// 计算子序列个数为count的所有不重复子序列的和
for (i = 0; i < num; i ) {
exsist=false;
// 检查数组中是否存在相同的子串
for (j = 0; j < num; j ) {
k = 0;
if (array[j] == array[i] && j != i) {
k = 1;
while (k < count && array[j k] == array[i k])
k ;
}
//如果存在一个相同的子序列，令exsisit为空，跳出检查循环进行下一个子序列的判断
if (k == count) {
exsist = true;
break;
}
}

// 如果子串并没有出现过，则相加
if (!exsist) {
beautyValue = getBeautyValue(array, count, i);
}
}
return beautyValue;
}
/*
* 获取下标从startPos开始往后count个数字的和
* */
private static int getBeautyValue(int[] array, int count, int startPos) {
int value=0;
for(int i=startPos;i<startPos count;i )
value =array[i];

return value;
}
}

#测试#

全部评论

推荐最新楼层

五楼

Java

如果是你的测试用例错了的话我按照一楼老哥的思路写了个 import java.util.*; public class Qujian { public static void main(String[] args){ Scanner sc=new Scanner(System.in); while (sc.hasNext()) { String input=sc.nextLine(); String[] numString=input.trim().split("\\s+"); int[] nums=new int[numString.length]; for(int i=0;i<nums.length;i++) nums[i]=Integer.valueOf(numString[i]); int sum=0; for(int i=0;i<nums.length;i++){ sum=sum+countOne(nums,i); } System.out.println(sum); } } public static int countOne(int[] nums,int index){ int now=nums[index]; int temp=index; while((index-1)>=0){ if(nums[index-1]==now) break; index--; } return (temp-index+1)*(nums.length-temp)*now; } }

遇到一个测试题，有没有大佬能够帮忙优化解决呀？

全站热榜