文档章节

leetcode: 441. Arranging Coins

开源中国首席精神砖家
 开源中国首席精神砖家
发布于 2017/02/13 22:36
字数 301
阅读 13
收藏 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.

 

 

Subscribe to see which companies asked this question.

 

解法1:直接计算:

# -*- coding:utf-8 -*- 
# leetcode solutions
# 441. Arranging Coins
# coding by Dennis Lu
# 2017/02/11

class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """

        count = 0
        row_point = 2
        total = 1

        while(total <= n):
        	total += row_point
        	row_point += 1
        	count += 1
        return count

解法2:二分法搜索:

# -*- coding:utf-8 -*- 
# leetcode solutions
# 441. Arranging Coins
# coding by Dennis Lu
# 2017/02/11

class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """

        first = 1
        last = n
        mid = int((n + 1) / 2)
        
        

        while(1):
        	num0 = (1 + mid) * mid * 0.5
        	num1 = (1 + mid + 1) * (mid + 1) * 0.5

        	if((num0 <= n) and (num1 > n)):
        		return mid
        	if(num0 > n):
        		last = mid - 1
        		mid = int((first + last) / 2)
        		continue
        	if(num1 <= n):
        		first = mid + 1
        		mid = int((first + last) / 2)

解法3:解不等式:

# -*- coding:utf-8 -*- 
# leetcode solutions
# 441. Arranging Coins
# coding by Dennis Lu
# 2017/02/11

import math

class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """

        return int(math.sqrt(2 * n + 0.25) - 0.5)

3的算法时间复杂度O(1)

© 著作权归作者所有

开源中国首席精神砖家

开源中国首席精神砖家

粉丝 0
博文 12
码字总数 3206
作品 0
广州
其他
私信 提问
Leetcode 441. Arranging Coins

版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn.net/Quincuntial/article/details/82260959 文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Descr...

SnailTyan
2018/08/31
0
0
LeetCode算法题-Arranging Coins(Java实现)

这是悦乐书的第229次更新,第241篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第96题(顺位题号是441)。您想要以楼梯形状形成总共n个硬币,其中每个第k行必须具有恰好k个硬...

小川94
01/13
0
0
决战Leetcode: easy part(51-96)

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

qq_32690999
2018/02/09
0
0
【DP】518. Coin Change 2

问题描述: You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may a......

牛奶芝麻
06/08
0
0
分配硬币 Arranging Coins

问题: 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 r......

叶枫啦啦
2017/06/27
21
0

没有更多内容

加载失败,请刷新页面

加载更多

SpringBoot 集成MongoDB

一、MongoDB 简介 MongoDB 如今是最流行的 NoSQL 数据库,被广泛应用于各行各业中,很多创业公司数据库选型就直接使用了 MongoDB,但对于大部分公司,使用 MongoDB 的场景是做大规模数据查询...

zw965
14分钟前
10
0
使用 Envoy 和 AdGuard Home 阻挡烦人的广告

> 原文链接:使用 Envoy 和 AdGuard Home 阻挡烦人的广告 通常我们使用网络时,宽带运营商会为我们分配一个 DNS 服务器。这个 DNS 通常是最快的,距离最近的服务器,但会有很多问题,比如: ...

米开朗基杨
47分钟前
14
0
springboot之全局处理异常封装

springboot之全局处理异常封装 简介 在项目中经常出现系统异常的情况,比如NullPointerException等等。如果默认未处理的情况下,springboot会响应默认的错误提示,这样对用户体验不是友好,系...

Purgeyao
58分钟前
22
0
cookie

cookie: n. 饼干;小甜点 为什么会引入Cookie(在客户端保持http状态) 因为http协议是一种无状态协议,web服务器本身不能识别出哪些请求是同一个服务器发送的,浏览器的每一次请求都是独立...

五公里
今天
23
0
PHP常用函数

<?php/** * 获取客户端IP * @return [string] [description] */function getClientIp() { $ip = NULL; if (isset($_SERVER['HTTP_X_FORWARDED_FOR'])) { $arr = explode('......

半缘修道半缘君丶
今天
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部