专栏首页蛮三刀的后端开发专栏【Leetcode】【python】Arranging Coins

【Leetcode】【python】Arranging Coins

Arranging Coins

标准答案代码来自书影博客

题目大意

你有n枚硬币,想要组成一个阶梯形状,其中第k行放置k枚硬币。 给定n,计算可以形成的满阶梯的最大行数。 n是非负整数,并且在32位带符号整数范围之内。

解题思路

数学方法

每行想填满需要k*(k+1)/2个硬币

二分枚举答案(Binary Search)

其实还是k*(k+1)/2的思路啊

代码

数学方法

class Solution(object):
    def arrangeCoins(self, n):
        k = 0
        while k*(k+1)/2 <= n:
            k += 1
        return k-1

二分枚举答案(Binary Search)

class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        l, r = 0, n
        while l <= r:
            m = (l + r) / 2
            if m * (m + 1) / 2 > n:
                r = m - 1
            else:
                l = m + 1
        return r

我提交的

class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        total = 0
        row = 1
        if n == 0:
            return 0
        if n == 1:
            return 1
        while True:
            if n - total < row:
                return row - 1
            elif n - total == row:
                    return row
            else:
                total += row
                row += 1

总结

题目较为简单,思路都大同小异,我的解法还是比较2B(体现在速度巨慢),主要学习的是二分法。 看了一个二分法详解可以有空多看看。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [Leetcode][python]Pascal's Triangle/Pascal's Triangle II/杨辉三角/杨辉三角 II

    后端技术漫谈
  • [Leetcode][python]Valid Palindrome/验证回文串

    判断一个字符串是否是回文字符串,只考虑字母和数字,并且忽略大小写。 注意点: 空字符串在这里也定义为回文串

    后端技术漫谈
  • [Leetcode][python]Implement strStr()/KMP算法

    两种思路: 1. 直接一个个匹配过去(遍历) 2. KMP算法:参考 http://www.ruanyifeng.com/blog/2013/05/...

    后端技术漫谈
  • 回溯:系列经典题目

    对于回溯算法,一开始接触感觉还是挺难的,随着刷到的题目的数量增多,慢慢也可以总结出来相应的套路出来。大家一起来看看下面的伪代码

    鹏-程-万-里
  • LeetCode第28/35题

    Return the index of the first occurrence of needle in haystack, or -1 if needle ...

    用户3112896
  • hdu1021

    @坤的
  • 力扣79——单词搜索

    单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

    健程之道
  • 【leetcode算法-搜索插入位置】

    给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

    用户5640963
  • Leetcode 1-10

    常规方法:使用双重循环,第一重从左往右固定索引,计算需要查找的结果,第二层循环从固定索引出发依次向右查找第一层计算的结果。时间复杂度\(O(n^2)\), 空间...

    努力努力再努力F
  • 2020-09-12:手撕代码:最小公倍数,复杂度多少?

    1.【更相减损法】=【等值算法】,避免了取模运算,但是算法性能不稳定,最坏时间复杂度为O(max(a, b)))。

    福大大架构师每日一题

扫码关注云+社区

领取腾讯云代金券