题目:
桌上有 n 堆力扣币,每堆的数量保存在数组 coins 中。我们每次可以选择任意一堆,拿走其中的一枚或者两枚,求拿完所有力扣币的最少次数。
示例 1:
输入:[4,2,1]
输出:4
解释:第一堆力扣币最少需要拿 2 次,第二堆最少需要拿 1 次,第三堆最少需要拿 1 次,总共 4 次即可拿完。
示例 2:
输入:[2,3,10]
输出:8
限制:
1 <= n <= 4
1 <= coins[i] <= 10
代码:
通过率:
思路:
这道题初看有些犯难,我想了很久要如何解题。后来决定先用数学方法将题目思路整理出来,再来写代码。
题目要求找出拿完所有力扣币的最少次数,在这条前提下,能拿两个力扣币就绝对不能拿一个,这样可以节约步骤。那么问题是,我们该如何确定取两个力扣币的次数?于是我想到了通过取余数来判断的方法。首先建立循环给数组内的数据元素编号,用这个数除以2,假如有余数,则说明这个数据除了拿几次两个力扣币以外,还需要单独拿一次一个力扣币的步骤。在这里利用if-else语句进行判断,余数为0,则直接用数据元素与2相除得到取完这堆硬币的拿取次数;余数不为0,拿取次数就是数据元素与2相除得到的商再加上1(拿一个力扣币的步骤)之和。最后在判断语句外将拿取次数涌单独的变量总和起来,等到循环结束,直接输出这个变量即可。这个变量每经历一次循环都会发生改变,拿取次数会逐渐相加。
这里指的注意的是,当数组元素等于1时的情况,1除以2取余数的话是等于1的,假如这种情况没有单独提出来,很容易在代码里造成误区,导致输出结果错误。
通过率的内存消耗还算合格,执行用时稍显拉跨,我在力扣的官方题解里面看了一圈,实验之下并没有找到很好的方法,解出来的思路代码大同小异,我看到有方法说用reduce+ceil方法向上取整的,但是我输入他的代码时输出结果却报错。
后来翻到下面这中方法,写的比我的代码简洁很多,省略了很多步骤,但是通过率差强人意。
代码: