청정알고리즘

문제

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

풀이

음수인 경우는 무조건 false를 return한다.

양수인 경우에는 Reverse Integer를 구해서 같은지 체크한다.

Time Complexity : $O(logn)$

코드

class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0) return false;
        long long num=0, t=x;
        while(t)
        {
            num = num*10+t%10;
            t/=10;
        }
        return x==num;
    }
};

문제

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

풀이

우선 글의 앞에 공백이 있을 수도 있으니, 앞에 있는 공백을 전부 제거한다.

그 후 가장 첫 글자가 부호인 경우에 $sgn$변수에 부호를 저장해준다.

그리고 정답을 저장하는 변수인 $ans$에 $ans=ans*10 + str[i]-\text{'0'}$를 계속 더해주면 된다.

Reverse Integer 문제와 마찬가지로 boundary case처리를 해주면 끝난다.

Time Complexity : $O(n)$

코드

class Solution {
public:
    int myAtoi(string str) {
        int st, ans=0, sgn=1;
        for(st=0;str[st]==' '&&st<str.length();st++);
        
        if(str[st]=='-')
        {
            sgn=-1;
            st++;
        }
        else if(str[st]=='+') st++;
        
        for(int i=st;i<str.length();i++)
        {
            if(str[i]<'0' || str[i]>'9') break;
            int num = str[i]-'0';
            if(ans>INT_MAX/10 || (ans==INT_MAX/10 && num>7)) return INT_MAX;
            if(ans<INT_MIN/10 || (ans==INT_MIN/10 && num>8)) return INT_MIN;
            ans = ans * 10 + num*sgn;
        }
        return ans;
    }
};

문제

Given a 32-bit signed integer, reverse digits of an integer.

풀이

$ans$ 변수를 관리 하면서

ans = 10*ans + x%10;
x /=10;

를 반복하면 된다.

주의해야할 점은, boundary condition을 처리하는 것이다.

첫 줄을 계산할 때 INT_MAX를 넘거나 INT_MIN보다 작아지면 바로 return 해준다.

Time Complexity : $O(log n)$

코드

class Solution {
public:
    int reverse(int x) {
        int ans = 0;
        while(x)
        {
            int num = x%10;
            x/=10;
            if(ans > INT_MAX/10 ||( ans == INT_MAX/10 && num>7))return 0;
            if(ans < INT_MIN/10 || (ans == INT_MIN/10 && num<-8))return 0;
            ans = ans*10+num;
        }
        return ans;
    }
};

문제

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P      A       H      N

  A  P   L  S   I   I   G

    Y        I        R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

풀이

$jmp=2\times \text{numRows}-2$의 주기로 반복되는 규칙이 생긴다는 것을 캐치하자.

그러면 줄별로 주기가 $jmp$가 되고, 규칙에 맞게 순서대로 출력을 하면 끝난다.

첫줄과 마지막 줄은 $jmp$마다 1개씩, 나머지 줄은 2개씩 포함된다는 것을 캐치한다면 나머지는 구현.

Time Complexity : $O(n)$  

코드

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows==1) return s;
        
        string ret;
        int l=s.size(), jmp = 2*numRows-2;
        
        for(int i=0;i<numRows;i++)
        {
            for(int j=0;j+i<l; j+=jmp)
            {
                ret += s[j+i];
                if(i!=0 && i!= numRows-1 && j+jmp-i<l) ret+=s[j+jmp-i];
            }
        }
        return ret;
    }
};

문제

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

풀이

문자열 내에서 Palindrome을 찾는 알고리즘으로 Manacher's Algorithm이 있다.

이를 이용하여 $O(n)$의 시간복잡도로 원하는 답을 찾을 수 있다.

Time Complexity : $O(n)$

코드

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.length()==0)return s;
        string sm;
        sm.push_back('$');
        for(int i=0;i<s.length();i++)
        {
            sm.push_back(s[i]);
            sm.push_back('$');
        }
        
        int r=0,p=0,l=sm.length(), ans=0, ansind;
        vector<int> a(l);
        for (int i=0;i<l;i++)
        {
            a[i] = i<=r?min(a[2*p-i],r-i):0;
            while (i-a[i]-1 >= 0 && i+a[i]+1 <l && sm[i-a[i]-1] == sm[i+a[i]+1]) a[i]++;
            if (r < i+a[i]) r = i+a[i], p = i;
            if(ans<a[i]) ans=a[i], ansind=i;
        }
        return s.substr((ansind-ans)/2,ans);      

    }
};

문제

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

풀이

전형적인 binary search 문제이다.

$l1=nums1.size(), l2=nums2.size()$라고 하자.

$nums1$에서 binary search를 돌리는 데 찾는 것은 다음과 같다.

'$nums1[i]$보다 작거나 같은 숫자가 $nums1, nums2$ 합쳐서 $(l1+l2+1)/2$ 개 이상이 되는 최소한의 index i'

현재 $nums1$에서의 index를 $m_1$이라고 하면 해당하는 $nums1[m_1]$보다 작은 숫자가 $nums1$에는 $m_1$개 있을 것이다.

