LeetCode学习过程

发表于 2025-02-24 更新于 2025-03-03 分类于 LeetCode学习阅读次数：本文字数： 9.5k 阅读时长 ≈ 17 分钟

自2025.2.24开始学习LeetCode，使用语言C++，这篇Blog记录学习过程。

2025.2.24

动计划·编程入门

C++ vector用法

参考：C++ vector的用法（整理）-CSDN博客

1. vector的初始化

vector<int> a(10);  //定义10个整数元素的向量
vector<int> a(10,1); //定义向量，每个元素赋值为1
vector<int> a(b); //用b向量来定义a，整体复制
vector<int> a(b.begin(),b.begin()+3); // 定义a为b中第0到第2个元素（共3个）

int b[7] = {1,2,3,4,5,6,7}
vector<int> a(b,b+5); //定义a为b中的前五个元素

2025.2.25

2. vector对象的操作

输入

vector<int> a;
a.assign(4,2); //(1) a只含4个元素，每个元素为2
a.assign(b.begin(),b.begin()+3);//(2) 将b的前三个元素构成的向量赋给a

输出

//返回数组元素
a.back(); //返回最后一个元素
a.front(); //返回第一个元素
a[i]; //返回第i个元素

//范围数组特征
a.empty(); //判断是否为空，空返回true，否则返回false
a.size();
a.capacity();

修改

//删除元素
a.clear(); //清空
a.pop_back(); //删除最后元素
a.erase(a.begin()+1,a.begin()+3); //清除数组第1到第2个元素，包含a.begin()+1,不包含a.begin()+3
//插入元素
a.push_back(5); //在最后插入元素5
a.insert(a.begin()+1,5); //在第1个元素位置插入元素5
a.insert(a.begin()+1,3,5); //在第一个元素位置插入3个元素，赋值为5
a.insert(a.begin()+1,b+3,b+6); //在第一个元素位置插入 b的第3到第5个元素，数量为3
//修改数组
a.resize(10); //将a的现有元素调至10个，多则删，少则补，取值随机
a.resize(10,2); //将a的现有元素调至10个，取值为2
a.reserve(100); //将a的容量（capacity）扩至100，（可以避免内存多次容量扩充操作，a的容量不足时电脑会自动扩容）
a.swap(b); //b为向量，将a中的元素和b中的元素整体交换

3. 顺序访问

添加元素

int a[6] = { 1,2,3,4,5,6};
vector<int> b(a,a+4);
vector<int> c;
for(int i = 0 ; i<10;i++){
	c.push_back(i); //直接添加元素
    c.push_back(a[i]); //从数组中选择元素添加
}
for(vector<int>::iterator it = b.begin();it<c.end();it++){
    c.push_back(*it); //从现有向量中选择元素添加
}
// vector<int>::iterator it 迭代器，*it类型为&int

【错误】
vector<int>a;
for(int i = 0;i<10;i++){
    a[i] = i; // 下标只能用于获取已经存在的元素
}

读取元素

int a[6]={1,2,3,4,5,6};
vector<int> b(a,a+4);
for(int i=0;i<b.size();i++){
    cout<<b[i]<<" ";
}

for(vector<int>::iterator it=b.begin();it<b.end();i++){
    cout<<*it<<" ";
}

4. 其他算法（使用其他库）

#include<algorithm>

sort(a.begin(),a.end()); //对a从begin到end排序，修改原数组元素
reverse(a.begin(),a.end()); //对a从begin到end倒序
copy(a.begin(),a.end(),b.begin()+1);////把a从begin到end的元素复制到b中，从b.begin()+1的位置开始复制，覆盖掉原有元素
find(a.begin(),a.end(),10); //在a从begin到end的元素中查找10，若存在返回其在向量中的位置 返回 vector<int>::iterator 类型
// ---- 判断是否查找成功 -----
	std::vector<int> a = { 1,6,3,2,5 };
	vector<int>::iterator it = find(a.begin(), a.end(),5);
	if (it != a.end())
		cout << "查找成功：" << *it;
	else
		cout << "查找失败";
	return 0;

2025.2.26

异或运算

题目：

给你两个整数，n 和 start 。

数组 nums 定义为：nums[i] = start + 2*i（下标从 0 开始）且 n == nums.length 。

请返回 nums 中所有元素按位异或（XOR）后得到的结果。

异或运算： ^

1. 模拟方法

