思路:
题目的主要信息:
- n根火柴,长度记录在数组Stick中,用这些火柴拼成正三角形或是正四边形
- 每一边只能选一根火柴,可以组成多个图形
- 求能够组成的图形面积和的最大值,返回一个二元的数组,其中,即数组第一个元素是所有三角形边的平方之和,第二个元素是所有正方形边的平方之和
方法一:贪心
具体做法:
我们都知道如果有6根相同长度的火柴,那么组成一个正方形的面积是大于组成两个正三角形的面积。因此我们采用贪心思想,尽可能多地优先组成正方形,剩下不足四条边再组成正三角形。
我们可以遍历火柴长度的数组,用另一个数组记录每种长度出现的次数,并记录最大长度。
然后我们遍历刚刚记录的数组,对于每种长度,优先组成四边形,然后再组成三角形,求其面积和。
class Solution { public: vector<long> MaxArea(int n, vector<int>& Stick) { vector<long> res(2); vector<int> cnt(100001); int maxlen = 0; for(int i = 0; i < n; i++){ maxlen = max(maxlen, Stick[i]); //找到最长的火柴 cnt[Stick[i]]++; //每种长度火柴有多少 } for(int i = 1; i <= maxlen; i++){ if(cnt[i] != 0){ int temp1 = cnt[i] / 4; //四边形面积最大,优先组成四边形 int temp2 = cnt[i] % 4 / 3; //剩下的再组成三角形 res[1] += (long) i * i * temp1; res[0] += (long) i * i * temp2; } } return res; } };
复杂度分析:
- 时间复杂度:,两次遍历,第一次遍历个数,第二次遍历数组最大值
- 空间复杂度:,最坏情况下,全是不同的长度
方法二:哈希表改进贪心
具体做法:
利用哈希表改进上述方法一。
火柴长度和对应数量可以存入哈希表,之后遍历哈希表,对于每种长度,优先组成正方形,再来三角形。
class Solution { public: vector<long> MaxArea(int n, vector<int>& Stick) { vector<long> res(2); unordered_map<int, int> mp; for(int i = 0; i < n; i++){ //利用哈希表记录每种长度有多少 mp[Stick[i]]++; } for(auto& it: mp){ if(it.second != 0){ int temp1 = it.second / 4; //四边形面积最大,优先组成四边形 int temp2 = it.second % 4 / 3; //剩下的再组成三角形 res[1] += (long) it.first * it.first * temp1; res[0] += (long) it.first * it.first * temp2; } } return res; } };
复杂度分析:
- 时间复杂度:,遍历数组,遍历哈希表最大为
- 空间复杂度:,最坏情况下,全是不同的长度