[思路]LeetCode Problems- 441. Arranging Coins
昨天一早在大學系版上看到教授給學弟妹出的LeetCode練習題,
想說剛畢業沒課的第一天來找點事情做,加上好奇心使然
註冊了網站帳號來看一下題目是甚麼
想說剛畢業沒課的第一天來找點事情做,加上好奇心使然
註冊了網站帳號來看一下題目是甚麼
題目原文是這樣的:
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枚硬幣,則一共可以排成"完整"階梯的階數是多少,
其中階梯硬幣的排法是 第?階就有?枚硬幣
看題目以及老師FB給的提示,
還必須要把階梯"畫"出來的樣子
一開始看到這個題目時還有點不太知道要從何下手,
但先撇開如何畫階梯這件事情不談,
先只關注輸入的值 n 來下手 [簡化問題]
要如何判斷n枚硬幣是可以排成"完整"階梯狀的數字呢?
不同階數的樓梯,彼此會不會有所關聯呢?
例如一階樓梯 硬幣數是1
二階樓梯 硬幣數是1+2=3
三階樓梯 硬幣數是1+2+3=6
四階硬幣數是1+2+3+4=10 諸如此類...
1 , 3 , 6 , 10 ,......這數列好像有某種關係
突然發覺這類型的數列以前國中數學好像有接觸過,這符合"三角數"的定義
於是用維基查了一下三角數
https://zh.wikipedia.org/wiki/%E4%B8%89%E8%A7%92%E5%BD%A2%E6%95%B8
在其中的性質欄中發現了有一個公式可以判別輸入值是否為三角數
因此我確立出程式的邏輯:
輸入值n-->帶入公式計算
-------->若算出來的答案a是整數
---->完整階梯數=a
---->畫出a階階梯*
-------->若算出來的答案a有小數
---->完整階梯數=無條件捨去的a(只留整數)
---->先畫出a階階梯*
---->剩餘的硬幣=原輸入n 減掉 第a個三角數(等於 a*(a+1)/2 )
---->再把剩餘的硬幣*畫出來擺在a階階梯下
根據這邏輯寫出IF判斷式:
float ans=(sqrt(8*n+1)-1)/2;
if (ans-int(ans)>0) //若有小數點代表不是三角數,整數為排到第?階
{
int a=int(ans);
//畫出完整階梯
int star=n-(a*(a+1))/2; //這是剩餘的硬幣數
//畫出不完整的階梯
;}
else //n是三角數,ans=第幾階
{
//畫出完整階梯
;}
架構完成後,接下來就是處理畫階梯的問題了
假如計算出的a等於5,則我要先畫出第一行有1個*,再跳到下一行畫出2個*,一直畫到第五行結束為止
很明顯地可以用for語法處理這個問題
for (int i=1;i<=a;i++){
cout<<"*";
cout<<endl;
}
這樣寫只會5行都是一個*,很快就會發現一個for是不夠用的,必須再多一個for迴圈控制輸出*的個數,故再改寫成
for (int i=1;i<=a;i++){
for (int j=1;j<=i;j++){
cout<<"*";
}
cout<<endl;
}
這樣就能畫出完整的階梯*
最後再把剩餘硬幣畫出來就結束了~~
最後寫出來的程式碼如下:
class Solution {
public:
int arrangeCoins(int n) {
float ans=(sqrt(8*n+1)-1)/2;
if (ans-int(ans)>0)//若有小數點代表不是三角數,整數為排到第?階
{
int a=int(ans);
int star=n-(a*(a+1))/2;
cout<<star<<endl;
cout<<"The coins can form the following rows:"<<endl;
//輸出完整階梯
for (int i=1;i<=a;i++){
for (int j=1;j<=i;j++){
cout<<"*";
}
cout<<endl;
}
//輸出不完整階梯
for (int i=1;i<=star;i++){
cout<<"*";
}
;}
else//n是三角數,ans=第幾階
{
cout<<"The coins can form the following rows:"<<endl;
//輸出階梯
int a=int(ans);
for (int i=1;i<=a;i++){
for (int j=1;j<i;j++){
cout<<"*";
}
cout<<endl;
}
;}
return int(ans);
}
};
滿懷信心地按了"submit"鍵送出,結果瞬間...
瀏覽器整個大當機LAG ?!
我還以為是我電腦的問題,按了重新整理好幾次都沒有改善
後來重新登入LeetCode後瀏覽傳送紀錄:
這時我才赫然發現,其實這問題本身並沒有要求把階梯畫出來,
只需要把完整的階梯數RETURN回去就好了,也就是公式解本身的答案而已
讓我光想如何畫階梯就用很久時間 =.=
後來就把程式碼輸出的部分就連大架構的IF判斷式都拿掉,只剩公式計算:
class Solution {
public:
int arrangeCoins(int n) {
long double ans=(sqrt(8*n+1)-1)/2;
long int a=floor(ans);
return a;
}
};
但第二次送出之後發現還是有問題:
在計算到最大值1804289383時居然答案出錯了!
可是若用計算機代這個值進去公式解,算出來的答案是正常的啊,
那問題會是出在甚麼地方?
再重新檢查一次程式碼,發現我公式算出來的答案有可能會有小數,所以當初變數類型是double
但是輸入的值是整數Int啊~!
看來是這個地方不同所以導致計算時答案不一樣
故在函式sqrt()裡面加上強制轉型,再改一些小細節:
class Solution {
public:
int arrangeCoins(unsigned int n) {
long double ans=(sqrt((double)8*n+1)-1)/2;
unsigned int a=floor(ans);
return a;
}
};
第三次按下"submit"鍵,終於通過了~~!
看來LeetCode判斷程式碼好壞用的是處理時間長短
所以其實這題最快可以直接簡寫成直接傳回公式解,就可以減少許多時間
假如多考慮到如何畫出階梯的話,
這其實算是個蠻不錯的練習題呢~~
留言
張貼留言