5 problems solved.

lintcoder · lintcoder · commit 3b016bff05bb · 2020-02-01T03:24:04.000+08:00
diff --git a/src/1021.cpp b/src/1021.cpp
@@ -0,0 +1,27 @@
+string removeOuterParentheses(string S) {
+        int len = S.size();
+        if (len == 0 || len == 2)
+            return "";
+        
+        int i = 0, last = 0;
+        int left = 0, right = 0;
+        string res("");
+        while (i < len)
+        {
+            if (S[i] == '(')
+                ++left;
+            else
+            {
+                ++right;
+                if (left == right)
+                {
+                    if (i - last + 1 > 2)
+                        res.insert(res.end(), S.begin()+last+1, S.begin()+i);
+                    last = i+1;
+                }
+            }
+            ++i;
+        }
+        
+        return res;
+    }
diff --git a/src/142.cpp b/src/142.cpp
@@ -0,0 +1,34 @@
+ListNode *detectCycle(ListNode *head) {
+        if (head == nullptr || head->next == head)
+        	return head;
+        ListNode* fast = head;
+        ListNode* slow = head;
+        fast = fast->next;
+        if (fast == nullptr)
+            return nullptr;
+        fast = fast->next;
+        slow = slow->next;
+        while (fast != nullptr && slow != nullptr)
+        {
+        	if (fast != slow)
+        	{
+        		fast = fast->next;
+        		slow = slow->next;
+        		if (fast == nullptr)
+        			return nullptr;
+        		else
+        			fast = fast->next;
+        	}
+        	else
+        		break;
+        }
+        if (fast == nullptr)
+        	return nullptr;
+        slow = head;
+        while (slow != fast)
+        {
+        	slow = slow->next;
+        	fast = fast->next;
+        }
+        return slow;
+    }
diff --git a/src/17.cpp b/src/17.cpp
@@ -0,0 +1,26 @@
+vector<string> letterCombinations(string digits) {
+        int len = digits.size();
+        vector<string> res;
+        if (len == 0)
+            return res;
+        string dict[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
+        int num[10] = {0,0,3,3,3,3,3,4,3,4};
+        
+        string s;
+        search(digits, 0, len, dict, num, s, res);
+        
+        return move(res);
+    }
+    
+    void search(const string& digits, int ct, int len, const string* dict, const int* num, string s, vector<string>& res)
+    {
+        if (ct < len)
+        {
+            int index = digits[ct]-'0';
+            int n = num[index];
+            for (int i = 0; i < n; ++i)
+                search(digits, ct+1, len, dict, num, s+dict[index][i], res);
+        }
+        else
+            res.push_back(s);
+    }
diff --git a/src/215.cpp b/src/215.cpp
@@ -0,0 +1,6 @@
+int findKthLargest(vector<int>& nums, int k) {
+        sort(nums.begin(), nums.end());
+        int len = nums.size();
+        
+        return nums[len-1-(k-1)];
+    }
diff --git a/src/23.cpp b/src/23.cpp
@@ -0,0 +1,37 @@
+ListNode* mergeKLists(vector<ListNode*>& lists) {
+        ListNode* head = nullptr;
+        lists.erase(remove(lists.begin(), lists.end(), nullptr), lists.end());
+        int len = lists.size();
+        if (len == 0)
+            return head;
+        if (len == 1)
+            return lists[0];
+        
+        struct cmp
+        {
+            bool operator()(ListNode* a, ListNode* b)
+            {
+                return a->val > b->val;
+            }
+        };
+        priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
+        for (int i = 0; i < len; ++i)
+            pq.push(lists[i]);
+        head = pq.top();
+        pq.pop();
+        if (head->next != nullptr)
+            pq.push(head->next);
+        ListNode* node = head;
+        while (!pq.empty())
+        {
+            ListNode* tmp = pq.top();
+            pq.pop();
+            if (tmp->next != nullptr)
+                pq.push(tmp->next);
+            node->next = tmp;
+            node = tmp;
+        }
+        node->next = nullptr;
+        
+        return head;
+    }
