LeetCode题练习与总结：火柴拼正方形--473

创作时间:

作者:

@小白创作中心

LeetCode题练习与总结：火柴拼正方形--473

引用

CSDN

https://blog.csdn.net/weixin_62860386/article/details/144494995

LeetCode是一个知名的在线编程练习平台，提供了大量高质量的算法题目，涵盖了各种难度级别和知识点。通过解决这些题目，可以有效地提升编程能力和算法思维。本文将详细解析一道经典的LeetCode算法题——"火柴拼正方形"，帮助读者掌握相关解题技巧。

一、题目描述

你将得到一个整数数组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] <= 10^8

二、解题思路

首先计算所有火柴棒的总长度，如果总长度不能被4整除，则直接返回false，因为无法拼成正方形。
确定正方形的边长，即总长度除以4。
将火柴棒数组从大到小排序，这样可以优先使用较长的火柴棒，减少搜索空间。
使用深度优先搜索（DFS）来尝试将火柴棒拼成正方形的四条边。每次尝试将一根火柴棒放入一条边，如果当前边加上这根火柴棒超过边长，则回溯到上一步，尝试其他火柴棒。
如果所有火柴棒都能放入四条边中，且每条边的长度等于正方形的边长，则返回true，否则返回false。

三、具体代码

import java.util.Arrays;

class Solution {
    public boolean makesquare(int[] matchsticks) {
        // 计算所有火柴棒的总长度
        int totalLength = 0;
        for (int length : matchsticks) {
            totalLength += length;
        }
        
        // 如果总长度不能被4整除，则无法拼成正方形
        if (totalLength % 4 != 0) {
            return false;
        }
        
        // 确定正方形的边长
        int sideLength = totalLength / 4;
        
        // 将火柴棒数组从大到小排序
        Arrays.sort(matchsticks);
        reverse(matchsticks);
        
        // 初始化四条边的长度
        int[] edges = new int[4];
        
        // 使用深度优先搜索尝试拼成正方形
        return dfs(matchsticks, edges, sideLength, 0);
    }
    
    // 深度优先搜索
    private boolean dfs(int[] matchsticks, int[] edges, int sideLength, int index) {
        // 如果所有火柴棒都尝试过了，检查四条边的长度是否相等
        if (index == matchsticks.length) {
            return edges[0] == sideLength && edges[1] == sideLength && edges[2] == sideLength && edges[3] == sideLength;
        }
        
        // 尝试将当前火柴棒放入四条边中的任意一条
        for (int i = 0; i < 4; i++) {
            // 如果当前边加上这根火柴棒超过边长，或者这根火柴棒和上一根相同且上一根放入该边失败，则跳过
            if (edges[i] + matchsticks[index] > sideLength || (i > 0 && edges[i] == edges[i - 1])) {
                continue;
            }
            
            // 将火柴棒放入当前边
            edges[i] += matchsticks[index];
            
            // 递归尝试下一根火柴棒
            if (dfs(matchsticks, edges, sideLength, index + 1)) {
                return true;
            }
            
            // 回溯，移除火柴棒
            edges[i] -= matchsticks[index];
        }
        
        // 所有边都无法放入当前火柴棒，返回false
        return false;
    }
    
    // 反转数组
    private void reverse(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

这段代码首先计算火柴棒的总长度，然后进行排序和深度优先搜索，最后检查是否能拼成正方形。

四、时间复杂度和空间复杂度

时间复杂度

计算火柴棒总长度：O(n)，其中n是火柴棒的数量。
排序火柴棒数组：O(n log n)，因为使用了数组的排序方法。
反转数组：O(n)，遍历数组一半的长度进行交换。
深度优先搜索（DFS）：最坏情况下，每个火柴棒都有4种选择（放入四条边中的任意一条），因此时间复杂度为O(4^n)。但是，由于我们使用了剪枝（如果当前边加上这根火柴棒超过边长，或者这根火柴棒和上一根相同且上一根放入该边失败，则跳过），实际上时间复杂度会小于O(4^n)。
综上所述，总的时间复杂度主要取决于DFS，即O(4^n)，但由于剪枝的存在，实际运行时间会小于这个值。

空间复杂度

边长数组：O(1)，因为它的长度是固定的4。
DFS递归栈：最坏情况下，递归的深度为n（火柴棒的数量），因此空间复杂度为O(n)。
综上所述，总的空间复杂度为O(n)，其中n是火柴棒的数量。这是因为DFS递归过程中，系统栈会保存每次递归的状态，而每个状态都需要存储火柴棒数组的当前索引和边长数组的状态。尽管边长数组的大小是固定的，但递归栈的深度与火柴棒数量成线性关系。