代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
You are given an integer array matchsticks
where matchsticks[i]
is the length of the ith
matchstick. You want to use all the matchsticks to make one square. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.
Return true
if you can make this square and false
otherwise.
Example 1:
Input: matchsticks = [1,1,2,2,2] Output: true Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.
Example 2:
Input: matchsticks = [3,3,3,3,4] Output: false Explanation: You cannot find a way to form a square with all the matchsticks.
Constraints:
1 <= matchsticks.length <= 15
1 <= matchsticks[i] <= 108
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)
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。