Simple

나름 쉬웠지만 풀지 못한 문제들을 정리해서 올린다.

(1) Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Example 1:

Input: nums = [3,0,1]
Output: 2

Explanation 1: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

(1) Solution

우선 0부터 n까지 다 더한 값을 구해서, 그 값을 이용해서 배열에 있는 값을 순차적으로 뺀다. 최종적으로 남는 값이 missing value다.

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        s = n * (n + 1) // 2
        for num in nums:
            s -= num
        return s

(2) Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node 8. (node 1에서 intersection이 없는 이유는 node 8 자체가 문제에서 정의된 intersection이기 때문)

단, O(n)의 시간복잡도, O(1)의 공간복잡도로 풀어야 함

(2) Solution

만약 linked list의 꼬리 부분에 intersection이 존재한다면, 두 개의 linked list를 하나로 이어서 intersection을 찾으면 된다. 이 방식이 동작하는 이유: 두 linked list의 길이를 A, B라고 한다면, 두 linked list를 하나로 합쳤을 경우 A + B 또는 B + A가 되기 때문에 intersection이 존재하는 tail에 반드시 도달할 수 밖에 없다. 또한, intersection 자체가 존재하지 않는 경우, 반드시 linked list의 끝 None 값에 동시에 도달하게 되어 있다.

class Solution:
    def getIntersectionNode(self, headA, headB):
        currA, currB = headA, headB
        
        while currA != currB:  # currA.val 이 아니라 currA 라는 노드 자체를 확인해야 한다.
            currB = headA if currB is None else currB.next
            currA = headB if currA is None else currA.next
            
        return currA