首页 > 试题广场 >

火柴拼图

[编程题]火柴拼图
  • 热度指数:1101 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
牛妹有n根火柴,她想用这些火柴去拼正三角形或者正四边形。牛妹想让最后拼出的总面积尽可能大的,请你帮帮她。 
返回一个Vector,Vector中存有两个数字。
其中最大面积
示例1

输入

4,[1,1,1,1]

输出

[0,1]

说明

构成一个边长为1的正四边形面积总和最大,值为1。所以Vector[0]=0,Vector[1]=1

备注:
Stick[i]表示第i根火柴的长度,一共有n根火柴 
//多多指教
public class User {
    public static void main(String[] args) {
        int[] arr = {1,1,1,1,1,1,2,2,2,3,1};
        maxArea2(maxArea1(arr.length,arr));
    }
    //统计每个元素有多少个,返回Map
   public static Map<Integer,Integer> maxArea1(int length , int[] arr){
       Map<Integer,Integer> map = new HashMap<>();
       int count = 0 ;
      for (int i = 0 ; i < length ; i++){
          if(map != null && map.get(arr[i]) != null ){
              continue;
          }
          for (int j = i ; j < length ; j++){
              if (arr[i] == arr[j] && arr[i] != 0){
                  count++ ;
              }
          }
          map.put(arr[i],count);
          count = 0 ;
      }
      //无意义,只是打印看看
      for (Integer key:map.keySet()){
          System.out.println(key +"  >>>   "+ map.get(key));
      }
      return map ;
   }
    //返回Vector集合
  static Vector<Integer> maxArea2(Map<Integer,Integer> map){
        Vector<Integer> vector = new Vector();
        int vector0 = 0;//正三角形边长
        int vector1 = 0;//正四边形边长
        for (Integer key:map.keySet()){
            int temp = map.get(key) ;
            //没有判断混合拼接,感觉太过于复杂感觉
           if(temp % 4 == 0 ){
               vector1 += key * temp / 4 ;
           }else if(temp % 3 == 0){
               vector0 += key * temp / 3 ;
           }else if(temp % 4 == 3 ){
                vector0 += 1 ;
                vector1 += key * temp / 4 ;
           }else{
               vector1 += key * temp / 4 ;
           }
        }

        //打印面积
       System.out.print("最大面积为:");
       System.out.println(Math.sqrt(3)/4 * vector0 + vector1 * vector1 );
       //存入集合并返回
      vector.add(vector0);
      vector.add(vector1 * vector1);
       return vector ;
   }

发表于 2020-06-19 00:43:57 回复(0)

问题信息

难度:
2条回答 3708浏览

热门推荐

通过挑战的用户

查看代码