Zichuan365' Blog HomeArchivesCategoriesGalleryAbout
LeetCode / STL容器
|LeetCodeSTL容器的使用

  • 六大模块：容器、容器适配器、迭代器、算法、仿函数、空间适配器

1.Stack_栈

LC_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
    bool isValid(string s) {
    	int n = s.size();
    	if (n % 2 == 1)
    		return false;

    	//保存映射关系
    	unordered_map<char, char> vis = {
    		{')', '('},
    		{']', '['},
    		{'}', '{'}
    	}; //key \ value

    	//find: 查找key是否存在  connt:存在返回1,不存在返回0
    	stack<char>stk;
    	for (int i = 0; i < s.size(); i++) {
    		if (vis.count(s[i]))
    		{   //出现的是左括号
    			if (stk.empty() || vis[s[i]] != stk.top())
    				return false;
    			stk.pop();
    		}
    		else //出现的是右括号
    			stk.push(s[i]);
    	}
    	return stk.empty();
    }

LC_32.最长有效括号

  • 给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

  • 子串：最长子串、最长子串、最长子串、最长子串、最长子串、最长子串

  • 输入: “(()”

  • 输出: 2

  • 解释: 最长有效括号子串为 “()”

  • 输入: “)()())”

  • 输出: 4

  • 解释: 最长有效括号子串为 “()()”

  • 解题：

  1. stack找到有效的括号，利用辅助vis(false,true)
  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
    int longestValidParentheses(string s) {
    	//题目的意思是子串,所以先找到符合的做出判断
    	//再使用滑动区间找寻
    	stack<int>arr;
    	vector<bool>vis(s.size(), true);

    	for (int i = 0; i < s.size(); i++) {
    		if (s[i] == '(')
    			arr.push(i);
    		else {
    			if (arr.empty())
    				vis[i] = false; //没有匹配的括号
    			else
    				arr.pop();
    		}
    	}
    	while (!arr.empty()) {
    		vis[arr.top()] = false;
    		arr.pop();
    	}

    	int res = 0;
    	int len = 0;
    	for (int i = 0; i < vis.size(); i++) {
    		if (vis[i] == false) {
    			len = 0;
    			continue;
    		}
    		len++;
    		res = max(len, res);
    	}
    	return res;
    }

LC_32.剑指09两个栈实现队列

  • 解题：用一个辅助栈来过一次手

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
class CQueue {
public:
    stack<int>s1;
    stack<int>s2;
    CQueue() {
    }
    //利用两个栈，加的时候，先将s1的放入s2, 然会加s1，s2的再回来
    void appendTail(int value){
        while(!s1.empty()){
            int temp = s1.top();
            s2.push(temp);
            s1.pop();
        }
        s1.push(value);
        while(!s2.empty()){
            int temp = s2.top();
            s1.push(temp);
            s2.pop();
        }
    }
    int deleteHead() {
        if(s1.empty())
            return -1;
        int temp = s1.top();
        s1.pop();
        return temp;
    }
};

单调栈问题

  • 入栈元素小标

  • 进行比较的是栈顶元素

  • 模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    stack<int>minn;
    for (int i = 0; i < len; i++) {
    	
    	while (!minn.empty() && T[i] > T[minn.top()]) {

    		minn.pop();
    	}
    	minn.push(i);
    }

LC_739. 每日温度（找右边第一个比他大的数—递减栈）

  • 请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

  • 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

  • 提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int>dailyTemperatures(vector<int>& T) {
	int len = T.size();
	vector<int>res(len, 0);

	stack<int>minn;
	//单调栈问题,储存的的元素下标
	//递减栈: 小于栈顶,加入栈
	for (int i = 0; i < len; i++) {
		while (!minn.empty() && T[i] > T[minn.top()]) {
			int resCnt = i - minn.top();
			res[minn.top()] = resCnt;
			minn.pop();
		}
		minn.push(i);
	}
	return res;
}

