几道题而已

收集几道题

 

1 ： subset sum problem问题

       问题描述：

There is integer array like {1,2,4,5,6,1,2,4,3,5,7,2,1}. I want to find the possible combination of pair which sum is 4.

There is integer array like {1,2,4,5,6,1,2,4,3,5,7,2,1}. I want to find the possible combination of pair which sum is 4.
input : {1,2,4,5,6,1,2,4,3,5,7,2,1}
output : {1,1,2}, {2,2}, {3,1}, {1,2,1}...etc which make the sum as 4

 

该类型问题的解法见 wiki，比较复杂

http://en.wikipedia.org/wiki/Subset_sum_problem

 

code sample (passed testing) 该解法是暴力法，即递归求出所有可能的组合

 

import java.util.ArrayList;
import java.util.Arrays;

public class Test 
{
    public static void main(String[] args)
    {
        int[] theArray={1,2,4,5,6,1,2,4,3,5,7,2,1};
        ArrayList<ArrayList<Integer>> allpairs=getPairs(theArray,0,4);
        System.out.println(allpairs.size());
        for(ArrayList<Integer> pair:allpairs)
        {
            System.out.println(Arrays.toString(pair.toArray()));
        }
        
        System.out.println("Complete the testing work!");
    }

    public static ArrayList<ArrayList<Integer>> getPairs(int[] theArray, int start, int sum)
    {
    
        if(sum==0)
        {
            ArrayList<ArrayList<Integer>> pairs=new ArrayList<ArrayList<Integer>>();
            ArrayList<Integer> pair=new ArrayList<Integer>();
            pairs.add(pair);
            return pairs;
        }
    
        if(start>=theArray.length)
        {
            return null;
        }
    
        ArrayList<ArrayList<Integer>> pairs=new ArrayList<ArrayList<Integer>>();
        
        //situation 1 include the start element;
        ArrayList<ArrayList<Integer>> subpairs=getPairs(theArray,start+1,sum-theArray[start]);
        if(subpairs!=null)
        {
            for(ArrayList<Integer> subpair:subpairs)
            {
                ArrayList<Integer> pair=new ArrayList<Integer>();
                if(pair!=null)
                {
                    pair.add(theArray[start]);
                    pair.addAll(subpair);
                    pairs.add(pair);
                }
            }
        }
        
        //situation 2 do not include the start element;
        ArrayList<ArrayList<Integer>> otherpairs=getPairs(theArray,start+1,sum);
        if(otherpairs!=null)
        {
            for(ArrayList<Integer> otherpair:otherpairs)
            {
                pairs.add(otherpair);
            }
        }
        return pairs;
    }
}

2：

很多机器，每台机器上都有很一部分数据，如何输出分布在所有机器上的所有数据的median

转化一下，

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

有两个数组，如何求两个数组的中间值？

找到一篇文章，慢慢读之：

http://www.leetcode.com/2011/03/median-of-two-sorted-arrays.html