周星星

Appearance

LeetCode火柴拼正方形.png

题目 ​

你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用所有的火柴棍拼成一个正方形。你不能折断任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须使用一次 。

如果你能使这个正方形，则返回 true ，否则返回 false 。

示例 1:

image.png

输入: matchsticks = [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴。
输入: matchsticks = [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴。

示例 2:

输入: matchsticks = [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。
输入: matchsticks = [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。

提示:

  • 1 <= matchsticks.length <= 15
  • 1 <= matchsticks[i] <= 108

理解题目 ​

题目的意思很简单，就是想你利用数组内容的元素去拼正方形，要使用所有的元素，不能将元素进行改变，而且只能用一次。

题解 ​

有两种解决方案，一种是回溯的。另外一种是动态规划+状态压缩

回溯 ​

首先计算所有火柴的总长度totalLen，如果totalLen 不是 4 的倍数，那么不可能拼成正方形，返回 false。当 totalLen 是 4 的倍数时，每条边的边长为 len = totalLen/4，用edges 来记录 4 条边已经放入的火柴总长度。对于第index 火柴，尝试把它放入其中一条边内且满足放入后该边的火柴总长度不超过len，然后继续枚举第index+1 根火柴的放置情况，如果所有火柴都已经被放置，那么说明可以拼成正方形。

为了减少搜索量，需要对火柴长度从大到小进行排序。

理解就是有四个桶，这个桶的高度就是边长，将火柴依次放入桶中，去检查放入当前的桶的高度是否小于边长，如果小于则可以继续放入，通过def回溯接着往里面放入，最后还要将放入火柴减去，不管这个火柴是符合还是不符合，因为这根火柴还可以放在其他的桶内也就是i+1的位置

ts
function makesquare(matchsticks: number[]): boolean {
    let totalLen = matchsticks.reduce((a, b) => a + b)
    if (totalLen % 4 !== 0) return false
    let len = Math.floor(totalLen / 4)
    matchsticks.sort((a,b)=>b-a)
    let edges = new Array(4).fill(0)
    return dfs(0, matchsticks, edges, len)
}
const dfs = (index, matchsticks, edges, len) => {
    if(index === matchsticks.length) return true
    for(let i=0;i<edges.length;i++){
        edges[i] += matchsticks[index]
        if(edges[i]<=len && dfs(index+1,matchsticks,edges,len)){
            return true
        }
        edges[i] -= matchsticks[index]
    }
    return false
}
function makesquare(matchsticks: number[]): boolean {
    let totalLen = matchsticks.reduce((a, b) => a + b)
    if (totalLen % 4 !== 0) return false
    let len = Math.floor(totalLen / 4)
    matchsticks.sort((a,b)=>b-a)
    let edges = new Array(4).fill(0)
    return dfs(0, matchsticks, edges, len)
}
const dfs = (index, matchsticks, edges, len) => {
    if(index === matchsticks.length) return true
    for(let i=0;i<edges.length;i++){
        edges[i] += matchsticks[index]
        if(edges[i]<=len && dfs(index+1,matchsticks,edges,len)){
            return true
        }
        edges[i] -= matchsticks[index]
    }
    return false
}

动态规划+状态压缩 ​

image.png

这题的题解主要是依靠了位运算的熟悉。

基本思路：

  • 首先计算所有火柴的总长度totalLen，如果totalLen 不是 4 的倍数，那么不可能拼成正方形，返回 false。当 totalLen 是 4 的倍数时，每条边的边长为 len = totalLen/4
  • 利用二进制的位操作，每一位表示一根火柴
  • 用状态 s 记录哪些火柴已经被放入（s 的第 k 位为 1 表示第 k 根火柴已经被放入），再通过 s & ~(1 << k)去获取前一个状态，通过dp[s1]和matchsticks[k]去判断，当前的火柴J可不可以放入这条边

举个例子： 比如说数组为[1,1,2,2,2]，i=7=111(二进制)。在循环j时首先检查当前火柴是否已经被使用，然后判断能否插入到没有该火柴的前一个状态：

  • j=0时，(i & (1 << j))=1表示火柴已经被使用，通过 i & ~(1 << j)=6=110确定前一个状态s1=110，接着根据前一个状态dp[110]和dp[110]+和matchsticks[j]来判断是否可以将火柴0放入这条边。
  • j=1时，(i & (1 << j))=1，s1=101，根据前一个状态dp[101]和dp[101]+matchsticks[j]来判断是否可以将火柴1放入这条边。
  • j=2时，(i & (1 << j))=1，s1=011，根据前一个状态dp[011]和dp[011]+matchsticks[j]来判断是否可以将火柴2放入这条边。
  • ...
ts
// 试着去理解了一下解法二的思路。 
// 为什么搜索过程中只需要有一根火柴可以放进去，就不需要搜索其他情况了。 
// 因为dp数组保存的是当前这个未放满的边的长度，对于每个状态s来说，dp数组存储的只有两种情况，
// 1、dp[s]=-1代表此时放火柴无法把前面的放满。
// dp[s]=其他值时代表此时前面的边可以被放满，注意此时dp的值肯定是固定的，
// 所以只要我们确定这个状态s能把前面放满，就可以了，
// 不需要再搜索了，dp[s]也就被确定下来了。
var makesquare3 = function (matchsticks: number[]) {
    const totalLen = matchsticks.reduce((a, b) => a + b);
    if (totalLen % 4 !== 0) {
        return false;
    }
    const len = Math.floor(totalLen / 4), n = matchsticks.length;
    // 为什么是这样的呢？
    // 我们给正方形的四条边进行编号，分别为 1，2，3 和 4。
    // 按照编号顺序依次将火柴放入正方形的四条边，只有前一条边被放满后，才能将火柴放入后一条边。
    // 用状态 s 记录哪些火柴已经被放入（s 的第 k 位为 1 表示第 k 根火柴已经被放入），
    // dp[s] 表示正方形未放满的边的当前长度
    const dp = new Array(1 << n).fill(-1);
    dp[0] = 0;

    for (let s = 1; s < (1 << n); s++) {
        for (let k = 0; k < n; k++) {
            // 使用二进制的位操作，每一位代表一根火柴
            //求状态s中第k位的火柴是否被使用，等于1则被使用，等于0则未被使用
            // console.log("(s & (1 << k))", `(${s} & (1 << ${k}))`)
            if ((s & (1 << k)) === 0) {
                continue;
            }
            // 如果去掉它的第 k 根火柴得到的状态s1
            // 将s中的第k位置设置为0 就是去掉第k位的状态，本来是1的
            // 查找前一个状态
            const s1 = s & ~(1 << k);
            console.log(`如果去掉它的第 k=${k} 根火柴得到的状态`, `s=${s},s1= ${s1} = ${s} & ~(1 << ${k}),dp[s1]=dp[${s1}]=${dp[s1]}`)
            if (dp[s1] >= 0 && dp[s1] + matchsticks[k] <= len) {
                //取余数是为了该边还差多少;
                dp[s] = (dp[s1] + matchsticks[k]) % len;
                // console.log("(dp[s1] + matchsticks[k]) % len", dp)
                break;
            }
        }

        console.log("============分割线")
    }
    console.log(dp)
    return dp[(1 << n) - 1] === 0;
}

console.log("火柴拼正方形", makesquare3([1,1, 2, 2, 2]))
// 试着去理解了一下解法二的思路。 
// 为什么搜索过程中只需要有一根火柴可以放进去，就不需要搜索其他情况了。 
// 因为dp数组保存的是当前这个未放满的边的长度，对于每个状态s来说，dp数组存储的只有两种情况，
// 1、dp[s]=-1代表此时放火柴无法把前面的放满。
// dp[s]=其他值时代表此时前面的边可以被放满，注意此时dp的值肯定是固定的，
// 所以只要我们确定这个状态s能把前面放满，就可以了，
// 不需要再搜索了，dp[s]也就被确定下来了。
var makesquare3 = function (matchsticks: number[]) {
    const totalLen = matchsticks.reduce((a, b) => a + b);
    if (totalLen % 4 !== 0) {
        return false;
    }
    const len = Math.floor(totalLen / 4), n = matchsticks.length;
    // 为什么是这样的呢？
    // 我们给正方形的四条边进行编号，分别为 1，2，3 和 4。
    // 按照编号顺序依次将火柴放入正方形的四条边，只有前一条边被放满后，才能将火柴放入后一条边。
    // 用状态 s 记录哪些火柴已经被放入（s 的第 k 位为 1 表示第 k 根火柴已经被放入），
    // dp[s] 表示正方形未放满的边的当前长度
    const dp = new Array(1 << n).fill(-1);
    dp[0] = 0;

    for (let s = 1; s < (1 << n); s++) {
        for (let k = 0; k < n; k++) {
            // 使用二进制的位操作，每一位代表一根火柴
            //求状态s中第k位的火柴是否被使用，等于1则被使用，等于0则未被使用
            // console.log("(s & (1 << k))", `(${s} & (1 << ${k}))`)
            if ((s & (1 << k)) === 0) {
                continue;
            }
            // 如果去掉它的第 k 根火柴得到的状态s1
            // 将s中的第k位置设置为0 就是去掉第k位的状态，本来是1的
            // 查找前一个状态
            const s1 = s & ~(1 << k);
            console.log(`如果去掉它的第 k=${k} 根火柴得到的状态`, `s=${s},s1= ${s1} = ${s} & ~(1 << ${k}),dp[s1]=dp[${s1}]=${dp[s1]}`)
            if (dp[s1] >= 0 && dp[s1] + matchsticks[k] <= len) {
                //取余数是为了该边还差多少;
                dp[s] = (dp[s1] + matchsticks[k]) % len;
                // console.log("(dp[s1] + matchsticks[k]) % len", dp)
                break;
            }
        }

        console.log("============分割线")
    }
    console.log(dp)
    return dp[(1 << n) - 1] === 0;
}

console.log("火柴拼正方形", makesquare3([1,1, 2, 2, 2]))

力扣 BenHao总的解法

ts
function makesquare(matchsticks: number[]): boolean {
    const total = matchsticks.reduce((a, b) => a + b)
    if (total % 4 != 0) {
        return false
    }
    const n = matchsticks.length, line = Math.floor(total / 4)
    const allPicked = (1 << n) - 1
    const dp = new Array(1 << n).fill(-1)
    dp[0] = 0
    for (let i = 0; i <= allPicked; i++) {
        for (let j = 0; j < n; j++) {
            console.log("i >> j", `i=${i} , j=${j} , (i >> j)=${i >> j} `)
            if ((i >> j & 1) != 0) {
                const before = i & ~(1 << j)
                console.log("before", before,`~(1 << j)=${~(1 << j)}`)
                //取该边长大于0，小于边长的值
                if (dp[before] >= 0 && matchsticks[j] + dp[before] <= line) {
                    // console.log("~(1 << j)",i,j)
                    dp[i] = (dp[before] + matchsticks[j]) % line
                    // console.log("改变的值",dp)
                    break;
                }
            }
        }
        console.log("===========断线", i,dp)
    }
    //如何确保最后一个会等于0
    return dp[allPicked] == 0
};

// console.log("火柴拼正方形",makesquare([3,3,3,3,4]))
console.log("火柴拼正方形", makesquare([1,1,2,2,2]))
function makesquare(matchsticks: number[]): boolean {
    const total = matchsticks.reduce((a, b) => a + b)
    if (total % 4 != 0) {
        return false
    }
    const n = matchsticks.length, line = Math.floor(total / 4)
    const allPicked = (1 << n) - 1
    const dp = new Array(1 << n).fill(-1)
    dp[0] = 0
    for (let i = 0; i <= allPicked; i++) {
        for (let j = 0; j < n; j++) {
            console.log("i >> j", `i=${i} , j=${j} , (i >> j)=${i >> j} `)
            if ((i >> j & 1) != 0) {
                const before = i & ~(1 << j)
                console.log("before", before,`~(1 << j)=${~(1 << j)}`)
                //取该边长大于0，小于边长的值
                if (dp[before] >= 0 && matchsticks[j] + dp[before] <= line) {
                    // console.log("~(1 << j)",i,j)
                    dp[i] = (dp[before] + matchsticks[j]) % line
                    // console.log("改变的值",dp)
                    break;
                }
            }
        }
        console.log("===========断线", i,dp)
    }
    //如何确保最后一个会等于0
    return dp[allPicked] == 0
};

// console.log("火柴拼正方形",makesquare([3,3,3,3,4]))
console.log("火柴拼正方形", makesquare([1,1,2,2,2]))

最后 ​

上面中有什么不妥的，欢迎来讨论