leetcode441. Arranging Coins

Ali_ 發布于2019-08-16 17:30 / 587人閱讀

摘要：題目要求用個硬幣搭臺階，要求第級臺階必須有個硬幣。思路和代碼反過來講，如果要搭級臺階，那么級臺階共包含個硬幣。因此我們只需要找到可以搭建的臺階的邊界，并采用二分法將邊界不斷縮小直到達到最大的臺階數。

題目要求

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個硬幣最多能夠搭多少級臺階？
如五個硬幣最多能夠搭兩級臺階，8個硬幣最多搭三級臺階。

思路和代碼

反過來講，如果要搭k級臺階，那么k級臺階共包含(k+1) * k / 2個硬幣。因此我們只需要找到可以搭建的臺階的邊界，并采用二分法將邊界不斷縮小直到達到最大的臺階數。

    public int arrangeCoins(int n) {
        long rgt = (int) (Math.sqrt(n) * Math.sqrt(2) + 1);
        long lft = 0;
        while(lft <= rgt) {
            long mid = lft + (rgt -lft) / 2;
            long total = (mid + 1) * mid / 2;
            if(total <= n) {
                lft = mid + 1;
            }else {
                rgt = mid - 1;
            }
        }
        return (int)lft-1;
    }

云服務器 GPU云服務器 Arranging Coins Leetcod LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/74544.html

[LeetCode] 441. Arranging Coins

Problem 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...

avwu 2019-08-19 11:13 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
[LeetCode - Dynamic Programming] Coin Change

摘要：解題思路動態規劃，用表示總價為的最小紙幣張數，很容易想到狀態轉移方程當然前提是要大于紙幣金額數。表示取一張面額加上合計為的最小紙幣數。另題目要求無法合計出的金額，要返回，所以要作特殊處理，否則就會返回元素初始化值代碼 Coin ChangeYou are given coins of different denominations and a total amount of money...

dackel 2019-08-16 10:26 評論0 收藏0
leetcode322. Coin Change

摘要：傳入的參數為手上有的紙幣的面額以及希望兌換的面額。這里假設紙幣的數量是無窮的。這題本質上考察的是動態規劃思想。這里有兩種動態規劃的方法，分別從遞歸和非遞歸的角度解決這個問題。具體的情況還是要看數據的分布情況來確定選擇哪種方法。題目要求 You are given coins of different denominations and a total amount of money ...

kohoh_ 2019-08-15 14:41 評論0 收藏0