LC_84. 柱状图中最大的矩形

  • 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

  • 求在该柱状图中，能够勾勒出来的矩形的最大面积。
    img

  • 他的最大面积：高*宽，每个高度能把他包住都算一次。

  • 宽度：左边第一个比他小的，右边第一个比他小的

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    int largestRectangleArea(vector<int>& heights) {
    	//为了当只存在一个元素时,也能计算
    	heights.push_back(0);

    	//相当于维护一个递增栈
    	int len = heights.size();
    	int res = 0;

    	//靠单调栈、靠特性:递增栈，下面的第一个元素肯定比他小
    	//找到右边第一个比他小的数、左边第一个比他小的数字
    	stack<int>maxx;
    	for (int i = 0; i < len; i++) {
    		while (!maxx.empty() && heights[i] < heights[maxx.top()]) {
    			int temp = maxx.top();
    			maxx.pop();
    			res = max(res, heights[temp] * (maxx.empty() ? i : (i - maxx.top() - 1)));
    		}                  //高度              宽度
    		maxx.push(i);
    	}

    	return res;
    }

容器盛水问题

  • 给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个容器，请返回容器能装多少水。

img、

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
long long maxWater(vector<int>& arr) {
	//a）5 1 1 1 1 6，桶左边界低
	//b）1 2 3 4 5 6，不能构成桶，桶边界递增
	//c）6 5 4 3  2 1，不能构成桶，桶边界递减
	//d）6 1 1 1 1 5，桶边界右边界低

	int len = arr.size();
	long long res = 0;
	stack<int>vis;
	vis.push(arr[0]);
	int tmp = arr[0];
	for (int i = 1; i < len; i++) {
		if (arr[i] < tmp)
			vis.push(arr[i]);
		else {
			while (!vis.empty()) {
				res += tmp - vis.top();
				vis.pop();
			}
			vis.push(arr[i]);
			tmp = arr[i];
		}
	}
	//考虑c、d
	while (!vis.empty()) {
		tmp = vis.top();
		vis.pop();
		while (!vis.empty() && vis.top() < tmp) {
			res += tmp - vis.top();
			vis.pop();
		}
	}
	return res;
}

2.Map_映射表

A.count() \ A.find()

  • 成员函数

  • auto it = A.find(key)
    • if(it == A.end())没查找到
  • count(key)返回0或者1

350. 两个数组的交集 II

  • 给定两个数组，编写一个函数来计算它们的交集。

  • 输入：nums1 = [1,2,2,1], nums2 = [2,2]

  • 输出：[2,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
    37
    38
    //无序：哈希表
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    	if (nums1.size() == 0 || nums2.size() == 0)
    		return {};

    	unordered_map<int, int>m;
    	for (auto num : nums1)
    		m[num]++;

    	vector<int>res;
    	for (auto num : nums2) {
    		if (m.count(num))
    		{
    			res.push_back(num);
    			m[num]--;
    			if (m[num] == 0)
    				m.erase(num);
    		}
    	}
    	return res;
    }

    //有序时：双指针
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    	sort(nums1.begin(), nums1.end());
    	sort(nums2.begin(), nums2.end());
    	vector<int> res;
    	int i = 0; 
    	int j = 0;
    	while (i < nums1.size() && j < nums2.size())
    		if (nums1[i] < nums2[j]) i++;
    		else if (nums1[i] > nums2[j]) j++;
    		else {
    			res.push_back(nums1[i]);
    			i++, j++;
    		}
    	return res;
    }

LC_1.两数之和

  • 数组中找两个元素之和为target

  • 解法：暴力：time——O（n^2）,空间——O（1）

  • 哈希表：time——O（n）,空间——O（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
    vector<int> twoSum(vector<int>& nums, int target)
    {
    	//vector<int>a;
    	//暴力O(n^2)
    	// for(int i=0;i!=nums.size();i++)
    	// {
    	//     for(int j=i;j!=nums.size();j++)
    	//     {
    	//         if(nums[i]+nums[j]==target&&i!=j)
    	//         {
    	//             a.push_back(i);
    	//             a.push_back(j);
    	//         }
    	//     }
    	// }
    	unordered_map<int, int>vis;//存放元素值,和元素下标
    	for (int i = 0; i < nums.size(); i++) {
    		auto iter = vis.find(target - nums[i]);
    		if (iter != vis.end()) {
    			return { i,iter->second };
    		}
    		vis.emplace(nums[i], i);
    	}
    	return {};
    }

