Linked List Components(Array,Hash Table,Linked List)

https://leetcode.com/problems/linked-list-components/description/

You are given the head of a linked list containing unique integer values and an integer array nums that is a subset of the linked list values.

Return the number of connected components in nums where two values are connected if they appear consecutively in the linked list.

 

Example 1:

Input: head = [0,1,2,3], nums = [0,1,3]
Output: 2
Explanation: 0 and 1 are connected, so [0, 1] and [3] are the two connected components.

Example 2:

Input: head = [0,1,2,3,4], nums = [0,3,1,4]
Output: 2
Explanation: 0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.

 

Constraints:

• The number of nodes in the linked list is n.
• 1 <= n <= 104
• 0 <= Node.val < n
• All the values Node.val are unique.
• 1 <= nums.length <= n
• 0 <= nums[i] < n
• All the values of nums are unique.

가볍게 linked list 문제도 하나 풀어보고 넘어갑시다.

 

잠깐의 생각이 필요한 문제였지만, 큰 어려움 없이 극복

 

1. Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:
        ans = 0
        s = set(nums)
        while head :
            if head.val in s :
                ans += 1
                temp = head
                while temp and temp.val in s:
                    temp = temp.next
                head = temp
            else:
                head = head.next
        return ans

 

2. C

find 함수는 내가 걍 만들어줬다.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool find(int* a, int size, int target){
    for(int i=0;i<size;i++){
        if(a[i]==target) return true;
    }
    return false;
}

int numComponents(struct ListNode* head, int* nums, int numsSize) {
    int ans = 0;
    while(head){
        if(find(nums,numsSize,head->val)){
            ans++;
            struct ListNode* temp = head;
            while(temp && find(nums,numsSize,temp->val)){
                temp = temp->next;
            }
            head = temp;
        }
        else head = head->next;
    }
    return ans;
}

 

 

3. C++

사실, Python이랑 C로 풀어지는 문제는 무조건 C++로도 풀린다..!

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int numComponents(ListNode* head, vector<int>& nums) {
        int ans = 0;
        while(head){
            if(find(nums.begin(),nums.end(),head->val)!=nums.end()){
                ans++;
                ListNode* temp = head;
                while(temp && find(nums.begin(),nums.end(),temp->val)!=nums.end()){
                    temp = temp->next;
                }
                head = temp;
            }
            else head = head->next;
        }
        return ans;
    }
};

 

C++ Unordered_set 에서 find는 map과 같이 s.find(~~value) 이런 식으로 하면 되고 이것이 s.end() 와 같냐 안 같냐로 find 성공 여부를 판단하면 된다.