力扣1~10题目汇总

我不是女神ヾ 2022-12-21 02:26 121阅读 0赞

力扣前1-10题相对可以的答案解析，自己刷题打卡，欢迎大家一起讨论，

不过博客还未开通评论功能待后续开发。

## [1. 两数之和][1.] ##

难度简单

给定一个整数数组 `nums` 和一个目标值 `target`，请你在该数组中找出和为目标值的那 **两个** 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

**示例:**

给定 nums = [2, 7, 11, 15], target = 9
    
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

通过次数1,521,891

提交次数3,055,876代码解析：

class Solution { 
    public:
        vector<int> twoSum(vector<int>& nums, int target) 
        { 
            int i=0,j=0;
            for(int i=0;i<nums.size();i++)
                for(int j=i+1;j<nums.size();j++)
                    if(nums[i] + nums[j] == target)
                        return { i,j};
            return { i,j};
    };

哈希表的做法，通过查找的方式

class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            map<int,int>hash;
            for(int i=0;i<nums.size();i++)
            {
                auto it = hash.find(target - nums[i]);
                if(it != hash.end()){
                    return {hash[target - nums[i]],i}; //上一次出现的值 现在的值
                }else
                    hash[nums[i]] = i;
            }
            return {};
        }
    };

## [2. 两数相加][2.] ##

难度中等

给出两个 **非空** 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 **逆序** 的方式存储的，并且它们的每个节点只能存储 **一位** 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

**示例：**

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出：7 -> 0 -> 8
    原因：342 + 465 = 807

/**
    * Definition for singly-linked list.
    * struct ListNode {
    *     int val;
    *     ListNode *next;
    *     ListNode(int x) : val(x), next(NULL) {}
    * };
    */
    class Solution {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            ListNode *root = new ListNode(0);
            ListNode* cur = root;
            int inc=0;
            while(l1 || l2 || inc){
                int val1 = l1 ? l1->val : 0;
                int val2 = l2 ? l2->val : 0;
                int sum = val1 + val2 + inc;
                inc = sum/10;
    
                cur->next = new ListNode(sum % 10);
                cur = cur->next;
    
                if(l1) l1=l1->next;
                if(l2) l2=l2->next;
            }
            return root->next;
        }
    };

## [3. 无重复字符的最长子串][3.] ##

难度中等

给定一个字符串，请你找出其中不含有重复字符的 **最长子串** 的长度。

**示例 1:**

输入: "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

**示例 2:**

输入: "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

**示例 3:**

输入: "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
         请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

是一个滑动窗口的问题，想用contains(C++20)检查容器是否含有带特定关键的元素(公开成员函数)，但好像是20的

class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            int i=0,j=0;
            int res=0;
            set<char> hashset;
            for(i=0;j<s.size();j++)
            {
                while(!hashset.insert(s[j]).second){ //证明之前元素有，收缩窗口大小 类似contains 有没有这个元素
                    hashset.erase(s[i]);
                    i++;
                }
                hashset.insert(s[j]);
                res = res>hashset.size() ? res :hashset.size();
            }
            
            return res;
        }
    };

## [4. 寻找两个正序数组的中位数][4.] ##

难度困难

给定两个大小为 m 和 n 的正序（从小到大）数组 `nums1` 和 `nums2`。请你找出并返回这两个正序数组的中位数。

\*\*进阶：\*\*你能设计一个时间复杂度为 `O(log (m+n))` 的算法解决此问题吗？

**示例 1：**

输入：nums1 = [1,3], nums2 = [2]
    输出：2.00000
    解释：合并数组 = [1,2,3] ，中位数 2

**示例 2：**

输入：nums1 = [1,2], nums2 = [3,4]
    输出：2.50000
    解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

**示例 3：**

输入：nums1 = [0,0], nums2 = [0,0]
    输出：0.00000

**示例 4：**

输入：nums1 = [], nums2 = [1]
    输出：1.00000

**示例 5：**

输入：nums1 = [2], nums2 = []
    输出：2.00000

这里按照题目的要求，log级别的时间辅助度，想到只能用二分，具体思路如下

class Solution {
    public:
        double findKMinNum(vector<int>& nums1, int l1, int h1, vector<int>& nums2, int l2, int h2, int k)
        {
            int m = h1 - l1 + 1;
            int n = h2 - l2 + 1;
    
            if (m>n) { //互换加快速度
                return findKMinNum(nums2, l2, h2, nums1, l1, h1, k);
            }
    
            if (m == 0) return nums2[l2 + k - 1];
            if (k == 1) return min(nums1[l1], nums2[l2]);
    
            int na = min(k / 2, m); //选2个数组中间数
            int nb = k - na;
            int va = nums1[l1 + na - 1];
            int vb = nums2[l2 + nb - 1];
    
            if (va == vb)
                return va;
            else if (va <vb)
                return findKMinNum(nums1, l1 + na, h1, nums2, l2, l2 + nb - 1, k - na);
            else
                return findKMinNum(nums1, l1, l1 + na - 1, nums2, l2 + nb, h2, k - nb);
        }
    
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int m = nums1.size();
            int n = nums2.size();
    
