题:
解:
这道题考的是穷举的算法。
一开始看到这道题的时候,本能的想到用递归实现。但使用递归的话数据少没问题,数据多了之后会抛栈溢出的异常。我查了一下,原因是使用递归创建了太多的变量,
每个变量创建的时候都会有一个“栈帧”,而Java虚拟机对栈帧有限制,不能超出一个范围。
并且递归和循环相比,递归的效率明显比循环低下,如果想要写一个算法的话,尽量不要使用递归,一方面是因为递归会创建很多变量,占用内存,另一方面是递归极容
易无限递归。
---------------
最后使用循环嵌套的方式完成了。
代码:
package com.lintcode; /**
* 三角形计数
* 给定一个整数数组,在该数组中,寻找三个数,分别代表三角形三条边的长度,
* 问,可以寻找到多少组这样的三个数来组成三角形?
* @author Administrator
*/
public class Test_003 {
// 这道题不能用递归,数据少的话还可以,但是多了就会堆栈溢出。
// 这道题就是考“穷举”,列出所有的可能性,再判断。三角形三个边需要三个数字,就循环嵌套三层。
// 然后找出三个数字中最大的和最小的和中间数,判断是否构成三角形。
/**
* @param args
*/
public static void main(String[] args) {
int[] S = new int[200];
for (int i = 0; i < 200; i++) {
S[i] = i+1;
}
int count = triangleCount(S);
System.out.println(count);
} public static int triangleCount(int S[]) {
int count = 0;
for(int i=0; i<S.length-2; i++){//第一条边
for (int j = i+1; j < S.length-1; j++) {//第二条边
for (int k = j+1; k < S.length; k++) {//第三条边
int min = getMin(S[i],S[j],S[k]);
int max = getMax(S[i],S[j],S[k]);
int middle = S[i]+S[j]+S[k]-min-max;
if ((min+middle)>max || (min==max)) {
count++;
}
}
}
}
return count;
}
//求最小值
private static int getMin(int a, int b, int c) {
int min = a;
if (min>b) {
min=b;
}
if (min>c) {
min=c;
}
return min;
}
//求最大值
private static int getMax(int a, int b, int c) {
int max = a;
if (max<b) {
max=b;
}
if (max<c) {
max=c;
}
return max;
}
}