{"id":1012,"date":"2017-06-21T19:48:49","date_gmt":"2017-06-21T11:48:49","guid":{"rendered":"http:\/\/www.mrtblog.cn\/?p=1012"},"modified":"2023-03-05T18:08:20","modified_gmt":"2023-03-05T10:08:20","slug":"%e3%80%90c%e3%80%91%e3%80%90leetcode%e3%80%912020-5-162020-6-30","status":"publish","type":"post","link":"http:\/\/www.mrtblog.cn\/?p=1012","title":{"rendered":"\u3010C++\u3011\u3010LeetCode\u30112020.5.16~2020.6.30"},"content":{"rendered":"
<\/span> 1,361<\/span> Views<\/span><\/div>

21. Merge Two Sorted Lists<\/strong><\/em><\/p>\n

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.<\/p>\n

Example:<\/p>\n

Input: 1->2->4, 1->3->4
\nOutput: 1->1->2->3->4->4<\/p>\n

\n\/**\n* Definition for singly-linked list.\n* struct ListNode {\n*     int val;\n*     ListNode *next;\n*     ListNode() : val(0), next(nullptr) {}\n*     ListNode(int x) : val(x), next(nullptr) {}\n*     ListNode(int x, ListNode *next) : val(x), next(next) {}\n* };\n*\/\nclass Solution {\npublic:\n    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {\n        if (!l1) return l2;\n        if (!l2) return l1;\n        ListNode* head = new ListNode();\n        ListNode* tmp = head;\n        while(l1 && l2)\n        {\n            if (l1->val < l2->val)\n            {\n                tmp->next = l1;\n                l1 = l1->next;\n            }\n            else\n            {\n                tmp->next = l2;\n                l2 = l2->next;\n            }\n            tmp = tmp->next;\n        }\n        while (l1)\n        {\n            tmp->next = l1;\n            l1 = l1->next;\n            tmp = tmp->next;\n        }\n        while (l2)\n        {\n            tmp->next = l2;\n            l2 = l2->next;\n            tmp = tmp->next;\n        }\n        return head->next;\n    }\n};\n<\/code><\/pre>\n
\n
22. Generate Parentheses<\/strong><\/em>
\nGiven n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.<\/p>\n
For example, given n = 3, a solution set is:<\/p>\n
[
\n“((()))”,
\n“(()())”,
\n“(())()”,
\n“()(())”,
\n“()()()”
\n]<\/p>\n
\nclass Solution {\npublic:\n    void DFS(int l, int r, string s, vector<string> &res)\n    {\n        if (l == 0 && r == 0)\n        {\n            res.push_back(s);\n        }\n        if (l > 0)\n        {\n            DFS(l - 1, r, s + "(", res);\n        }\n        if (r > 0 && l < r)\n        {\n            DFS(l, r - 1, s + ")", res);\n        }\n    }\n    vector<string> generateParenthesis(int n) {\n        vector<string> res;\n        DFS(n, n, "", res);\n\n        return res;\n    }\n};\n<\/code><\/pre>\n
\n
23. Merge k Sorted Lists<\/strong><\/em><\/p>\n
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.<\/p>\n
Example:<\/p>\n
Input:
\n[
\n1->4->5,
\n1->3->4,
\n2->6
\n]
\nOutput: 1->1->2->3->4->4->5->6<\/p>\n
\n\/**\n* Definition for singly-linked list.\n* struct ListNode {\n*     int val;\n*     ListNode *next;\n*     ListNode() : val(0), next(nullptr) {}\n*     ListNode(int x) : val(x), next(nullptr) {}\n*     ListNode(int x, ListNode *next) : val(x), next(next) {}\n* };\n*\/\nclass Solution {\npublic:\n    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {\n        if (!l1) return l2;\n        if (!l2) return l1;\n        ListNode* head = new ListNode();\n        ListNode* tmp = head;\n        while(l1 && l2)\n        {\n            if (l1->val < l2->val)\n            {\n                tmp->next = l1;\n                l1 = l1->next;\n            }\n            else\n            {\n                tmp->next = l2;\n                l2 = l2->next;\n            }\n            tmp = tmp->next;\n        }\n        while (l1)\n        {\n            tmp->next = l1;\n            l1 = l1->next;\n            tmp = tmp->next;\n        }\n        while (l2)\n        {\n            tmp->next = l2;\n            l2 = l2->next;\n            tmp = tmp->next;\n        }\n        return head->next;\n    }\n    ListNode* mergeKLists(vector<ListNode*>& lists) {\n        if (lists.size() == 0)\n        {\n            return NULL;\n        }\n        \/\/0 1 2 3 4 5 6 7-> 0 2 4 6-> 0 4 -> 0\n        int step = 1;\n        while (step < lists.size())\n        {\n            for (int i = 0; i < lists.size();i += 2*step)\n            {\n                ListNode* left = lists[i];\n                ListNode* right = NULL;\n                if (i + step < lists.size())\n                {\n                    right = lists[i + step];\n                }\n                lists[i] = mergeTwoLists(left, right);\n            }\n            step *= 2;\n        }\n        return lists[0];\n    }\n};\n<\/code><\/pre>\n
\n
24. Swap Nodes in Pairs<\/strong><\/em>
\nGiven a linked list, swap every two adjacent nodes and return its head.<\/p>\n
You may not modify the values in the list’s nodes, only nodes itself may be changed.<\/p>\n
Example:<\/p>\n
Given 1->2->3->4, you should return the list as 2->1->4->3.<\/p>\n
\n\/**\n* Definition for singly-linked list.\n* struct ListNode {\n*     int val;\n*     ListNode *next;\n*     ListNode() : val(0), next(nullptr) {}\n*     ListNode(int x) : val(x), next(nullptr) {}\n*     ListNode(int x, ListNode *next) : val(x), next(next) {}\n* };\n*\/\nclass Solution {\npublic:\n    ListNode* swapPairs(ListNode* head) {\n\n        ListNode* pre = new ListNode();\n        ListNode* first = pre;\n        pre->next = head;\n        ListNode *l, *r, *end;\n        l = head;\n        while(l)\n        {\n            \/\/pre -> l -> r -> end\n            \/\/pre -> r -> l -> end\n            \/\/pre = l, l = end\n            r = l->next;\n            if (!r) break;\n            end = r->next;\n            pre->next = r;\n            r->next = l;\n            l->next = end;\n\n            pre = l;\n            l = end;\n        }\n        return first->next;\n    }\n};\n<\/code><\/pre>\n
\n
25. Reverse Nodes in k-Group<\/strong><\/em>
\nGiven a linked list, reverse the nodes of a linked list k at a time and return its modified list.<\/p>\n
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.<\/p>\n
Example:<\/p>\n
Given this linked list: 1->2->3->4->5<\/p>\n
For k = 2, you should return: 2->1->4->3->5<\/p>\n
For k = 3, you should return: 3->2->1->4->5<\/p>\n
Note:<\/p>\n
Only constant extra memory is allowed.
\nYou may not alter the values in the list’s nodes, only nodes itself may be changed.<\/p>\n
\n\/**\n* Definition for singly-linked list.\n* struct ListNode {\n*     int val;\n*     ListNode *next;\n*     ListNode() : val(0), next(nullptr) {}\n*     ListNode(int x) : val(x), next(nullptr) {}\n*     ListNode(int x, ListNode *next) : val(x), next(next) {}\n* };\n*\/\nclass Solution {\npublic:\n    ListNode* reverseKGroup(ListNode* head, int k) {\n        ListNode* res = new ListNode();\n        res->next = head;\n        ListNode* pre = res;\n\n        while (pre)\n        {\n            \/\/\u5148\u627e\u5230\u6240\u6709\u9700\u8981\u7684\u8282\u70b9\n            bool findNull = false;\n            vector< ListNode*> nodes;\n            ListNode* tmp = pre->next;\n            \/\/pre->0->1->2->3->4->end\n            for (int i = 0; i < k + 1; ++i)\n            {\n                \/\/end\u8282\u70b9\u662f\u53ef\u4ee5\u7a7a\u7684\n                if (i == k)\n                {\n                    nodes.push_back(tmp);\n                    break;\n                }\n                \/\/\u5176\u4ed6\u4efb\u610f\u8282\u70b9\u90fd\u4e0d\u80fd\u7a7a\n                if (!tmp)\n                {\n                    findNull = true;\n                    break;\n                }\n                else\n                {\n                    nodes.push_back(tmp);\n                    tmp = tmp->next;\n                }\n            }\n\n            if (findNull)\n            {\n                break;\n            }\n\n            \/\/\u5f00\u59cb\u79fb\u52a8\n            \/\/pre->0->1->2->3->4->end ==> pre->1 4->3->2->1->0 end\n            for (int i = nodes.size() - 2; i > 0; --i)\n            {\n                nodes[i]->next = nodes[i - 1];\n            }\n            \/\/pre->0 4->3->2->1->0 end ==> pre->1 4->3->2->1->0->end\n            nodes[0]->next = nodes[nodes.size() - 1];\n            \/\/pre->0 4->3->2->1->0->end ==> pre->4->3->2->1->0->end\n            pre->next = nodes[nodes.size() - 2];\n            \/\/\u65b0\u7684pre\u5e94\u8be5\u6307\u5411end\u524d\u9762\n            pre = nodes[0];\n        }\n        return res->next;\n    }\n};\n<\/code><\/pre>\n
\n
26. Remove Duplicates from Sorted Array<\/strong><\/em><\/p>\n
Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.<\/p>\n
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.<\/p>\n
Example 1:<\/p>\n
Given nums = [1,1,2],<\/p>\n
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.<\/p>\n
It doesn’t matter what you leave beyond the returned length.
\nExample 2:<\/p>\n
Given nums = [0,0,1,1,1,2,2,3,3,4],<\/p>\n
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.<\/p>\n
It doesn’t matter what values are set beyond the returned length.
\nClarification:<\/p>\n
Confused why the returned value is an integer but your answer is an array?<\/p>\n
Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.<\/p>\n
Internally you can think of this:<\/p>\n
\n\/\/ nums is passed in by reference. (i.e., without making a copy)\nint len = removeDuplicates(nums);\n\n\/\/ any modification to nums in your function would be known by the caller.\n\/\/ using the length returned by your function, it prints the first len elements.\nfor (int i = 0; i < len; i++) {\n    print(nums[i]);\n}\n<\/code><\/pre>\n
\nclass Solution {\npublic:\n    int removeDuplicates(vector<int>& nums) {\n        if (nums.size() == 0)\n        {\n            return 0;\n        }\n        int idx = 1;\n        int tmpVal = nums[0];\n        for (int i = 1; i < nums.size(); ++i)\n        {\n            if (nums[i] != tmpVal)\n            {\n                nums[idx++] = nums[i];\n                tmpVal = nums[i];\n            }\n        }\n        return idx;\n    }\n};\n<\/code><\/pre>\n
\n
27. Remove Element<\/strong><\/em><\/p>\n
Given an array nums and a value val, remove all instances of that value in-place and return the new length.<\/p>\n
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.<\/p>\n
The order of elements can be changed. It doesn’t matter what you leave beyond the new length.<\/p>\n
Example 1:<\/p>\n
Given nums = [3,2,2,3], val = 3,<\/p>\n
Your function should return length = 2, with the first two elements of nums being 2.<\/p>\n
It doesn’t matter what you leave beyond the returned length.
\nExample 2:<\/p>\n
Given nums = [0,1,2,2,3,0,4,2], val = 2,<\/p>\n
Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.<\/p>\n
Note that the order of those five elements can be arbitrary.<\/p>\n
It doesn’t matter what values are set beyond the returned length.
\nClarification:<\/p>\n
Confused why the returned value is an integer but your answer is an array?<\/p>\n
Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.<\/p>\n
\nclass Solution {\npublic:\n    int removeElement(vector<int>& nums, int val) {\n        if (nums.size() == 0)\n        {\n            return 0;\n        }\n        int len = 0;\n        for (; len < nums.size(); ++len)\n        {\n            if (nums[len] == val)\n            {\n                int idx = -1;\n                for (int j = len + 1; j < nums.size(); ++j)\n                {\n                    if (nums[j] != val)\n                    {\n                        idx = j;\n                        break;\n                    }\n                }\n                if (idx == -1)\n                {\n                    break;\n                }\n                nums[len] = nums[idx];\n                nums[idx] = val;\n            }\n        }\n        return len;\n    }\n};\n<\/code><\/pre>\n
\n
28. Implement strStr()<\/strong><\/em>
\nImplement strStr().<\/p>\n
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.<\/p>\n
Example 1:<\/p>\n
Input: haystack = “hello”, needle = “ll”
\nOutput: 2
\nExample 2:<\/p>\n
Input: haystack = “aaaaa”, needle = “bba”
\nOutput: -1
\nClarification:<\/p>\n
What should we return when needle is an empty string? This is a great question to ask during an interview.<\/p>\n
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().<\/p>\n
\n\/\/\u8bd5\u4e86\u4e24\u79cd\u529e\u6cd5\uff0c\u4e00\u79cd\u662f\u987a\u5e8f\u904d\u5386\u622a\u53d6\u76f4\u63a5compare\uff0c\u8017\u65f64ms\n\/\/\u53e6\u4e00\u79cd\u662f\u4f7f\u7528kmp\uff0c\u8df3\u8dc3compare\uff0c\u8017\u65f68ms\nclass Solution {\npublic:\n    int strStr(string haystack, string needle) {\n        if (haystack == needle)\n        {\n            return 0;\n        }\n        if (haystack.size() < needle.size())\n        {\n            return -1;\n        }\n        for (int i = 0; i <= haystack.size() - needle.size(); ++i)\n        {\n            if (haystack.substr(i, needle.size()) == needle)\n            {\n                return i;\n            }\n        }\n        return -1;\n    }\n    void getNext(string& strs, vector<int> &next)\n    {\n        int i = 0;\n        int j = -1;\n        next[0] = -1;\n        while (i < strs.size())\n        {\n            if (j == -1 || strs[i] == strs[j])\n            {\n                next[++i] = ++j;\n            }\n            else j = next[j];\n        }\n    }\n    int strStr_KMP(string haystack, string needle) {\n        if (haystack == needle) return 0;\n        if (haystack.size() < needle.size()) return -1;\n\n        vector<int> next(needle.size() + 1, 0);\n        getNext(needle, next);\n        int i = 0, j = 0;\n        while (i < haystack.size() && j < int(needle.size()))\n        {\n            if (j == -1)\n            {\n                ++i;\n                j = 0;\n            }\n            else if (haystack[i] == needle[j])\n            {\n                i++;\n                j++;\n            }\n            else\n            {\n                j = next[j];\n            }\n        }\n        if (j == needle.size())\n        {\n            return i - j;\n        }\n        return -1;\n    }\n};\n<\/code><\/pre>\n
\n
29. Divide Two Integers<\/strong><\/em>
\nGiven two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.<\/p>\n
Return the quotient after dividing dividend by divisor.<\/p>\n
The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.<\/p>\n
Example 1:<\/p>\n
Input: dividend = 10, divisor = 3
\nOutput: 3
\nExplanation: 10\/3 = truncate(3.33333..) = 3.
\nExample 2:<\/p>\n
Input: dividend = 7, divisor = -3
\nOutput: -2
\nExplanation: 7\/-3 = truncate(-2.33333..) = -2.
\nNote:<\/p>\n
Both dividend and divisor will be 32-bit signed integers.
\nThe divisor will never be 0.
\nAssume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [\u22122^31,  2^31 \u2212 1]. For the purpose of this problem, assume that your function returns 2^31 \u2212 1 when the division result overflows.<\/p>\n
\nclass Solution {\npublic:\n    bool isValid(int val, int flag)\n    {\n        if (flag < 0)\n        {\n            return val >= INT_MIN;\n        }\n\n        return val <= INT_MAX;\n    }\n    int divide(int dividend, int divisor) {\n        int flag = ((dividend < 0) == (divisor < 0)) ? 1 : -1;\n        if (divisor == 0)\n        {\n            return flag == 1 ? INT_MAX : INT_MIN;\n        }\n        if (divisor == 1)\n        {\n            return dividend;\n        }\n        if (divisor == -1 && dividend == INT_MIN)\n        {\n            return INT_MAX;\n        }\n\n        long long divd = abs(dividend);\n        long long divs = abs(divisor);\n\n        int res = 0;\n\n        while (divd >= divs)\n        {\n            long tmp = divs;\n            int base = 1;\n            while (divd > (tmp << 1))\n            {\n                base = base << 1;\n                tmp = tmp << 1;\n            }\n            divd -= tmp;\n            res += base;\n        }\n\n        return flag * res;\n    }\n};\n<\/code><\/pre>\n
\n
30. Substring with Concatenation of All Words<\/strong><\/em>
\nYou are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.<\/p>\n
Example 1:<\/p>\n
Input:
\ns = “barfoothefoobarman”,
\nwords = [“foo”,”bar”]
\nOutput: [0,9]
\nExplanation: Substrings starting at index 0 and 9 are “barfoo” and “foobar” respectively.
\nThe output order does not matter, returning [9,0] is fine too.
\nExample 2:<\/p>\n
Input:
\ns = “wordgoodgoodgoodbestword”,
\nwords = [“word”,”good”,”best”,”word”]
\nOutput: []<\/p>\n
\nclass Solution {\npublic:\n    void findStr(const string& s, int index, vector<string>& words, vector<int> &res)\n    {\n        map<string, int> wordMap;\n        vector<int> wordCount(words.size(), 0);\n        int mapIndex = 0;\n        for (auto i : words)\n        {\n            if (wordMap.find(i) == wordMap.end())\n                wordMap[i] = mapIndex;\n            mapIndex++;\n            wordCount[wordMap[i]]++;\n        }\n\n        int len = words[0].size();\n        int strLen = len * words.size();\n        int start = index;\n\n        int matchCount = 0;\n        while (index + len <= s.size())\n        {\n            if (matchCount == mapIndex)\n            {\n                \/\/a a b a[a b a] ==> a [a b a] (count+1)\n                \/\/\u5339\u914d\u5230\u4e86,\u6b64\u65f6index\u540e\u79fb\uff0ccount\u53d8\u5316\n                res.push_back(index);\n                const string& nowWord = s.substr(index, len);\n                index += len;\n                wordCount[wordMap[nowWord]]++;\n                matchCount--;\n                continue;\n            }\n            const string& nowWord = s.substr(start, len);\n            if (wordMap.find(nowWord) == wordMap.end())\n            {\n                \/\/a a c b[a b a] ==> b [a b a]\n                \/\/\u51fa\u73b0\u4e86\u4e00\u4e2a\u4e0d\u80fd\u5339\u914d\u7684\u5355\u8bcd\uff0c\u4e4b\u524d\u7edf\u8ba1\u8fc7\u5f97\u5355\u8bcd\u5168\u90e8\u53bb\u9664\n                while (index < start)\n                {\n                    const string& tmpWord = s.substr(index, len);\n                    index += len;\n                    wordCount[wordMap[tmpWord]]++;\n                    matchCount--;\n                }\n                \/\/\u6ce8\u610f\u8fd9\u91ccindex\u548cstart\u76f8\u7b49\uff0c\u8fd8\u8981\u518d\u8df3\u4e00\u6b21\n                index += len; start = index;\n                continue;\n            }\n            if (wordCount[wordMap[nowWord]] < 1)\n            {\n                \/\/a a a b[a b a] ==> a a b [a b a]\n                \/\/\u53ef\u4ee5\u5339\u914d\uff0c\u4f46\u662f\u6b21\u6570\u4e0d\u591f\uff0c\u53bb\u9664\u8fd9\u4e2a\u5355\u8bcd\u9996\u6b21\u51fa\u73b0\u4f4d\u7f6e\u4e4b\u524d\u7684\u6240\u6709\u7edf\u8ba1\n                while (s.substr(index, len) != nowWord)\n                {\n                    wordCount[wordMap[s.substr(index, len)]]++;\n                    index += len;\n                    matchCount--;\n                }\n                \/\/\u6ce8\u610f\u8fd9\u91cc\u627e\u5230\u4e86\uff0c\u518d\u4f4d\u79fb\u4e00\u6b21\uff0c\u4f46\u662f\u4e0d\u9700\u8981\u8ba1\u6570\n                index += len; start += len;\n                continue;\n            }\n            \/\/\u6700\u540e\u5c31\u662f\u5e38\u89c4\u60c5\u51b5\uff0c\u8ba1\u6570\n            wordCount[wordMap[nowWord]]--;\n            start += len;\n            matchCount++;\n        }\n    }\n    vector<int> findSubstring(string s, vector<string>& words) {\n        if (words.size() == 0\n            || words[0].size() * words.size() > s.size())\n        {\n            return {};\n        }\n\n        vector<int> res;\n        for (int i = 0; i < words[0].size(); ++i)\n        {\n            findStr(s, i, words, res);\n        }\n\n        return res;\n    }\n};\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
1,361 Views21. Merge Two Sorted Lists Merge two sorted  […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1012","post","type-post","status-publish","format-standard","hentry","category-lc"],"_links":{"self":[{"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/posts\/1012","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1012"}],"version-history":[{"count":10,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/posts\/1012\/revisions"}],"predecessor-version":[{"id":1217,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/posts\/1012\/revisions\/1217"}],"wp:attachment":[{"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1012"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1012"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1012"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}