題目來源：糖果
問題：
假設有 N 位小朋友站一排並且每個小朋友手上都會有一個號碼牌。
這時你必須根據以下的規則去分糖果給每一位小朋友：
例子
假設有五位小朋友並手拿號碼牌 [3 2 1 4 3] 則我們需要的糖果是 9 顆。
分送的糖果數量為 => [3 2 1 2 1] 所以是 9 顆糖果
想法
關於這題我的想法就是，如果小朋友的號碼牌是 純遞增 或 純遞減，那麼答案就是等差級數取和並且差為1。
如果是有增有減，那問題就比較麻煩一些。所以一開始我會先找出有可能發生的情況。
所以，根據上面的分析最糟的情況就是排對小朋友人數大於等於3人和號碼牌有增有減。
虛擬碼
小朋友人數為 N 人
如果 N <= 1
回傳 N // (因位小朋友人數等於糖果人數)
如果 N == 2
回傳 3
如果小朋友的號碼牌皆為遞增或遞減
回傳 [N(N+1)] / 2 //利用等差級數公式求和, 差為 1
// 遇到複雜情況計算
第一位小朋友給一顆糖果
從第 2 位小朋友看到最後一位小朋友
如果 這位小朋友的號碼大於前一位小朋友
給 前一位小朋友糖果數量加一顆
如果沒有
給一顆堂
從最後一位小朋友在看到第一位小朋友
如果目前這位小朋友的數字比前一位小，但是糖果又比前一位多或相等
前一位的糖果會等於 目前這位小朋友的糖果加1顆
回傳所有小朋友的糖果總和
舉個例子來說：假設目前的小朋友號碼牌如下
[1 2 3 4 5 1 3 4 2 3 2 1 4] (小朋友號碼牌)
則第一輪就是先處理遞增的情況，所以只要是遞增的糖果數量都是正確的。
{1 2 3 4 5 1 2 3 1 2 1 1 2} (糖果數量)
那經過第一輪之後，遞增正確了。我接著要處理的就是遞減的部份。所以我要往回看，只要是目前這位小朋友的數字比前一位小但是糖果卻又比前面一位多或相等，則前一位的糖果就要比目前這一位多一顆。這樣一來，遞減的部份也就會正確了。
經過第一輪的結果（只要自己數字 比前一位大，自己的糖果就是前一位的糖果 加1）
[1 2 3 4 5 1 3 4 2 3 2 1 4]
{1 2 3 4 5 1 2 3 1 2 1 1 2}
第二輪 :
[1 2 3 4 5 1 3 4 2 3 2 1 4]
{1 2 3 4 5 1 2 3 1 2 1 1 2}
因為倒數第二位比倒數第三位數字小，但是糖果卻是一樣多，所以倒數第三位的糖果應該是倒數第二位的糖果數量加1, 所以應該是 **2**
[1 2 3 4 5 1 3 4 2 3 2 1 4]
{1 2 3 4 5 1 2 3 1 2 2 1 2}
因為倒數第三位的比倒數第四位的數字小，但是糖果卻是一樣多，所以倒數第四位應該是倒數第三位的糖果數量加1
如果你用 C＃ 可以利用我的 測試程式 來驗證
如果你用 Java or Python or C++ 可上 LeetCode Online Judge 驗證
還是想不出來嗎？參考我的 解答(C#版本) 吧！
// c# 第一版本解答
public int calculateMinimunCandies(int[] ratings)
{
if (ratings == null || ratings.Length == 0)
return 0;
else if (ratings.Length == 1)
return ratings.Length;
else if (ratings.Length == 2)
return 3;
int[] candies = new int[ratings.Length];
candies[0] = 1;
// 處理遞增狀況
for (int i = 1; i < ratings.Length; i++)
{
if (ratings[i] > ratings[i - 1])
candies[i] = candies[i - 1] + 1;
else
candies[i] = 1;
}
// 處理遞減狀況
for (int i = ratings.Length - 1; i > 0; i--)
{
if (ratings[i] < ratings[i - 1] && candies[i] >= candies[i - 1])
candies[i - 1] = candies[i] + 1;
}
return candies.Sum();
}
上面的答案在時間複雜度來說應該是 O(N^2), 那有沒有辦法更精進呢？
有，因為上面的答案並沒有處理 **純遞增** 或 **純遞減**，如果加上這個處理，除了最糟狀況，其他的狀況還是有精進的。
// c# 加入處理純遞增 case
public int calculateMinimunCandies(int[] ratings)
{
if (ratings == null || ratings.Length == 0)
return 0;
else if (ratings.Length == 1)
return ratings.Length;
else if (ratings.Length == 2)
return 3;
bool isAlwaysIncrease = true;
int[] candies = new int[ratings.Length];
candies[0] = 1;
for (int i = 1; i < ratings.Length; i++)
{
if (ratings[i] > ratings[i - 1])
{
candies[i] = candies[i - 1] + 1;
}
else
{
candies[i] = 1;
isAlwaysIncrease = false;
}
}
if (isAlwaysIncrease)
{
int totalCandies = ((1 + ratings.Length) * ratings.Length) / 2;
return totalCandies;
}
for (int i = ratings.Length - 1; i > 0; i--)
{
if (ratings[i] < ratings[i - 1] && candies[i] >= candies[i - 1])
candies[i - 1] = candies[i] + 1;
}
return candies.Sum();
}
加入純遞增的判斷後，雖然最糟的狀況還是 O(N^2)，但是如果是遇到純遞增的狀況，就有機會將複雜度降低到 O(N) 了。
那最後還是來個重構看看吧 (記住：要重構一定要在安全的狀況下，也就是有 test case 的情況下進行，否則是一不小心是很容易改壞調的喔)
// c# Refactor version
public int calculateMinimunCandies(int[] ratings)
{
if (ratings == null || ratings.Length == 0)
return 0;
else if (ratings.Length == 1)
return ratings.Length;
else if (ratings.Length == 2)
return 3;
bool isAlwaysIncrease = true;
int toatalCandies = 0;
int[] candies = new int[ratings.Length];
ForwardCheck(ratings, candies, ref isAlwaysIncrease);
if (isAlwaysIncrease)
{
toatalCandies = ((1 + ratings.Length) * ratings.Length) / 2;
}
else
{
candies = BackwardCheck(ratings, candies, toatalCandies);
toatalCandies = candies.Sum();
}
return toatalCandies;
}
private static int[] BackwardCheck(int[] ratings, int[] candies, int toatalCandies)
{
for (int i = ratings.Length - 1; i > 0; i--)
{
if (ratings[i] < ratings[i - 1] && candies[i] >= candies[i - 1])
candies[i - 1] = candies[i] + 1;
}
return candies;
}
private static int[] ForwardCheck(int[] ratings, int[] candies, ref bool isAlwaysIncrease)
{
candies[0] = 1;
for (int i = 1; i < ratings.Length; i++)
{
if (ratings[i] > ratings[i - 1])
candies[i] = candies[i - 1] + 1;
else
{
candies[i] = 1;
isAlwaysIncrease = false;
}
}
return candies;
}
iThome鐵人賽
看影片追技術