leetcode441. 排列硬币

leetcode

题目描述

你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。

给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。

示例 1：

输入：n = 5 输出：2 解释：因为第三行不完整，所以返回 2 。 示例 2：

输入：n = 8 输出：3 解释：因为第四行不完整，所以返回 3 。

提示：

1 <= n <= 231 - 1

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

解题思路

法1

数学:
根据题意,我们可以知道,n=x*(x+1)/2,因为层数每一层递增一个,所以它们的和为
n=1+2+3+....+x(x为第x层) 利用公式 x=(-1+(8n+1)^1/2)/2
我们可以直接使用原生的math.sqrt函数进行开方

• 时间复杂度(O(1))
• 空间复杂度(O(1))

执行结果

法1

func arrangeCoins(n int) int {
 return int((math.Sqrt(float64(8*n+1))) - 1)/2
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 2 MB , 在所有 Go 提交中击败了 79.55% 的用户 通过测试用例： 1335 / 1335 炫耀一下: