本文主要是介绍LeetCode 441. Arranging Coins（排列硬币），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述：
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 = 5The coins can form the following rows:
¤
¤ ¤
¤ ¤Because the 3rd row is incomplete, we return 2.
Example 2:
n = 8The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤Because the 4th row is incomplete, we return 3.
你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
给定一个数字 n，找出可形成完整阶梯行的总行数。
n 是一个非负整数，并且在32位有符号整型的范围内。
示例 1:
n = 5硬币可排列成以下几行:
¤
¤ ¤
¤ ¤因为第三行不完整，所以返回2.
示例 2:
n = 8硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤因为第四行不完整，所以返回3.
思路：
根据数学等差数列的相关知识，阶梯的前n行，一共有枚硬币，其中
，
；
或者是有枚硬币，其中
，
；
现在有n枚硬币组成阶梯，如果前k行的硬币总数小于等于n，即；且前k+1行的硬币总数大于n，即
，则k就是我们要找的答案。
n枚硬币组成的阶梯绝对不会超过n行，我们可以二分查找k值。
实现（C++）:
class Solution {public:int arrangeCoins(int n) {if(n<1){return n;}int begin = 0;int end =n;while(begin<=end){long long mid = begin+(end-begin)/2;long sum = mid*(mid+1)/2;if(sum>n)end = mid-1;elsebegin = mid+1;}return begin-1;}
};
这篇关于LeetCode 441. Arranging Coins（排列硬币）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
