Leetcode 解析 (441. Arranging Coins)

所有的平静都是来自于认识到事物并非我们所想的那样。

闲来无事刷道题呗。

题目介绍

简单的说,假如你有 N 枚硬币,需要摆成阶梯的形式,即第 N 行一定有 N 个硬币。求最多能摆多少行。

题目分析

最直观的解法,因为我们知道第 N 行必须要需要 N 个硬币。所以我们只要从第一行开始,每加一行减掉对应所需 X 个。什么时候总数不够了,那么游戏到此结束。

解法一


/**
     * @param Integer $n
     * @return Integer
     */
    function arrangeCoins($n)
{
        $i = 1;
        if ($n == 0) return 0;
        while ($n > 0) {
            $n -= $i;
            $i++;
            if ($n < $i) return $i - 1;
        }
    }

这种解法时间复杂度 O(n),空间复杂度 O(1)。空间复杂度无需再优化了,可以看看能否在时间上动动手脚。

解法二

这时间上优化先看看从 O(n) 到 O(log2n) 。台阶 1-n ,本质上就是一个有序的集合,既然是有序,当然就可以用到 Binary Search 的思想。每次找到中位数,计算中位数m(即第m行)所需要的硬币总和和给定的硬币数进行比较,不断压缩空间。

/**
     * @param Integer $n
     * @return Integer
     */
    function arrangeCoins($n)
    {
        $left = 0;
        $right = $n;
        while ($left < $right) {
            $middle = $left + (($right - $left + 1) >> 1);
            //$middleSum=($middle*$middle+$middle)/2;
            $middleSum = $middle * ($middle + 1) / 2;
            if ($middleSum <= $n) {
                $left = $middle;
            } else {
                $right = $middle - 1;
            }
        }
        return $left;
    }
本作品采用《CC 协议》,转载必须注明作者和本文链接
吴亲库里
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!