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

一、题目描述

你将得到一个整数数组 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

二、解题思路

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

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

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

1. 时间复杂度

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

综上所述，总的时间复杂度主要取决于DFS，即O(4^n)，但由于剪枝的存在，实际运行时间会小于这个值。

2. 空间复杂度

• 边长数组：O(1)，因为它的长度是固定的4。
• DFS递归栈：最坏情况下，递归的深度为n（火柴棒的数量），因此空间复杂度为O(n)。

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

五、总结知识点

• 数组操作：

  • 使用for循环遍历数组，计算所有元素的和。
  • 使用Arrays.sort()方法对数组进行排序。
  • 实现了一个reverse()方法来反转数组元素的顺序。

• 数学运算：

  • 计算数组元素的总和。
  • 检查总和是否能被4整除，以确定是否可能构成正方形。

• 递归算法：

  • 实现了一个深度优先搜索（DFS）算法来尝试将火柴棒拼成正方形的四条边。
  • 在递归函数中，使用回溯法来尝试所有可能的组合。

• 剪枝策略：

  • 在DFS中，通过判断当前边加上火柴棒是否会超过边长来剪枝，避免不必要的递归调用。
  • 通过比较当前边与上一边的长度来避免重复尝试相同的组合。

• 逻辑判断：

  • 使用if语句来检查是否所有火柴棒都已尝试，以及是否所有边的长度都相等。
  • 使用continue语句来跳过不符合条件的迭代。

• 基本编程概念：

  • 变量声明和初始化。
  • 函数定义和调用。
  • 递归的概念和应用。

• 问题解决策略：

  • 将问题分解为更小的子问题（将火柴棒分配到四条边）。
  • 使用穷举法（DFS）来探索所有可能的解决方案。
  • 在探索过程中使用剪枝来优化性能。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。