首页 > 试题广场 >

火柴拼图

[编程题]火柴拼图
  • 热度指数: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根火柴 
总算是写出来了,就是凡是数目大于等于4就要先拼正方形;凡是数目对4取余数为3的,就要把余数拿来拼三角形
class Solution:
    def MaxArea(self , n , Stick ):
        # write code here
        # 存放两个输出量,即边长平方
        vector = [0,0]
        # 连三角形都不够拼的
        if n < 3:
            return vector
        # 从大到小按顺序排好,这点很重要
        Stick.sort(reverse = True)
        i = 0
        while i < n:
            # 统计该长度火柴有几根
            numi = Stick.count(Stick[i])
            # 凡是numi>=4就要拼正方形,因为面积大
            # *(numi//4)是关键一点,保证了不足4个的火柴被排除
            vector[1] += (Stick[i]**2) * (numi//4)
            # 拼完正方形剩3根的,或本身就只有3根,拿来拼三角形
            if numi%4 == 3:
                vector[0] += Stick[i] ** 2
            # 下一个数
            i += numi
        return vector


发表于 2021-09-29 15:24:59 回复(0)
11
import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 n
     * @param Stick int整型一维数组 Stick
     * @return long长整型一维数组
     */
    public long[] MaxArea (int n, int[] Stick) {
        // write code here
        long[] res = new long[2];
        //  先找到最大长度
        int maxLength = 0;
        for (int i=0; i< n;i++){
            maxLength = Math.max(maxLength,Stick[i]);
        }
        //  使用计数,对数量进行计数, 0~maxLength
        int[] count = new int[maxLength + 1];
        for (int i=0; i<n;i++){
            count[Stick[i]]++;
        }

        for (int j = 1; j<= maxLength;j++){
                //   优先拼接四边形,因为面积总是更大。使用while循环拼接出所有的四边形
            while (count[j] >= 4){
                res[1] += (long) j*j;
                count[j] -=4;
            }
               //  拼接三角形
            if (count[j] == 3){
                res[0] += (long)j*j;
                count[j] -=3;
            }
        }
        return res;
    }
}


发表于 2020-08-19 14:59:29 回复(0)
i*i那里要转Long,不然无法通过
import java.util.*;


public class Solution {
    /**
     *
     * @param n int整型 n
     * @param Stick int整型一维数组 Stick
     * @return long长整型一维数组
     */
    public long[] MaxArea (int n, int[] Stick) {
        long[] result = new long[2];
        int maxLen = 0;
        for(int len : Stick){
            maxLen = Math.max(maxLen, len);
        }

        int[] counter = new int[maxLen+1];
        for(int len : Stick){
            counter[len]++;
        }

        for(int i=1;i<=maxLen;i++){
            if(counter[i] >= 4){
                int num = counter[i]/4;
                result[1] += num * (long)i * i;
                counter[i] -= num * 4;
            }

            if(counter[i] == 3){
                result[0] += (long)i * i;
            }
        }

        return result;
    }
}


发表于 2020-08-08 17:57:19 回复(0)
class Solution {
public:
    /**
     * 
     * @param n int整型 n
     * @param Stick int整型vector Stick
     * @return long长整型vector
     */
    vector<long> MaxArea(int n, vector<int>& Stick) {
        // write code here
                 //优先构建正方形
        int stick[n];
        stack<int> s;
        s.push(0); //避免数组越界
        int res[2]={0,0};
        //vector<int> res(2,0);
        for(int i=0;i<n;i++) stick[i]=Stick[i];
        sort(stick,stick+n);
                //排序
        for(int i=0;i<n;i++) s.push(stick[i]);
        int num=stick[n-1],count=0;
        while(!s.empty()){
            if(s.top()==num){
                s.pop();
                count++;
            }
            else{
                
                res[1]+=(count/4)*num*num;
                res[0]+=(count%4==3?1:0)*num*num;
                num=s.top();
                count=0;
                
            }
        }
        //return res;
        cout<<res[0]<<" "<<res[1];
    }
};
//大佬能不能帮忙看看呀??看了大家的代码我觉得自己的思路应该没差啊,但是跑不起来,运行结果是;:段错误:您的程序发生段错误,可能是数组越界、堆栈溢出,
搞不明白啊,哭了
发表于 2020-08-05 23:31:51 回复(1)
class Solution {
public:
    /**
     * 
     * @param n int整型 n
     * @param Stick int整型vector Stick
     * @return long长整型vector
     */
    vector<long> MaxArea(int n, vector<int>& Stick) {
        long a, b;
        int Max = 0;
        vector<long> r(2, 0);
        for(int i=0;i<Stick.size();i++)
            Max = max(Max, Stick[i]);
        int cnt[Max+1];
        memset(cnt, 0, sizeof(cnt));
        for(int i=0;i<Stick.size();i++)
            cnt[Stick[i]]++;
        for(int i=1;i<=Max;i++){
            if(cnt[i]!=0){
                if(cnt[i]>=4){
                    int t = cnt[i]/4;
                    cnt[i] -= 4*t;
                    r[1] += (long)t*i*i;
                }
                if(cnt[i]==3){
                    r[0] += (long)i*i;
                }
            }
        }
        return r;
    }
};

发表于 2020-06-27 10:57:27 回复(0)
//多多指教
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)
如果从题解来看,实际就是要求火柴不能组合使用
比如1 1 1 1 2 2 2 2 
我们可以组合成一个变成为3的正方形,面积是9
按照题解的话,则是组合成一个边长为1的正方形和一个边长为2的正方形,面积之和为5
感觉不是太合理。

public long[] MaxArea (int n, int[] Stick) {
        // write code here
        long[] ans = new long[2];
        int maxLen = 0;
        int[] cnt = new int[100006];
        for(int len : Stick) {
            maxLen = Math.max(maxLen, len);
            cnt[len]++;
        }
        for(int i=1; i<=maxLen; i++) {
            if(cnt[i] != 0) {
                int t1 = cnt[i] / 4, t2 = cnt[i] % 4 / 3;
                ans[1] += (long)i*i*t1;
                ans[0] += (long)i*i*t2;
            }
        }
        return ans;
    }


发表于 2020-06-17 23:29:19 回复(5)
#include<algorithm>
using namespace std;
class Solution {
public:
    vector<long> MaxArea(int n, vector<int>& Stick) {
        int my_max=0;
        for(int i=0;i<n;++i){
            if(my_max<Stick[i])
                my_max=Stick[i];
        }
        vector<int> s(my_max+1,0);
        vector<long> result(2,0);
        for(int i=0;i<n;++i){
            s[Stick[i]]++;
        }
        for(int i=0;i<=my_max;++i){
            if(s[i]){
                if(s[i]>=4){
                    int count=s[i]/4;
                    s[i]-=4*count;
                    result[1]+=(long)count*i*i;
                }
                if(s[i]==3){
                    result[0]+=(long)i*i;
                }
            }
        }
        return result;
    }
};

编辑于 2020-06-17 11:06:07 回复(0)