leetcode 141(find cycle in linked list), 142, 287, 268(missing num)

141 https://leetcode.com/problems/linked-list-cycle/

 

https://qkqhxla1.tistory.com/1043에 이론을 정리해놨다. 

class Solution(object):
    def hasCycle(self, head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

142 https://leetcode.com/problems/linked-list-cycle-ii/

 

linked list의 순환이 시작되는 첫번째 위치를 찾는 문제. 한번 만난 후에 fast는 놔두고, slow만 처음으로 돌아간 후 한칸씩 가면서 만나는 지점이 사이클의 시작지점이다. https://code-giraffe.tistory.com/29 를 봤는데 복잡해서 그냥 외워버렸다.

class Solution(object):
    def detectCycle(self, head):
        start = slow = fast = head
        while fast and fast.next:
            #print slow.val, fast.val
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                slow = start
                break

        #print 'm =',slow.val, fast.val

        while fast and fast.next:
            if slow == fast:
                #print 'slow =',slow.val
                return slow
            slow = slow.next
            fast = fast.next

287 https://leetcode.com/problems/find-the-duplicate-number/

 

제한 조건이 있으므로 제한 조건에 맞춰서 풀어야 한다. 

문제의 조건이 1~n의 수가 n+1길이의 nums에 들어간다고 나와있다. n+1의 길이의 배열 nums에 1~n의 수가 들어가며 한 숫자만 항상 중복이라고 하면 nums배열은 그래프(링크드 리스트)라고 볼수 있다. 그리고 한 수가 중복되니까 위처럼 링크드 리스트중 중복을 이루는 부분의 시작하는 부분을 구하면 된다.

 

ex) [1,3,4,2,2] 의 경우 각각의 인덱스를 Node의 값으로, nums리스트의 인덱스의 실제 값을 next값으로 생각하면 연결된 링크드 리스트가 된다. Node(val=0, next=1) -> Node(val=3, next=2) -> Node(val=4, next=2) -> Node(val=2, next=4)

이런식으로.

ex) [3,1,3,4,2] -> Node(val=0, next=3) -> Node(val=4, next=2) -> Node(val=3, next=4) -> Node(val=4, next=2)

 

이런식으로 생각하고 cycle이 시작하는 부분의 값을 구해주면 된다고 한다.

class Solution(object):
    def findDuplicate(self, nums):
        start = slow = fast = 0
        while True:
            #print slow, fast
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                slow = start
                break
     
        while fast:
            if slow == fast:
                #print 'here =',slow
                return slow
            slow = nums[slow]
            fast = nums[fast]

268 https://leetcode.com/problems/missing-number/

0~n까지의 수 중에 한가지 수가 빠져있다고 한다. 그 수를 찾아야 한다. 제한 조건이 오직 constant한 변수만 사용해서 풀어보라고 한다.

discussion을 보면 다들 1~n의 합은 n(n+1)/2이고 여기서 nums배열의 합을 빼면 빠진 수가 나오는거로 수학으로 풀었는데 xor로도 가능하다.(이것도 discussion에 있음.)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        r = 0
        for n in nums:
            r ^= n
        for i in range(len(nums)+1):
            r ^= i
        return r