leet code

995 - Serialize and Deserialize Binary Tree

serialize

serialize는 DFS(preorder traversal)로 serialize

deserialize

deserialize는 DFS(preorder traversal)로 deserialize

• 중첩함수의 함수 원형
• Info deserializeInternal(int idx)
• idx는 class 내부에 serialized_string이 있고, 그 string의 index입니다.
• Info 구조체
  • TreeNode* node
  • int idx
• input으로 들어가는 idx

deserialize는 좀 비효율이 있는 것 같습니다.

string을 매 함수마다 전달하고 싶지 않아서, Info라는 구조체를 만들었습니다.

• 1차 수정 후에 memory 공간효율은 좋아졌지만, 속도는 느려졌음

C++ time(beats 46.28%), space(40.82%)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

#include<string>
#include<iostream>

using namespace std;

struct Info {
    TreeNode* node;
    int idx;
};

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        //preorder traversal

        string result;
        //serialize root
        if(root)
        {
            result += to_string(root->val) + ",";
        }else
        {
            result += "#,";
            return result;
        }
        //traverse left
        result += serialize(root->left);
        //traverse right
        result += serialize(root->right);

        return result;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        _str = data;
        if(data == "") return nullptr;

        // if root is null, then return
        // if root is not null and left is null, then new node of root
        // 
        return deserializeInternal(0).node;
    }

    Info deserializeInternal(int idx){

        // process root
        Info rootInfo = getNode(idx);
        if(!rootInfo.node)
        {
            return rootInfo;
        }
        printf("node: %d\n", rootInfo.node->val);
        printf("idx: %d\n", rootInfo.idx);

        // process left
        Info leftInfo = deserializeInternal(rootInfo.idx);
        rootInfo.node->left = leftInfo.node;

        // process right
        Info rightInfo = deserializeInternal(leftInfo.idx);
        rootInfo.node->right = rightInfo.node;

        Info returnInfo;
        returnInfo.node = rootInfo.node;
        returnInfo.idx = rightInfo.idx;

        return returnInfo;
    }

    Info getNode(int idx)
    {
        char a[6]={0,};
        int i=0;
        while(true)
        {
            if(_str[idx+i] == ',' || _str[idx+i] == NULL)
                break;
            a[i] = _str[idx+i];
            i++;
        }

        Info info;
        if(_str[idx] == '#')
        {
            info.node = nullptr;
        }else
        {
            info.node = new TreeNode(atoi(a));
        }
        info.idx = idx + i + 1;
        return info;
    }

private:
    string _str;
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

C++ 1차 수정. serializer. time(beats 27.53%) space(beats 62.74%)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

#include<string>
#include<iostream>

using namespace std;

struct Info {
    TreeNode* node;
    int idx;
};

class Codec {
public:

    void serializeHelper(TreeNode* root)
    {
        //preorder traversal

        //serialize root
        if(root)
        {
            _str += to_string(root->val) + " ";
        }else
        {
            _str += "# ";
            return;
        }
        //traverse left
        serializeHelper(root->left);
        //traverse right
        serializeHelper(root->right);
    }
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        serializeHelper(root);
        return _str;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        _str = data;
        if(data == "") return nullptr;

        // if root is null, then return
        // if root is not null and left is null, then new node of root
        // 
        return deserializeInternal(0).node;
    }

    Info deserializeInternal(int idx){

        // process root
        Info rootInfo = getNode(idx);
        if(!rootInfo.node)
        {
            return rootInfo;
        }

        // process left
        Info leftInfo = deserializeInternal(rootInfo.idx);
        rootInfo.node->left = leftInfo.node;

        // process right
        Info rightInfo = deserializeInternal(leftInfo.idx);
        rootInfo.node->right = rightInfo.node;

        Info returnInfo;
        returnInfo.node = rootInfo.node;
        returnInfo.idx = rightInfo.idx;

        return returnInfo;
    }

    Info getNode(int idx)
    {
        char a[6]={0,};
        int i=0;
        while(true)
        {
            if(_str[idx+i] == ' ' || _str[idx+i] == NULL)
                break;
            a[i] = _str[idx+i];
            i++;
        }

        Info info;
        if(_str[idx] == '#')
        {
            info.node = nullptr;
        }else
        {
            info.node = new TreeNode(atoi(a));
        }
        info.idx = idx + i + 1;
        return info;
    }

private:
    string _str;
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

C++ 2차수정. deserializer. time(beats 36.14%), space(beats 67.78%)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

#include<string>
#include<iostream>

using namespace std;

struct Info {
    TreeNode* node;
    int idx;
};

class Codec {
public:

    void serializeHelper(TreeNode* root)
    {
        //preorder traversal

        //serialize root
        if(root)
        {
            _str += to_string(root->val) + " ";
        }else
        {
            _str += "# ";
            return;
        }
        //traverse left
        serializeHelper(root->left);
        //traverse right
        serializeHelper(root->right);
    }
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        serializeHelper(root);
        return _str;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        _iss = istringstream(data);
        return deserializeInternal();
    }

    TreeNode* deserializeInternal(){

        // process root
        string w;
        _iss >> w;
        if(w == "#") return nullptr;

        TreeNode* root = new TreeNode(stoi(w));

        // process left
        root->left = deserializeInternal();

        // process right
        root->right = deserializeInternal();

        return root;
    }

private:
    string _str;
    istringstream _iss;
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

