首页 > 代码库 > Java实现三角形计数
Java实现三角形计数
题：
解：
这道题考的是穷举的算法。
一开始看到这道题的时候，本能的想到用递归实现。但使用递归的话数据少没问题，数据多了之后会抛栈溢出的异常。我查了一下，原因是使用递归创建了太多的变量，
每个变量创建的时候都会有一个“栈帧”，而Java虚拟机对栈帧有限制，不能超出一个范围。
并且递归和循环相比，递归的效率明显比循环低下，如果想要写一个算法的话，尽量不要使用递归，一方面是因为递归会创建很多变量，占用内存，另一方面是递归极容
易无限递归。
---------------
最后使用循环嵌套的方式完成了。
代码：
1 package com.lintcode; 2 3 /** 4 * 三角形计数 5 * 给定一个整数数组，在该数组中，寻找三个数，分别代表三角形三条边的长度， 6 * 问，可以寻找到多少组这样的三个数来组成三角形？ 7 * @author Administrator 8 */ 9 public class Test_003 {10 // 这道题不能用递归，数据少的话还可以，但是多了就会堆栈溢出。11 // 这道题就是考“穷举”，列出所有的可能性，再判断。三角形三个边需要三个数字，就循环嵌套三层。12 // 然后找出三个数字中最大的和最小的和中间数，判断是否构成三角形。13 /**14 * @param args15 */16 public static void main(String[] args) {17 int[] S = new int[200];18 for (int i = 0; i < 200; i++) {19 S[i] = i+1;20 }21 int count = triangleCount(S);22 System.out.println(count);23 }24 25 public static int triangleCount(int S[]) {26 int count = 0;27 for(int i=0; i<S.length-2; i++){//第一条边28 for (int j = i+1; j < S.length-1; j++) {//第二条边29 for (int k = j+1; k < S.length; k++) {//第三条边30 int min = getMin(S[i],S[j],S[k]);31 int max = getMax(S[i],S[j],S[k]);32 int middle = S[i]+S[j]+S[k]-min-max;33 if ((min+middle)>max || (min==max)) {34 count++;35 }36 }37 }38 }39 return count;40 }41 //求最小值42 private static int getMin(int a, int b, int c) {43 int min = a;44 if (min>b) {45 min=b;46 }47 if (min>c) {48 min=c;49 }50 return min;51 }52 //求最大值53 private static int getMax(int a, int b, int c) {54 int max = a;55 if (max<b) {56 max=b;57 }58 if (max<c) {59 max=c;60 }61 return max;62 }63 }
Java实现三角形计数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。