文档章节

Arranging Coins

叶枫啦啦
 叶枫啦啦
发布于 2017/06/27 20:00
字数 417
阅读 12
收藏 0
点赞 0
评论 0

问题:

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

n = 5
The coins can form the following rows:
¤
¤ ¤
¤ ¤
Because the 3rd row is incomplete, we return 2.

 

Example 2:

n = 8
The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
Because the 4th row is incomplete, we return 3.

解决:

① 按照第i行会有i个硬币分配,当n<0时,停止计数即可。55ms

public class Solution {
    public int arrangeCoins(int n) {
        int i = 1;
        int count = 0;
        while(n > 0){
            n = n - i;
            i ++;
            if(n >= 0){
                count ++;
            }
        }
        return count;
    }
}
② 采用折半查找的方式:46ms

我们要找到满足以下条件的x:
1 + 2 + 3 + 4 + 5 + 6 + 7 + ... + x <= n
即sum_{i=1}^x i <= n (i从1到x求和)
对它进行简化求和可以得到(x * ( x + 1)) / 2 <= n
在这种情况下,使用
折半查找来慢慢缩小满足方程的x的范围

public class Solution {
    public int arrangeCoins(int n) {
        int start = 0;
        int end = n;
        while (start <= end){
            int mid = (end - start) / 2 + start; //(end - start) / 2 + start  VS  (start + end) >>> 1
            if ((0.5 * mid * mid + 0.5 * mid ) <= n){//公式
                start = mid + 1;
            }else{
                end = mid - 1;
            }

        }
        return start - 1;
    }
}

③ 利用一元二次方程求根的数学方法求解:47ms

我们已知:
1 + 2 + 3 + 4 + 5 + 6 + 7 + ... + x <= n
即sum_{i=1}^x i <= n
求和可得(x * ( x + 1)) / 2 <= n
利用一元二次方程求根公式可得:
x = 1 / 2 * (-sqrt(8 * n + 1)-1)(为负数,不符合题意) 
或 x = 1 / 2 * (sqrt(8 * n + 1)-1)

public class Solution {
    public int arrangeCoins(int n) {//(int)((sqrt(1 + 8 * (long)n)-1) / 2)
        return (int) ((Math.sqrt(1 + 8.0 * n) - 1) / 2);// java会将中间结果自动装箱为long型数据
    }
}

© 著作权归作者所有

共有 人打赏支持
叶枫啦啦
粉丝 3
博文 540
码字总数 260604
作品 0
海淀
决战Leetcode: easy part(51-96)

本博客是个人原创的针对leetcode上的problem的解法,所有solution都基本通过了leetcode的官方Judging,个别未通过的例外情况会在相应部分作特别说明。 欢迎互相交流! email: tomqianmaple@...

qq_32690999 ⋅ 02/09 ⋅ 0

硬币包含问题(最少找钱问题)

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. I......

golang_yh ⋅ 2016/02/13 ⋅ 0

Swift的反初始化deinit问题

