{"id":924,"date":"2017-04-30T11:53:56","date_gmt":"2017-04-30T03:53:56","guid":{"rendered":"http:\/\/www.mrtblog.cn\/?p=924"},"modified":"2023-03-05T16:44:39","modified_gmt":"2023-03-05T08:44:39","slug":"%e3%80%90c%e3%80%91%e3%80%90leetcode%e3%80%912020-4-222020-4-29","status":"publish","type":"post","link":"http:\/\/www.mrtblog.cn\/?p=924","title":{"rendered":"\u3010C++\u3011\u3010LeetCode\u30112020.4.22~2020.4.29"},"content":{"rendered":"
<\/span> 1,517<\/span> Views<\/span><\/div>

1. Two Sum<\/strong><\/em><\/p>\n

Given an array of integers, return indices<\/strong> of the two numbers such that they add up to a specific target.<\/p>\n

You may assume that each input would have exactly<\/em><\/strong> one solution, and you may not use the same<\/em> element twice.<\/p>\n

Example:<\/strong><\/p>\n

Given nums = [2, 7, 11, 15], target = 9,\n\nBecause nums[0] + nums[1] = 2 + 7 = 9,\nreturn [0, 1].\n<\/pre>\n
\nclass Solution {\npublic:\n    vector<int> twoSum(vector<int>& nums, int target) {\n\n        map<int,int> numsMap;\n\n        for (int i = 0; i < int(nums.size()); ++i) {\n            map<int, int>::iterator iter = numsMap.find(target - nums[i]);\n            if (iter != numsMap.end()) {\n                return {iter->second, i};\n            } else {\n                numsMap.insert(make_pair(nums[i], i));\n            }\n        }\n        return {-1, -1};\n    }\n};\n<\/code><\/pre>\n
\n
2. Add Two Numbers<\/strong><\/em><\/p>\n
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.<\/p>\n
You may assume the two numbers do not contain any leading zero, except the number 0 itself.<\/p>\n
Example:<\/strong><\/p>\n
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)\nOutput: 7 -> 0 -> 8\nExplanation: 342 + 465 = 807.\n<\/pre>\n
\n\/**\n* Definition for singly-linked list.\n* struct ListNode {\n*     int val;\n*     ListNode *next;\n*     ListNode(int x) : val(x), next(NULL) {}\n* };\n*\/\nclass Solution {\npublic:\n    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {\n\n        int addVal = 0;\n        ListNode *HeadNode = new ListNode(0);\n        ListNode *WalkNode = HeadNode;\n        while (l1 && l2) {\n            int tmpVal = l1->val + l2->val + addVal;\n\n            WalkNode->next = new ListNode(tmpVal % 10);\n            WalkNode = WalkNode->next;\n\n            addVal = tmpVal \/ 10;\n            l1 = l1->next;\n            l2 = l2->next;\n        }\n\n        while (l1) {\n            int tmpVal = l1->val + addVal;\n\n            WalkNode->next = new ListNode(tmpVal % 10);\n            WalkNode = WalkNode->next;\n\n            addVal = tmpVal \/ 10;\n            l1 = l1->next;\n        }\n\n        while (l2) {\n            int tmpVal = l2->val + addVal;\n\n            WalkNode->next = new ListNode(tmpVal % 10);\n            WalkNode = WalkNode->next;\n\n            addVal = tmpVal \/ 10;\n            l2 = l2->next;\n        }\n\n        if (addVal) {\n            WalkNode->next = new ListNode(addVal);\n            addVal = 0;\n        }\n\n        if (HeadNode) {\n            return HeadNode->next;\n        }\n\n        return NULL;\n    }\n};\n<\/code><\/pre>\n
\n
3. Longest Substring Without Repeating Characters<\/em><\/strong>
\nGiven a string, find the length of the longest substring without repeating characters.<\/p>\n
Example 1:<\/strong>
\nInput: “abcabcbb”
\nOutput: 3
\nExplanation: The answer is “abc”, with the length of 3.<\/p>\n
Example 2:<\/strong>
\nInput: “bbbbb”
\nOutput: 1
\nExplanation: The answer is “b”, with the length of 1.<\/p>\n
Example 3:<\/strong>
\nInput: “pwwkew”
\nOutput: 3
\nExplanation: The answer is “wke”, with the length of 3.
\nNote that the answer must be a substring, “pwke” is a subsequence and not a substring.<\/p>\n
\nclass Solution {\npublic:\n    int lengthOfLongestSubstring(string s) {\n        if (s.size() <= 1) {\n            return s.size();\n        }\n        int nowCount = 0;\n        int maxCount = 0;\n        int tmpDistance = 0;\n        map<char, int> char2Index;\n        for (size_t i = 0; i < s.size(); ++i) {\n            map<char, int>::iterator iter = char2Index.find(s[i]);\n            if (iter == char2Index.end()) {\n                \/\/not found \u7d2f\u8ba1\/\u8bb0\u5f55\n                nowCount++;\n                char2Index.insert(make_pair(s[i], i));\n            } else {\n                \/\/find \u5237\u65b0nowCount\n                tmpDistance = i - iter->second;\/\/\u91cd\u590d\u4e32\u8ddd\u79bb\n                \/\/nowCount\u5c0f,\u8bf4\u660e\u5728\u91cd\u590d\u70b9\u53f3\u8fb9,\u7ee7\u7eed\u52a0;nowCount\u5927,\u8bf4\u660e\u5728\u91cd\u590d\u70b9\u5de6\u8fb9,\u4e0d\u52a0\u4e86\n                nowCount = nowCount < tmpDistance ? nowCount + 1 : tmpDistance;\n                iter->second = i;\/\/\u66f4\u65b0\u4f4d\u7f6e\n            }\n\n            maxCount = maxCount < nowCount ? nowCount : maxCount;\n        }\n        return maxCount;\n    }\n};\n<\/code><\/pre>\n
\n
4. Median of Two Sorted Arrays<\/strong><\/em><\/p>\n
There are two sorted arrays nums1 and nums2 of size m and n respectively.<\/p>\n
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).<\/p>\n
You may assume nums1 and nums2 cannot be both empty.<\/p>\n
Example 1:<\/strong>
\nnums1 = [1, 3]
\nnums2 = [2]<\/p>\n
The median is 2.0<\/p>\n
Example 2:<\/strong>
\nnums1 = [1, 2]
\nnums2 = [3, 4]<\/p>\n
The median is (2 + 3)\/2 = 2.5<\/p>\n
\nclass Solution {\npublic:\n    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {\n        size_t Len1 = nums1.size();\n        size_t Len2 = nums2.size();\n        int mid1 = 0, mid2 = 0;\n\n        int i = 0, j = 0;\n        int Count = 0;\n        int MaxVal = 9999999;\n        while ((i < Len1 || j < Len2)) {\n            \/\/\u627e\u5230\u4e24\u4e2a\u4e2d\u4f4d\u6570\u5373\u53ef\n            int tmp1 = i < Len1 ? nums1[i] : MaxVal;\n            int tmp2 = j < Len2 ? nums2[j] : MaxVal;\n            int tmp = tmp1 < tmp2 ? tmp1 : tmp2;\n\n            if (tmp1 < tmp2) i++;\n            else j++;\n\n            if (Count == (Len1 + Len2 - 1) \/ 2) mid1 = tmp;\n            if (Count == (Len1 + Len2) \/ 2) {\n                mid2 = tmp;\n                break;\n            }\n\n            Count++;\n        }\n        return (mid1 + mid2) \/ 2.0;\n    }\n};\n<\/code><\/pre>\n
\n
5. Longest Palindromic Substring<\/em><\/strong>
\nGiven a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.<\/p>\n
Example 1:<\/strong>
\nInput: “babad”
\nOutput: “bab”
\nNote: “aba” is also a valid answer.<\/p>\n
Example 2:<\/strong>
\nInput: “cbbd”
\nOutput: “bb”<\/p>\n
\nclass Solution {\npublic:\n    int findStartEnd(string &s, int len, int &l, int r) {\n        int lastestL = l;\/\/\u6700\u540e\u5339\u914d\u4f4d\u7f6eL\n        int lastestR = r;\/\/\u6700\u540e\u5339\u914d\u4f4d\u7f6eR\n        while (l >= 0 && l < s.size() && r < s.size()) {\n            if (s[l] == s[r]) {\n                lastestL = l;\n                lastestR = r;\n                l--;\n                r++;\n                len += 2;\n            } else {\n                break;\n            }\n        }\n\n        l = lastestL;\n        r = lastestR;\n\n        return len;\n    }\n\n    string longestPalindrome(string s) {\n        if (s.size() <= 1) {\n            return s;\n        }\n        int sta = 0, maxLen = 1;\n        for (int i = 0 ; i < s.size(); ++i) {\n            \/\/\u5355\u6570\u5411\u4e24\u8fb9\u6269\u6563,\u5df2\u7ecf\u4e0d\u6ee1\u8db3\u5f53\u524d\u6700\u5927\u503c,\u526a\u679d\n            if ((s.size() - 1 - i) * 2 + 1 <= maxLen) {\n                break;\n            }\n            int l = i - 1;\n            int tmpLen = 0;\n            \/\/ \u5bfb\u627eaba\u7c7b\u578b\n            tmpLen = findStartEnd(s, 1, l, l + 2);\n            if (tmpLen > maxLen) {\n                maxLen = tmpLen;\n                sta = l;\n            }\n\n            l = i;\n            \/\/\u5bfb\u627eabba\u7c7b\u578b\n            tmpLen = findStartEnd(s, 0, l, l + 1);\n            if (tmpLen > maxLen) {\n                maxLen = tmpLen;\n                sta = l;\n            }\n\n        }\n        return s.substr(sta, maxLen);\n    }\n};\n<\/code><\/pre>\n
\n
6. ZigZag Conversion<\/em><\/strong>
\nThe string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)<\/p>\n
P   A   H   N
\nA P L S I I G
\nY   I   R
\nAnd then read line by line: “PAHNAPLSIIGYIR”<\/p>\n
Write the code that will take a string and make this conversion given a number of rows:<\/p>\n
string convert(string s, int numRows);<\/p>\n
Example 1:<\/strong>
\nInput: s = “PAYPALISHIRING”, numRows = 3
\nOutput: “PAHNAPLSIIGYIR”<\/p>\n
Example 2:<\/strong>
\nInput: s = “PAYPALISHIRING”, numRows = 4
\nOutput: “PINALSIGYAHRPI”
\nExplanation:
\nP     I    N
\nA   L S  I G
\nY A   H R
\nP     I<\/p>\n
\nclass Solution {\npublic:\n\/*\nn = 6\n\n0A         1         1\n1B       1 1       1\n2C     1   1     1\n3D   1     1   1\n4E 1       1 1\n5F         G\n\n0: 2 * (n - 1)\n1: 2 * (n - 2) || 2 * (n - 5)\n2: 2 * (n - 3) || 2 * (n - 4)\n3: 2 * (n - 4) || 2 * (n - 3)\n4: 2 * (n - 5) || 2 * (n - 2)\n5: 2 * (n - 1)\n\n2 * (n - (index + 1)) || 2 * ( n - (n + 1 - (index + 1)))\n2 * ( n - (index + 1)) || 2 * ((index + 1) - 1)\n(n - (index + 1 )) * -1 + n - 1 =  (index + 1) - 1\n((index + 1) - 1) * -1 + n - 1 = n - (index + 1 )\n*\/\n    string convert(string s, int numRows) {\n        if (numRows <= 1 || s.size() <= 1) {\n            return s;\n        }\n        string res = "";\n        for (size_t i = 0 ; i < numRows; ++i) {\n            size_t j = i;\n            if (j == 0 || j == numRows - 1) {\n                while (j < s.size()) {\n                    res += s[j];\n                    j += 2 * (numRows - 1);\n                }\n            } else {\n                \/\/int sign = -1;\n                int equal = (numRows - (i + 1));\n                while (j < s.size()) {\n                    res += s[j];\n                    j += 2 * equal;\n                    equal = (equal * -1) + numRows - 1;\n                    \/\/sign *= -1;\n                }\n            }\n        }\n\n        return res;\n    }\n};\n<\/code><\/pre>\n
\n
7. Reverse Integer<\/em><\/strong><\/p>\n
Given a 32-bit signed integer, reverse digits of an integer.<\/p>\n
Example 1:<\/strong>
\nInput: 123
\nOutput: 321<\/p>\n
Example 2:<\/strong>
\nInput: -123
\nOutput: -321<\/p>\n
Example 3:<\/strong>
\nInput: 120
\nOutput: 21
\nNote:
\nAssume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [\u2212231,  231 \u2212 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.<\/p>\n
\nclass Solution {\npublic:\n    int reverse(int x) {\n        long long int sign = x < 0 ? -1 : 1;\n        long long int count = 1;\n        long long int tmp = (long long int)x * sign;\n        long long int base = 1;\n        long long int res = 0;\n        while (tmp > 0) {\n            count *= 10;\n            tmp \/= 10;\n        }\n        count \/= 10;\n        tmp = (long long int)x * sign;\n        while (tmp > 0) {\n            res += tmp \/ count * base;\n            tmp -= (tmp \/ count) * count;\n            count \/= 10;\n            base *= 10;\n        }\n\n        res *= sign;\n        if (res > INT32_MAX) {\n            res = 0;\n        }\n        if (res < INT32_MIN) {\n            res = 0;\n        }\n\n        return res;\n    }\n};\n<\/code><\/pre>\n
\n
8. String to Integer (atoi)<\/em><\/strong><\/p>\n
Implement atoi which converts a string to an integer.<\/p>\n
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.<\/p>\n
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.<\/p>\n
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.<\/p>\n
If no valid conversion could be performed, a zero value is returned.<\/p>\n
Note:<\/p>\n
Only the space character ‘ ‘ is considered as whitespace character.
\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]. If the numerical value is out of the range of representable values, INT_MAX (2^31 \u2212 1) or INT_MIN (\u22122^31) is returned.<\/p>\n
Example 1:<\/strong>
\nInput: “42”
\nOutput: 42<\/p>\n
Example 2:<\/strong>
\nInput: ”   -42″
\nOutput: -42
\nExplanation: The first non-whitespace character is ‘-‘, which is the minus sign.
\nThen take as many numerical digits as possible, which gets 42.<\/p>\n
Example 3:<\/strong>
\nInput: “4193 with words”
\nOutput: 4193
\nExplanation: Conversion stops at digit ‘3’ as the next character is not a numerical digit.<\/p>\n
Example 4:<\/strong>
\nInput: “words and 987”
\nOutput: 0
\nExplanation: The first non-whitespace character is ‘w’, which is not a numerical
\ndigit or a +\/- sign. Therefore no valid conversion could be performed.<\/p>\n
Example 5:<\/strong>
\nInput: “-91283472332”
\nOutput: -2147483648
\nExplanation: The number “-91283472332” is out of the range of a 32-bit signed integer.
\nThefore INT_MIN (\u2212231) is returned.<\/p>\n
\nclass Solution {\npublic:\n    int myAtoi(string str) {\n        long ans = 0;\n        bool tag = true;\n        for (int i = 0; i < str.length(); ) {\n            \/\/\u8df3\u8fc7\u6240\u6709\u5148\u5bfc\u7a7a\u683c\n            while (str[i] == ' ') {\n                ++i;\n            }\n            \/\/\u6807\u8bb0\u6b63\u8d1f\u53f7\n            if (str[i] == '-' || str[i] == '+') {\n                tag = (str[i] == '-') ? false : true;\n                ++i;\n            }\n            \/\/\u4e0d\u7528\u5904\u7406\u5176\u4ed6\u7b26\u53f7,\u53d1\u73b0\u65e0\u6548\u7b26\u53f7\u76f4\u63a5\u7ed3\u675f\n            while (str[i] >= '0' && str[i] <= '9') {\n                ans = ans * 10 + (str[i] - '0');\n                \/\/\u51cf\u679d\n                if (tag && ans >= INT_MAX) {\n                    return INT_MAX;\n                }\n                if (!tag && -ans <= INT_MIN) {\n                    return INT_MIN;\n                }\n                ++i;\n            }\n            return (tag ? ans : -ans);\n        }\n        return (tag ? ans : -ans);\n    }\n};\n<\/code><\/pre>\n
\n
9. Palindrome Number<\/em><\/strong>
\nDetermine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.<\/p>\n
Example 1:<\/strong>
\nInput: 121
\nOutput: true<\/p>\n
Example 2:<\/strong>
\nInput: -121
\nOutput: false
\nExplanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.<\/p>\n
Example 3:<\/strong>
\nInput: 10
\nOutput: false
\nExplanation: Reads 01 from right to left. Therefore it is not a palindrome.<\/p>\n
\nclass Solution {\npublic:\n    bool isPalindrome(int x) {\n        if (x < 0) {\n            return false;\n        }\n        long long int L = x;\n        long long int R = 0;\n        long long int count = 0;\n        while (x) {\n            R = R * 10 + x % 10;\n            if (R > INT_MAX) return false;\n            x \/= 10;\n        }\n\n        return (L == R);\n    }\n};\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
1,517 Views1. Two Sum Given an array of integers, retur […]<\/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-924","post","type-post","status-publish","format-standard","hentry","category-lc"],"_links":{"self":[{"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/posts\/924","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=924"}],"version-history":[{"count":24,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/posts\/924\/revisions"}],"predecessor-version":[{"id":1011,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/posts\/924\/revisions\/1011"}],"wp:attachment":[{"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=924"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=924"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=924"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}