청정알고리즘

문제

Given a linked list, remove the n-th node from the end of list and return its head.

풀이

어떤 node를 지우기 위해선 그 노드의 앞 node를 알아야한다.

head node는 앞 node가 없기 때문에, 임시로 prev node를 만들어서 앞에 붙여준다.

그 후, 두개의 포인터를 관리하는데, 서로 차이가 n+1만큼 떨어지게 관리한다.

이렇게 하면 앞쪽 포인터가 NULL에 도착했을 때, 뒷쪽포인터는 지워야할 node의 앞 node를 가리키게 된다.

따라서 뒷쪽포인터를 이용하여, 삭제작업을 진행하면 된다.

Time Complexity : $O(n)$

코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode * prev = new ListNode(0);
        prev->next=head;
        ListNode * n1= prev;
        ListNode * n2= prev;
        
        for(int i=0;i<=n;i++) n2=n2->next;
        while(n2)
        {
            n1=n1->next;
            n2=n2->next;
        }
        ListNode * d = n1->next;
        n1->next=n1->next->next;
        delete d;
        
        return prev->next;
    }
};

문제

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d= target? Find all unique quadruplets in the array which gives the sum of target.

풀이

3Sum과 같은 방식으로 풀이한다.

Index 두 개를 잡고, 3Sum과 같은 방식으로 계산한다.

Time Complexity : $O(n^3)$

코드

class Solution {
public:
    vector< vector<int> > fourSum(vector<int> &nums, int target) {
        vector<vector<int> > ret;
        sort(nums.begin(), nums.end());
        int l = nums.size();
        for(int z=0;z<l-3;z++)
        {
            for (int i=z+1;i<l-2;i++)
            {
                int j=i+1, k=l-1;
                while(j<k)
                {
                    int sum = nums[z] + nums[i] + nums[j] + nums[k];
                    if (sum > target){k--; continue;}
                    if (sum < target){j++; continue;}

                    ret.push_back({nums[z],nums[i],nums[j],nums[k]});
                    while(j<l-1 && nums[j+1]==nums[j]) j++;
                    while(k>0 && nums[k-1]==nums[j]) k--;
                    j++, k--;
                }
                while(i<l-1 && nums[i+1]==nums[i]) i++;
            }
            
            while(z<l-1 && nums[z+1]==nums[z]) z++;
        }
        return ret;
    }
};

문제

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

풀이

재귀함수를 이용하여 구한다.

string $s$에서 맨 앞 글자를 빼고 구성한 string을 $s'$이라고 하면

$letterCombinations(s)$ = (맨 앞글자 한 글자에 해당하는 글자 리스트) $\prod letterCombinations(s')$ 

이므로, 이 관계를 이용하여 함수를 구현한다.

Time Complexity : $O(4^|S|)$

코드

class Solution {
private:
    vector<string> let[10]={{},{},{"a","b","c"},{"d","e","f"},
                           {"g","h","i"},{"j","k","l"},
                           {"m","n","o"},{"p","q","r","s"},
                           {"t","u","v"},{"w","x","y","z"}};
public:
    vector<string> letterCombinations(string digits) {
        if(digits=="") return vector<string>();
        
        vector<string> ret(0);
        int num = digits[0]-'0';
        if(digits.length()==1)return let[num];
        
        vector<string> s=letterCombinations(digits.substr(1));
        for(int i=0;i<let[num].size();i++)
            for(int j=0;j<s.size();j++)
                ret.push_back(let[num][i]+s[j]);
        return ret;
    }
};