在学习Swift反初始化的内容的时候,碰到一个问题。 struct Bank { static var coinsInBank = 10_000 static func vendCoins(var numberOfCoinsToVend: Int) ->Int { numberOfCoinsToVend = ......

rainckoo ⋅ 2015/02/01 ⋅ 1

Swift构造器(Initializer)与析构器(Deinitializer)

为了初始化结构体和类等类型的实例属性。 默认构造器 [html] view plaincopy struct Fahrenheit { var temperature: Doubleinit(){ temperature = 32.0 } } var f = Fahrenheit() //调用默认......

智捷课堂 ⋅ 2014/07/01 ⋅ 0

codecombat之Sarven沙漠25-37关代码分享

codecombat中国游戏网址:http://www.codecombat.cn/ 所有代码为javascript代码分享 25、捡闪亮东西的人 // 很快的获取最多的金币 loop { var coins = this.findItems(); var coinIndex = 0...

comA ⋅ 2015/08/30 ⋅ 0

开源P2P数字货币--Novacoin

Novacoin 是另一种P2P数字加密货币。和其他大多数货币不同的是在货币核心整合了保护机制,可以识别违规挖矿行为。总数量限制为20亿,数量相当可观,如需要还可以向上调整。 Novacoin是PPC的一...

红薯 ⋅ 2013/12/04 ⋅ 0

详解动态规划最少硬币找零问题--JavaScript实现

硬币找零问题是动态规划的一个经典问题,其中最少硬币找零是一个变种,本篇将参照上一篇01背包问题的解题思路,来详细讲解一下最少硬币找零问题。如果你需要查看上一篇,可以点击下面链接: ...

YinTokey ⋅ 05/27 ⋅ 0

开源货币--Feathercoin

Feathercoin 依据 Litecoin 设计,2013年4月发布,可以比 Litecoin 更频繁的调整挖矿难度。Feathercoin 会经常更新,加入新功能和改进,杜绝恶意的挖矿行为。 特性: 2.5 minute block targe...

红薯 ⋅ 2013/12/04 ⋅ 0

动态规划之硬币表示问题

问题描述: 有数量不限的硬币,币值为25分、10分、5分和1分,请编写代码计算n分有几种表示法。 求解思路: 这也是典型的动态规划问题,我们可以这样考虑:当只有1分的硬币时,n从1到n分别有多...

一贱书生 ⋅ 2016/11/22 ⋅ 0

再谈RestAPI最佳实践

本文由 伯乐在线 - Justin Wu 翻译自 javacodegeeks。 近一年半,我参与了两到三个项目的工作,这些项目涉及到大量供“外部”使用的Rest API,稍后我们会看到为什么要将“外部”这个词放在引...

山哥 ⋅ 2014/06/09 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

【elasticsearch】 随笔 Date datatype

一。时间类型的本质 首先json是没有时间类型的,对于es来说,时间类型的标示可以是下面三种情况 1.一个时间格式的字符串,如:"2014-11-27T08:05:32Z","2015-01-01" or "2015/01/01 12:10:3...

xiaomin0322 ⋅ 23分钟前 ⋅ 0

阿里云资源编排ROS使用教程

阿里云资源编排ROS详细内容: 阿里云资源编排ROS使用教程 资源编排(Resource Orchestration)是一种简单易用的云计算资源管理和自动化运维服务。用户通过模板描述多个云计算资源的依赖关系、...

mcy0425 ⋅ 26分钟前 ⋅ 0

适配器设计模式

1、适配器模式 把一个类的接口变换成客户端所期待的另一种接口 使原本因接口不匹配而无法在一起工作的两个类能够在一起工作 分为类的适配器模式和对象的适配器模式 2、类适配器模式 类的适配...

职业搬砖20年 ⋅ 30分钟前 ⋅ 0

npm操作报错 _stream_writable.js:61

有一天 不知道什么原因(估计和node的版本有关),无论你做什么npm的操作 都会报错/usr/local/lib/node_modules/npm/node_modules/readable-stream/lib/_stream_writable.js:61 这时候只要执...

lilugirl ⋅ 33分钟前 ⋅ 0

Eclipse安装插件的几种方式

Eclipse魅力之一就是支持可扩展的插件,来丰富自身的功能,这种方式也是建立在开源思想之上的。具体使用什么方式去安装插件,要看我们拿到的是什么。 1. 拿到的是一串URL,如http://subclips...

GordonNemo ⋅ 36分钟前 ⋅ 0

div图片叠加

css实现代码如下: <div style="position: relative;"><!--这个层为外面的父层,需设置相对位置样式--> <div style="position: absolute;"><!--子层,需设置绝对位置样式--> <i......

niithub ⋅ 37分钟前 ⋅ 0

作用域slot

如果父组件需要使用子组件中的内容怎么办,比如父组件需要控制子组件的显示 <div id="root"><child><template slot-scope="props"><h1>{{props.item}} <div>编辑</div></h1><......

金于虎 ⋅ 40分钟前 ⋅ 1

HongHu commonservice-eureka 项目构建过程

上一篇我们回顾了关于 spring cloud eureka的相关基础知识,现在我们针对于HongHu cloud的eureka项目做以下构建,整个构建的过程很简单,我会将每一步都构建过程记录下来,希望可以帮助到大家...

明理萝 ⋅ 43分钟前 ⋅ 1

xml和对象的相互转化

@Data//setter和getter方法,toString和equals,hashcode方法@EqualsAndHashCode//代表重写equals和hashcode方法@XmlAccessorType(XmlAccessType.FIELD)public class Classroom {@X......

拐美人 ⋅ 43分钟前 ⋅ 0

tableView cell的高度 分组头部尾部的高度 自适应

@property (nonatomic) CGFloat rowHeight; // default is UITableViewAutomaticDimension@property (nonatomic) CGFloat sectionHeaderHeight; // default is UITableViewA......

娜一片蓝色星海 ⋅ 44分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部