6 problems solved.

lintcoder · lintcoder · commit 541756281092 · 2021-10-10T20:51:33.000+08:00
diff --git a/src/116.cpp b/src/116.cpp
@@ -0,0 +1,26 @@
+Node* connect(Node* root) {
+        if (root == nullptr || (root->left == nullptr && root->right == nullptr))
+            return root;
+        
+        doconnect(root);
+        
+        return root;
+    }
+    
+    void doconnect(Node* node)
+    {
+        if (node->left != nullptr)
+        {
+            Node* tmp = node;
+            Node* nd = node->left;
+            while (tmp->next != nullptr)
+            {
+                nd->next = tmp->right;
+                nd = tmp->next->left;
+                tmp->right->next = nd;
+                tmp = tmp->next;
+            }
+            nd->next = tmp->right;
+            doconnect(node->left);
+        }
+    }
diff --git a/src/117.cpp b/src/117.cpp
@@ -0,0 +1,56 @@
+Node* connect(Node* root) {
+        if (root == nullptr || (root->left == nullptr && root->right == nullptr))
+            return root;
+        
+        doconnect(root);
+        
+        return root;
+    }
+    
+    void doconnect(Node* node)
+    {
+        Node* tmp = node;
+        Node* first = nullptr;
+        while (tmp != nullptr)
+        {
+            if (tmp->left != nullptr)
+            {
+                first = tmp->left;
+                break;
+            }
+            if (tmp->right != nullptr)
+            {
+                first = tmp->right;
+                break;
+            }
+            tmp = tmp->next;
+        }
+        
+        if (first != nullptr)
+        {
+            Node* nd = first;
+            if (tmp->left == first && tmp->right != nullptr)
+            {
+                nd->next = tmp->right;
+                nd = tmp->right;
+            }
+            
+            Node* cur = tmp->next;
+            while (cur != nullptr)
+            {
+                if (cur->left != nullptr)
+                {
+                    nd->next = cur->left;
+                    nd = cur->left;
+                }
+                if (cur->right != nullptr)
+                {
+                    nd->next = cur->right;
+                    nd = cur->right;
+                }
+                cur = cur->next;
+            }
+            
+            doconnect(first);
+        }
+    }
diff --git a/src/1893.cpp b/src/1893.cpp
@@ -0,0 +1,30 @@
+bool isCovered(vector<vector<int>>& ranges, int left, int right) {
+        int len = ranges.size();
+        if (len == 0)
+            return false;
+        auto cmp = [](const vector<int>& a, const vector<int>& b) {
+            return (a[0] < b[0] || (a[0]==b[0] && a[1] < b[1]));
+        };
+        sort(ranges.begin(), ranges.end(), cmp);
+        
+        int lh = left, rh = right;
+        for (int i = 0; i < len; ++i)
+        {
+            if (lh >= ranges[i][0] && lh <= ranges[i][1])
+            {
+                if (rh <= ranges[i][1])
+                    return true;
+                else
+                    lh = ranges[i][1]+1;
+            }
+            if (rh >= ranges[i][0] && rh <= ranges[i][1])
+            {
+                if (lh >= ranges[i][0])
+                    return true;
+                else
+                    rh = ranges[i][0]-1;
+            }
+        }
+        
+        return false;
+    }
diff --git a/src/227.cpp b/src/227.cpp
@@ -0,0 +1,74 @@
+int calculate(string s) {
+        int len = s.size();
+        int i = 0;
+        deque<char> dq;
+        
+        int n = 0;
+        while (i < len)
+        {
+            if (s[i] != ' ')
+            {
+                dq.push_back(s[i]);
+                ++n;
+            }
+            ++i;
+        }
+        
+        i = 0;
+        int v = 0;
+        deque<int> number;
+        deque<char> op;
+        bool flag = false;
+        while (i < n)
+        {
+            if (dq[i] >= '0' && dq[i] <= '9')
+            {
+                v = v*10 + (dq[i]-'0');
+                ++i;
+                flag = true;
+            }
+            else
+            {
+                if (dq[i] == '+' || dq[i] == '-')
+                {
+                    number.push_back(v);
+                    op.push_back(dq[i]);
+                    v = 0;
+                    ++i;
+                    flag = false;
+                }
+                else
+                {
+                    char c = dq[i];
+                    ++i;
+                    int v2 = 0;
+                    while (i < n && dq[i] >= '0' && dq[i] <= '9')
+                    {
+                        v2 = v2*10 + (dq[i]-'0');
+                        ++i;
+                    }
+                    if (c == '*')
+                        v *= v2;
+                    else
+                        v /= v2;
+                    flag = true;
+                }
+            }
+        }
+        if (flag)
+            number.push_back(v);
+        
+        int k = op.size();
+        int j = 0;
+        int sum = number[0];
+        while (j < k)
+        {
+            if (op[j] == '+')
+                sum += number[j+1];
+            else
+                sum -= number[j+1];
+            ++j;
+        }
+        
+        return sum;
+    }
diff --git a/src/25.cpp b/src/25.cpp
@@ -0,0 +1,53 @@
+ListNode* reverseKGroup(ListNode* head, int k) {
+        if (head == nullptr || head->next == nullptr || k == 1)
+            return head;
+        
+        int sz = 0;
+        ListNode* tmp = head;
+        while (tmp != nullptr)
+        {
+            tmp = tmp->next;
+            ++sz;
+        }
+        
+        int q = sz/k;
+        int r = sz - q*k;
+        int i = 1, n = 0;
+        ListNode* h = nullptr;
+        ListNode* tail = nullptr;
+        ListNode* ps = head, *pds = head, *pde = head;
+        ps = ps->next;
+        while (i < k)
+        {
+            ListNode* pp = ps->next;
+            ps->next = pds;
+            pds = ps;
+            ps = pp;
+            ++i;
+        }
+        h = pds;
+        ++n;
+        tail = pde;
+        
+        while (n < q)
+        {
+            pds = ps;
+            pde = ps;
+            i = 1;
+            ps = ps->next;
+            while (i < k)
+            {
+                ListNode* pp = ps->next;
+                ps->next = pds;
+                pds = ps;
+                ps = pp;
+                ++i;
+            }
+            tail->next = pds;
+            tail = pde;
+            ++n;
+        }
+        
+        tail->next = ps;
+        return h;
+    }
diff --git a/src/57.cpp b/src/57.cpp
@@ -0,0 +1,64 @@
+vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
+        vector<vector<int>> res;
+        int len = intervals.size();
+        if (len == 0)
+        {
+            res.push_back(newInterval);
+            return res;
+        }
+        
+        int pos[2] = {-1,-1};
+        for (int i = 0; i < 2; ++i)
+        {
+            int j = 0;
+            for (; j < len; ++j)
+            {
+                if (newInterval[i] <= intervals[j][1])
+                {
+                    pos[i] = j;
+                    break;
+                }
+            }
+            if (pos[i] == -1)
+                pos[i] = len;
+        }
+        
+        if (pos[0] == pos[1])
+        {
+            if (pos[0] == len || newInterval[1] < intervals[pos[0]][0])
+            {
+                res.reserve(len+1);
+                for (int i = 0; i < pos[0]; ++i)
+                    res.push_back(intervals[i]);
+                res.push_back(newInterval);
+                for (int i = pos[0]; i < len; ++i)
+                    res.push_back(intervals[i]);
+                return res;
+            }
+            else
+            {
+                intervals[pos[0]][0] = newInterval[0] < intervals[pos[0]][0] ? newInterval[0] : intervals[pos[0]][0];
+                return intervals;
+            }
+        }
+        else
+        {
+            for (int i = 0; i < pos[0]; ++i)
+                res.push_back(intervals[i]);
+            int lh = newInterval[0] < intervals[pos[0]][0] ? newInterval[0] : intervals[pos[0]][0];
+            if (pos[1] == len || newInterval[1] < intervals[pos[1]][0])
+            {
+                res.push_back({lh, newInterval[1]});
+                for (int i = pos[1]; i < len; ++i)
+                    res.push_back(intervals[i]);
+            }
+            else
+            {
+                res.push_back({lh, intervals[pos[1]][1]});
+                for (int i = pos[1]+1; i < len; ++i)
+                    res.push_back(intervals[i]);
+            }
+            
+            return res;
+        }
+    }
