2022-10-21：你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i

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编写。代码如下：

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代码

本作品采用《CC 协议》，转载必须注明作者和本文链接