多对一算法问题

0 0

多对一算法问题25

boolean isMatch(double[]array,double target){
}

match的规则是，先在array里面找，有没有一个元素array[i]==target,如果有则返回true，如果没有，继续找有没有任意两个元素相加==target,即array[i]+array[j]==target;如果还是没有继续找有没有任意三个元素相加==target,以此类推，只到array.length()个相加能不能==target为止，最终如果还是没找到，则返回false.

问题补充：

kidding87 写道

楼主换了个分多的号来了。。。
那个我觉得应该用深度搜索来解吧，你这个直接限定死了

能讲的具体些吗？

问题补充：

kidding87 写道

数组先排序~
例子：[1,2,5,6,7,10,12,15,20,23,24,26,29] 50
循环取1、2。。。、29
开始从深度挖掘取1 ，剩余49 寻找最接近49的数 29剩余 20 ok找到20 然后后退看有没有能代理20的找15 剩余5 找到5，在用12 。。。
基本就是过程
1 29 20
1 29 15 5
1 29 12 6 2
1 29 10 就不行了然后 pop 29
1 26 23
。。。。
思路有点乱，利用堆栈~

好吧，我先试试，看代码能不能写出来

问题补充：

kidding87 写道

哥，小弟愚钝，代码写不出来，赐教

问题补充：

kidding87 写道

 /**
     * match(深度匹配，参数：数组n[],查询值t,截止位置end,查询记录栈stack,深度deep)
     * MyStack 以LinkedList为基础的stack简单的pop push操作，重写toString 使用list.toString()
    */
    public static void match(int[]n,int t,int end,MyStack stack,int deep){
        for(int i=leftApproachT(n, t,end);i>=0;i--){
          int temp=t-n[i];
          int temp2 =deep;
          stack.push(n[i]);
            if(temp>0) {
                match(n, temp,i,stack,temp2++);
            }
            else if(temp==0){
                System.out.println(stack);
                }
            //将不需要的数据出栈
            for(int j=deep;j>=0;j--)
                stack.pop();
        }
    }
    /**
     * leftApproachT(从左开始查询最接近t的值所在数组n中对应的位置)
    */
    public static int leftApproachT(int[]n,int t,int end){
      for(int i=0;i<end;i++){
          if(n[i]>t) return i-1;
      }
      return end-1;
    }

判断出来没什么难度，把结果也都打出来

谢谢！！！能找出来，但是数量稍微多一点的时候，效率一下降低了，而且容易outOfMemory！

问题补充：

kidding87 写道

我刚试过了，oom没有遇到，你看看把MyStack直接用linkedList，查询的结果集确实非常大

int[] n = { 1, 2, 5, 6, 7, 10, 12, 15, 20, 23, 24, 26, 29,30,31,33,40,55,59,66,88
,100,111,123,140,150,180,200,211,222,332,332,400,451,900,1223,2203,2234,5552};
int t=6000;
效率我觉得还是比较高的，一秒钟差不多10W条数据吧
这个结果集至少超过10G。。。

我试验了用100条数据去跑，跑了几个小时了也没跑出结果，不过100条数据的组合确实比较多

public static void main(String[] args) {
		long start = System.currentTimeMillis();
		Random ran = new Random();
		int[] a = new int[100];
		for (int i = 0; i < a.length; i++) {
			a[i] = ran.nextInt(1000);
		}
		Arrays.sort(a);
		match(a, 5000, a.length, new LinkedList(), 0);
		System.out.print(count);
		long time = System.currentTimeMillis() - start;
		System.out.println(time/1000);
	}

问题补充：

kidding87 写道

不过我跑100条是指找出所有的情况，你一秒钟差不多10W条数据是什么个情况

算法多对一

2012年1月31日 09:19

jshen3
5
0 0 0

12个答案按时间排序按投票排序

0 0

采纳的答案

 /**
     * match(深度匹配，参数：数组n[],查询值t,截止位置end,查询记录栈stack,深度deep)
     * MyStack 以LinkedList为基础的stack简单的pop push操作，重写toString 使用list.toString()
    */
    public static void match(int[]n,int t,int end,MyStack stack,int deep){
        for(int i=leftApproachT(n, t,end);i>=0;i--){
          int temp=t-n[i];
          int temp2 =deep;
          stack.push(n[i]);
            if(temp>0) {
                match(n, temp,i,stack,temp2++);
            }
            else if(temp==0){
                System.out.println(stack);
                }
            //将不需要的数据出栈
            for(int j=deep;j>=0;j--)
                stack.pop();
        }
    }
    /**
     * leftApproachT(从左开始查询最接近t的值所在数组n中对应的位置)
    */
    public static int leftApproachT(int[]n,int t,int end){
      for(int i=0;i<end;i++){
          if(n[i]>t) return i-1;
      }
      return end-1;
    }

判断出来没什么难度，把结果也都打出来

