LeetCode practice

本文最后更新于：2024年8月4日 下午

LeetCode 刷题

本篇文章将持续更新，刷题过程的思路、语言的底层原理等细节。

vector的erase操作与remove操作

remove

  • remove的实现方式是用被删除对象的后一个对象将其覆盖。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    vector<int> demo{1, 3, 3, 4, 3, 5};
    // 覆盖要删除的元素， remove 后元素应该如右所示 1 4 5 4 3 5
    auto iter = std::remove(demo.begin(), demo.end(), 3);
    for (auto first = demo.begin(); first < demo.end(); ++first)
    {
        cout << *first << " ";
    }
    cout << endl;
    cout << "size is :" << demo.size() << endl;
    cout << "capacity is :" << demo.capacity() << endl;
    return 0;
}
// 1 4 5 4 3 5
// size is :6
// capacity is :6

remove会返回一个迭代器，代表新向量的结尾。

erase

erase函数会将目标真正地移除。

注意一个语法细节：erase(iter,iter)如果前后两个迭代器指向位置相同，则不做任何删改；若想要删除某一位元素，只需填写单独一个参数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    vector<int> demo{1, 3, 3, 4, 3, 5};
    auto iter = std::remove(demo.begin(), demo.end(), 3);
    demo.erase(iter, std::end(demo));
    for (auto first = demo.begin(); first < demo.end(); ++first)
    {
        cout << *first << " ";
    }
    cout << endl;
    // 输出剩余的元素
    cout << "size is :" << demo.size() << endl;
    cout << "capacity is :" << demo.capacity() << endl;
    return 0;
}
// 1 4 5 
// size is :3
// capacity is :6

map数据结构

map

  • map 底层原理是通过红黑树实现，map内部的数据都是有序的。其查询，插入，删除操作的事件复杂度都是logn。

    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
    #include<iostream>
    #include<map>
    #include<string>
     
    using namespace std;
     
    int main()
    {
    	// 构造函数
    	map<string, int> dict;
    	
    	// 插入数据的三种方式
    	dict.insert(pair<string,int>("apple",2));
    	dict.insert(map<string, int>::value_type("orange",3));
    	dict["banana"] = 6;
     
    	// 判断是否有元素
    	if(dict.empty())
    		cout<<"该字典无元素"<<endl;
    	else
    		cout<<"该字典共有"<<dict.size()<<"个元素"<<endl;
     
    	// 遍历
    	map<string, int>::iterator iter;
    	for(iter=dict.begin();iter!=dict.end();iter++)
    		cout<<iter->first<<ends<<iter->second<<endl;
     
    	// 查找
    	if((iter=dict.find("banana"))!=dict.end()) //  返回一个迭代器指向键值为key的元素，如果没找到就返回end()
    		cout<<"已找到banana,其value为"<<iter->second<<"."<<endl;
    	else
    		cout<<"未找到banana."<<endl;
     
    	if(dict.count("watermelon")==0) // 返回键值等于key的元素的个数
    		cout<<"watermelon不存在"<<endl;
    	else
    		cout<<"watermelon存在"<<endl;
    	
    	pair<map<string, int>::iterator, map<string, int>::iterator> ret;
    	ret = dict.equal_range("banana"); // 查找键值等于 key 的元素区间为[start,end)，指示范围的两个迭代器以 pair 返回
    	cout<<ret.first->first<<ends<<ret.first->second<<endl;
    	cout<<ret.second->first<<ends<<ret.second->second<<endl;
     
    	iter = dict.lower_bound("boluo"); // 返回一个迭代器，指向键值>=key的第一个元素。
    	cout<<iter->first<<endl;
    	iter = dict.upper_bound("boluo"); // 返回一个迭代器，指向值键值>key的第一个元素。
    	cout<<iter->first<<endl;
    	return 0;
    }

unordered_map

该类型不会根据key排序，存储时根据key的hash值判断元素是否相同。

获取随机数

1
2
srand((unsigned)time(NULL));//seed
random_num = rand();

除自身外数组乘积

此题需计算数组中，除目标数以外，所有对象的乘积，且时间复杂度在O(n)内，例如：

  • nums = [1,2,3,4];
  • output = [24,12,8,6];

解题思路

  • 关键点在于，时间有要求，不能双重循环，计算乘积时，需要只计算一遍；
  • 将每个数的前缀积与后缀积计算出来，再经过一次循环即可解决；
1
2
3
4
5
for(int i = 0;i<nums.size()-1;i++)
        {
            a*=nums[i];//乘积，从第一项开始乘，并进行存储
            prefix.push_back(a);
        }

deque的使用

首先，对比stack、queue、deque，毫无疑问deque是好用的：

  • deque可随机访问，另外俩不行；
  • deque有迭代器；
  • deque可双向操作；
1
2
3
4
5
6
7
8
9
empty()
push_back()
push_front()
pop_back()
pop_front()
front()
back()
emplace()//插入指定位置
erase()

成员函数应有尽有

