30
回答
一道面试题,求解。
利用AWS快速构建适用于生产的无服务器应用程序,免费试用12个月>>>   

从1到19,共19个整数,请打印出利用这19个整数任意多个相加结果等于20的所有可能性,每个数字在 同一个算式中只能出现一次。
如:
1+19
1+2+17
1+2+3+14
1+2+3+4+10
........................
3+4+6+7
3+5+12  

<无标签>
举报
yujigemu
发帖于7年前 30回/1K+阅
共有30个答案 最后回答: 7年前

import java.util.ArrayList;

import java.util.List;

public class test2 {

public static int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 };

public static List<String> createString(int nums) {  

        StringBuilder stringBuilder = new StringBuilder(nums + "+");  

        List<String> results = new ArrayList<String>();  

        for (int i = 0; i < numbers.length; i++) {  

         int   temp = 20 - nums;  

            for (int j = i; j < numbers.length; j++) {  

                if (temp - numbers[j] > 0)//大于零说明可以继续加

                {  

                 stringBuilder.append(numbers[j] + "+");  

                    temp = temp - numbers[j];  

                } 

                else if (temp - numbers[j] == 0)//等于0就是没了

                { 

                 stringBuilder.append(numbers[j] + "");  

                    temp = temp - numbers[j];  

                    results.add(stringBuilder.toString());

                    stringBuilder = new StringBuilder(nums + "+");  

                    break;  

                } 

                else

                {  

                    if (j < numbers.length)  

                    stringBuilder = new StringBuilder(nums + "+");  

                    continue;  

                }  

            }  

        }  

        return results;  

    }  

    public static void run() {  

        List<String> allExpressions = new ArrayList<String>();  

        for (int j = 0; j < numbers.length; j++) {  

            List<String> list = test2.createString(numbers[j]);  

            allExpressions.addAll(list);  

        }  

        for (int i = 0; i < allExpressions.size(); i++) {  

            System.out.println(allExpressions.get(i));  

        }  

    }  

public static void main(String[] args) {

// TODO Auto-generated method stub

run();  

}

}

  def enumerate(a: Int, b: Int, c: Int): Unit = {
    if (a + b + c == 20 && a < b && b < c) {
      println(a + "+" + b + "+" + c)
      if (b < c - 2) enumerate(a, b + 1, c - 1)
      else if (3 * a < 15) enumerate(a + 1, a + 2, 17 - 2 * a)
    }
  }

24种可能,通过enumerate(1,2,17)开始调用

total=20;

int numbers=int((sqrt(total)-1)/2); //estimate the  digits array number
new int digArray(numbers);

inline IsExpable(digmin,digmax){    //if the rest digit is expandable
        if int((digmax-1)/2)>digmin){ return 1};
        return 0;
}

digArray(0)=1;
digArray(1)=total-digArray(0);
int printindex=0;
int numindex=1;

while(digArray(0)<digArray(1)){
          numindex=1;
          while (IsExpable(digArray(numindex-1),digArray(numindex))==1){  //totally expand the number in order
                        digArray(numindex+1)=digArray(numindex)-digArray(numindex-1)-1;
                        digArray(numindex)=digArray(numindex-1)+1;
                         numindex++;
           }
 
          printindex=numindex;
 
         while(printindex>1){   //print the digits by accumulating the rear part of the array
                       printArray(digArray,printindex);
                       digArray(printindex-1)=digArray(printindex-1)+digArray(printindex);
                       printindex--;
         }
 
          digArray(0)++;        //increase the minmum digit
          digArray(1)=total-digArray(0)
}

delete digArray;
 

引用来自#6楼“屁屁果”的帖子

63,手机不好弄,睡觉了

public class TestMain {
	static Long count = 0L;
	static final int _int = 20;
	public static void main(String[] args) {
			//min=1, sum= _int , sum=min+max   max=?,调用计算方法
			getInt(1, _int, _int + " ");
		System.out.println("总共 :" + count + " ");
	}
	static void getInt(int min, int sum, String str) {
		if (min >= sum)
			return;
		// 求出最大值
		int max = sum - min;
			while (min <max ) {// max必须比min大,最小值只有一个!!!!
				String str1 = str.replace(sum + "", min + "+" + max);
				System.out.println(_int + "=" + str1);
				count++;// 计数器
				//调用递归,把最小值+1,分解最大值
				getInt(min+1, max, str1);
				min++;//,最小值每次加1, 1+19 将会出现 2+18,19会分解成2+17, 2+17将会出现3+16依次类推,直到求出里最大的最小值
				max--;//最大值每次减 1
			}
	}

}

贴上代码,结果是 63种情况

引用来自#8楼“屁屁果”的帖子

引用来自#6楼“屁屁果”的帖子

63,手机不好弄,睡觉了

public class TestMain {
	static Long count = 0L;
	static final int _int = 20;
	public static void main(String[] args) {
			//min=1, sum= _int , sum=min+max   max=?,调用计算方法
			getInt(1, _int, _int + " ");
		System.out.println("总共 :" + count + " ");
	}
	static void getInt(int min, int sum, String str) {
		if (min >= sum)
			return;
		// 求出最大值
		int max = sum - min;
			while (min <max ) {// max必须比min大,最小值只有一个!!!!
				String str1 = str.replace(sum + "", min + "+" + max);
				System.out.println(_int + "=" + str1);
				count++;// 计数器
				//调用递归,把最小值+1,分解最大值
				getInt(min+1, max, str1);
				min++;//,最小值每次加1, 1+19 将会出现 2+18,19会分解成2+17, 2+17将会出现3+16依次类推,直到求出里最大的最小值
				max--;//最大值每次减 1
			}
	}

}

贴上代码,结果是 63种情况

递归的效率太低了

不知道有没有什么好方法

顶部