2012年2月02日 13:55

kidding87
1566
1 1 19

添加评论

0 0

拿楼主给的例子，我用流将结果集写出，1个小时差不多写了10G
总的结果集大小我估计比50G大的多，这么大的结果集，想比较短的时间算出来基本不可能

2012年2月06日 14:32

kidding87
1566
1 1 19

添加评论

0 0

2012年2月06日 11:23

kidding87
1566
1 1 19

添加评论

0 0

public class Test {

	private static int count = 0;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = { 1, 2, 5, 6, 7, 10, 12, 15, 20, 23, 24, 26, 29 };
		System.out.print(isMatch(a, 50));
	}

	public static boolean isMatch(int[] array, int target) {
		Arrays.sort(array);
		LinkedList<Integer> stack = new LinkedList<Integer>();
		findMatch(array, 0, target, stack);
		return count > 0;
	}

	public static void findMatch(int[] array, int start, int target,
			LinkedList<Integer> stack) {
		for (int i = start; i < array.length; i++) {
			if (array[i] == target) {
				stack.push(array[i]);
				printStack(stack);
				count++;
				stack.pop();
			} else if (array[i] < target) {
				stack.push(array[i]);
				findMatch(array, i + 1, target - array[i], stack);
				stack.pop();
			} else {
				return;
			}
		}

	}

	public static void printStack(List<Integer> stack) {
		System.out.print("find a solution: ");
		for (int i : stack) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

}

find a solution: 29 7 6 5 2 1
find a solution: 26 10 6 5 2 1
find a solution: 24 12 6 5 2 1
find a solution: 23 12 7 5 2 1
find a solution: 20 15 7 5 2 1
find a solution: 20 12 10 5 2 1
find a solution: 24 10 7 6 2 1
find a solution: 29 12 6 2 1
find a solution: 26 15 6 2 1
find a solution: 20 15 12 2 1
find a solution: 24 23 2 1
find a solution: 26 12 6 5 1
find a solution: 23 15 6 5 1
find a solution: 15 12 10 7 5 1
find a solution: 29 15 5 1
find a solution: 24 20 5 1
find a solution: 26 10 7 6 1
find a solution: 24 12 7 6 1
find a solution: 23 20 6 1
find a solution: 20 12 10 7 1
find a solution: 24 15 10 1
find a solution: 29 20 1
find a solution: 26 23 1
find a solution: 20 10 7 6 5 2
find a solution: 15 12 10 6 5 2
find a solution: 26 10 7 5 2
find a solution: 24 12 7 5 2
find a solution: 23 20 5 2
find a solution: 23 12 7 6 2
find a solution: 20 15 7 6 2
find a solution: 20 12 10 6 2
find a solution: 29 12 7 2
find a solution: 26 15 7 2
find a solution: 26 12 10 2
find a solution: 23 15 10 2
find a solution: 20 12 7 6 5
find a solution: 29 10 6 5
find a solution: 24 15 6 5
find a solution: 26 12 7 5
find a solution: 23 15 7 5
find a solution: 23 12 10 5
find a solution: 20 15 10 5
find a solution: 15 12 10 7 6
find a solution: 29 15 6
find a solution: 24 20 6
find a solution: 23 20 7
find a solution: 23 15 12
find a solution: 26 24
true

2012年2月02日 15:27

hubeen
37
0 0 0

添加评论

0 0

public static void match(int[]n,int t){
        for(int i=leftApproachT(n, t);i>=0;i--){
          int temp=t-n[i];
            if(temp>0) {
                match(n, temp);
            }
            else if(temp==0){System.out.println("find");}
        }
    }
    public static int leftApproachT(int[]n,int t){
        for(int i=0;i<n.length;i++){
            if(n[i]>t) return i-1;
        }
        return n.length-1;
    }

2012年2月02日 10:51

kidding87
1566
1 1 19

添加评论

0 0

上面的只是一种思路，不保证代码可运行，以及效率

2012年2月02日 10:40

buptwhisper
60
0 0 1

添加评论

0 0

反过来想，不是拆整数，用拆数组的办法试试

提供思路如下：
假设数组为a0, a1, a2,..., an-1, an,要匹配的数为M
采用下法来判断：

if an == M, 这时候当然找到了，返回true
如果不匹配，那么再check a0, a1, a2, ..., an-1 这个子数组与 M 或者 M - an是否匹配，如果匹配，就返回true，否则返回false；当然我没考虑效率哈。

boolean isMatch(double[]array,double target){  

  return isMatch(array, target, array==null?0:array.length());
} 

boolean isMatch(double[]array,double target, int index){
  if(array == null || array.length() < index + 1 || index < 0){
     return false;
  }

  if(array[index] == target){
     return true;
  }
  return isMatch(array, target, index - 1) || 
  return isMatch(array, target - array[index], index - 1);
}

2012年2月02日 10:38

buptwhisper
60
0 0 1