同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
你将得到一个整数数组 matchsticks
,其中 matchsticks[i]
是第 i
个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒,但你可以把它们连在一起,而且每根火柴棒必须 使用一次 。
如果你能使这个正方形,则返回 true
,否则返回 false
。
示例 1:
输入: matchsticks = [1,1,2,2,2] 输出: true 解释: 能拼成一个边长为2的正方形,每边两根火柴。
示例 2:
输入: matchsticks = [3,3,3,3,4] 输出: false 解释: 不能用所有火柴拼成一个正方形。
提示:
1 <= matchsticks.length <= 15
1 <= matchsticks[i] <= 108
方法一:排序 + 回溯
用 $edges[i]$ 记录正方形每条边当前的长度,对于第 $u$ 根火柴,尝试把它加到 $edges[i]$ 每条边,若加入后 $edges[i]$ 不超过正方形期望长度 $x$,则继续往下递归 $u+1$ 根火柴。若所有火柴都能被加入,说明满足拼成正方形的要求。
这里对 $matchsticks$ 从大到小排序,可以减少搜索次数。
时间复杂度 $O(4^n)$,其中 $n$ 表示 $matchsticks$ 的长度。每根火柴可以被放入正方形的 $4$ 条边,共有 $n$ 根火柴。
方法二:状态压缩 + 记忆化搜索
记当前火柴被划分的情况为 $state$。对于第 $i$ 个数,若 $state \\ & \\ (1<<i)=0$,说明第 $i$ 个火柴棒未被划分。我们的目标是从全部数字中凑出 $k$ 个和为 $s$ 的子集。
记当前子集的和为 $t$。在未划分第 $i$ 个火柴棒时:
注:若 $t+matchsticks[i]==s$,说明恰好可以得到一个和为 $s$ 的子集,下一步将 $t$ 归零(可以通过 $(t+matchsticks[i]) %s$ 实现),并继续划分下一个子集。
class Solution:
def makesquare(self, matchsticks: List[int]) -> bool:
def dfs(u):
if u == len(matchsticks):
return True
for i in range(4):
if i > 0 and edges[i - 1] == edges[i]:
continue
edges[i] += matchsticks[u]
if edges[i] <= x and dfs(u + 1):
return True
edges[i] -= matchsticks[u]
return False
x, mod = divmod(sum(matchsticks), 4)
if mod or x < max(matchsticks):
return False
edges = [0] * 4
matchsticks.sort(reverse=True)
return dfs(0)
class Solution:
def makesquare(self, matchsticks: List[int]) -> bool:
@cache
def dfs(state, t):
if state == (1 << len(matchsticks)) - 1:
return True
for i, v in enumerate(matchsticks):
if (state & (1 << i)):
continue
if t + v > s:
break
if dfs(state | (1 << i), (t + v) % s):
return True
return False
s, mod = divmod(sum(matchsticks), 4)
matchsticks.sort()
if mod:
return False
return dfs(0, 0)
class Solution {
public boolean makesquare(int[] matchsticks) {
int s = 0, mx = 0;
for (int v : matchsticks) {
s += v;
mx = Math.max(mx, v);
}
int x = s / 4, mod = s % 4;
if (mod != 0 || x < mx) {
return false;
}
Arrays.sort(matchsticks);
int[] edges = new int[4];
return dfs(matchsticks.length - 1, x, matchsticks, edges);
}
private boolean dfs(int u, int x, int[] matchsticks, int[] edges) {
if (u < 0) {
return true;
}
for (int i = 0; i < 4; ++i) {
if (i > 0 && edges[i - 1] == edges[i]) {
continue;
}
edges[i] += matchsticks[u];
if (edges[i] <= x && dfs(u - 1, x, matchsticks, edges)) {
return true;
}
edges[i] -= matchsticks[u];
}
return false;
}
}
class Solution {
public:
bool makesquare(vector<int>& matchsticks) {
int s = 0, mx = 0;
for (int& v : matchsticks) {
s += v;
mx = max(mx, v);
}
int x = s / 4, mod = s % 4;
if (mod != 0 || x < mx) return false;
sort(matchsticks.begin(), matchsticks.end(), greater<int>());
vector<int> edges(4);
return dfs(0, x, matchsticks, edges);
}
bool dfs(int u, int x, vector<int>& matchsticks, vector<int>& edges) {
if (u == matchsticks.size()) return true;
for (int i = 0; i < 4; ++i) {
if (i > 0 && edges[i - 1] == edges[i]) continue;
edges[i] += matchsticks[u];
if (edges[i] <= x && dfs(u + 1, x, matchsticks, edges)) return true;
edges[i] -= matchsticks[u];
}
return false;
}
};
func makesquare(matchsticks []int) bool {
s := 0
for _, v := range matchsticks {
s += v
}
if s%4 != 0 {
return false
}
sort.Sort(sort.Reverse(sort.IntSlice(matchsticks)))
edges := make([]int, 4)
var dfs func(u, x int) bool
dfs = func(u, x int) bool {
if u == len(matchsticks) {
return true
}
for i := 0; i < 4; i++ {
if i > 0 && edges[i-1] == edges[i] {
continue
}
edges[i] += matchsticks[u]
if edges[i] <= x && dfs(u+1, x) {
return true
}
edges[i] -= matchsticks[u]
}
return false
}
return dfs(0, s/4)
}
impl Solution {
pub fn makesquare(matchsticks: Vec<i32>) -> bool {
let mut matchsticks = matchsticks;
fn dfs(matchsticks: &Vec<i32>, edges: &mut [i32; 4], u: usize, x: i32) -> bool {
if u == matchsticks.len() {
return true;
}
for i in 0..4 {
if i > 0 && edges[i - 1] == edges[i] {
continue;
}
edges[i] += matchsticks[u];
if edges[i] <= x && dfs(matchsticks, edges, u + 1, x) {
return true;
}
edges[i] -= matchsticks[u];
}
false
}
let sum: i32 = matchsticks.iter().sum();
if sum % 4 != 0 {
return false;
}
matchsticks.sort_by(|x, y| y.cmp(x));
let mut edges = [0; 4];
dfs(&matchsticks, &mut edges, 0, sum / 4)
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。