美文网首页
441-排列硬币

441-排列硬币

作者: 饮酒醉回忆 | 来源:发表于2019-09-26 09:48 被阅读0次

    排列硬币

    题目

    你总共有n枚硬币,你需要将它们摆成一个阶梯形状,第k行就必须正好有k枚硬币。

    给定一个数字n,找出可形成完整阶梯行的总行数。

    n 是一个非负整数,并且在32位有符号整型的范围内。

    示例 1:

    n = 5

    硬币可排列成以下几行:
    ¤
    ¤ ¤
    ¤ ¤

    因为第三行不完整,所以返回2.
    示例 2:

    n = 8

    硬币可排列成以下几行:
    ¤
    ¤ ¤
    ¤ ¤ ¤
    ¤ ¤

    因为第四行不完整,所以返回3.

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/arranging-coins
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    思路

    最简单的思路就是依次行数减掉

    使用数学公式是最快的

    代码

    最简单的思路

    class Solution {
        public int arrangeCoins(int n) {
            int row = 1;
            while(n >= row){
                n -= row++;
            }
            return row-1;
        }
    }
    

    数学公式

    class Solution {
        public int arrangeCoins(int n) {
            return (int)((-1+Math.sqrt(1+8*(long)n))/2);
        }
    }
    

    相关文章

      网友评论

          本文标题:441-排列硬币

          本文链接:https://www.haomeiwen.com/subject/mcunectx.html