2
#yyds干货盘点# leetcode算法题：火柴拼正方形
source link: https://blog.51cto.com/u_13321676/5645576
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# leetcode算法题：火柴拼正方形
精选 原创将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
如果你能使这个正方形，则返回 true ，否则返回 false 。
输入: matchsticks = [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴。
输入: matchsticks = [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。
代码实现：
class Solution {
public boolean makesquare(int[] matchsticks) {
int totalLen = Arrays.stream(matchsticks).sum();
if (totalLen % 4 != 0) {
return false;
}
Arrays.sort(matchsticks);
for (int i = 0, j = matchsticks.length - 1; i < j; i++, j--) {
int temp = matchsticks[i];
matchsticks[i] = matchsticks[j];
matchsticks[j] = temp;
}
int[] edges = new int[4];
return dfs(0, matchsticks, edges, totalLen / 4);
}
public boolean dfs(int index, int[] matchsticks, int[] edges, int len) {
if (index == matchsticks.length) {
return true;
}
for (int i = 0; i < edges.length; i++) {
edges[i] += matchsticks[index];
if (edges[i] <= len && dfs(index + 1, matchsticks, edges, len)) {
return true;
}
edges[i] -= matchsticks[index];
}
return false;
}
}
public boolean makesquare(int[] matchsticks) {
int totalLen = Arrays.stream(matchsticks).sum();
if (totalLen % 4 != 0) {
return false;
}
Arrays.sort(matchsticks);
for (int i = 0, j = matchsticks.length - 1; i < j; i++, j--) {
int temp = matchsticks[i];
matchsticks[i] = matchsticks[j];
matchsticks[j] = temp;
}
int[] edges = new int[4];
return dfs(0, matchsticks, edges, totalLen / 4);
}
public boolean dfs(int index, int[] matchsticks, int[] edges, int len) {
if (index == matchsticks.length) {
return true;
}
for (int i = 0; i < edges.length; i++) {
edges[i] += matchsticks[index];
if (edges[i] <= len && dfs(index + 1, matchsticks, edges, len)) {
return true;
}
edges[i] -= matchsticks[index];
}
return false;
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK