广联达4.29笔试,第四题(钢筋(火柴)拼正方形)
实际上这道题等价于leetcode上的2道原题,将能否将集合划分为为k个等和子集或火拆拼正方形
前者是后者的一般形式
后者中k=4(因为正方形是四条边)
原始思路就是构建k个bucket,将数组nums中的元素依次试探性装入buket,最后判断是否能装够k个bucket且每个bucket中的数值和相等
优化就是预处理+回溯中的break:先对nums排序,从后往前遍历,如果nums[i] == len(这里指正方形边长) ,则k--
package GuangLianDa; import java.util.*; public class Main4 { //.火柴正方形 leetcode 473 public boolean makesquare(int[] nums) { if (nums == null || nums.length<4) return false; int count = 0; for (int x:nums) count+=x; if (count%4 !=0) return false; int len = count/4; int k = 4; //.划分成4个等和子集 Arrays.sort(nums); if (nums[nums.length-1]>len) return false; int beginIndex = nums.length-1; while (beginIndex>=0 && len == nums[beginIndex]){ k--; beginIndex--; } int[] bucket = new int[k]; return rec(nums,bucket,beginIndex,k,len); } private boolean rec(int[] nums,int[] bucket,int beginIndex,int k,int target){ if (beginIndex<0) return true; int putnum = nums[beginIndex]; for (int i =0;i<k;i++){ if (putnum+bucket[i]<=target){ if (rec(nums,bucket,beginIndex-1,k,target)){ return true; } bucket[i] = bucket[i] - putnum; if (bucket[i] == 0) break; } } return false; } }