LeetCode算法题-Arranging Coins(Java实现)

作者 : 开心源码 本文共1281个字,预计阅读时间需要4分钟 发布时间: 2022-05-12 共149人阅读

这是悦乐书的第229次升级,第241篇原创

01 看题和准备

今天详情的是LeetCode算法题中Easy级别的第96题(顺位题号是441)。您想要以楼梯形状形成总共n个硬币,其中每个第k行必需具备刚好k个硬币。给定n,找到可以形成的完整楼梯行的总数。n是一个非负整数,适合32位有符号整数的范围。例如:
n = 5
硬币可以形成以下行:
¤
¤¤
¤¤
由于第3行不完整,我们返回2。

n = 8
硬币可以形成以下行:
¤
¤¤
¤¤¤
¤¤
由于第4行不完整,我们返回3。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

由于每一行所表示的硬币需要和行号相等,因而我们可以直接对n从1开始做减法。使用一个变量从1开始做自加,n每次减去该变量,直到n不大于0,最后判断n能否等于0,等于0就返回该变量,否则返回该变量减1。

public int arrangeCoins(int n) {    int i = 0;    while (n > 0) {        i++;        n -= i;    }    return n == 0 ? i : i-1 ;   }

03 第二种解法

利用二分法和等差数列的特性。每行楼梯对应的硬币数,可以构成一个公差为1的等差数列,前n行楼梯总共需要(1+n)*n/2个硬币,我们可以使用二分法,不断取中间值,获取对应的硬币数,而后和n做比较,假如等于,直接返回当前中间数,假如小于,低位变成中间位加1,假如大于,高位变成中间位减1,最后返回高位。

在计算等差数列前n个数之和时,使用long类型,以免溢出。

public int arrangeCoins2(int n) {    int low = 0, high = n;    while (low <= high) {        int mid = low + (high - low)/2;        long sum = (1L+mid)*mid/2;        if (sum == n) {            return mid;        } else if (sum < n) {            low = mid+1;        } else {            high = mid-1;        }    }    return high;}

04 第三种解法

还是利用等差数列的求和公式x=(1+n)×n/2,可以反向推导求n的值。

2x = (1+n)*n;

n^2 + n – 2x = 0;

此时就变成解一元二次方程的根了,2a分之负b加减根号下b的平方减4乘以a乘以c,由于n大于0,所以只用求正根就可。

n = (-1 + Math.sqrt(1-4×(-2x)))/2;

n = (-1 + Math.sqrt(1+8x))/2;

其中,我们需要注意数据类型的隐式转换,Math.sqrt返回的double类型的数据,因而8最好是double或者者long类型的。

public int arrangeCoins3(int n) {    return (int)((-1 + Math.sqrt(1 + 8.0*n)) / 2);}

05 小结

算法专题目前已连续日更超过两个月,算法题文章96+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是一律内容,假如大家有什么好的解法思路、建议或者者其余问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » LeetCode算法题-Arranging Coins(Java实现)

发表回复