主題
題目連結(jié)：
題目意譯：
你被給定一個(gè)索引值從 0 開(kāi)始數(shù)的相異整數(shù)陣列 nums 、一個(gè)整數(shù) start 以及一整數(shù) goal。現(xiàn)在有一數(shù) x 其初始值設(shè)為 start，而你想要執(zhí)行一些操作使得 x 之值變?yōu)?goal。你可以重複執(zhí)行以下的操作：
如果 0 ≦ x ≦ 1000，則對(duì)於任意一個(gè)索引值 i（0 ≦ i < nums.length），你可以把 x 設(shè)為以下的任意一個(gè)值：
x + nums[i]
x - nums[i]
x ^ nums[i] （按位元之 XOR 結(jié)果）
注意，你可以按照任意的順序使用每個(gè) nums[i] 任意次。把 x 之值設(shè)超出 0 ≦ x ≦ 1000 這個(gè)範(fàn)圍是合法的，但是其後不得再做任何操作。
回傳將 x = start 轉(zhuǎn)變?yōu)?goal 的最小所需之操作數(shù)。如果不可能，則回傳 -1。
限制：
1 ≦ nums.length ≦ 1000
-10 ^ 9 ≦ nums[i], goal ≦ 10 ^ 9
0 ≦ start ≦ 1000
start != goal
nums 中所有整數(shù)皆相異。
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： nums = [2,4,12], start = 2, goal = 12
輸出： 2
解釋?zhuān)?我們可以經(jīng)由如下 2 次操作從 2 → 14 → 12。
- 2 + 12 = 14
- 14 - 2 = 12
範(fàn)例 2：
輸入： nums = [3,5,7], start = 0, goal = -4
輸出： 2
解釋?zhuān)?我們可以經(jīng)由如下 2 次操作從 0 → 3 → -4。
- 0 + 3 = 3
- 3 - 7 = -4
注意，最後一次操作把 x 之值設(shè)超出 0 ≦ x ≦ 1000 這個(gè)範(fàn)圍，而這是合法的。
範(fàn)例 3：
輸入： nums = [2,8,16], start = 0, goal = 1
輸出： -1
解釋?zhuān)?沒(méi)有任何方式可以從 0 變?yōu)?1。
解題思維：
我們可以利用廣度優(yōu)先搜尋（Breadth First Search，BFS）從 start 開(kāi)始慢慢擴(kuò)張看看，看可不可以抵達(dá) goal。並且我們需要利用一個(gè)布林陣列來(lái)表示每個(gè) 0（含）～ 1000（含）是否出現(xiàn)過(guò)。
利用一佇列（Queue）來(lái)儲(chǔ)存要被操作的數(shù)字以及這些數(shù)字現(xiàn)在經(jīng)歷過(guò)的操作數(shù)。
假設(shè)現(xiàn)在要操作的數(shù)字為 K，其已經(jīng)歷過(guò) S 次操作。則我們就掃過(guò) nums 中所有數(shù)字來(lái)試著將 K 變換看看，因此會(huì)有 3 × nums.length 個(gè)可能的數(shù)字（每個(gè) nums[i] 有 3 種操作可以選）。
再假設(shè)現(xiàn)在考慮的是變換後的數(shù)字 K'，先檢查其值是否等於 goal。如果是的話，則 S + 1 即為所求。
不是的話，再判斷 K' 是否有落於 0 ～ 1000 的範(fàn)圍之內(nèi)。如果沒(méi)有，則此時(shí) K' 無(wú)法再執(zhí)行任何操作了，所以可以直接忽略。
如果有在範(fàn)圍的話，再根據(jù)上面宣告的布林陣列來(lái) K' 是否出現(xiàn)過(guò)。如果有的話就忽略 K'，因?yàn)橄惹凹热灰呀?jīng)變成過(guò)該數(shù)了，那現(xiàn)在又變回去只是徒增操作數(shù)而已。
如果沒(méi)有出現(xiàn)過(guò)，則此時(shí)才能把 K' 以及操作步數(shù) S + 1 放到佇列之中等待之後繼續(xù)操作。
如果全部的可能都跑完且還沒(méi)有抵達(dá) goal 的話，則代表不可能將 start 變?yōu)?goal。因此回傳 -1。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
