題目
(https://leetcode-cn.com/problems/matchsticks-to-square/)
還記得童話《賣火柴的小女孩》嗎制恍?現(xiàn)在进萄,你知道小女孩有多少根火柴吆你,請找出一種能使用所有火柴拼成一個正方形的方法肆汹。不能折斷火柴终吼,可以把火柴連接起來酪惭,并且每根火柴都要用到。
輸入為小女孩擁有火柴的數(shù)目掂碱,每根火柴用其長度表示怜姿。輸出即為是否能用所有的火柴拼成正方形。
示例 1:
輸入: [1,1,2,2,2]
輸出: true
解釋: 能拼成一個邊長為2的正方形疼燥,每邊兩根火柴沧卢。
示例 2:
輸入: [3,3,3,3,4]
輸出: false
解釋: 不能用所有火柴拼成一個正方形。
注意:
給定的火柴長度和在 0 到 10^9之間醉者。
火柴數(shù)組的長度不超過15但狭。
分析
首先判斷什么情況下不能形成正方形。什么情況可以撬即。
如果邊數(shù)少于4跟邊數(shù)不是4的倍數(shù)立磁。肯定不能形成正方形
首先我們一邊一邊放火材剥槐。如果超過邊長的話唱歧,就回溯。一直到每個邊都剛好擺成正方形
就無腦遍歷粒竖。
代碼
class Solution {
public boolean makesquare(int[] nums) {
//如果邊少于4不能形成正方形
if (null == nums || nums.length<4){
return false;
}
int account = 0 ;
for (int temp:nums) {
account += temp;
}
//變數(shù)總和不是4的倍數(shù)不能成為正方形
if (account%4!=0){
return false;
}
//冒泡排序 降序
for (int k = 0; k < nums.length - 1; k++) {
for (int j = k + 1; j < nums.length; j++) {
if (nums[k] < nums[j]) {
int temp = nums[k];
nums[k] = nums[j];
nums[j] = temp;
}
}
}
int sideLength = account/4;
for (int i:nums) {
//如果有一邊大于邊長颅崩。不能形成正方形
if (i>sideLength){
return false;
}
}
//四邊
int [] sides = new int[4];
boolean search = search(0, sides, nums, sideLength);
return search;
}
private static boolean search(int pos,int[] sides,int[] nums,int sideLength) {
//遍歷完成后判斷每一邊是否都相等
if(pos >= nums.length){
return sides[0] == sideLength && sides[1] == sideLength
&& sides[2] == sideLength && sides[3] == sideLength;
}
for (int i = 0; i < sides.length; i++) {
if (sides[i]+nums[pos]>sideLength){
continue;
}
sides[i] += nums[pos];
if (search(pos+1,sides,nums,sideLength)){
return true;
};
//回溯
sides[i] = sides[i]-nums[pos];
}
return false;
}
}