火柴拼图

问题描述：牛妹有n根火柴，她想用这些火柴去拼正三角形或者正四边形。牛妹想让最后拼出的总面积尽可能大的，请你帮帮她。 返回一个Vector，Vector中存有两个数字。其中最大面积
示例
输入：4,[1,1,1,1]
返回值：[0,1]
说明：构成一个边长为1的正四边形面积总和最大，值为1。所以Vector[0]=0，Vector[1]=1

方法一

思路分析

    因为要构成正三角形或者正四边形，那么首先对给定的火柴，对不同长度的火柴进行计数统计，对不同长度的火柴，先判断火柴数是否大于等于四，如果大于等于四，那么可以构成正四边形，因此计算该正四边形的面积，之后更新该长度的火柴数；接着判断火柴数是否大于等于3，如果是，那么可以构成正三角形，因此计算该正三角形的面积，该长度的火柴已经无法构成正三角形或者正四边形，因此不做更新。具体过程如下:
  • 首先找到给定火柴数组中长度最大的火柴长度变量m
  • 构建存储不同长度火柴的统计数组，其下标对应长度，数组值表示对应长度的火柴数
  • 从最大长度的火柴开始遍历，先判断是否构成正四边形，并计算构成正四边形的数量以及面积，之后判断是否构成正三角形，并计算正三角形的面积
  • 遍历结束

图解

输入：[1,1,1,2,2,2,2,3,4,5,5,5,5,5,5,5,6,6,6]
遍历过程如下：


C++核心代码 

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 length_stick = 0;
        vector<long>res(2);
        vector<int>a(100010,0);
        for(int i=0;i<n;i++)
        {
            if(length_stick<Stick[i])
                length_stick=Stick[i];
             a[Stick[i]]++;//a[k]表示该长度对应的数量，这也是记录m的原因
        }
        for(int i=1;i<=length_stick;i++)
        {
            if(a[i]>=4)//首先判断能构成正四边形
            {
                int num = a[i]/4;//最多构成正四边形的个数
                a[i] -= num*4;//更新构成正四边形后的火柴数
                res[1] += (long)i*i*num;//记录面积
            }
            if(a[i]>=3)//判断是否能构成正三角形，如果可以只能构成一个
            {
                 res[0] += (long)i*i;
            }
        }
        return res; 
    }
};

复杂度分析

  • 时间复杂度：首先循环遍历数组找到长度最长的火柴长度$max(Stick)$，时间复杂度为$O(n)$，遍历以此数组统计不同长度火柴对应的数量，时间复杂度为$O(n)$，然后对统计得到的数组进行遍历，时间复杂度为$O(max(Stick))$，因此时间复杂度为$O(n+max(Stick))$
  • 空间复杂度：设置一个长度为$max(Stick)$的数组用于存储不同长度火柴对应的数量，因此空间复杂度为$O(max(Stick))$

方法二

思路分析

      在方法一的基础上，为了降低空间复杂度与时间复杂度，因此我们可以使用map数据容器存储不同长度对应的火柴数量，这样就不需要找到长度最长的火柴。减少一次循环统计。

C++核心代码 

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
        map<long, long> a;
        vector<long>res(2,0);
        for (int i = 0; i < n; i++)//将火柴长度以及对应的数量存入map
        {
         if (a.end() != a.find(Stick[i])) a[Stick[i]]++;
         else a.insert(pair<int, int>(Stick[i], 1));
        
        }
        for (auto it : a)//遍历map
        {
           if(it.second>=4)//尽可能先组成正四边形
           {
                int p = it.second/4;//组成正四边形的个数
                res[1] += (long)(it.first)*(it.first)*p;
                it.second -= p*4;//更新组成四边形后的火柴数
                
            }
            if(it.second>=3)//计算是否可以构成正三角形
            {
                 res[0] += (long)(it.first)*(it.first);
            }
        }
        return res; 
    }
};

复杂度分析

  • 时间复杂度：循环遍历数组统计不同长度火柴的数量存入map中，时间复杂度为$O(n)$，循环遍历map，时间复杂度为$O(kind(Stick))$，其中$kind(Stick)$表示数组中按照长度对火柴的分类数量
  • 空间复杂度：设置一个统计不同长度火柴的数量的容器，其大小为Stick中按照长度分类火柴的种类，空间复杂度为$O(kind(Stick))$