【刷题日记】473. 火柴拼正方形

简介: 本次刷题日记的第 52 篇,力扣题为:473. 火柴拼正方形,中等

本次刷题日记的第 52 篇,力扣题为:473. 火柴拼正方形中等

一、题目描述:

image.png

火柴拼正方形,有点意思,回忆一下童年的手工课


二、这道题考察了什么思想?你的思路是什么?

题目说的比较明确,看完题目可能瞬间会有想法,可是一下子好像不知道如何去落地,来仔细看看题目要求

  • 题目给出一个数组,是每一个火柴的长度
  • 题目要求我们用给出的火柴拼出一个正方形,要求火柴不能被折断,需要我们正好能拼出一个正方形

这么一看,火柴若是摆着我们面前,能不能拼出要求的正方形,我们尝试一下就知道了,但是我们如何用程序的方式来展现呢,如何分步骤来完整这个拼接的过程 呢?

分析

拼接一个完整正方形的前提,我们要明白,火柴是不让折断的,那么我们是否应该在拼接之前,先计算一下,给出的火柴长度,加起来是否满足一个正方形的周长,我们只需要火柴全部加起来能被 4 整除即可

另外我们是不是会先找出最长的火柴来作为第一根火柴进行拼接,然后再去找合适的火柴进行适配

类似于这样打乱的火柴棍,我们用手拼接正方形的话,我们肯定是先会拿出最长的火柴来进行拼接

image.png

我们就可以先从长到短的排个队,如果不从大到小的排个队的话,我们后续进行筛选的操作,无用功太多

image.png

开始拼接正方形的时候,拿出第一根做正方形的其中一边,如果当前的这个长度,是小于需要拼接正方形的边长,那么我们就再拿次长的进行拼接,如果是已经等于需要拼接正方形的边长,那么我们再拼接第 2 条边image.png

image.png

同理

image.png

最终,我们就可以拼接成我们期望的正方形

image.png

那么我们在编码的时候,我们如何做到先选择第一根长的,然后再去匹配后面的每一根呢?

还记得回溯法吗,上面的操作方式就可以使用回溯的方式来进行实现, 最后所有的火柴都用上了,且拼接成一个完整的正方形,那么说明给出的火柴是 ok 的

三、编码

根据上述逻辑和分析,我们就可以翻译成如下代码

注意需要将火柴按大到小的排序,否则会出现时间超限的情况,因为需要类似于如下的案例,就会时间超限,做了很多无用功

image.png

编码如下:

func makesquare(matchsticks []int) bool {
    // 校验给出的火柴总长度是否可以被 4 整除
    var total int
    for _, stick := range matchsticks {
        total += stick
    }
    if total%4 != 0 {
        return false
    }
    // 排序数组,从大到小
    sort.Sort(sort.Reverse(sort.IntSlice(matchsticks))) 
    // 开始一个一个的去拼接
    avg := total / 4
    var sqt = [4]int{}
    var dfs func(int) bool
    dfs = func(idx int) bool {
        // 已经将 matchsticks 递归完毕
        if idx == len(matchsticks) {
            return true
        }
        for i := range sqt {
            sqt[i] += matchsticks[idx]
            if sqt[i] <= avg && dfs(idx + 1) {
                return true
            }
            sqt[i] -= matchsticks[idx]
        }
        // 程序能走到这里,说明有火柴没有用上,因此直接返回 false
        return false
    }
    return dfs(0)
}

四、总结:

image.png

此处的空间复杂度相对来说比较好看出来,是 O(n) ,因此我们递归消耗了栈空间,因此是 O(n) ,那么此处的时间复杂度是多少呢,我们可以仔细来看看

按照上述的编码方式,我们可以发现,题目给出的 n 根火柴,都有机会放在 4 条边的任意一边,知道满足可以拼接成一个完整的正方形即可,因此时间复杂度是 O(4^n)

原题地址:473. 火柴拼正方形

今天就到这里,学习所得,若有偏差,还请斧正

欢迎点赞,关注,收藏

朋友们,你的支持和鼓励,是我坚持分享,提高质量的动力

image.png

好了,本次就到这里

技术是开放的,我们的心态,更应是开放的。拥抱变化,向阳而生,努力向前行。

我是阿兵云原生,欢迎点赞关注收藏,下次见~

相关文章
|
前端开发 JavaScript
HTML+CSS+JAVASCRIPT实现——情人节表白情书
本文主要介绍如何使用HTML三件套来实现制作一封情人节表白情书,富含情谊与爱,打动女生的心灵
791 2
HTML+CSS+JAVASCRIPT实现——情人节表白情书
|
2月前
|
人工智能
AcWing 271. 杨老师的照相排列
AcWing 271. 杨老师的照相排列
29 0
AcWing 4261. 孤独的照片(每日一题)
AcWing 4261. 孤独的照片(每日一题)
|
测试技术 索引 Cloud Native
【刷题日记】120. 三角形最小路径和
本次刷题日记的第 38 篇,力扣题为:120. 三角形最小路径和 ,中等
|
Cloud Native
【刷题日记】1184. 公交站间的距离
好久不刷题,没有锻炼思维,感觉脑袋都要生锈了,刷题感觉还是要从简单题刷题才能慢慢找到感觉
|
存储 前端开发 JavaScript
你小子!过年了,写了一个拼图小游戏来拼掘金兔年礼盒,来玩玩不?
你小子!过年了,写了一个拼图小游戏来拼掘金兔年礼盒,来玩玩不?
212 2
【AcWing每日一题】4261. 孤独的照片
【AcWing每日一题】4261. 孤独的照片
76 0
【代码分享】【像极了恋爱】甜甜的汤圆,祝丽姿元宵快乐(表白特效)
【代码分享】【像极了恋爱】甜甜的汤圆,祝丽姿元宵快乐(表白特效)
124 0
|
机器学习/深度学习 C++
蓝桥杯C++小朋友崇拜圈
蓝桥杯C++小朋友崇拜圈
117 0
【寒假每日一题】AcWing 4652. 纸张尺寸
目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解
88 0