LC_387.字符串中的第一个唯一字符

  • 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

  • 解法：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//时间复杂度n,空间复杂度n

//哈希表的很多使用都可以转化为vector<int>的使用
//26个字母:vector<int>vis(26,0);
int firstUniqChar(string s) {
	unordered_map<int, int>vis;
	for (int i = 0; i < s.size(); i++)
		vis[s[i]]++;
	for (int i = 0; i < s.size(); i++) {
		if (vis[s[i]] == 1) {
			return i;
		}
	}
	return -1;
}

3.Set_集合

  • 成员函数

  • 初始化：unordered_set< string >res (words.begin(),words.end()); //vector< string > & words

LC_820.单词的压缩编码

  • 给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。

  • 例如，如果这个列表是 [“time”, “me”, “bell”]，我们就可以将其表示为 S = “time#bell#” 和 indexes = [0, 2, 5]。

  • 对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 “#” 结束，来恢复我们之前的单词列表。

  • 那么成功对给定单词列表进行编码的最小字符串长度是多少呢？

  • 输入: words = [“time”, “me”, “bell”]

  • 输出: 10

  • 说明: S = “time#bell#” ， indexes = [0, 2, 5] 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int minimumLengthEncoding(vector<string>& words) {
	//初始化:1
	unordered_set<string>res;
	for (auto it : words) {
		res.insert(it);
	}
	//初始化:2
	//unordered_set<string>res(words.begin(),words.end());

	//对于每个单词,我们对其进行重复的查找,利用set容器无重复元素，删除重复的元素
	for (auto it : words) {
		for (int i = 1; i < it.size(); i++) {
			res.erase(it.substr(i));    // time "ime" "me" "e"
		}                               // me "e" 
	}                                   // bell "e" "el" "ell"
	//time#bell#,一个单词需要加上一个#
	int nums = 0;
	for (auto it : res) {
		nums += it.size() + 1;
	}
	return nums;
}

4.Queue_单向队列

  • 成员函数

  • A.push();
  • A.front();//返回元素
  • A.back(); //返回元素
  • A.pop();

LC_225. 用队列实现栈

  • 进入之后，N-1个元素再重新进

    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
    queue<int>arr;
    void push(int x) {
    	arr.push(x);
    	int size = arr.size();

    	for (int i = 0; i < size - 1; i++) {
    		int temp = arr.front();
    		arr.push(temp);
    		arr.pop();
    	}
    }

    int pop() {
    	if (arr.empty())
    		return -1;
    	else {
    		int temp = arr.front();
    		arr.pop();
    		return temp;
    	}
    }

    int top() {
    	return arr.front();
    }

    bool empty() {
    	return arr.empty();
    }

5.deque_双向队列

239. 区间的滑动窗口最大值

  • 给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

  • 返回滑动窗口中的最大值。

  • 题目：

  • 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3

  • 输出: [3,3,5,5,6,7]

  • 解释:

  • 滑动窗口的位置 —– 最大值

  • [1 3 -1] -3 5 3 6 7 —– 3

  • 1 [3 -1 -3] 5 3 6 7 —– 3

  • 1 3 [-1 -3 5] 3 6 7 —– 5

  • 1 3 -1 [-3 5 3] 6 7 —– 5

  • 1 3 -1 -3 [5 3 6] 7 —– 6

  • 1 3 -1 -3 5 [3 6 7] —– 7

  • 解题：

  • 利用双向队列的堆栈特性

  • pop_back()\ pop_front() \ push_back()\ push_front()\ A.front()\ A.back()

    • 头部保存最大元素
    • 利用存放元素下标来保证没有超出区间的范围
    • 每次比较和尾部数据进行比较，从而保证前面节点：老元素。后面节点：新元素。这样可以完成上一条。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
	if (nums.size() == 0)
		return {};
	vector<int>res;
	deque<int>deque;

	//头部:最大数据
	//尾部比较，然后淘汰元素:保证了老元素前,新元素后
	//元素下标,保证区间范围
	for (int i = 0; i < nums.size(); i++) {
		if (!deque.empty() && i - deque.front() >= k)
			deque.pop_front();
		while (!deque.empty() && nums[i] > nums[deque.back()])
			deque.pop_back();
		//这里忘记了
		deque.push_back(i);
		//这里忘记了
		if (i - k + 1 >= 0)
			res.push_back(nums[deque.front()]);
	}
	return res;
}

