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 协议 ,转载请注明出处!