使用 PHP 解 Leetcode:1431. Kids With the Greatest Number of Candies 擁有最多糖果的孩子

題目資訊

題目網址:1431. Kids With the Greatest Number of Candies
難易度:Easy 簡單
通過率:88.1%(截至發文時間)

這題表示有數量不一定的小朋友,並由陣列 candies 定義;其中有個整數變數為 extraCandies,表示若小朋友的糖果加上變數的數字後(即多得到這個數量的糖果),是否能夠成為擁有最多的糖果或是跟原本最多糖果的小朋友並列第一。

而所謂第一名的基準,看下來是依照原本未加上多的糖果的最多數量。以 Example 1 為例,原本最多糖果的小朋友擁有 5 顆,雖然在增加 3 顆就擁有 8 顆糖果,但是所謂「最多」的基準還是 5 顆;像是第一位小朋友原本的 2 顆糖果再加上 3 顆也不過 5 顆糖果,但是因為已經與基準並列第一,也因此就過關。

以下解法一是我第一次提交時的程式碼,但發現整體成績並不理想,於是開始以解法一為基底進行優化,後來就寫出了解法二。

解法一:使用 if

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
/**
* @param Integer[] $candies
* @param Integer $extraCandies
* @return Boolean[]
*/
function kidsWithCandies($candies, $extraCandies) {
// 取最大值
$max = 0;
for ($i=0; $i<count($candies); $i++) {
if ($candies[$i] > $max) {
$max = $candies[$i];
}
}
// 比較
$ans = array();
for ($i=0; $i<count($candies); $i++) {
if (($candies[$i] + $extraCandies) >= $max) {
$ans[$i] = true;
} else {
$ans[$i] = false;
}
}
return $ans;
}
}

程式過程

  1. 宣告一個 $max 變數並設定初始值為 0,用於放置最大數值。(最多糖果)
  2. 透過迴圈尋找陣列中最大數值,並放置於變數 $max
  3. 宣告一個陣列 $ans,用於放置要回傳答案之陣列。
  4. 透過迴圈去跑每一位小朋友,原本所擁有糖果數加上被多給數量後,是否有超過原本擁有最多的小朋友;若有則讓給該陣列位置 true,反之則為 false

這樣有什麼問題?

最後成果出來了,我沒有截圖到但我印象中只贏過 14.8 % 的人 XDD

後來我就開始思考,該如何優化我的程式碼?

  • 我知道還有一個 max 函數可以比較指定數字中取最大者,或許可使用看看?
  • 想起上週看了工程師 YouTuber Nic 大神的 提升軟體開發品質! 寫程式的 6 招實用技巧 這部影片,其中第三項的「簡化條件表達式」,剛好可以現學現賣 XD 就來嘗試看看簡化條件表達式~

解法二:捨棄 if,並使用 max 函數

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
/**
* @param Integer[] $candies
* @param Integer $extraCandies
* @return Boolean[]
*/
function kidsWithCandies($candies, $extraCandies) {
// 取最大值
$max = 0;
for ($i=0; $i<count($candies); $i++) {
$max = max($max, $candies[$i]);
}
// 進行比較
$ans = array();
for ($i=0; $i<count($candies); $i++) {
$ans[$i] = ($candies[$i] + $extraCandies) >= $max;
}
// 輸出答案
return $ans;
}
}

我優化了哪些部分?

  • 取最大值的迴圈,我使用 max 函數取代了原本的 if,比起原本使用 if 先判斷再給值的方法,少了一個步驟。
  • 我將判斷增加糖果後是否有超過原本最多糖果數量的 if 拿掉了,我直接將原本的判斷式放置在該陣列位置,因為原本判斷式就會回傳 true 或是 false 了,不需要特地做一個 if,在那邊 true 的話給 true,false 就給 false XD

成果

優化此程式碼後,贏過了 82.95% 的人,與原本只贏過 14.8% 的人有極大差距 XD

提交成功:贏過 82.95% 的人

從比較圖來看,優化前的第一次需花費 20ms,第二次提交我優化了判斷式的部分就大幅提升至 8ms,雖然第三次提交優化 max 那個部分 Memory 來多了第二次提交一些些,但我想能少一個步驟還是比較好的!

Time Submitted