            int k = (m + n) / 2;
            if ((m + n) % 2 == 1) {
                return findKMinNum(nums1, 0, m - 1, nums2, 0, n - 1, ((m + n)+1)/2);
            }
            else
                return (findKMinNum(nums1, 0, m - 1, nums2, 0, n - 1, k + 1) +
                    findKMinNum(nums1, 0, m - 1, nums2, 0, n - 1, k)) / 2.0;
        }
    };

## [5. 最长回文子串][5.] ##

难度中等2879

给定一个字符串 `s`，找到 `s` 中最长的回文子串。你可以假设 `s` 的最大长度为 1000。

**示例 1：**

输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。

**示例 2：**

输入: "cbbd"
    输出: "bb"

代码解析，使用扩的方式

class Solution {
    public:
        string longestPalindrome(string s) {
            int len=s.size();
            if(len==0||len==1)
                return s;
            int start=0,end=0;
            int maxlen = 0;
            int len1=0,len2=0;
            for(int i=0;i<s.size();i++)
            {
                len1 = externMaxLen(s, i, i);
                if(i<s.size()-1 && s[i] == s[i+1]) len2 = externMaxLen(s, i, i+1);
                //cout<<"i: " << i << "  len1 :" << len1 << "  len2: " << len2 << endl;
                maxlen = max(max(len1,len2),maxlen);
                if(maxlen > end-start+1){
                    start = i - (maxlen-1)/2 ;
                    end = i + maxlen/2;  
                }
            }
            return s.substr(start,maxlen);
        }
    
    private:
        int externMaxLen(string s, int l, int r)
        {
            while(l>0 && r<s.size()-1 && s[l-1] == s[r+1])
                l--,r++;
            return r-l+1;
        }
    };

## [6. Z 字形变换][6. Z] ##

难度中等897

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 `"LEETCODEISHIRING"` 行数为 3 时，排列如下：

L   C   I   R
    E T O E S I I G
    E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：`"LCIRETOESIIGEDHN"`。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

**示例 1:**

输入: s = "LEETCODEISHIRING", numRows = 3
    输出: "LCIRETOESIIGEDHN"

**示例 2:**

输入: s = "LEETCODEISHIRING", numRows = 4
    输出: "LDREOEIIECIHNTSG"
    解释:
    
    L     D     R
    E   O E   I I
    E C   I H   N
    T     S     G

代码块，很直接，建立对应的string数组

class Solution {
    public:
        string convert(string s, int numRows) {
            if(numRows == 1) return s;
            vector<string> rows(min(numRows,int(s.size())));//防止字母个数还没行数多
    
            int curRow = 0;
            bool goDown = false;
    
            for(auto x : s){
                rows[curRow] += x;
                if(curRow == numRows-1 || curRow == 0) goDown= !goDown;
                curRow += goDown ? 1 : -1;
            }
    
            string res;
            for (string row : rows) res += row;
            return res;
        }
    };

## [7. 整数反转][7.] ##

难度简单2318

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

**示例 1:**

输入: 123
    输出: 321

**示例 2:**

输入: -123
    输出: -321

**示例 3:**

输入: 120
    输出: 21

**注意:**

假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 \[−231, 231 − 1\]。请根据这个假设，如果反转后整数溢出那么就返回 0。

代码块，这个可能会出现溢出的现象，需要注意

class Solution {
    public:
        int reverse(int x) {
    
            long res;//避免溢出
            if(x == INT_MIN) return 0;
            if(x<0) return -reverse(-x);
    
            int tmp=0;
            while(x){
                tmp = x % 10;
                res = res*10 + tmp;
                x = x/10;
            }
            if(res>INT_MAX) return 0;
            return res;
        }
    };

## [8. 字符串转换整数 (atoi)][8. _ _atoi] ##

难度中等893

请你来实现一个 `atoi` 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：

*  如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
 *  假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
 *  该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0 。

**提示：**

*  本题中的空白字符只包括空格字符 `' '` 。
 *  假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 \[−231, 231 − 1\]。如果数值超过这个范围，请返回 INT\_MAX (231 − 1) 或 INT\_MIN (−231) 。

**示例 1:**

输入: "42"
    输出: 42