class Solution {
public:
    int xorOperation(int n, int start) {
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans ^= (start + i * 2);
        }
        return ans;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/xor-operation-in-an-array/solutions/371258/shu-zu-yi-huo-cao-zuo-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2. 数学方法

异或性质：

x ^ x = 0
x ^ 0 = x
x ^ y = y ^ x（交换律）
( x ^ y ) ^ z = x ^ ( y ^ z )（结合律）
x ^ y ^ y = x（自反性）；
∀ i ∈ Z，有 4i ^ ( 4i + 1) ^ ( 4i + 2 ) ^ ( 4i + 3 ) = 0

本题需要计算 $start\oplus(start+2\times i) \oplus (start+4\times i)\oplus\cdots\oplus(start+2(n-1))$ ,争取利用上性质6，对式子进行变换，构造成 $x\oplus x+1\oplus x+2 \oplus x+3$ 的形式

首先，由于式子每个元素元素的奇偶性和start相同，所以可以单独提取出二进制的最低位，记为e，其余位对2向下整除向右移位

且当start和n同为奇数时，e为1，其余情况e均为0， $\underbrace{1\oplus1\oplus\cdots\oplus1}_{n(n为奇数)}=1$

注： $\lfloor \frac{x}{2}\rfloor$ 操作可以舍去二进制的最低位并且所有位数向右移动一位，即 $7 = \{111\} \rightarrow \lfloor7/2\rfloor = 3 = \{11\}$ 或 $10 = \{1010\} \rightarrow \lfloor10/2\rfloor = 5 = \{101\}$

原式 = $[s\oplus s+1\oplus s+2 \oplus s+3\oplus\cdots\oplus s+(n-1)]\times2+e$ ,其中 $s = \lfloor\frac{start}{2}\rfloor$

构造函数sumXor(x)表示 $1\oplus2\oplus3\oplus\cdots\oplus x$ 利用异或性质1和性质3，原式可以表示为： $sumXor(s+(n-1))\oplus sumXor(s-1)\times+e$ ，相同元素异或为0，消去前面s-1个相同的元素。

\text{sumXor}(x)=\begin{cases}x,&x=4k,k\in Z\\(x-1)\oplus x,&x=4k+1,k\in Z\\(x-2)\oplus(x-1)\oplus x,&x=4k+2,k\in Z\\(x-3)\oplus(x-2)\oplus(x-1)\oplus x,&x=4k+3,k\in Z&\end{cases}

分别计算每种情况：

注： $x = 4k + 0/1/2/3时，x的二进制为\{\bold{xxxx}|00/01/10/11\}$

$(x-1)\oplus x = \{\bold{xxx|00}\}\oplus \{\bold{xxx|01}\} = \{000|01\} = 1$
$(x-2)\oplus (x-1)\oplus x = \{\bold{xxx|00} \}\oplus \{\bold{xxx|01}\}\oplus \{\bold{xxx|10}\} = \{\bold{ 000|01}\}\oplus\{\bold{xxx|10}\}=\{\bold{xxx}|11\} = x+1$
$(x-3)\oplus(x-2) \oplus (x-1)\oplus x = 0$

注：由于每个式子中x取的值不一样，不可以把上一个结论带入下一个计算

于是可以简化为：

\mathrm{sumXor}(x)=\begin{cases}x,&x=4k,k\in Z\\1,&x=4k+1,k\in Z\\x+1,&x=4k+2,k\in Z\\0,&x=4k+3,k\in Z\end{cases}

实现代码

class Solution {
public:
    int sumXor(int x) {
        if (x % 4 == 0) {
            return x;
        }
        if (x % 4 == 1) {
            return 1;
        }
        if (x % 4 == 2) {
            return x + 1;
        }
        return 0;
    }

