for Robot Artificial Inteligence

21. Delete Node in a Linked List

|

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode* t; // temp node
        t = node->next; // node 넥스트부터 값을 받음
        * node = * t; // 노드 넥스트를 노드로 기준 옮김, 둘다 포인터이므로, 카피할때는 포인터로 다시 가르켜야한다.
        delete t;
    }
};

Comment  Read more

20. Longest common Prefix

|

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string prefix = "";
        if(strs.empty())
            return prefix;

        for(int i =0; i<strs[0].size();i++) // flower , size 6;
        {
            int j=1;
            for(;j<strs.size();j++) // j는 각각 string element에 prefix를 체크하는 역할
                // 각각 string 엘레먼트의 i번째를 체크, 만약 틀리다면 바로 return prefix.
                // 즉 second for loop에서의 한바퀴 도는 것은 각각 엘레먼트의 i 값을 체크하는 것이다.
            {
                if(strs[0][i]!=strs[j][i])
                    return prefix;
            }
            if(j==strs.size())
            {
                prefix+=strs[0][i];
            }
        }
        return prefix;
    }
};
  • 주의해야할 점, logic 할때 “!=”로 해야한다.

Comment  Read more

19. count and say[난이도上]

|

  • to_string() <- integer를 string으로 바꿔주는 함수
class Solution {
public:
    string countAndSay(int n) {
        if(n==0)
            return "";
        string res = "1";
        while(--n)
        {
            string current = "";
            for(int i =0; i<res.size();i++)
            {
                //first is size 1
                int count =1;
                while((i+1<res.size())&&(res[i]==res[i+1]))
                {
                    // it is false for first res however, after it is activated.
                    count++;
                    i++;
                }
                current += to_string(count) + res[i];
            }
            res = current;
        }
        return res;
    }
};

Comment  Read more

18. Implement strStr()

|

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.size(), n = needle.size();
        for (int i = 0; i <= m - n; i++) {
            int j = 0;
            for (; j < n; j++) {
                if (haystack[i + j] != needle[j]) {
                    break;
                }
            }
            if (j == n) {
                return i;
            }
        }
        return -1;
    }
};
  • 하나하나 걸쳐서 하는 것이다
  • 즉 i는 기준점(pivot)이 되고 needle 크기만큼 움직인다.(j) 그리고 그 needle의 엘레먼트와 해당 지준점으로 부터 needle size값 만큼 traversal하게 되는 j 값이 일치할떄 second for loop가 break 없이 종료가 되고 j 값은 needle.size() 만큼의 값이 됨으로, j==needle.size() 조건을 만족을 한다면 needle의 단어를 haystack 찾음으로 해당 기준점 index i를 리턴한다
  • 그렇지 않고 만약 기준점 i로 부터 needle size값 만큼 traversal하게 될때 needle와 엘레먼트 값과 haystack 기준점으로부터 시작하는 needle size 만큼의 값이 일치하지 않다면 break를 하여 second for loop를 종료하고, 이떄 j의 값은 second for loop가 complete 되지 않은 상태에서 종료하였기 때문에 needle.size()값과 최종 traversal한 j의 값이 일치하지 않으므로 first for loop를 다시 반복한다.

  • 설명 : http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220917078260

Comment  Read more

17. String to Integer (atoi)

|

class Solution {
public:
    int myAtoi(string str) {
        int result = 0;
        if(str[0]>=65)
            return 0;
        result = stoi(str);
        if(result>=INT_MAX) return INT_MAX;
        if(result<=INT_MIN) return INT_MIN;
        return result;
    }
};
  • discards all leading whitespaces
  • indicator(-1 or 1)
  • overflow
  • invalid input
class Solution {
public:
    int myAtoi(string str) {
        int indicator = 1, base = 0, i = 0;
        cout<<str[0] - '0';
        while(str[i]==' '){i++;}
        if(str[i] == '-' || str[i]=='+')
        {
            indicator = 1 - 2*(str[i++]=='-'); // 만약 트루면 1-2=-1, 아니면 1-0 =1
        }
        while(str[i]>='0' && str[i] <= '9')// 범위 0~9(여기선 아직 character 데이터 유형)
        {
            if(base>INT_MAX/10 || (base==INT_MAX/10 && str[i]-'0'>7)) // str[i]-'0', 즉 integer로 바꾸눈 문구. 7보다 커야한다.
            {
                if(indicator == 1) return INT_MAX;
                else return INT_MIN;
            }
            base = 10*base + (str[i++]-'0');
        }
        return base*indicator;

    }
};

  • str[i] - ‘0’ 뒤에 ‘0’ 붙이는 거 자채가 character값을 integer 값으로 바꾸는 것이다.

Comment  Read more