{"id":960,"date":"2017-05-11T00:00:20","date_gmt":"2017-05-10T16:00:20","guid":{"rendered":"http:\/\/www.mrtblog.cn\/?p=960"},"modified":"2023-03-05T17:21:19","modified_gmt":"2023-03-05T09:21:19","slug":"%e3%80%90c%e3%80%91%e3%80%90leetcode%e3%80%912020-5-82020-5-15","status":"publish","type":"post","link":"http:\/\/www.mrtblog.cn\/?p=960","title":{"rendered":"\u3010C++\u3011\u3010LeetCode\u30112020.5.8~2020.5.15"},"content":{"rendered":"
<\/span> 1,446<\/span> Views<\/span><\/div>

15. 3Sum<\/strong><\/em><\/p>\n

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.<\/p>\n

Note:<\/p>\n

The solution set must not contain duplicate triplets.<\/p>\n

Example :<\/strong>
\nGiven array nums = [-1, 0, 1, 2, -1, -4],<\/p>\n

A solution set is:
\n[
\n[-1, 0, 1],
\n[-1, -1, 2]
\n]<\/p>\n

\nclass Solution {\npublic:\n    \/*-4 -1 -1 0 1 2*\/\n    \/*\u95ee\u9898\u4e3b\u8981\u5728\u8df3\u8fc7\u91cd\u590d\u5143\u7d20*\/\n    void SkipI(vector<int>& nums, int& i)\n    {\n        while (i + 1 < nums.size() && nums[i+1] == nums[i])\n        {\n            i++;\n        }\n        i++;\n    }\n    void SkipL(vector<int>& nums, int& l, const int& r)\n    {\n        while (l + 1 < r && nums[l] == nums[l+1])\n        {\n            l++;\n        }\n        l++;\n    }\n    void SkipR(vector<int>& nums, const int& l, int& r)\n    {\n        while (r - 1 > l && nums[r] == nums[r-1])\n        {\n            r--;\n        }\n        r--;\n    }\n    vector<vector<int>> threeSum(vector<int>& nums) {\n        if (nums.size() < 3)\n        {\n            return {};\n        }\n        sort(nums.begin(), nums.end());\n        vector<vector<int>> Result;\n        for (int i = 0; i < nums.size();)\n        {\n            int l = i + 1;\n            int r = nums.size() - 1;\n            while (l < r)\n            {\n                int res = nums[i] + nums[l] + nums[r];\n                if (res < 0)\n                {\n                    SkipL(nums, l, r);\n                }\n                else if (res > 0)\n                {\n                    SkipR(nums, l, r);\n                }\n                else\n                {\n                    Result.push_back({nums[i], nums[l], nums[r]});\n                    SkipL(nums, l, r);\n                    SkipR(nums, l, r);\n                }\n            }\n            SkipI(nums, i);\n        }\n        return Result;\n    }\n};\n<\/code><\/pre>\n
\n
16. 3Sum Closest<\/strong><\/em>
\nGiven an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.<\/p>\n
Example :<\/strong><\/p>\n
Given array nums = [-1, 2, 1, -4], and target = 1.<\/p>\n
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).<\/p>\n
\nclass Solution {\npublic:\n    int threeSumClosest(vector<int>& nums, int target) {\n        if (nums.size() < 3)\n        {\n            return 0;\n        }\n        sort(nums.begin(), nums.end());\n        int bais = 99999;\n        int res = 1;\n        for (int i = 0; i < nums.size() - 2; ++i)\n        {\n            int a = i + 1;\n            int b = nums.size() - 1;\n            while (a < b)\n            {\n                int tmp = nums[a] + nums[b] + nums[i];\n                if (tmp == target)\n                {\n                    return target;\n                }\n                else if (tmp < target)\n                {\n                    a++;\n                }\n                else\n                {\n                    b--;\n                }\n                int tmpBais = tmp - target < 0 ? target - tmp : tmp - target;\n                if (tmpBais <= bais)\n                {\n                    bais = tmpBais;\n                    res = tmp;\n                }\n            }\n        }\n        return res;\n    }\n};\n<\/code><\/pre>\n
\n
17. Letter Combinations of a Phone Number<\/strong><\/em>
\nGiven a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.<\/p>\n
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.<\/p>\n
Example :<\/strong><\/p>\n
Input: “23”
\nOutput: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
\nNote:<\/p>\n
Although the above answer is in lexicographical order, your answer could be in any order you want.
\n<\/code><\/p>\n
\nclass Solution {\npublic:\n    vector<string> letterCombinations(string digits) {\n        vector<string> res;\n        vector<string> Demo = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};\n        for (int i = 0; i < digits.size(); ++i)\n        {\n            int val = digits[i] - '0';\n            if (val > 9 || val < 2)\n            {\n                continue;\n            }\n            static vector<string> tmp;\n            tmp.clear();\n            for (int j = 0 ; j < Demo[val - 2].size(); ++j)\n            {\n                \/\/res\u4e2d\u5b57\u7b26\u4e32\u53d6\u51fa\u7ed9\u672b\u4f4d\u52a0\u4e0a\u65b0\u7684\u5b57\u7b26\n                for (int k = 0; k < res.size(); ++k)\n                {\n                    string s = res[k];\n                    string x(1, Demo[val-2][j]);\n                    tmp.push_back(s + x);\n                }\n                \/\/\u7b2c\u4e00\u8f6e\u63a8\u4e00\u6b21\n                if (tmp.size() == 0)\n                {\n                    for (int l = 0 ; l < Demo[val - 2].size(); ++l)\n                    {\n                        string x(1, Demo[val-2][l]);\n                        tmp.push_back(x);\n                    }\n                }\n            }\n            res.clear();\n            res.assign(tmp.begin(), tmp.end());\n        }\n        return res;\n    }\n};\n<\/code><\/pre>\n
\n
18. 4Sum<\/strong><\/em>
\nGiven an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.<\/p>\n
Note:<\/p>\n
The solution set must not contain duplicate quadruplets.<\/p>\n
Example :<\/strong><\/p>\n
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.<\/p>\n
A solution set is:
\n[
\n[-1,  0, 0, 1],
\n[-2, -1, 1, 2],
\n[-2,  0, 0, 2]
\n]<\/p>\n
\nclass Solution {\npublic:\n    \/*-4 -1 -1 0 1 2*\/\n    const int NUM = 4;\n    void SkipL(vector<int>& nums, int& l, const int& r)\n    {\n        while (l + 1 < r && nums[l] == nums[l+1])\n        {\n            l++;\n        }\n        l++;\n    }\n    void SkipR(vector<int>& nums, const int& l, int& r)\n    {\n        while (r - 1 > l && nums[r] == nums[r-1])\n        {\n            r--;\n        }\n        r--;\n    }\n    vector<vector<int>> fourSum(vector<int>& nums, int target) {\n        if (nums.size() < NUM)\n        {\n            return {};\n        }\n        sort(nums.begin(), nums.end());\n        vector<vector<int>> Result;\n        for (int i = 0; i <= nums.size() - NUM;)\n        {\n            for (int j = i + 1; j <= nums.size() - NUM + 1;)\n            {\n                int l = j + 1;\n                int r = nums.size() - 1;\n                while (l < r)\n                {\n                    int res = nums[i] + nums[j] + nums[l] + nums[r];\n                    if (res < target)\n                    {\n                        SkipL(nums, l, r);\n                    }\n                    else if (res > target)\n                    {\n                        SkipR(nums, l, r);\n                    }\n                    else\n                    {\n                        Result.push_back({nums[i], nums[j], nums[l], nums[r]});\n                        SkipL(nums, l, r);\n                        SkipR(nums, l, r);\n                    }\n                }\n                SkipL(nums, j, nums.size() - NUM + 2);\n            }\n            SkipL(nums, i, nums.size() - NUM + 1);\n        }\n        return Result;\n    }\n};\n<\/code><\/pre>\n
\n
19. Remove Nth Node From End of List<\/strong><\/em>
\nGiven a linked list, remove the n-th node from the end of list and return its head.<\/p>\n
Example :<\/strong><\/p>\n
Given linked list: 1->2->3->4->5, and n = 2.<\/p>\n
After removing the second node from the end, the linked list becomes 1->2->3->5.
\nNote:<\/p>\n
Given n will always be valid.<\/p>\n
Follow up:<\/p>\n
Could you do this in one pass?<\/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* removeNthFromEnd(ListNode* head, int n) {\n        ListNode* pre = head;\n        ListNode* MoveNode = head;\n        int count = 0;\n        while (MoveNode)\n        {\n            MoveNode = MoveNode->next;\n            \/\/\u8fbe\u5230\u8ddd\u79bb\u540epre\u79fb\u52a8\n            if (count >= n && MoveNode)\n            {\n                pre = pre->next;\n            }\n            count++;\n        }\n        \/\/\u5220\u9664\u7684\u662f\u7b2c\u4e00\u4e2a\n        if (count == n && head)\n        {\n            return head->next;\n        }\n        \/\/\u5220\u9664\u5bf9\u5e94\u4f4d\u7f6e\n        if (pre && pre->next)\n        {\n            pre->next = pre->next->next;\n        }\n        return head;\n    }\n};\n<\/code><\/pre>\n
\n
20. Valid Parentheses<\/strong><\/em><\/p>\n
Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.<\/p>\n
An input string is valid if:<\/p>\n
Open brackets must be closed by the same type of brackets.
\nOpen brackets must be closed in the correct order.
\nNote that an empty string is also considered valid.<\/p>\n
Example 1:<\/strong>
\nInput: “()”
\nOutput: true<\/p>\n
Example 2:<\/strong>
\nInput: “()[]{}”
\nOutput: true<\/p>\n
Example 3:<\/strong>
\nInput: “(]”
\nOutput: false<\/p>\n
Example 4:<\/strong>
\nInput: “([)]”
\nOutput: false<\/p>\n
Example 5:<\/strong>
\nInput: “{[]}”
\nOutput: true<\/p>\n
\nclass Solution {\npublic:\n    bool isValid(string s) {\n        stack<char> SymStack;\n        for (size_t i = 0; i < s.size(); ++i)\n        {\n            if (s[i] == '(' || s[i] == '[' || s[i] == '{')\n            {\n                SymStack.push(s[i]);\n            }\n            else\n            {\n                if (!SymStack.empty() &&\n                    (  (s[i] == ')' && SymStack.top() == '(')\n                    || (s[i] == ']' && SymStack.top() == '[')\n                    || (s[i] == '}' && SymStack.top() == '{')))\n                {\n                    SymStack.pop();\n                }\n                else\n                {\n                    return false;\n                }\n            }\n        }\n        return SymStack.empty();\n    }\n};\n<\/code><\/pre>\n
\n","protected":false},"excerpt":{"rendered":"
1,446 Views15. 3Sum Given an array nums of n integers,  […]<\/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-960","post","type-post","status-publish","format-standard","hentry","category-lc"],"_links":{"self":[{"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/posts\/960","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=960"}],"version-history":[{"count":4,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/posts\/960\/revisions"}],"predecessor-version":[{"id":1009,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/posts\/960\/revisions\/1009"}],"wp:attachment":[{"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=960"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=960"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=960"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}