【算法学习】语言基础

动态数组类型

//初始化一个int型数组nums
vector<int> nums;

//初始化一个大小为n的数组nums，数组中默认都为0
vector<int> nums(n);

//初始化一个元素为1、3、5的数组nums
vector<int> nums{ 1, 3, 5 };

//初始化一个大小为n的数组，其值全部为2
vector<int> nums(n, 2);

//初始化一个二维int数组dp
vector<vector<int>> dp;

//初始化一个大小为m*n的布尔数组dp；
//其中的值都为true
vector<vector<bool>> dp(m, vector<bool>(n, true));

下面是它的成员函数

//返回数组是否为空
bool empty();

//返回数组的元素个数
size_type size();

//返回数组最后一个元素的引用
reference back();

//在数组尾部插入一个元素val
void push_back(const value_type& val);

//删除数组尾部的元素
void pop_back();

下面举一个例子

#include 
#include 
using namespace std;


int main() {
	int n = 10;
	//数组大小为10，元素值都为0
	vector<int> nums(n);
	//输出false(0)
	cout << nums.empty();
	//输出：10
	cout << nums.size();

	//可以通过方括号直接取值或修改值
	int a = nums[4];
	nums[0] = 11;

	//在数组尾部插入一个元素20
	nums.push_back(20);
	//输出：11
	cout << nums.size();

	//得到数组最后一个元素的引用
	int b = nums.back();
	//输出20
	cout << b;

	//删除数组的最后一个元素（无返回值）
	nums.pop_back();
	//输出10
	cout << nums.size();

	//交换nums[0]和nums[1]
	swap(nums[0], nums[1]);

}

利用索引访问很高效，从尾部增删元素也很高效。而从中间或头部增删元素要涉及迁移数据，很低效，所以要从算法层面避免。

字符串string

常见用法

	string s;
	string s = "abc";

	//返回字符串长度
	size_t size();
	
	//判断字符串是否为空
	bool empty();

	//在字符串尾部插入一个字符c
	void push_back(char c);

	//删除字符串尾部的字符
	void pop_back();

	//返回从索引pos开始，长度为len的子字符串
	string substr(size_t pos, size_t len);

举例说明

#include 
#include 
#include 
using namespace std;


int main() {

	//s是空字符串
	string s;
	s = "abcd";
	cout << s[2];
	s.push_back('e');
	cout << s;
	cout << s.substr(2, 3);
	s += "xyz";
	cout << s;
}

哈希表 unordered_map

	//初始化一个key为int，value为int的哈希表
	unordered_map<int, int> mapping;

	//初始化一个key为string，value为int数组的哈希表
	unordered_map<string, vector<int>> mapping;

哈希表的值可以是任意类行，但是键只能是特定类型，一般使用int、string。

常见的成员函数

	//返回哈希表的键值对个数
	size_type size();

	//返回哈希表是否为空
	bool empty();

	//返回哈希表中key出现的个数，可用于判断键是否存在于哈希表中
	size_type count(const key_type& key);

	//通过key消除哈希表中的键值对
	size_type erase(const key_type& key);

常见使用方法

#include 
#include 
#include 
#include 
using namespace std;


int main() {
	vector<int> nums{ 1, 2, 3, 4, 5, 3, 6 };
	//计数器
	unordered_map<int, int> counter;
	for (int num : nums) {
		//可以用方括号直接访问或修改对应的键
		counter[num]++;
	}

	//遍历哈希表中的键值对
	for (auto& it : counter) {
		int key = it.first;
		int val = it.second;
		cout << key << ";" << val << endl;
	}
}

使用方括号访问键时，若key不存在，则会自动创建key

哈希集合unordered_set

	//初始化一个存储int的哈希集合
	unordered_set<int> visited;

	//成员函数如下

	//返回哈希集合中键值对个数
	size_type size();

	//返回哈希集合是否为空
	bool empty();

	//类似哈希表，如果key存在则返回1，否则返回0
	size_type count(const key_type& key);

	//向集合中插入一个元素key
	pair<iterator, bool> insert(const key_type& key);

	//删除哈希集合中的元素key，如果删除成功则返回1，如果key不存在则返回0
	size_type erase(const key_type& key);

队列

	//初始化一个存储int的队列
	queue<int> q;

	//其常用成员函数
	
	//判断队列是否为空
	bool empty();

	//返回队列中元素的个数
	size_type size();

	//将元素加入队尾
	void push(const value_type& val);

	//返回队头元素的引用
	value_type& front();

	//删除队头元素
	void pop();

队列简单，但C++不会像其他语言那样pop时返回对应元素
所以一般是这样处理的

int e = q.front();  q.pop();

堆栈stack

	//初始化一个int类型的堆栈
	stack<int> stk;

	//其成员函数

	//返回堆栈是否为空
	bool empty();

	//返回堆栈中元素的个数
	size_type size();

	//在栈顶添加元素
	void push(const value_type& val);

	//返回栈顶元素的引用
	value_type& top();

	//删除栈顶元素
	void pop();