j
jaryue
V1
2023/04/09阅读:18主题:默认主题
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 炫耀一下:
作者介绍
j
jaryue
V1