資訊專欄INFORMATION COLUMN
摘要：題目要求用個(gè)硬幣搭臺(tái)階，要求第級(jí)臺(tái)階必須有個(gè)硬幣。思路和代碼反過來講，如果要搭級(jí)臺(tái)階，那么級(jí)臺(tái)階共包含個(gè)硬幣。因此我們只需要找到可以搭建的臺(tái)階的邊界，并采用二分法將邊界不斷縮小直到達(dá)到最大的臺(tái)階數(shù)。
題目要求
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個(gè)硬幣搭臺(tái)階，要求第k級(jí)臺(tái)階必須有k個(gè)硬幣。問n個(gè)硬幣最多能夠搭多少級(jí)臺(tái)階？
如五個(gè)硬幣最多能夠搭兩級(jí)臺(tái)階，8個(gè)硬幣最多搭三級(jí)臺(tái)階。
反過來講，如果要搭k級(jí)臺(tái)階，那么k級(jí)臺(tái)階共包含(k+1) * k / 2個(gè)硬幣。因此我們只需要找到可以搭建的臺(tái)階的邊界，并采用二分法將邊界不斷縮小直到達(dá)到最大的臺(tái)階數(shù)。
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;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/74544.html
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...
摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
摘要：解題思路動(dòng)態(tài)規(guī)劃，用表示總價(jià)為的最小紙幣張數(shù)，很容易想到狀態(tài)轉(zhuǎn)移方程當(dāng)然前提是要大于紙幣金額數(shù)。表示取一張面額加上合計(jì)為的最小紙幣數(shù)。另題目要求無法合計(jì)出的金額，要返回，所以要作特殊處理，否則就會(huì)返回元素初始化值代碼 Coin ChangeYou are given coins of different denominations and a total amount of money...
摘要：傳入的參數(shù)為手上有的紙幣的面額以及希望兌換的面額。這里假設(shè)紙幣的數(shù)量是無窮的。這題本質(zhì)上考察的是動(dòng)態(tài)規(guī)劃思想。這里有兩種動(dòng)態(tài)規(guī)劃的方法，分別從遞歸和非遞歸的角度解決這個(gè)問題。具體的情況還是要看數(shù)據(jù)的分布情況來確定選擇哪種方法。 題目要求 You are given coins of different denominations and a total amount of money ...
閱讀 1908·2021-11-11 16:55
閱讀 1483·2019-08-30 15:54
閱讀 802·2019-08-29 15:34
閱讀 2290·2019-08-29 13:11
閱讀 2939·2019-08-26 13:28
閱讀 1914·2019-08-26 10:49
閱讀 1022·2019-08-26 10:40
閱讀 2583·2019-08-23 18:21
