23.03.05 Today’s Leetcode

1345. Jump Game IV (hard)

DFS Approach - but failed because it cannot overcome cycle in jumpping loop

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        pos = defaultdict(set)
        for index, num in enumerate(arr):
            pos[num].add(index)
        
        print(pos)
        n = len(arr)
        dp = [math.inf] * n
        def dfs(cur):
            # print(cur)
            if cur >= n or cur < 0:
                return math.inf
            if cur == n - 1:
                dp[cur] = 0
                return 0
            if dp[cur] > 0 and dp[cur] < math.inf:
                return dp[cur]
            if dp[cur] == -1:
                # visited but not updated
                return math.inf
            dp[cur] = -1
            temp = math.inf
            temp = min(temp, dfs(cur + 1))
            temp = min(temp, dfs(cur - 1))
            for connect in pos[arr[cur]]:
                if connect != cur:
                    temp = min(temp, dfs(connect))
            dp[cur] = temp + 1
            print(dp)
            return dp[cur]
        
        dfs(0)
        print(dp)
        return dp[0] 

BFS Approach

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        if n == 1:
            return 0
        
        indices = defaultdict(list)
        for i in range(n):
            indices[arr[i]].append(i)
        
        storeIndex = deque()
        visited = [False] * n
        storeIndex.append(0)
        visited[0] = True
        steps = 0
        
        while storeIndex:
            size = len(storeIndex)
            while size > 0:
                currIndex = storeIndex.popleft()
                size -= 1
                if currIndex == n - 1:
                    return steps
                
                jumpNextIndices = indices[arr[currIndex]]
                jumpNextIndices.append(currIndex - 1)
                jumpNextIndices.append(currIndex + 1)
                for jumpNextIndex in jumpNextIndices:
                    if 0 <= jumpNextIndex < n and not visited[jumpNextIndex]:
                        storeIndex.append(jumpNextIndex)
                        visited[jumpNextIndex] = True
                jumpNextIndices.clear()
            steps += 1
        return -1

231. Power of Two (easy)

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n == 0:
            return False
        if n == 1:
            return True
        return n % 2 == 0 and self.isPowerOfTwo(n // 2)

191. Number of 1 Bits (easy)

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            if n % 2 == 1:
                count += 1
            n = n // 2
        return count