阿里第一题有人讨论下吗(虽然笔试gg但算法不能停)

public static void main(String[]args){
    Scanner in = new Scanner(System.in);  int N = in.nextInt();    ArrayList<Integer>list = new ArrayList<>();  while (N-- > 0){
        list.add(in.nextInt());    }
    System.out.println(fun(list)); } public static int fun(ArrayList<Integer>list){  if(list.size() < 3){  return 0;    }  int res = 0;  for(int i = 1;i < list.size()-1;i++){  for(int j = i+1 ; j < list.size(); j++){  double a = list.get(0),b = list.get(i),c = list.get(j);  boolean flag ;   if(b-a== c-b||c/b == b/a){
                flag = b-a == c-b?true:false; //标记等差或等比    double index = flag?(b-a):(b/a); //比值或差值     ArrayList<Integer>temp = (ArrayList<Integer>)list.clone();   //找出j位置后符合条件的值    for(int k = j+1 ; k < temp.size(); ){  int x = temp.get(k);  if((flag&&x-c==index)||(!flag && x/c==index)) { //等差或等比    c = x; //更新最后一个位置的值    temp.remove(k);  }  else{
                        k++;    }
                }

                temp.remove(0);temp.remove(i-1);temp.remove(j-2);    //a,b,c三个值不进入下层递归  if(temp.size() == 0){
                    res += list.size()/3;    }else {
                    res += (list.size()-temp.size())/3*fun(temp); //递归剩下的数组    }
            }else continue;  }
    }  return res; }


全部评论
这样递归会超时啊,10000的排列太大了
点赞 回复 分享
发布于 2018-09-09 11:46
已知正整数数组A,记为{a(1),a(2),a(3),a(4) ...... a(n) ......}, 数组中任一元素大小不超过10000,任意两个元素互不相同。 现在按照以下规则尝试将数组A拆分成若干个(一个或者多个)子数组: A中任意一个元素a(n)必然出现于某个子数组中,且无论是子数组之间还是子数组内元素均不重复出现。 对于任意一个子数组B,记为{b(1),b(2),b(3),b(4) ...... b(n) ......},B中任一元素b(i),b(i)在数组A中对应的下标小于b(i+1)在数组A中对应的下标。(如果b(i+1)存在的话) 对于任意一个子数组,数组长度大于等于3,同时其值按照子数组中的顺序构成一个等比或者等差数列。 问题: 求数组A符合以上条件拆分有多少种可能的组合,如不存在则返回0。 以数组 [ 1 2 3 4 5 6 ] 为例其可能的拆分为: [ 1 2 3 ] [ 4 5 6 ] [ 1 2 3 4 5 6 ] [ 1 3 5 ] [ 2 4 6 ] 则其可能的组合数为3. 以数组 [ 1 2 4 3 5 ] 为例则不存在这样的拆分, 其可能的组合数为0
点赞 回复 分享
发布于 2018-09-07 21:18
题目是什么
点赞 回复 分享
发布于 2018-09-07 21:04

相关推荐

06-12 16:23
已编辑
小米_软件开发(准入职员工)
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务