拼多多笔试,第二题,leetcode能A,笔试时死活60%
class Solution { //.火柴正方形 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){ bucket[i] += putnum; if (rec(nums,bucket,beginIndex-1,k,target)){ return true; } bucket[i] = bucket[i] - putnum; if (bucket[i] == 0) break; } } return false; } }
#拼多多笔试##拼多多##笔试题目#