例题：

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

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:
    int lengthOfLongestSubstring(string s) {
        deque<char> q;
        unsigned long res = 0;
        deque<char>::iterator iter;
        for(int i = 0;i<s.length();i++)
        {
            if(q.empty())
            {
                q.push_back(s[i]);
                if(res == 0)
                {
                    res =1;
                }
                continue;
            }
            for(iter = q.begin();iter!=q.end();iter++)
            {
                if(s[i] == *iter)
                {
                    while(q.front()!=s[i] && !q.empty())
                    {
                        q.pop_front();
                    }
                    q.pop_front();
                    break;
                }
            }
            q.push_back(s[i]);
            res = max(res,q.size());
        }
        return res;

    }
};

个人代码规范并不紧凑，其实行数很好，deque很好用。

最小覆盖字串（hard）

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

例子：

1
2
3
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

本人思路：

  • 滑动窗口，即从左侧开始，维护两个指针，分别指向窗口的左端和右端；
  • 当s的字串不满足题目条件时，向右移动右指针，窗口向右伸长，寻找合适的值；
  • 当s的字串满足题目条件时，向右移动左指针，试图减小窗口，寻找最小的区间；
  • 重复上述两个步骤，直至右指针达到最右端，且左指针最后尝试移动完毕。

代码如下：

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
class Solution {
public:
    unordered_map<char,int> s_map;
    unordered_map<char,int> t_map;//两个全局变量，方便调用
    bool check()  // 判断当前是否满足“覆盖”这个条件
    {
        for(auto i : t_map)// C++11新特性，使用：进行遍历
        {
            if(s_map[i.first] < i.second)
            {
                return false;
            }
        }
        return true;
    }
    string minWindow(string s, string t) {
        for(int i = 0; i < t.length(); i++)
        {
            t_map[t[i]]++;
        }
        int left = 0;
        int right = 0;
        int res_left = 0;//保存最佳位置的左指针
        int min_length = s.length() + 1;//保存最佳位置的子序列长度
        while(1)
        {
            while(!check() && right < s.length())//寻找下一个匹配的窗口
            {
                s_map[s[right]]++;
                right++;
            }
            if(check())//移动左值针寻找最小窗口
            {
                while(check() && left <= right)
                {
                    s_map[s[left]] --;
                    left++;
                }
                if(right - left + 1 < min_length)
                {
                    min_length = right - left + 1;
                    res_left = left -1;
                }
            }
            if(right >= s.length() || left >= s.length())
            {
                break;
            }
        }
        if(min_length == s.length() + 1)
        {
            return "";
        }
        return s.substr(res_left, min_length);

    }
};

接雨水（hard）

本人第一个独立短时间想出来并实现的hard题。

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

img

1
2
3
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
  • 题目思路：可以动态规划，可以假设左右为高墙，最后去除重复区域等；
  • 本人做法：求出最高的一根柱子，从左至右、从右至左，分别向该目标靠拢。
  • 换句话说，使用左视图、右视图的思想，在左侧向右侧看过去，只能看见最高的那根柱子；
  • 那么在这根最高柱子之前的雨水积累量，是很好计算的；
  • 具体来说：从左侧开始遍历，到最高柱子为止的过程中，有res+= height_left - height[i];
  • 即对于向右的每一格，如果当前格子比该蓄水单元的最左侧格子矮，那么它就会被蓄水。
  • 这就是很简单的一次遍历就可以解决的问题了，时间复杂度为n；

代码：

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
58
class Solution {
public:
    int trap(vector<int>& height) {
        int max_height = -1;
        int max_height_index = -1;
        int c = 0;
        int res = 0;
        for(int i : height)
        {
            if(i > max_height){
                max_height = i;
                max_height_index = c;
            }
            c++;
        }
        int start_left = 0;
        int height_left = 0;
        while(height[start_left] == 0)// 寻找左侧的起点，起点之前无蓄水，起点之后一格比起点低，必定蓄水！
        {
            start_left++;
            if(start_left == height.size())
            {
                return 0;
            }
        }
        height_left = height[start_left];
        for(int i = start_left + 1; i< max_height_index;i++)
        {
            if(height[i] <= height_left)
            {
                res+= height_left - height[i];//当前柱子低于本水池的左柱，且明确知道右柱为全场最高的柱子，那么该柱子上必蓄水！
            }
            else
            {
                height_left = height[i];// 当前柱子高于池子左柱了，之前那个池子便结束了，应用这个更高的柱子，作为新的左柱！
                continue;
            }
        }
        int start_right = height.size()-1;
        while(height[start_right] == 0)//找右侧起点，同上述找左侧起点一致
        {
            start_right--;
        }
        int height_right = height[start_right];
        for(int i = start_right - 1; i > max_height_index ; i--)
        {
            if(height[i] <= height_right)
            {
                res += height_right - height[i];
            }
            else{
                height_right = height[i];
                continue;
            }
        }
        return res;
    }
};

补充：很喜欢我想出来的做法，轻便快捷，找到最高柱子作为一个“极点”，整道题便豁然开朗了！

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！