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.
排列硬币。你总共有 n 枚硬币,你需要将它们摆成一个阶梯形状,第 k 行就必须正好有 k 枚硬币。给定一个数字 n,找出可形成完整阶梯行的总行数。n 是一个非负整数,并且在32位有符号整型的范围内。
我给出一个网友的思路。
时间O(1)
空间O(1)
Java实现
1 class Solution { 2 public int arrangeCoins(int n) { 3 return (int) (Math.sqrt((double) 2 * n + 0.25) - 0.5); 4 } 5 }
JavaScript实现
1 /** 2 * @param {number} n 3 * @return {number} 4 */ 5 var arrangeCoins = function (n) { 6 return Math.floor(Math.sqrt(2 * n + 1 / 4) - 1 / 2); 7 };
[LeetCode] 441. Arranging Coins
原文:https://www.cnblogs.com/cnoodle/p/13222616.html