当前位置: 首页 > 資訊 >

Day 04 : 找不出的零錢 Non-constructible Change

先來看一下題目

Given an array of positive integers (representing coins), find the smallest value that cannot be constructed from those integers.

這題算是網路蠻多人分享的找零錢變形題,實作起來很簡單,其實難度也不高,但是如果沒有看過遇過,突然被考到還真的會想不到好的作法!/images/emoticon/emoticon20.gif

我們一起來推推看吧!
簡單來說這題題目就是在問:
假設給你一堆金幣(都是大於0的數) ,找出這些金幣不能組出來的最小值
當然我們不可以重複用同樣的金幣,不然如果給你1塊就全部都可以湊出來了!

一開始看到題目很直覺的想法就是:
從1開始確認,1有沒有辦法被這些數字組成, 2, 3, ... → 暴力
我相信大家一開始都會覺得很簡單啊解完了!但這覺對不是最好的方式!

『再想想有沒有更好的方式?』
(很常在解題目毫無頭緒的時候,看到有Array就可以想到排序)

如果先把array排序會有幫助嗎?因為是找是找最小值,應該有幫助吧?

假設 input : [6, 4, 5, 1, 1, 8, 9]
sortedInput -> [1, 1, 4, 5, 6, 8, 9]

我們從1開始,先把一開始可以湊到的最多金額數設為 0 (currentMax = 0)
取出sortedInput[0]= 1 -> 把 currentMax 0加上1-> currentMax = 1
也就是我們可以湊到的最多為1

接著我們又可以拿到 sortedInput[1]= 1
所以 1+1=2 (currentMax = 2)
我們現在可以湊到的數為 {1, 2}

接著我們拿到 4
4 - 2 = 2 > 1
我們現在最大可以湊到的數是 1 + 1 + 4 = 6
我們現在可以湊到的數為 {1, 2, 4, 5, 6}

那3要怎麼湊呢? (沒錯答案就是3)
在這裡我們可以發現,每次我們在湊錢的時候,
如果拿到下一個數,和前面加起來目前湊到最大的數相差大於1,那個數就是答案。

欸等等,為什麼? <- (我一開始看到別人這樣做的時候的反應!)

我們來想想!
我們每次在檢查當下的數時都存了當下可以組成的最大的數
而我們知道下一個想要組合而成的數都是當下組成的最大的數+1(也就是目前走到input array地方的所有數和+1)
那個如果下一個數不是剛好是組成的最大的數+1,
我們不就沒有辦法拿到其他的數來得到目前組成的最大的數+1嗎?
是不是瞬間有頭緒了!!

Time Complexity: O(nlogn) -> 時間主要花在排序,只用檢查一次陣列
Space Complexity: O(1) (or O(n) 如果不能使用in place sort)

最後來看程式碼吧!

function nonConstructibleChange(coins) {
  coins.sort((a,b) => a-b);
	let currentMax = 0;
	for(const coin of coins){
		if (coin > currentMax + 1) return currentMax + 1;
		currentMax += coin;
	}
  return currentMax + 1;
}

Reference: Elements of Programming Interviews in python, page 189

明日題目預告:
入門不可以錯過的題目 Two Sum