leetcode hot100刷题日记——1.两数之和

vector

从基础来，老子不信了自己还能搞不定这100道题了！
详见链接:
link1
《【C++ STL】vector类最全详解（什么是vector?vector类的常用接口有哪些？）》
link2
《【C++】详解vector二维数组的全部操作（超细图例解析！！！）》

这位大大讲的特别详细。我就在自己博客里面总结一些点让自己复习方便点。

概念

（1）vector是一个能够存放任意类型的动态数组，能够增加和压缩数据。
（2）vector与array的区别：array静态空间；vector动态空间。但两者都采用连续存储空间来存储元素。
（3）vector分配空间策略：会分配一些额外的空间以适应可能的增长。
（4）与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好

一维vector

（1）定义：

vector<typename> name;

（2）常见构造：

vector();//无参构造（构造一个没有元素的空容器，size = 0）

vector (const vector& x); //拷贝构造

举例：

vector<int> v1; //构造int类型的空容器

vector<int> v2(10, 2); //构造含有10个2的int类型容器，前者是个数，后者是值

vector<int> v3(v2); //拷贝构造int类型的v2容器的复制品

vector<int> v4(v2.begin(), v2.end()); //使用迭代器拷贝构造v2容器的某一段内容

（3）遍历：

//下标
vector<int> v(5, 1);
//使用“下标+[]”的方式遍历容器
for (size_t i = 0; i < v.size(); i++)
{
	cout << v[i] << " ";
}

//迭代器
vector<int> v(10,2);//复习一下：10个2
vector<int>::iterator it=v.begin();
while(it!=v.end()){
	cout<<*it<<" ";
}

//上面的有点复杂，更常用的
for(auto it:v){
	cout<<it<<" ";
}

（4）常用操作（务必记住每一个，好吗？好的。都别忘记加括号，好吗？好的）：

• size()：返回容器中有效元素个数
• empty()：判断容器是否为空，size为0返回1，size不为0返回1
• back()：返回最后一个元素的引用（下标）
• front()：返回第一个元素的引用
• push_back()：在末尾添加一个元素，有效元素个数加1
• pop_back()：删除最后一个元素，有效元素个数减1
• insert()：在指定迭代器位置的元素之前插入新元素来扩展容器
• erase()：从容器中删除单个元素，或一系列元素（迭代器区间[first,last]）
• swap()：交换两个容器的内容
• find()：查找

开始具体用法：

//1.push_back()
vector<int> v;
for (int i = 0; i < 5; i++)
{
	v.push_back(i);
}
//输出就是：0 1 2 3 4 


//2.pop_back()
v.pop_back();
//输出就是0 1 2 3

//3.insert()
int a[] = { 1,2,3,4,5 };
vector<int> v(a, a + 5);//这里把a数组的值放进去了v，注意看写法，要有5个空间
// 在第一个位置插入一个 0
v.insert(v.begin(), 0);
for (auto ch : v)
{
	cout << ch << " ";//0 1 2 3 4 5
}
cout << endl;

// 在最后一个位置插入2个6
v.insert(v.end(), 2, 6);
for (auto ch : v)
{
	cout << ch << " ";//0 1 2 3 4 5 6 6
}
cout << endl;


//4.erase()
//删除指定位置的元素
v.erase(v.begin());// 1 2 3 4 5 6 6
//删除指定区间的元素
v.erase(v.begin(), v.begin() + 2);//3 4 5 6 6

//5.swap()
vector<int> v1(5, 2);//2 2 2 2 2
vector<int> v2(6, 3);//3 3 3 3 3 3
swap(v1, v2);
for (auto ch : v1)
{
	cout << ch << " ";//3 3 3 3 3 3
}


//6.find
int a[] = { 1,2,3,4,5,1,2,5,8,6 };
vector<int> v(a, a + 10);//再次复习，10是长度
//注意：find咋用的
//前两个参数指定寻找范围：v的开头到v的结尾
//第三个参数：要找的数值是8
//返回的是迭代器位置
vector<int>::iterator pos = find(v.begin(), v.end(), 8);
//很明显，a数组里面有8，所以会返回8在的位置9
//之后就可以删除掉8
if (pos != v.end())
{
	v.erase(pos);
}
//但如果我们要找的数不在vector里面呢？那么就会返回迭代器的末尾下标
//所以我们的if判断条件是pos是否等于v.end()
//不等于，找到了
//等于，没找到

扩展点：

• capacity()：返回分配的存储容量大小（即有效元素的最大容量）

vector<int> v(10,2);//复习一下：10个2
cout<<v.size()<<endl;//10
cout<<v.capacity()<<endl;//10

• reserve()：调整容器的容量大小（capacity)

