leetcode
leetcode 401 ~ 450
排列硬币

排列硬币

难度:

标签:

题目描述

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

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

 

示例 1:

输入:n = 5
输出:2
解释:因为第三行不完整,所以返回 2 。

示例 2:

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

 

提示:

  • 1 <= n <= 231 - 1

代码结果

运行时间: 27 ms, 内存: 15.9 MB


/*
 * 题目思路:
 * 给定一个数字 n,表示总共有 n 枚硬币。
 * 按照阶梯状排列硬币,要求每一行硬币的数量依次递增,
 * 即第 i 行必须正好有 i 枚硬币。
 * 最后一行可以不完整。
 * 问可以形成多少完整的行。
 * 使用 Java Stream 实现。
 */
import java.util.stream.IntStream;
public class Solution {
    public int arrangeCoins(int n) {
        return (int) IntStream.iterate(1, i -> i + 1)
            .takeWhile(i -> (n -= i) >= 0)
            .count();
    }
}

解释

方法:

这道题目可以使用二分搜索来解决。首先,我们知道对于k行阶梯,需要的硬币总数是前k项的和,即(k * (k + 1)) / 2。我们的目标是找到最大的k,使得(k * (k + 1)) / 2 <= n。通过二分搜索,我们可以在1到n之间寻找这样的k值,直到找到满足条件的最大k。

时间复杂度:

O(log n)

空间复杂度:

O(1)

代码细节讲解

🦆
在二分搜索中,为什么可以确定使用1到n作为初始的搜索范围?
在这个问题中,我们知道每一行至少需要1枚硬币,因此最少的行数可以是1。同时,因为最坏的情况是每一行只有1枚硬币,这样最多可以有n行(每行1枚硬币)。因此,潜在的行数k的范围从1到n是合理的,这也是我们设置二分搜索的初始范围为1到n的原因。
🦆
二分搜索过程中,若`sum_total(mid) == n`直接返回mid的理由是什么,这种情况下的阶梯是完整的吗?
如果`sum_total(mid) == n`,意味着前mid行可以完全使用n枚硬币构成,每一行正好满足行数所需硬币数的条件,没有多余也没有缺少。这说明找到了一个完整的阶梯结构,mid正是我们要找的最大行数。因此,这种情况下,阶梯是完整的,直接返回mid是合理的。
🦆
函数`sum_total`中的计算逻辑`if n % 2 == 0`看起来似乎有些复杂,它的目的是什么?是否有更简单的方法来计算前n项和?
这个计算逻辑似乎是为了应对n为奇数和偶数的情况,但实际上这种处理方式有错误和不必要的复杂性。前n项和的计算可以直接使用公式`(n * (n + 1)) / 2`,这个公式适用于任何整数n,既简单又准确。
🦆
为什么在`sum_total(mid) > n`时,将搜索的右边界设置为`mid - 1`?这是否意味着mid已经不能作为可能的解?
如果`sum_total(mid) > n`,意味着前mid行所需的硬币总数超过了我们拥有的硬币数n,因此mid行不可能完全使用n枚硬币构成。这表明mid太大了,我们需要在更小的行数中寻找答案。因此,将搜索的右边界设置为`mid - 1`是合理的,确实意味着mid不可以作为可能的解。

相关问题