LidemyOJ 學習筆記 - [#1008-幾個水桶]
最近在看 Huli 大大的「先別急著寫 leetcode 」課程練功，做到一題有趣的題目，想來寫寫文章做個筆記。
題目
故事有點長，以下用白話文簡述 :
很久很久以前，有個 Lidemy 王國，這個王國的每個水桶容量都是 2 的 n 次方，例如最小的五個水桶的容量為：
1、2、4、8、16
而最大的水桶容量為 2³¹ = 2147483648。
國王派士兵去取水，希望每一次取水都能帶最少的水桶去，而且每一個水桶一定都要裝滿。
現在已知要取水的單位(input)，請幫忙算算看，最少需要帶幾個水桶(output)?
參考以下範例 :
input : 20
output : 2
Hint : 20 單位的水，帶一個 16 的水桶加一個 4 的水桶即可，所以答案是 2
我的解法
初步解題想法
- 找出 < = 總水量的最大水桶容量
- 算出剩餘還沒裝的水量
- 剩下的水再重複 1 、2 步驟，每找一次，水桶數就加 1 ，直到剩餘水量為 0
程式碼
想了老半天，想出以下解法 :
function solve(lines) {
let w = Number(lines[0]); // 因 LidemyOJ 作答方式的限制，所以以這種方式取出 input
let bucketNum = 0;
function checkWater(w) {
let bucketWater = 0;
let i = 0;
// 找出容量小於等於總水量的最大水桶
while(Math.pow(2, i) <= w) {
bucketWater = Math.pow(2, i);
i++
}
// 算出裝完還剩多少水
let leftWater = w - bucketWater;
return leftWater;
}
while(w != 0) {
// 重複執行 checkWater 直到水量為 0
w = checkWater(w);
// 每執行一次，水桶數就 +1
bucketNum ++
}
console.log(bucketNum) // output
}Huli 的解法
共提供三個解法如下
解法一
- 我們不會重複使用一樣容量的水桶，因為如果用一個 4 和一個 4 去裝水，不如帶一個 8 去就能解決。所以我們能從最大容量的水桶開始查找，慢慢用越來越小容量的水桶把水裝完。
function solve(lines) {
let n = Number(lines[0]);
// 用 for 迴圈分別跑出所有水桶容量，並用陣列表示
let arr = [];
for(let i=1; i<= 2**31; i*=2) {
arr.push(i)
}
let sum = 0; // 計算水桶量
// 使用 for 迴圈從最大容量開始倒著遍歷
for(let i=arr.length - 1; i>=0; i--) {
// 找出容量小於等於總水量的最大水桶
if(arr[i] <= n) {
n-= arr[i] // 算出剩餘水量
sum++ // 水桶數加一
}
}
console.log(sum)
}解法二
利用二進位的觀念解題。
先剖析十進位是如何組成的
123 = 1x100 + 2x10 + 3x1
= 1x10^2 + 2x10^1 + 3x10^0 // ^為次方符號剖析將二進位轉換為十進位的過程
10100 = 1x2^4 + 0 + 1x2^2 + 0 + 0
= 2^4 + 2^2
= 20由過程可以發現，20 是由 2⁴ + 2² 所組成。
因此，將一個數(input) 轉換為二進位，再找出二進位的字串中有幾個 1，便是答案，也就是我們需要的水桶數量(output)!
JS 數字 10 進位轉 2 進位的方法
(20).toString(2) // 10100找出二進位的字串中有幾個 1
- 字串一樣可以用 for 迴圈查找 (每次都會忘記，還在想說要不要先把它轉成陣列)
for(let i=0; i<str.length; i++) {
if(str[i] === '1') {
sum++
}
}完整解法如下
function solve(lines) {
let n = Number(lines[0])
let sum = 0;
// 將總水量轉換為二進位字串
let str = n.toString(2);
for(let i=0; i<str.length; i++) {
// 字串中每找到一個 '1', 水桶數就 +1
if(str[i] === '1') {
sum++
}
}
console.log(sum)
}解法三
function solve(lines) {
let n = Number(lines[0])
let sum = 0;
// 跑迴圈直到水量為 0
while(n>0) {
// n&1 可以回傳 n 的 2 進位數最後一位是 0 還是 1
sum += n&1;
// 每加完一次就往右移，也就是去掉最後一位數，繼續檢查、累加
n >>= 1
}
console.log(sum)
}一個問題能有許多不同的解法，一直都是學習程式的路上讓我覺得十分有趣的地方。做完題目也深刻感覺到自己相關知識方面的不足，看完解法二和解法三，簡直驚呆，尤其解法三，更是太狠了。
當初在 leetcode 的世界，總還是覺得有些寸步難行，看完題目腦袋都一片空白😵。後來發現 Huli 的這個課程，正如課程某章節的標題說到，「初學者只管拿分，誰管你什麼效率」，決定先開始當個能拿分的小菜雞再說⭐️⭐️⭐️✔️，這陣子陸續看了幾個章節後，發現在訓練程式邏輯思考方面，對我來說真的十分有幫助，也推薦給大家~
