LeetCode 473 Matchsticks to Square

题目描述

Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.

Example 1:

Input: [1,1,2,2,2]
Output: true

Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

Example 2:

Input: [3,3,3,3,4]
Output: false

Explanation: You cannot find a way to form a square with all the matchsticks.

Note:

The length sum of the given matchsticks is in the range of 0 to 10^9.
The length of the given matchstick array will not exceed 15.

题目分析

题目的问题抽象出来就是:在n个数中能否找出4组数,使得他们的和相等。

题目显然是一个递归问题,循环条件是4组数的和,返回条件是将n个数都用到后,每组数的和是否相等。

注意

  1. 应该先对数组排序,并从大到小进行递归,因为两个大数相加更可能超过正方形的边长,所以递归深度更少。否则会超时。
  2. 在第一次做时,我额外用了boolean数组来判断nums的对应元素是否使用过,但是这些操作在递归中就包括了。

代码

public boolean makesquare(int[] nums) {
    if (nums == null || nums.length < 4) {
        return false;
    }

    int tmp = 0;
    for (int i : nums) {
        tmp += i;
    }

    if (tmp % 4 != 0) {
        return false;
    }

    Arrays.sort(nums);
    return robot(0, nums, new int[4], tmp / 4);
}

private boolean robot(int pos, int[] nums, int[] sum, int each) {
    if (pos == nums.length) {
        return sum[0] == each && sum[1] == each && sum[2] == each;
    }

    for (int i = 0; i < 4; i++) {
        int index = nums.length - 1 - pos;
        if (sum[i] + nums[index] > each) {
            continue;
        }
        sum[i] += nums[index];
        if (robot(pos + 1, nums, sum, each)) {
            return true;
        }
        sum[i] -= nums[index];
    }

    return false;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏诸葛青云的专栏

C语言位运算的妙用你知道多少?

位运算在驱动开发中是经常遇到的,尤其是置0和置1。既要指定的位数发生变化,又不能改变其它位的值,还要高效率的编写代码,这时候技巧就很重要了。在位运算中有几个符号...

1654
来自专栏余林丰

Effective Java通俗理解(上)

  这篇博客是Java经典书籍《Effective Java(第二版)》的读书笔记,此书共有78条关于编写高质量Java代码的建议,我会试着逐一对其进行更为通俗...

2697
来自专栏老马说编程

(27) 剖析包装类 (中) / 计算机程序的思维逻辑

本节继续探讨包装类,主要介绍Integer类,下节介绍Character类,Long与Integer类似,就不再单独介绍了,其他类基本已经介绍完了,不再赘述。 ...

22110
来自专栏java一日一条

30 分钟 Java Lambda 入门教程

Lambda作为函数式编程中的基础部分,在其他编程语言(例如:Scala)中早就广为使用,但在Java领域中发展较慢,直到java8,才开始支持Lambda。

2014
来自专栏微信公众号:Java团长

Java知识点集锦

答:不是。Java中的基本数据类型只有8个:byte、short、int、long、float、double、char、boolean;除了基本类型(primi...

1231
来自专栏阮一峰的网络日志

Base64笔记

昨天的《MIME笔记》中提到,MIME主要使用两种编码转换方式----Quoted-printable和Base64----将8位的非英语字符转化为7位的ASC...

1664
来自专栏我爱编程

Day18内建模块collections&base64collectionsbase64

collections collections是Python内建的一个集合模块,提供了许多有用的集合类。 namedtuple >>> from collect...

4248
来自专栏阿杜的世界

【转】Java知识点集锦(1~40)

答:不是。Java中的基本数据类型只有8个:byte、short、int、long、float、double、char、boolean;除了基本类型(primi...

1052
来自专栏依乐祝

[译]聊聊C#中的泛型的使用(新手勿入)

今天忙里偷闲在浏览外文的时候看到一篇讲C#中泛型的使用的文章,因此加上本人的理解以及四级没过的英语水平斗胆给大伙进行了翻译,当然在翻译的过程中发现了一些问题,因...

1184
来自专栏偏前端工程师的驿站

(cljs/run-at (->JSVM :browser) "语言基础")

前言  两年多前知道cljs的存在时十分兴奋,但因为工作中根本用不上,国内也没有专门的职位于是搁置了对其的探索。而近一两年来又刮起了函数式编程的风潮,恰逢有幸主...

2217

扫码关注云+社区

领取腾讯云代金券