Leetcode Hot 100

Leetcode Hot 100

前言

今天是2024年5月25日 凌晨 1:24 分 在寝室洗衣房写下这段话。距离9.28还有4个月。也不知道那个时候的我有没有offer了（shushu不会还是0 offer吧，做梦都想去tp，有点难，那就梦梦浙大吧，耳机里突然响起来《落空》这首歌——“我们都曾试过想以后，以后却不会来了”。。。。。。希望我的梦想不会落空。加油！！！开刷leetcode hot 100 为了我梦想，为了不留遗憾，再冲一次吧。）

1.两数之和

  1. 算法一（哈希表）
    核心思想：for循环，使用map依次存储数组下标和对应的数；使用map.count(target - num[i]) 查询目前map中是否已经存储了所需要的值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            vector<int> res(2);
            map<int,int> mp;
            for(int i=0;i<nums.size();i++){
                if(mp.count(target - nums[i]) > 0){
                    res[0] = i;
                    res[1] = mp[target - nums[i]];
                    return res;
                }
                mp[nums[i]] = i;
            }
            return res;
        }
    };

  2. 算法二（快慢指针）
    核心思想：$两个指针 i,j 不断向前移动找到答案（ j < i ）$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        for(auto i=nums.begin();i<nums.end();i++){
            for(auto j=nums.begin();j<i;j++){
                if((*i + *j) == target){
                    res.push_back(j-nums.begin());
                    res.push_back(i-nums.begin());
                    break;
                }
            }
        }
        return res;
    }
};

2.两数相加

核心思想：高精度加法

tips:

  1. 注意最后一个进位也要考虑进来
  2. 构造链表
    1
    2
    3
    4
    5
    6
    7
    8
    9
    1.初始化
    ListNode* prehead = new ListNode(0), *cur = prehead;

    2.赋值
    cur->next = new ListNode(v);
    cur = cur->next;

    3.返回构造的链表
    return prehead->next;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* prehead = new ListNode(0), *cur = prehead;
        ListNode *p = l1;
        vector<int> a,b;
        while(p){
            a.push_back(p->val);
            p = p->next;
        }
        p = l2;
        while(p){
            b.push_back(p->val);
            p = p->next;
        }
        int len = max(a.size(),b.size());
        int t = 0;
        vector <int> res;
        for(int i=0;i<len;i++){
            int v = 0;
            if(i<a.size()){
                v += a[i];
            }
            if(i<b.size()){
                v += b[i];
            }
            v += t;
            if(v>=10){
                v -= 10; t = 1;
            }
            else{
                t = 0;
            }
            cur->next = new ListNode(v);
            cur = cur->next;

        }
        //注意最后一个进位也要考虑进来
        if(t >= 1){
            cur->next = new ListNode(t);
            cur = cur->next;
        }
        return prehead->next;
    }
};

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


核心思想：滑动窗口 + un ordered set
tips:

  1. count（检查当前窗口内是否有重复元素）
  2. erase（去掉左指针所指向元素，i++ ——> 即窗口右移）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.size();
        unordered_set<char> str; //无重复字符且无序
        int r = 0;//定义右指针
        int res = 0;
        //遍历左指针
        for(int i=0;i<len;i++){

            //不断移动右指针
            while(!str.count(s[r]) && r<len){
                str.insert(s[r]);
                r++;
            }
            //跳出了while循环代表有重复元素出现了，此时移动左指针(从set中删除当前左指针所指向元素)
            res = max(res,r-i);
            str.erase(s[i]);

        }
        return res;
    }
};

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


核心思想：先合并成一个单调递增的数组；然后计算新数组的中位数，算法复杂度为O(n+m); 还可以用二分优化到log(n+m);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size(); int len2 = nums2.size();
        int n=0,m=0; //分别指示num1,num2两个数组的指针
        vector<int> ans;

        //构建一个单调递增的ans数组
        while(n < len1 && m < len2){
            if(nums1[n] < nums2[m]){
                ans.push_back(nums1[n]);
                n++;
            }
            else{
                ans.push_back(nums2[m]);
                m++;
            }
        }
        while(n < len1){
            ans.push_back(nums1[n]);
            n++;
        }
        while(m < len2){
            ans.push_back(nums2[m]);
            m++;
        }
        int len = ans.size();
        double res;
        if(len % 2 == 0){
            res = (ans[len/2 - 1] + ans[len/2]) / 2.0;
        }
        else{
            res = ans[len/2];
        }
        return res;
    }

};

5. 最长回文子串