C++ 다른 사람의 코드 time(64.72%), space(beats 72.47%)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        stringstream ss;
        serialize_helper(root,ss);
        return ss.str();
    }

    void serialize_helper(TreeNode* root,stringstream& ss){
        if(!root) ss<<"# ";
        else{
            ss<<root->val<<" ";
            serialize_helper(root->left,ss);
            serialize_helper(root->right,ss);
        }
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        stringstream ss(data);
        return deserialize_helper(ss);
    }

    TreeNode* deserialize_helper(stringstream& ss){
        string val="";
        ss>>val;
        if(val=="#") return nullptr;
        TreeNode* root=new TreeNode(stoi(val));
        root->left=deserialize_helper(ss);
        root->right=deserialize_helper(ss);
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

이것보다 좀 더 최적화 하려면, stringstream을 직접 for loop 돌게 하면 됩니다.

principle-of-recursion - 1440

수행 시간은 상위권에 있는 정답을 제출해도 전혀 재현되지 않았습니다.

따라서 여기에 표시하지 않았습니다.

C++

class Solution {
public:
    void reverseString(vector<char>& s) {
        char tmp;
        for (int i = 0, j=s.size()-1; i < j ; ++i, --j) {
            tmp = s[i];
            s[i] = s[j];
            s[j] = tmp;
        }
    }
};

principle-of-recursion - 1681

가장 빠른 구현으로 풀었는데, 이상하네요..

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:
    ListNode* swapPairs(ListNode* head) {

        ListNode* cur = head;
        int tmp;

        while(cur && cur->next)
        {
            tmp = cur->val;
            cur->val = cur->next->val;
            cur->next->val = tmp;

            cur = cur->next->next;
        }

        return head;
    }
};

2378 - Reverse Linked List

C++ 아무생각 없이 푼거 time(beats 97.17%)

/**
 * 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:
    ListNode* reverseList(ListNode* head) {
        ListNode* resultDummyHead = new ListNode(0);
        ListNode* cur = head;
        while(cur)
        {
            ListNode* newNode = new ListNode(cur->val);
            newNode->next = resultDummyHead->next;
            resultDummyHead->next = newNode;

            cur = cur->next;
        }
        return resultDummyHead->next;
    }
};

C++ memory O(1). time(beats 97.17%), space(beats 40.99%)

/**
 * 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:
    ListNode* reverseList(ListNode* head) {
        if(!head) return head;
        if(!head->next) return head;
        ListNode* prev = nullptr;
        ListNode* curr = head;
        ListNode* next = curr->next;

        while(curr)
        {
            ListNode* tmpNext = curr->next;
            curr->next = prev;

            prev = curr;
            curr = next;
            if(tmpNext)
                next = tmpNext->next;
        }

        return prev;
    }
};

3233 - Search in a Binary Search Tree

이 문제는 쉬웠습니다.

C++ time(beats 85.32%), space(beats 62.77%)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(!root) return nullptr;

        // process root
        if(root->val == val) return root;

        // process left
        TreeNode* left = searchBST(root->left, val);
        if(left)
            return left;

        // process right
        TreeNode* right = searchBST(root->right, val);
        if(right)
            return right;

        return nullptr;
    }
};

3234 - Pascal's Triangle II

C++ time(beats 100%), space(beats 31.49%)

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row{1};

        while(rowIndex--)
        {
            vector<int> row2{1};
            for(int i=0; i<row.size()-1; ++i)
            {
                row2.push_back(row[i]+row[i+1]);
            }
            row2.push_back(1);

            row = row2;
        }

        return row;
    }
};

1661 - Fibonacci Number

C++ time(beats 100%), space(beats 95.86%)

class Solution {
public:
    int fib(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        if(n==2) return 1;
        if(cache[n]) return cache[n];

        int result = fib(n-1) + fib(n-2);
        if(!cache[n]) cache[n] = result;
        return result;
    }

private:
    int cache[32] = {0, };
};

1662 - Climbing Stairs

C++ time(beats 100%), space(beats 96.86%)

class Solution {
public:
    int climbStairs(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        if(n==3) return 3;

        if(cache[n]) return cache[n];

        int result = climbStairs(n-1) + climbStairs(n-2);
        cache[n] = result;

        return result;
    }

private:
    int cache[47]= {0, };
};

2375 - Maximum Depth of Binary Tree

C++ time(beats 69.03%), space(beats 52.13%)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        queue<TreeNode*> q;
        q.push(root);

        int rslt = 0;
        while(!q.empty())
        {
            int qLen = q.size();
            for(int i=0; i<qLen; ++i)
            {
                TreeNode* cur = q.front();
                q.pop();
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
            rslt++;
        }

        return rslt;
    }
};

1144 - Find Pivot Index

C++ time(beats 58.03%), space(beats 64.42%)

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int total = 0;
        int left = 0;
        for(int i=0; i<nums.size(); ++i)
            total += nums[i];
        for(int i=0; i<nums.size(); ++i)
        {
            if(left==total-nums[i])
                return i;
            left += nums[i];
            total -= nums[i];
        }

        return -1;
    }
};

1147 - Largest Number At Least Twice of Others

C++

class Solution {
public:
    int dominantIndex(vector<int>& nums) {
        int max = 0;
        int maxIdx = 0;
        for(int i=0; i<nums.size(); ++i)
            if(nums[i] > max)
            {
                max = nums[i];
                maxIdx = i;
            }
        int half = max/2;
        printf("%d\n", half);
        for(int i=0; i<nums.size(); ++i)
            if(i!=maxIdx && nums[i] > half) return -1;
        return maxIdx;
    }
};