牛妹有n根火柴,她想用这些火柴去拼正三角形或者正四边形。牛妹想让最后拼出的总面积尽可能大的,请你帮帮她。
返回一个Vector,Vector中存有两个数字。
其中最大面积。
4,[1,1,1,1]
[0,1]
构成一个边长为1的正四边形面积总和最大,值为1。所以Vector[0]=0,Vector[1]=1
Stick[i]表示第i根火柴的长度,一共有n根火柴
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
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; } }
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; } }
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]; } };
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; } };
//多多指教 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 ; }
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; }
#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; } };