進入圖論啦 (ﾟ⊿ﾟ)(ﾟ⊿ﾟ)(ﾟ⊿ﾟ)

今天看的是 2059. Minimum Operations to Convert Number，對於給定的 array，可以進行加減或 bitwise-XOR 操作，如果能算出 target number 就返回最小的計算數字。由於題目有限制，中間計算過程的數字必須在 0-1000 之間，因此可以把不在範圍內的中間數都排除掉。

BFS 的基本操作就是用 queue 去做 pop & append 來實現。另外，這題可以用 array 或 set 記下曾經走過的地方（因為求最小次數，找過的沒必要再重複找第二次，重複找不可能是答案），有點像在做剪枝的動作。

有了 BFS 概念，那雙向 BFS 呢？雙向其實就是同時從起點和終點做搜尋，會需要比較多的空間來儲存中間值。

class Solution:
    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:
        arr1 = [-1 for _ in range(1001)]
        arr2 = [-1 for _ in range(1001)]
        q = [start]
        q2 = [goal]

        if start <= 1000 and start > 0:
            arr1[start] = 0
        
        curr = 1
        tmp_ans = 1005

        while q:
            n = len(q)
            n2 = len(q2)

            for i in range(n):
                tmp = q.pop(0)

                for j in nums:
                    tmp2 = [tmp+j, tmp-j, tmp^j]
                    for k in tmp2:
                        if k == goal:
                            return curr
                        if k > 1000 or k < 0:
                            continue
                        if arr2[k] > 0:
                            tmp_ans = min(tmp_ans, arr2[k]+curr)
                        if arr1[k] == -1:
                            arr1[k] = curr
                            q.append(k)
            
            if tmp_ans < 1005:
                return tmp_ans

            for i in range(n2):
                tmp = q2.pop(0)
                for j in nums:
                    tmp3 = [tmp+j, tmp-j, tmp^j]
                    for k in tmp3:
                        if k <= 1000 and k >= 0 and arr2[k] == -1:
                            arr2[k] = curr
                            q2.append(k)

            curr += 1

        return -1

• 雙向 BFS
  • 2059. Minimum Operations to Convert Number
  • 127. Word Ladder