2022-10-21：你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。
你要用 所有的火柴棍 拼成一个正方形。
你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
如果你能拼出正方形，则返回 true ，否则返回 false 。
输入: matchsticks = [1,1,2,2,2]。
输出: true。
答案2022-10-21：
状态压缩的动态规划。
力扣473。各种语言测试，rust运行速度最快，内存占用最低，golang次之，java和c#最慢并且内存占用最高。
代码用rust编写。代码如下：
代码语言：javascript复制use std::iter::repeat;
impl Solution {
pub fn makesquare(matchsticks: Vec<i32>) -> bool {
let mut matchsticks = matchsticks;
let mut sum = 0;
for num in matchsticks.iter() {
sum = num;
}
if sum & 3 != 0 {
return false;
}
let mut dp: Vec<i32> = repeat(0).take(1 << matchsticks.len()).collect();
return Solution::process(&mut matchsticks, 0, 0, sum >> 2, 4, &mut dp);
}
fn process(
arr: &mut Vec<i32>,
status: i32,
cur: i32,
len: i32,
edges: i32,
dp: &mut Vec<i32>,
) -> bool {
if dp[status as usize] != 0 {
return dp[status as usize] == 1;
}
let mut ans = false;
if edges == 0 {
ans = if status == (1 << arr.len()) - 1 {
true
} else {
false
};
} else {
let mut i = 0;
while i < arr.len() as i32 && !ans {
if ((1 << i) & status) == 0 && cur arr[i as usize] <= len {
if cur arr[i as usize] == len {
ans |= Solution::process(arr, status | (1 << i), 0, len, edges - 1, dp);
} else {
ans |= Solution::process(
arr,
status | (1 << i),
cur arr[i as usize],
len,
edges,
dp,
);
}
}
i = 1;
}
}
dp[status as usize] = if ans { 1 } else { -1 };
return ans;
}
}
fn main() {
let matchsticks = vec![1, 1, 2, 2, 2];
let ans = Solution::makesquare(matchsticks);
println!("ans = {:?}", ans);
}
struct Solution {}执行结果如下：
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_07_4_week/Code02_MatchsticksToSquare.java)
