23.02.08 Today’s Leetcode

45. Jump Game II (medium)

1. DP Solution top-down dynamic programming

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * n
        dp[n - 1] = 0
        for i in range(n - 2, -1, -1):
            min_ = 10**9
            for j in range(i + 1, min(n, i + nums[i] + 1)):
                min_ = min(min_, dp[j])
            dp[i] = min_ + 1
        # print(dp)
        return dp[0]

1. Greedy Algorithm

solution : leetcode Jump Game II Solution

class Solution:
    def jump(self, nums: List[int]) -> int:
        layer = 0
        left, right = 0, 0

        while right < len(nums) - 1:
            left, right = right + 1, max(idx + nums[idx] for idx in range(left, right + 1))
            layer += 1
        
        return layer

1. Two Sum (easy)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        temp = {}
        for i in range(n):
            p = target - nums[i]
            if p in temp:
                return [i, temp[p]]
            temp[nums[i]] = i
        return [-1, -1]

88. Merge Sorted Array (easy)

class Solution:
    def merge(self, nums1, m, nums2, n):
        i, j = m - 1, n - 1
        cur = m + n - 1
        while cur >= 0:
            if i == -1 or j == -1:
                break
            target = 0
            if nums1[i] > nums2[j]:
                target = nums1[i]
                nums1[i] = 0
                i -= 1
            else:
                target = nums2[j]
                nums2[j] = 0
                j -= 1
            nums1[cur] = target
            cur -= 1

        if i == -1:
            for x in range(j, -1, -1):
                nums1[cur] = nums2[x]
                cur -= 1

65. Valid Number (very very hard)

사실 문제를 처음 맞닥뜨렸을 때 아무런 생각이 들지 않았다. 수많은 if들을 쓰고 케이스를 나누어서 풀 수야 있겠지만 새로운 테스트케이스가 추가되고 케이스로 분류되지 않는 테스트케이스가 있을 수 있기 때문에 이렇게 푸는게 맞는건가? 라는 근본적인 의문이 들었다. 그래서 곧바로 Solution을 봤는데 역시나 어마무시한 방법이 있었다. 바로 DFA라는 건데 유형을 나누어서 정리를 하고 이 케이스들에 맞지 않으면 바로 return False를 해버리는 좋은 아이디어였다. state르 분류하는게 가장 중요한 것 같은데, 아래와 같이 분류가 된다고 한다. 이런 풀이를 이용한다면 새로운 테스트케이스가 나와도 state만 추가하면 되기 때문에 아주 좋은, reusable한 code인것 같다.

class Solution:
    def isNumber(self, s: str) -> bool:
        D = 'digit'
        dfa = {
            0: {
                '+': 1,
                '-': 1,
                D: 2,
                '.':5
            },
            1: {
                D: 2,
                '.':5
            },
            2: {
                '.':3,
                D: 2,
                'e':6,
                'E':6
            },
            3: {
                D:4,
                'e':6,
                'E':6
            },
            4: {
                D:4,
                'e':6,
                'E':6
            },
            5: {
                D: 4
            },
            6: {
                '+': 7,
                '-': 7,
                D: 8
            },
            7: {
                D: 8
            },  
            8: {
                D: 8
            },  
        }
        
        accepted_states = (2, 3, 4, 8)
        state = 0
        for s_ in s:
            key = s_ if not s_.isdigit() else 'digit'
            if key not in dfa[state]:
                return False
            state = dfa[state][key]
        return state in accepted_states