使用不变量来确定二分搜索中的边界条件

Question

我正在尝试解决 LeetCode.com 上的排列硬币：

您总共有 n 个硬币，您想要形成楼梯形状，其中每 k 行 必须正好有 K 个硬币。给定 n，找到可以形成的完整楼梯行的总数。n 是一个非负整数，适合 32 位有符号整数的范围。 当 n=5 时，输出为：2。

根据给出的解决方案，我们可以将问题重新表述为：

找到最大k，以便k*(k+1)/2<=N

我的不变性(灵感来自这个 Quora 答案(：

我有一个从 L 到 R 的间隔，使得a[L]<=k*(k+1)/2<=N和a[R]>k*(k+1)/2<=N.然后，在我检查了两者之间的元素 M 之后，我将 L 或 R 设置为 M，保持不变量。

但我不确定我的不变量是否正确：

1. 我不确定这是否会给我 k 的maximum值;
2. 我应该继续迭代while(l<r)还是while(l<=r)？l和r是用于迭代的常用两个指针;
3. 在我计算mid为k*(k+1)/2后，我应该使用l=mid+1还是l=mid(同样r=mid-1或r=mid(？

谢谢！

Answer 1

你把问题弄得太复杂了，从逻辑上讲，你需要做的就是：

int number = n; //the number you are getting
int index = 0;
int iteration = 0;
while(index <= number){
iteration++;
index += iteration;
}
return iteration; //this will be the maximum complete level, the code is incomplete but this sounds like an assignment so good luck!!

对于更有效的解决方案，您可以使用Guass公式对数字求和，例如，对数字1-100求和，您可以执行以下操作： 101*100/2 或 (n+1(*n/2.. 因此，如果您感到舒适，您可以：

int number = n; //the number you are getting
double iteration = sqrt(number/2.0)*2;//remember to add the brackets 
//inside.
if(iteration - Math.floor(iteration) >= 0.5)return iteration + 1;
else return iteration;

如果有任何错误，请随时纠正我...