//通过以下代码，capacity变成100
void TestVectorExpandOP()
{
	vector<int> v;
	size_t sz = v.capacity();
	v.reserve(100); // 提前将容量设置好，可以避免一遍插入一遍扩容
	cout << "making bar grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

• resize()：开空间 + 初始化，并且填上默认值，调整容器的有效元素大小(size)

//访问时候用下标
vector<int> v2;
v2.resize(10);
for (size_t i = 0; i < 10; i++)
{
    v2[i] = i;
}

二维

（1）声明：
size1是多少行，size2是多少列，0是赋予的初始化值

vector<vector<int>> table(size1, vector<int>(size2, 0));

（2）初始化（这个要记住！）：

• 定义时直接初始化

//行为r，列为c的二位数组
vector<vector<int>> ans(r, vector<int>(c));
//下面定义的是行为r，列为c的二维数组，初始值为0
vector<vector<int>> ans(r,vector<int>(c,0));

• 用resize来提前构建

vector<vector<int>> mat(r);//这个r必须有，规定有多少行
for(int i=0;i<r;i++){
	mat[i].resize(c);
}

• push_back插入

vector<vector<int>>mat(r);//复习，r不可以省略！
mat[i].push_back(1);//这就是该第i-1行的插入一个元素，值为1

（3）添加与删除操作

• 添加一行

//插入到下标为2的行（实际上是在第三行）
vector<int>row(5,6);//定义要插入的数组，复习，5个6的意思
a.insert(a.begin()+2,row);//第一个参数位置，第二个参数要插入的数组

• 添加一列

//插入到下标为2的列（实际上是第三列）
//a.size()代表行数
for(int i=0;i<a.size();i++)
{
	//实际上就是每一行的第三个插入一个9
	a[i].insert(a[i].begin()+2,9)
}

• 删除一行

//删除下标为2的行，实际上是第三行
a.erase(a.begin()+2,a.begin()+3);

• 删除一列

//和insert插入一列时候思想一样
for(int i=0;i<a.size();i++){
	a[i].erase(a[i].begin()+2,a[i].begin()+3);
}

例题：杨辉三角link3

class Solution{
	public:
		vector<vector<int>> generate(int numRows){
		//二维数组定义
		vector<vector<int>>tr;
		tr.resize(numRows);//开辟numRows行
		for(int i=0;i<numRows;i++){
			tr[i].resize(i+1,0);//为每一行开辟空间，初始化为0
			tr[i].front()=tr[i].back()=1;//每一行的第一个和最后一个元素是1。复习front()和back()
			}
		for(int i=2;i<numRows;i++){
			for(int j=1;j<i;j++){
				tr[i][j]=tr[i-1][j-1]+tr[i-1][j];
				}
			}
		return tr;
		}
}

哈希

依旧是详见大大link4
（1）定义
在关键字和储存位置之间建立对应关系，让元素查找以O(1)效率进行。（通过散列函数）

（2）常见散列函数

• 线性定址法：直接取关键字的某个线性函数作为存储地址
• 除留余数法：将关键字对某一小于散列表长度的数p取余的结果作为存储地址

但，通过以上方法构建的哈希表在理想的情况下能够做到一个关键字对应一个地址，但是实际情况是会有冲突发生，也就是散列函数会将多个关键字映射到同一个地址上。

• 开放地址法：
  1）线性探测法：当发生冲突时，就顺序查看下一个存储位置，如果位置为空闲状态，就将该关键字存储在该位置上，如果还是发生冲突，就依次往后查看，当查看到存储空间的末尾时还是找不到空位置，就返回从头开始查看。
  ……
  其他见大大说的link4

（3）使用：

unordered_map<elemType_1, elemType_2> var_name; //声明一个没有任何元素的哈希表，
//其中elemType_1和elemType_2是模板允许定义的类型，如要定义一个键值对都为Int的哈希表：

//初始化，可以给值
unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
//如果知道要创建的哈希表的元素个数时，也可以在初始化列表中指定元素个数，下面就是3个值
unordered_map<int, int> hmap{ {{1,10},{2,12},{3,13}},3 };

（4）常用函数：

• begin()：返回一个指向哈希表开始位置的迭代器。

unordered_map<int,int>iterator iter=hmap.begin();
cout << iter->first << ":" << iter->second; //这里要记住怎么hash表中的两个元素！！！

• end( )函数：作用于begin函数相同，返回一个指向哈希表结尾位置的下一个元素的迭代器。
• cbegin() 和 cend()：这两个函数的功能和begin()与end()的功能相同，唯一的区别是cbegin()和cend()是面向不可变的哈希表。
• empty()函数：判断哈希表是否为空，空则返回true，非空返回false。
• size()函数：返回哈希表的大小
• erase()函数： 删除某个位置的元素，或者删除某个位置开始到某个位置结束这一范围内的元素， 或者传入key值删除键值对
• find()函数：以key作为参数寻找哈希表中的元素，如果哈希表中存在该key值则返回该位置上的迭代器，否则返回哈希表最后一个元素下一位置上的迭代器
  （这些和vector都很像）

不太一样的：

• at()函数：根据key查找哈希表中的元素

unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
int elem = hmap.at(3);//13

• clear()函数：清空哈希表中的元素

• count()函数： 统计某个key值对应的元素个数， 因为unordered_map不允许重复元素，所以返回值为0或1

int count = hmap.count(key);

• 遍历：

unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
unordered_map<int, int>::iterator iter = hmap.begin();
for( ; iter != hmap.end(); iter++){
 cout << "key: " <<  iter->first  << "value: " <<  iter->second <<endl;//复习，first和second
}

力扣第一题：两数之和link5

解答：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // //1.两重循环，时间复杂度O(n^2),空间复杂度O(1)
        // vector<int> res;
        // for(int i=0;i<nums.size();i++){
        //     for(int j=i+1;j<nums.size();j++){
        //         if(nums[i]+nums[j]==target){
        //             res.push_back(i);//复习push_back,在末尾插入元素i
        //             res.push_back(j);
        //             return res;
        //         }
        //     }
        // }
        // return res;

        //2.哈希表，时间复杂度O(N),空间复杂度O(N)
        unordered_map<int,int>map;
        for(int i=0;i<nums.size();i++){
            auto it=map.find(target-nums[i]);//返回的是位置，这个是不是和vector有点像呢？
            if(it!=map.end()){
                return {it->second,i};//复习first和second是啥来着？
            }
            map[nums[i]]=i;
        }
        return {};
    }
};