[leetcode] 78, 79, 160, 163

160. Intersection of Two Linked Lists

https://leetcode.com/problems/intersection-of-two-linked-lists/

My Answer 1: Accepted (Runtime: 160 ms - 75.08% / Memory Usage: 29.2 MB - 99.20%)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        hA = headA
        hB = headB
        
        while hA != hB:
            if hA.next is None and hB.next is None:
                hA = None
                break
            hA = hA.next if hA.next else headB
            hB = hB.next if hB.next else headA
        
        return hA

hA 와 hB 의 길이가 다를 수 있기 때문에
모두 한 노드씩 움직이다가 끝이 나면 A -> B, B -> A 헤드를 보도록 함

if hA.next is None and hB.next is None: 이 순간이 되면 겹치는 부분이 없다는 뜻

예전에 풀어본 기억이 났다...!

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        hA = headA
        hB = headB

        while hA!=hB:
              hA = headB if not hA else hA.next
              hB = headA if not hB else hB.next
        return hA

더 깔끔한 코드

이걸로 알아두기~~

---

163. Missing Ranges

https://leetcode.com/problems/missing-ranges/
https://www.lintcode.com/problem/641/

My Answer 1: Accepted (Runtime: 1458 ms / Memory Usage: 39.94 MB) - 48.80%

class Solution:
    def findMissingRanges(self, nums, lower, upper):
        r = []
        start = lower

        for i in range(len(nums)):
            if nums[i] < lower:
                continue
            if nums[i] > upper:
                break
            if start == nums[i]:
                start += 1
            else:
                r.append([start, nums[i]])
                start = nums[i] + 1
        if start <= upper:
            r.append([start, upper+1])

        ans = []
        for i in range(len(r)):
            if r[i][0] > r[i][1] - 1:
                continue
            elif r[i][0] == r[i][1] - 1:
                ans.append(str(r[i][0]))
            else:
                ans.append(str(r[i][0]) + "->" + str(r[i][1]-1))
        
        return ans

이거.. lintcode 에서는 medium 문제...

우선 start 를 lower 값으로 잡고
nums[i] 가 start 랑 같으면 존재하는 값이니까 start + 1

다르면 중간에 없는 숫자들이 있다는 뜻이므로 그 범위인 [start, nums[i]] 를 r 에 넣어줌
start 는 다음 구간이 존재하는지 보기 위해 nums[i]+1 로

없는 구간들을 모두 r 에 저장했으면 string 으로 바꿔주는 작업 진행

r 은 [start, end+1] 의 형태로 저장됐다는 점을 이용
if r[i][0] == r[i][1] - 1 => 숫자 하나만 없다는 의미

Solution 1: Accepted (Runtime: 1366 ms / Memory Usage: 33.65 MB) - 56.40%

class Solution:
    def findMissingRanges(self, nums, lower, upper):
        result = []
        nums = [lower-1] + nums + [upper+1]
        for i in range(1, len(nums)):
            l = nums[i-1]
            h = nums[i]
            if h - l >= 2:
                if h - l == 2:
                    result.append(str(l+1))
                else:
                    result.append(str(l+1)+"->"+str(h-1))
        return result

nums 앞 뒤에 lower, upper 도 임의로 추가해주기

nums 를 두개씩 보면서 둘의 차이가 2 이상이면 없는 숫자가 있다는 거니까
2 일때는 없는 숫자 하나, 2 보다 크면 없는 구간 저장

---

78. Subsets

https://leetcode.com/problems/subsets/

My Answer 1: Accepted (Runtime: 32 ms - 79.29% / Memory Usage: 14.3 MB - 79.73%)

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def func(n, sub):
            self.ans.append(sub)
            
            if len(n) == 0:
                return
            
            for i in range(len(n)):
                func(n[i+1:], sub+[n[i]])
        
        self.ans = []
        func(nums, [])
        
        return self.ans

재귀로 n[i+1:] 을 다음 nums 로 넘겨서 subset 조합 모두 ans 에 넣어주기

---

79. Word Search

https://leetcode.com/problems/word-search/

My Answer 1: Accepted (Runtime: 3372 ms - 91.96% / Memory Usage: 14.3 MB - 72.87%)

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def func(i, j, w):
            if w == len(word)-1:
                return True
            
            tmp = board[i][j]
            board[i][j] = "0"
            
            a = 0
            if i > 0 and board[i-1][j] == word[w+1]:
                a |= func(i-1, j, w+1)
            if j > 0 and board[i][j-1] == word[w+1]:
                a |= func(i, j-1, w+1)
            if i < len(board)-1 and board[i+1][j] == word[w+1]:
                a |= func(i+1, j, w+1)
            if j < len(board[0])-1 and board[i][j+1] == word[w+1]:
                a |= func(i, j+1, w+1)
            
            board[i][j] = tmp
            
            return a
                
        
        for i in range(len(board)):
            for j in range(len(board[i])):
                if board[i][j] == word[0]:
                    if func(i, j, 0):
                        return True
        
        return False

word 의 시작 단어를 만나면 재귀 돌려서 단어가 완성되는지 확인

한번 본 문자들은 임시적으로 0 으로 변경

사방 중에 다음 문자가 있는지 확인해서 전체 word 를 다 찾으면 return True

(or) | 연산으로 하나라도 True 가 있으면 True 를 return 하도록 함