**示例 2:**

输入: "   -42"
    输出: -42
    解释: 第一个非空白字符为 '-', 它是一个负号。
         我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

**示例 3:**

输入: "4193 with words"
    输出: 4193
    解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。

**示例 4:**

输入: "words and 987"
    输出: 0
    解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
         因此无法执行有效的转换。

**示例 5:**

输入: "-91283472332"
    输出: -2147483648
    解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
         因此返回 INT_MIN (−231) 。

代码思路：这道题做的很懵逼，唯一保证数据越界这个点

class Solution {
    public:
        int myAtoi(string s) {
            int flag = 1;
            int start=0,res = 0;
            while(s[start]==' ') start++;
            if(s[start]=='-') flag = -1;
            if(s[start]=='+' || s[start]=='-') start++;
            for(;start<s.size() && isdigit(s[start]);start++)
            {
                //if(!isdigit(s[start])) continue;
                if(res>INT_MAX/10 || res == INT_MAX/10 && s[start] - '0' > 7)
                    return flag==1 ? INT_MAX : INT_MIN;
                res = res*10 + (s[start] - '0');
                //cout << "res: " << res << endl;
            }
            return res*flag;
        }
    };

## [9. 回文数][9.] ##

难度简单1301

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

**示例 1:**

输入: 121
    输出: true

**示例 2:**

输入: -121
    输出: false
    解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

**示例 3:**

输入: 10
    输出: false
    解释: 从右向左读, 为 01 。因此它不是一个回文数。

**进阶:**

你能不将整数转为字符串来解决这个问题吗？

代码解析：参考将字符串翻转

class Solution {
    public:
        bool isPalindrome(int x) {
            if(x<0) return false;
            string s1 = to_string(x);
            string s2 = to_string(x);
            //string s2=s1;
            reverse(s1.begin(),s1.end());
    
            int res = s1.compare(s2);
            if(res == 0)
                return true; 
            return false;
            //return s1.compare(s2) == 0 ? true:false;
        }
    };

## [10. 正则表达式匹配][10.] ##

难度困难1665

给你一个字符串 `s` 和一个字符规律 `p`，请你来实现一个支持 `'.'` 和 `'*'` 的正则表达式匹配。

*  `'.'` 匹配任意单个字符
 *  `'*'` 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 **整个** 字符串 `s`的，而不是部分字符串。

**示例 1：**

输入：s = "aa" p = "a"
    输出：false
    解释："a" 无法匹配 "aa" 整个字符串。

**示例 2:**

输入：s = "aa" p = "a*"
    输出：true
    解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

**示例 3：**

输入：s = "ab" p = ".*"
    输出：true
    解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

**示例 4：**

输入：s = "aab" p = "c*a*b"
    输出：true
    解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

**示例 5：**

输入：s = "mississippi" p = "mis*is*p*."
    输出：false

**提示：**

*  `0 <= s.length <= 20`
 *  `0 <= p.length <= 30`
 *  `s` 可能为空，且只包含从 `a-z` 的小写字母。
 *  `p` 可能为空，且只包含从 `a-z` 的小写字母，以及字符 `.` 和 `*`。
 *  保证每次出现字符 `*` 时，前面都匹配到有效的字符

代码块：程序都有说明，应该比较详细

class Solution {
    public:
        bool isMatch(string s, string p) {
            if(p.empty()) return s.empty();
    
            //1. 第二个字母为*
            if(p[1] == '*'){
                if(s[0] == p[0] || (!s.empty() && p[0]=='.')) //第一个数字相等 或任意变化
                    return isMatch(s.substr(1),p) || isMatch(s,p.substr(2)); // 重复下一个匹配 或者 不存在重复了
                else
                    return isMatch(s,p.substr(2)); //不存在匹配的情况
            }
            //2. 第二个字母不为*
            else{
                if(p[0] == s[0] || !s.empty() && p[0]=='.')
                    return isMatch(s.substr(1),p.substr(1)); //相等走一格
                else
                    return false;
            }
        }
    };

[1.]: https://leetcode-cn.com/problems/two-sum/
[2.]: https://leetcode-cn.com/problems/add-two-numbers/
[3.]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[4.]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
[5.]: https://leetcode-cn.com/problems/longest-palindromic-substring/
[6. Z]: https://leetcode-cn.com/problems/zigzag-conversion/
[7.]: https://leetcode-cn.com/problems/reverse-integer/
[8. _ _atoi]: https://leetcode-cn.com/problems/string-to-integer-atoi/
[9.]: https://leetcode-cn.com/problems/palindrome-number/
[10.]: https://leetcode-cn.com/problems/regular-expression-matching/