核心思想：动态规划 f[i][j] , 区间dp ，以[i,j]这段长度上的回文子串
（1） 求最长回文子串长度
（2） 求具体的最长回文子串 ：不断判断某个区间是否是回文子串，如果是，则更新最大长度的左右下标值，之后通过该下标序号来截取具体的子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n == 0) return "";
        
        // 初始化二维动态规划表
        bool f[n+1][n+1];

        // 填充对角线为true，因为单个字符总是回文
        for (int i = 0; i < n; ++i) {
            f[i][i] = true;
        }

        int start = 0, maxLen = 1; // 记录最长回文串的起始位置和长度

        // 填充动态规划表
        for (int len = 2; len <= n; ++len) { // 长度从2开始
            for (int i = 0; i + len - 1 < n; ++i) { // i是子串的起始位置,j是右端点小于n
                int j = i + len - 1; // j是子串的结束位置
                // 如果首尾字符相同，并且中间部分也是回文，则整个序列是回文
                if (s[i] == s[j] && (len < 3 || f[i + 1][j - 1])) {
                    f[i][j] = true;
                    maxLen = len;
                    start = i;
                }
                else {
                    f[i][j] = false;
                }
            }
        }

        // 返回最长的回文子串
        return s.substr(start, maxLen);
    }
};

10. 正则表达式匹配

核心思想：动态规划

11. 盛最多水的容器

核心思想：双指针（最短木板原理，因此两个指针所指向的板中较短的那个指针要向中心移动）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int l = 0; int r = n-1;
        int maxv = 0;
        while(l<r){
            maxv = max(maxv,(r-l)*min(height[l],height[r]));
            if(height[l] < height[r]){
                l++;
            }
            else{
                r--;
            }
        }
        return maxv;
    }
};

15. 三数之和

核心思想：双指针＋set去重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        set<vector<int>> ret;
        sort(nums.begin(),nums.end());

        int len = nums.size();
 
        for(int i=0;i<len;i++){
            int x = -nums[i];
            int l = i+1; int r = len-1;
            while(l<r){
                if(nums[l] + nums[r] + nums[i] < 0){
                    l++;
                }
                else if(nums[l] + nums[r] + nums[i] > 0){
                    r--;
                }
                else{
                    ret.insert({nums[i],nums[l],nums[r]}); 
                    l++; r--;//在当前已经满足条件的情况下，只移动一个指针肯定不能够继续满足条件
                }
            }
        }

        vector<vector<int>> ans(ret.begin(),ret.end());
        return ans;
    }
};

17. 电话号码的字母组合

20. 有效的括号

核心思想：栈的先进后出（注意栈是否为空时的一些边界情况）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    map <char,char> mp;
    bool isValid(string s) {
        mp.insert({'(',')'});
        mp.insert({'{','}'});
        mp.insert({'[',']'});
        stack<char> st;
        int n = s.size();
        bool flag = true;
        //剪枝提前返回
        if(n % 2) {
            return false;
        }
        for(int i=0;i<n;i++){
            if(s[i] == '(' || s[i] == '{' || s[i] == '['){
                st.push(s[i]);
            }
            else{
                //如果读入了一个右括号而此时没有左括号在栈中，则一定不满足条件
                if(st.empty() || mp[st.top()] != s[i]){
                    return false;
                } 
                st.pop();
            }
        }
        return st.empty(); //如果遍历完了整个字符串之后，还符合条件的话，栈肯定为空
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置

核心思想：二分查找
tips:注意空数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans;
        if(nums.size() == 0){
            ans.push_back(-1);
            ans.push_back(-1);
            return ans;
        }
        int l = 0, r = nums.size()-1;
        //找开始位置
        while(l<r){
            int mid = (l+r) / 2;
            if(nums[mid] >= target){
                r = mid;
            } 
            else{
                l = mid+1;
            }
        }
        if(nums[l] != target) ans.push_back(-1);
        else{
            ans.push_back(l);
        }

        //找结束位置
        l = 0, r = nums.size()-1;
        while(l<r){
            int mid = (l+r+1) / 2;
            if(nums[mid] <= target){
                l = mid;
            } 
            else{
                r = mid-1;
            }
        }
        if(nums[l] != target) ans.push_back(-1);
        else{
            ans.push_back(l);
        }


        return ans;
    }
};

70. 爬楼梯

核心思想：
（1）递归+剪枝
（2）动态规划（d[n] = d[n-1] + d[n-2]）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    /*递归＋剪枝
    int st[50];
    int dfs(int i){
        if(i<=1){
            return 1;
        }
        if(st[i]) return st[i]; //剪枝操作，如果该数已经计算过了，就直接查找不需要再递归计算
        else{
            st[i] = dfs(i-1) + dfs(i-2);
        }
        return st[i];
    }
    */
    int climbStairs(int n) {
        //dfs(n);
        int f[50];
        f[1] = 1;
        f[2] = 2;
        for(int i=3;i<=n;i++){
            f[i] = f[i-1] + f[i-2];
        }
        return f[n];
    }
};

283. 移动零

核心思想：

  1. 移除数组元素：数组的元素在内存地址中是连续的， 不能单独删除数组中的某个元素，只能覆盖。
  2. 通过快慢指针来实现数组元素覆盖
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int l=0,r=0;
        for(r=0;r<n;r++){
            if(nums[r] != 0){
                nums[l] = nums[r];
                l++;
            }
        }
        //r最后所在位置为最后一个位置的下一位（因为r要遍历到此才会跳出for循环）
        for(int i=l;i<=r-1;i++){
            nums[i] = 0;
        }
    }
};

Leetcode Hot 100
https://cs-lb.github.io/2024/05/25/Leetcode-Hot-100/
作者
Liu Bo
发布于
2024年5月25日
许可协议