    int xorOperation(int n, int start) {
        int s = start >> 1; //对start左移一位
        int e = n & start & 1; //判断n和start都为奇数
        int ret = sumXor(s - 1) ^ sumXor(s + n - 1);
        return ret << 1 | e; //相当于 ans × 2 + e
    }
};

注：

判断一个数为奇数：x & 1值为1则为奇数，否则，偶数。
判断两个数同为奇数： x & y & 1同为奇数则为1，否则，为0

2025.3.2

哈希表

参考文章：https://blog.csdn.net/Peealy/article/details/116895964

哈希表定义

在关键字和存储位置之间建立对应关系（散列函数），是的元素的查找可以以O（1）的效率进行。

常见的散列函数

线性定址法：取关键字的某个线性函数作为存储地址

$Hash(key) = a \times key + b$
除留余数法：将关键字对某一小于散列表长度的数p取余的结果作为存储地址

$Hash（key） = key \space \bold{mod}\space p$
平方取中法：对关键字取平方，然后将得到结果的中间几位作为存储地址
折叠法：关键字分隔为几个部分，几部分叠加和作为存储地址

地址冲突解决方法

冲突：几个关键字映射到了同一个地址上

开放地址法
1. 线性探测法：顺序查看下一个存储位置，如果空闲则把关键字存储在该位置上，如果冲突依次往后查看，直至末尾还是没有位置则返回从头开始查看
2. 平方探测法：不同于线性探测法的依次顺序查看下一个位置，平方探测是以 $1^2,-1^2,2^2,-2^2,\cdots$ 的规则向后探测
3. 再散列法：利用两个散列函数，当通过第一个散列函数得到的关键字的存储地址发生冲突时，使用第二个散列函数计算出地址增量，计算方式如下：
  $H_i = (Hash_1(key)+i*Hash_2(key))\bold{mod}\space p$
4. 伪随机法：当发生冲突时，加入一个随机数作为地址增量寻找新的存储地址：
  $H_i = (Hash(key)+d_i) \bold{mod} \space{p}$
拉链法

将具有相同存储地址的关键字链成一个单链表，m个存储地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构，例如一个散列函数为Hash(key) = key % 13的存储结构为：

STL库中的哈希表

#incldue<unordered_map>

声明和初始化

#include<unordered_map>
unordered_map<elemType_1,elemType_2> var_name; //声明
unordered_map<int,int> var_name; //声明一个key和value都是int类型的哈希表
unordered_map<int,int> var_name;{{0,2},{1,5},{2,3}}; //初始化

插入元素

使用operator[]的方法插入

umap["apple"] = 3;

使用insert()方法插入

umap.insert({"orange",2})
umap.insert(make_pair("banana",5)); //使用c++标准库的函数模板make_pair构造std::pair对象插入

获取元素&哈希表状态

begin()和end() 返回一个指向哈希表开始和结尾位置下一个元素的迭代器

cbegin()和cend() 功能和begin()和end()相同，但是面向不可变的哈希表

unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
unordered_map<int, int>::iterator iter = hmap.begin();
unordered_map<int, int>::iterator iter = hmap.end();

const unordered_map<int, int> hmap{ {1,10},{2,12},{3,13} };
//注意这里的迭代器也要是不可变的const_iterator迭代器
unordered_map<int, int>::const_iterator iter_b = hmap.cbegin();  
unordered_map<int, int>::const_iterator iter_e = hmap.cend();

empty()：判断哈希表是否为空，空则返回true，非空则返回false

size()：返回哈希表的大小

bool isEmpty = hmap.empty();
int size = hmap.size();

查找元素

find()函数

//find()返回存在改key值位置上的迭代器，如果不存在则返回end()
unordered_map<int, int>::iterator it = umap.find("apple");
//或者直接使用 auto
auto it = umap.find("apple")
    
if (it != umap.end()) {
    std::cout << "Found apple: " << it->second << std::endl;
} else {
    std::cout << "apple not found" << std::endl;
}

at()函数

//at() 直接返回哈希表中的元素
unordered_map<std::string, int> umap = { {"apple", 5}, {"banana", 3} };
int elem = hmap.at("apple");

直接使用operator[]访问

unordered_map<std::string, int> umap = { {"apple", 5}, {"banana", 3} };

区别：

at()返回与指定 key 关联的 value 的引用，如果不存在会抛出std::out_of_range异常，可以使用try-catch块捕捉异常
find()返回迭代器指向key所对应的元素，如果不存在返回end()，不会抛出异常
operator[]如果 key 不存在，会自动插入一个默认值

std::unordered_map<std::string, int> umap = {{"apple", 5}, {"banana", 3}};
    
    // 使用 at()
    try {
        int appleValue = umap.at("apple");
        std::cout << "apple: " << appleValue << std::endl;
        
        // 尝试访问不存在的 key，抛出异常
        int orangeValue = umap.at("orange");
        std::cout << "orange: " << orangeValue << std::endl;
    } catch (const std::out_of_range& e) {
        std::cout << "Exception caught: " << e.what() << std::endl;
    }
    // 命令行输出：Exception caught: invalid unordered_map<K, T> key
	
    // 使用 find()
    auto it = umap.find("banana");
    if (it != umap.end()) {
        std::cout << "banana: " << it->second << std::endl;
    } else {
        std::cout << "banana not found" << std::endl;
    }

修改与删除元素

修改：直接通过operator[]修改对应key的value
umap["apple"] = 10;
删除：使用erase()或者直接使用迭代器删除

umap.erase("banana");
auto it = umap.find("orange");
if(it !=umap.end())
    umap.erase(it);

清空：empty()函数