따라서 $nums2$에 $m_2=(m1+m2+1)/2 - m_1$개가 있어야 한다.

리스트의 상황을 간단히 그리면 다음과 같다.

nums1[0]    nums1[1]   ...   nums1[$m_1-1$] |||  nums1[$m_1$]  ... 

nums2[0]    nums2[1]   ...   nums2[$m_2-1$] |||  nums2[$m_2$]   ...

각 list가 정렬되어 있음은 주어진 조건이므로 우리는

$nums2[m_2-1] <= nums1[m_1]$과 $nums1[m_1-1] <= nums2[m_2]$만 체크하면 충분하다.

첫번째 조건을 만족하지 못하면 $nums1[m_1]$이 너무 작다는 뜻이니, $m_1$을 증가시켜주면 되고

두번째 조건을 만족하지 못하면 반대로 $nums1[m_1]$이 너무 크다는 뜻이니 $m_1$을 감소시켜주면 된다.

이 조건을 이용하여 binary search를 진행하여 중간값을 찾는다.

그렇게 하면 |||로 나누어진 구간 왼쪽과 오른쪽에 숫자가 반반씩 있게 되고,

홀짝을 비교하여 ||| 앞뒤에 있는 4개의 숫자를 단순계산하여 중간값을 찾을 수 있다.

Time Complexity : $O(log(n+m))$

코드

class Solution {
public:
    double findMedianSortedArrays(vector& nums1, vector& nums2) {
        vector& n1=(nums1.size()<nums2.size()?nums1:nums2);
        vector& n2=(nums1.size()<nums2.size()?nums2:nums1);
        
        int l1 = n1.size(), l2=n2.size();
        int l=0, r=l1, midnum = (l1+l2+1)>>1;
        while(l<=r)
        {
            int m1 = (l+r)>>1;
            int m2 = midnum-m1;
            if(m1>r && n2[m2-1]>n1[m1]) l = m1+1;
            else if( m1>l && n1[m1-1]>n2[m2]) r=m1-1;
            else
            {
                int ans;
                if(m1==0) ans=n2[m2-1];
                else if(m2==0) ans=n1[m1-1];
                else ans = max(n1[m1-1], n2[m2-1]);
                if((l1+l2)&1) return ans;
                
                int ans2;
                if(m1==l1) ans2 = n2[m2];
                else if(m2==l2) ans2= n1[m1];
                else ans2 = min(n1[m1], n2[m2]);
                return (ans+ans2)/2.0;
            }
        }
        return 0.0;
    }
};

문제

Given a string, find the length of the longest substring without repeating characters.

풀이

Sliding Window 방식을 사용한다. 

반복되는 문자가 없는 Window를 계속 관리해준다.

새 문자가 window에 추가될 때, 이 문자가 window에 없는 문자면 그냥 window를 늘려가면 되고,

이미 등장한 문자면 현재 추가될 문자의 가장 최신 위치를 찾아서, 그 앞까지를 새로운 window로 정하면 된다.

이를 빠르게 계산하기 위해 알파벳별로 최근에 등장한 위치를 저장해두면서 관리한다.

이를 계산해놓으면 새 문자가 추가될때, 해당하는 window를 O(1)에 계산할수 있다.

Time Complexity : $O(n)$

코드

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int l=s.length(),ans=0;
        int index[128]={0,};
        
        for(int i=0,j=0;j<l;j++)
        {
            i = max(index[s[j]],i);
            ans = max(ans, j-i+1);
            index[s[j]] = j+1;
        }
        return ans;
    }
};

문제

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

풀이

list를 순회하면서 실제 덧셈을 하는 것 같이 계산을 해준다.

받아올림할 변수인 carry를 잘 관리하는 것이 핵심.

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* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry=0;
        ListNode *ans=new ListNode(0);
        ListNode *p=l1;
        ListNode *q=l2;
        ListNode *now=ans;
        while(p!=NULL || q!=NULL)
        {
            int s =(p?p->val:0)+(q?q->val:0)+carry;
            carry = s/10;
            now->next = new ListNode(s%10);
            now = now->next;
            if(p) p=p->next;
            if(q) q=q->next;
        }
        if(carry) now->next = new ListNode(carry);
        return ans->next;
    }  
};

문제

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

풀이

해쉬맵을 이용해서 nums에 있는 모든 숫자들을 (숫자, index) pair로 저장한다.

그 후 nums를 모두 돌면서, 합이 target이 되는 원소가 nums에 존재하는 지를 찾으면 끝난다.

주의할점은 index를 확인하면서 현재 index와 더할 숫자의 index가 다른것을 체크해 주어야한다.

Time Complexity : $O(n)$

코드

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        unordered_map<int,int> m;
        vector ret;
        for(int i=0;i<nums.size();i++) m[nums[i]]=i;
        
        for(int i=0;i<nums.size();i++)
        {
            int t = target-nums[i];
            if(m.find(t)!=m.end() && m[t]!=i)
            {
                ret.push_back(i);
                ret.push_back(m[t]);
                return ret;
            }
        }
        return nums;
    }
};