6.list_双向链表

  • 成员函数

  • A.erase(迭代器)

LC_146. LRU缓存机制

  • 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

  • 获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。

  • 写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

  • 例题：

  • LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

  • cache.put(1, 1);

  • cache.put(2, 2);

  • cache.get(1); // 返回 1

  • cache.put(3, 3); // 该操作会使得关键字 2 作废

  • cache.get(2); // 返回 -1 (未找到)

  • cache.put(4, 4); // 该操作会使得关键字 1 作废

  • cache.get(1); // 返回 -1 (未找到)

  • cache.get(3); // 返回 3

  • cache.get(4); // 返回 4

  • 题解：

    • 利用list存储元素，从而保证时序性
    • 利用unordered_map存储list的iterator，从而保证删除、查找的时间
      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
      59
      60
      61
      62
      63
      64
      class LRUCache {
      public:
      	LRUCache(int capacity) {
      		size = capacity;
      	}

      	list<pair<int, int>>arr;
      	unordered_map<int, list<pair<int, int>>::iterator>vis;
      	//list<pair<int,int>>arr;
      	//unordered_map<key,arr::iterator>vis;
      	//存放迭代器是为了便于删除和查找

      	int get(int key) {
      		//it是key值
      		auto it = vis.find(key);

      		if (it == vis.end()) {
      			return -1;
      		}
      		else {
      			//放到前面去
      			pair<int, int>temp = *vis[key];//迭代器解引就是对应值

      			arr.erase(vis[key]);
      			arr.push_front(temp);
      			vis[key] = arr.begin();
      			return temp.second;
      		}
      	}

      	void put(int key, int value) {
      		auto it = vis.find(key);

      		//不存在
      		if (it == vis.end()) {
      			if (arr.size() == size) {
      				//删除尾元素
      				pair<int, int>temp = arr.back();
      				//双删除
      				int deleteKey = temp.first;
      				vis.erase(deleteKey);
      				arr.pop_back();

      				arr.push_front({ key,value });
      				vis[key] = arr.begin();
      			}
      			else {
      				arr.push_front({ key,value });
      				vis[key] = arr.begin();
      			}
      		}
      		//存在
      		else {
      			//存在只需要放到前面去,list删除只能用迭代器
      			arr.erase(vis[key]);

      			arr.push_front({ key,value });
      			vis[key] = arr.begin();
      		}

      	}
      private:
      	int size;
      };

7.vector_动态数组

  • 成员函数：
    copy(src_Begin, src_End , dest_Begin)

  • Copy：归并算法会使用到

  • copy(B.begin() , B.end(), A.begin());

    • OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)

  • erase(iterator position)//返回下元素指针

  • insert函数
    insert( dest_插入数组的位置, src_输入开始位置 , dest_输入结束位置)

  • 分类：

    • 单一元素(1)——A.insert (iterator position, const value_type& val);
    • 相同元素(2)——A.insert (iterator position, size_type n, const value_type& val);
    • 范围元素(3)——使用广泛——A.insert (iterator position, InputIterator first, InputIterator last);
文章作者: Inter
文章链接: https://zuizichuan.cn/2020/08/19/LeetCode-STL%E5%AE%B9%E5%99%A8%E7%9A%84%E4%BD%BF%E7%94%A8/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Zichuan365' Blog！