Jackie's Blog
LeetCode知识补充
Jackie
  2025-01-24   2025-02-19  4.3k 字  18 分钟

LeetCode知识补充

对还不清楚的知识作补充，每个点中自己熟悉的部分已略过

  • 部分参考资料

Hello算法

时间复杂度

时间复杂度

O(1)常数阶<O(logn)对数阶<O(n)线性阶<O(nlogn)线性对数阶<O(n2)平方阶<O(n3)立方阶<O(2n)指数阶

常对幂指阶

待补充

内存管理

以C++为例来介绍一下编程语言的内存管理

image

  • 栈区（Stack）：由编译器自动分配释放，存放函数的参数值，局部变量的值等，其操作方式类似于数据结构中的栈
  • 堆区（Heap）：一般由程序员分配释放，若程序员不释放，程序结束时可能由OS收回
  • 未初始化数据区（UninitializedData）：存放未初始化的全局变量和静态变量
  • 初始化数据区（InitializedData）：存放已经初始化的全局变量和静态变量
  • 程序代码区（Text）：存放函数体的二进制代码

计算程序占用多大内存

image

为什么64位的指针就占用了8个字节，而32位的指针占用4个字节呢？

1个字节占8个比特，那么4个字节就是32个比特，可存放数据的大小为232，也就是4G空间的大小，即：可以寻找4G空间大小的内存地址

安装64位的操作系统的计算机内存都已经超过了4G，也就是指针大小如果还是4个字节的话，就已经不能寻址全部的内存地址，所以64位编译器使用8个字节的指针才能寻找所有的内存地址

264是一个非常巨大的数，对于寻找地址来说已经足够用了

内存对齐

  1. 平台原因：不是所有的硬件平台都能访问任意内存地址上的任意数据，某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。为了同一个程序可以在多平台运行，需要内存对齐
  2. 硬件原因：经过内存对齐后，CPU访问内存的速度大大提升
struct node{
   int num;
   char cha;
}a;
int main() {
    cout << sizeof(a) << endl;//8而不是5
}

相对来说计算机内存资源一般都是充足的，我们更希望的是提高运行速度

编译器一般都会做内存对齐的优化操作，也就是说当考虑程序真正占用的内存大小的时候，也需要认识到内存对齐的影响

vector

C++标准模板库（STL）中的一个容器类，用于表示一个动态数组。它可以存储多个元素，并且可以根据需要自动调整大小。

vector<int>& nums

接收一个引用参数，这个参数是一个存储整数的动态数组。在函数内部，可以通过nums这个名字直接访问和操作传入的数组，而不会对数组进行复制

vector<vector<int>> result

二维向量

vector<vector<int>> matrix={
    {1, 2, 3},
    {4, 5},
    {6, 7, 8, 9}
};
#include <iostream>
#include <vector>
using namespace std;

int main(){
    vector<vector<int>> matrix={
    {1,2,3},
    {4,5},
    {6,7,8,9}
    };

    //增加一行
    matrix.push_back({10,11,12});
    cout<<"增加一行后："<<endl;
    for(const auto& row:matrix){
        for(int num:row){
            cout<<num<<" ";
        }
        cout<<endl;
    }
    cout<<endl;

    //删除一行
    matrix.erase(matrix.begin()+1);//删除第二行
    cout<<"删除第二行后"<<endl;
    for(const auto& row:matrix){
        for(int num:row){
            cout<<num<<" ";
        }
        cout<<endl;
    }
    cout<<endl;

    //修改一行
    matrix[1]={13,14,15};//修改第二行
    cout<<"修改第二行后："<<endl;
    for(const auto& row:matrix){
        for(int num:row){
            cout<<num<<" ";
        }
        cout<<endl;
    }
    cout<<endl;

    //修改一个元素
    matrix[2][0]=99;//修改第三行的第一个元素
    cout<<"修改第三行的第一个元素后："<<endl;
    for(const auto& row:matrix){
        for(int num:row){
            cout<<num<<" ";
        }
        cout<<endl;
    }
    cout<<endl;

    //查询一个元素
    int element=matrix[2][0];
    cout<<"矩阵元素[2][0]="<<element<<endl;

    return 0;
}

区别普通数组、std::array、vector

  • 普通数组
//数据类型 数组名[数组大小];
#include <iostream>
using namespace std;

int main() {
    int array[5] = {1, 2, 3, 4, 5};
    cout << array[0] << endl;//1
    cout << sizeof(array) / sizeof(array[0]) << endl;//5
    return 0;
}
  • std::array

数组大小在编译时确定，不可改变，但它是C++标准库中的一个类模板，提供了更多成员函数和方法

//array<数据类型, 数组大小> 数组名;
#include <iostream>
#include <array>
using namespace std;

int main() {
    array<int, 5> array = {1, 2, 3, 4, 5};
    cout << array[0] << endl;//1
    cout << array.at(0) << endl;//1，会边界检查，提高健壮性
    cout << array.size() << endl;//5
    //支持拷贝赋值
    array<int, 5> arr;
    arr = array;
    return 0;
}
  • vector
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec = {1, 2, 3, 4, 5};
    cout << vec.size() << endl;//5
    cout << vec[0] << endl;//1
    vec.push_back(7);//添加一个元素
    cout << vec[5] << endl;//7
    vec.pop_back();//删除最后一个元素
    vec.insert(vec.begin() + 2, 10);//插入一个元素
    cout << vec[2] << endl;//10
    vec.erase(vec.begin() + 2);//删除一个元素
    return 0;
}

>><<

  • >>：右移运算符

a>>b表示将a的二进制表示向右移动b位

a=20;//二进制10100
a>>1//10100向右移动一位，得到1010，即十进制的10
a>>2//10100向右移动二位，得到101，即十进制的5

快速除以2的幂次方

右移运算符在处理有符号数和无符号数时有所不同：

  • 有符号数：算术右移，对于一个负数，右移后空出的位会被1填充，保持数的符号不变
  • 无符号数：逻辑右移，空出的位会被0填充
  • <<：左移运算符

a<<b表示将a的二进制表示向左移动b位

a=5;//二进制101
a<<1//101向左移动一位，得到1010，即十进制的10
a<<2//101向左移动二位，得到10100，即十进制的20

快速乘以2的幂次方

delete

用于释放动态分配的内存的关键字，与new操作符相对应，new用于分配内存并构造对象，而delete用于销毁对象并释放其占用的内存

  • 释放单个对象
int* ptr=new int(10);
delete ptr;
  • 释放数组
int* arr=new int[10];
delete[] arr;

※delete后的指针tmp的变化

使用delete或delete[]释放指针tmp指向的内存后，tmp本身并不会自动变为nullptr。tmp仍然会保留原来的内存地址值，但这个地址所指向的内存已经不再有效。此时，tmp被称为“野指针”

为了避免野指针问题，建议在释放内存后立即将指针设置为nullptr

unordered_set

  • 构造函数

可以接受一个范围（如两个迭代器），直接将该范围内的元素初始化为集合中的元素

  • find function

unordered_set的find方法用于查找指定元素。如果找到了元素，返回指向该元素的迭代器；如果没有找到，返回end()

#include <unordered_set>

vector<int> nums={1,2,3,4,5};
unordered_set<int> s(nums.begin(),nums.end()); //s={1,2,3,4,5}
s.insert(6);//插入元素
s.erase(3);//删除元素
auto it=s.find(4);
if(it!=s.end()){
    cout<<"Found:"<<*it<<endl;//输出"Found:4"
}

范围for循环

C++11引入了范围for循环，用于简化容器的遍历操作，可以直接遍历容器中的每个元素

for(范围声明:范围表达式){
    // 循环体
}
//相当于
for(auto it=v.begin();it!=v.end();++it){
    int num=*it;
    //循环体
}
vector<int>v={1,2,3,4};
for(int num:v){
    cout<<num<<" ";//输出"1 2 3 4"
}

iterator

迭代器是一种检查容器内元素并遍历元素的数据类型，通常用于对C++中各种容器内元素的访问，但不同的容器有不同的迭代器，初学者可以将迭代器理解为指针

begin()&end()

begin()是指向容器第一个元素的迭代器

end()是指向容器最后一个元素的下一个位置的迭代器

迭代器

通用功能

  • 比较两个迭代器是否相等（==、!=）
  • 前置和后置递增运算（++）
  • 读取元素的解引用运算符（*）。只能读元素，也就是解引用只能出现在赋值运算符的右边
  • 箭头运算符（->），解引用迭代器，并提取对象的成员

类型

  • 输入迭代器（input iterator）
  • 输出迭代器（output iterator）
  • 前向迭代器（forward iterator）
  • 双向迭代器（bidirectional iterator）
  • 随机访问迭代器（random-access iterator）
  • 输入迭代器
    • 通用的四种功能
    • 只能利用迭代器进行输入功能
    • 它只能用于单遍扫描算法
  • 输出迭代器
    • 通用的四种功能
    • 只能利用迭代器进行输出功能
    • 只能用于单遍扫描算法
  • 前向迭代器
    • 通用的四种功能
    • 能利用迭代器进行输入和输出功能
    • 能用于多遍扫描算法
  • 双向迭代器
    • 通用的四种功能
    • 能利用迭代器进行输入和输出功能
    • 能用于多遍扫描算法
    • 前置和后置递减运算（–），意味着它能够双向访问
  • 随机访问迭代器
    • 通用的四种功能
    • 能利用迭代器进行输入和输出功能
    • 前置和后置递减运算（–），意味着它是双向移动的
    • 比较两个迭代器相对位置的关系运算符（<、<=、>、>=）
    • 支持和一个整数值的加减运算（+、+=、-、-=）
    • 两个迭代器上的减法运算符（-），得到两个迭代器的距离
    • 支持下标运算符（iter[n]），访问距离起始迭代器n个距离的迭代器指向的元素
    • 能用于多遍扫描算法。在支持双向移动的基础上，支持前后位置的比较、随机存取、直接移动n个距离
迭代器 功能 读写及支持
输入迭代器 提供对数据的只读访问 只读，支持++、==、!=
输出迭代器 提供对数据的只写访问 只读，支持++
前向迭代器 提供读写操作，能向前推进迭代器 读写，支持++
双向迭代器 提供读写操作，能向前和向后操作 读写，支持++、–
随机访问迭代器 提供读写操作，能以跳跃的方式访问容器任意数据，是功能最强的迭代器 读写，支持++、–、[n]、-n、<、<=、>、>=

常用容器的迭代器

  • vector——随机访问迭代器
  • deque——随机访问迭代器
  • list——双向迭代器
  • set/multiset——双向迭代器
  • map/multimap——双向迭代器
  • stack——不支持迭代器
  • queue——不支持迭代器

实例

双向迭代器和随机访问迭代器最为常用，下面演示这两种迭代器用法

  • map
#include <iostream>
#include <map>
using namespace std;

int main(){
    map<int,int> m;
    for(int i=0;i<10;i++){
        m[i]=i*10;
    }
    map<int,int>::iterator iter;
    cout<<"遍历m并打印：";
    for(iter=m.begin();iter!=m.end();++iter){
        cout<<"("<<iter->first<<","<<iter->second<<") ";
    }
    //此时iter=m.end(),这个位置是最后一个元素的下一个位置，没有存储数据
    iter--;
    cout<<"\nm的最后一个元素为：("<<iter->first<<","<<iter->second<<")"<<endl;
    return 0;
}

image

对于迭代器来说，虽然都是加1或者减1，但--不等同于-=1，++不等同于+=1，他们实现的是不同的功能

  • vector
#include<iostream>
#include<vector>
using namespace std;

int main(){
    vector<int> v;
    for(int i=0;i<10;i++){
        v.push_back(i);
    }
    vector<int>::iterator iter;
    cout<<"用!=比较两个迭代器遍历：";
    for(iter=v.begin();iter!=v.end();iter++){//用!=比较两个迭代器
        cout<<*iter<<" ";
    }
    cout<<endl;
    
    cout<<"用<比较两个迭代器遍历： ";
    for(iter=v.begin();iter<v.end();iter++){//用<比较两个迭代器
        cout<<*iter<<" ";
    }
    cout<<endl;

    iter=v.begin();//让迭代器重新指向首个元素的位置
    cout<<"间隔一个输出：";
    while(iter<v.end()){//间隔一个输出
        cout<<*iter<<" ";
        iter+=2;//用+=移动迭代器
    }
    cout<<endl;

    iter=v.begin();
    cout<<"vector[5]=";
    cout<<iter[5]<<endl;//用[]访问
    return 0;
}

image

对于vector容器来说，其迭代器有失效的可能

vector容器有动态扩容的功能，每当容器容量不足时，vector就会进行动态扩容，动态扩容不是在原来空间后追加空间，而是寻找一段新的更大的空间，把原来的元素复制过去

但是这样容器存储元素的位置就改变了，原来的迭代器还是指向原来的位置，因此每次进行动态扩容后原来的迭代器就会失效

辅助函数

STL中有用于操作迭代器的三个函数模板，它们是：

  • advance(iter,n)

    使迭代器iter向前或向后移动n个元素

  • distance(iter1,iter2)

    计算两个迭代器之间的距离，即迭代器iter1经过多少次++操作后和迭代器iter2相等。如果调用时iter1已经指向iter2的后面，则这个函数会陷入死循环

  • iter_swap(iter1,iter2)

    用于交换两个迭代器iter1、iter2指向的值

  • map
#include<iostream>
#include<map>
using namespace std;

int main(){
    map<int,int>m;
    for(int i=0;i<10;i++){
    m[i]=i*10;
    }

    //1.使用advance函数
    map<int,int>::iterator iter1=m.begin();
    advance(iter1,2);//iter1向后移动两个元素，指向key=2的位置
    cout<<"当前iter1指向的元素:("<<iter1->first<<","<<iter1->second<<")"<<endl;

    advance(iter1,-1);//iter1向前移动一个元素，指向key=1的位置
    cout<<"当前iter1指向的元素:("<<iter1->first<<","<<iter1->second<<")"<<endl;

    //2.使用distance函数
    map<int,int>::iterator iter2=m.end();
    iter2--;//iter2指向最后一个元素的位置
    cout<<"iter1和iter2的距离:"<<distance(iter1,iter2)<<endl;

    //3.使用iter_swap函数
    cout<<"交换前打印：";
    for(iter1=m.begin();iter1!=m.end();iter1++){
        cout<<"("<<iter1->first<<","<<iter1->second<<") ";
    }
    cout<<endl;

    iter1=m.begin();//指向第一个元素
    iter2=m.end();
    iter2--;//指向最后一个元素

    //iter_swap(iter1,iter2);//交换第一个元素和最后一个元素
    swap(iter1->second,iter2->second);//交换值部分

    cout<<"交换后打印：";
    for(iter1=m.begin();iter1!=m.end();++iter1){
        cout<<"("<<iter1->first<<","<<iter1->second<<") ";
    }
    cout<<endl;

    return 0;
}

在std::map中，每个元素是一个键值对（std::pair<constKey,Value>）。iter_swap函数会交换两个迭代器所指向的元素的内容。然而，std::map的键（Key）是常量，不能被修改。因此，当你尝试交换两个元素时，iter_swap会试图修改键的值，这会导致编译错误

image

  • list
#include<iostream>
#include<list>
using namespace std;

int main(){
    int a[10]={1,2,3,4,5,6,7,8,9,10};
    list<int>lst(a,a+10);
    list<int>::iterator iter1=lst.begin();

    advance(iter1,2);//it1向后移动两个元素，指向3
    cout<<"当前iter1指向的元素:"<<*iter1<<endl;//输出3
    advance(iter1,-1);//it1向前移动一个元素，指向2
    cout<<"当前iter1指向的元素:"<<*iter1<<endl;//输出2

    list<int>::iterator iter2=lst.end();
    iter2--;//iter2指向最后一个元素的位置，即10的位置
    cout<<"iter1和iter2的距离"<<distance(iter1,iter2)<<endl;//输出8

    cout<<"交换前打印：";
    for(iter1=begin(lst);iter1!=end(lst);iter1++){
        cout<<*iter1<<" ";
    }
    iter1=begin(lst);
    iter_swap(iter1,iter2);//交换1和10
    cout<<"\n交换后打印：";
    for(iter1=begin(lst);iter1!=end(lst);iter1++){
        cout<<*iter1<<" ";
    }
    cout<<endl;

    return 0;
}

image

红黑树

 评论
评论插件加载失败
正在加载评论插件
  1. LeetCode知识补充
    1. 时间复杂度
    2. 内存管理
      1. 计算程序占用多大内存
      2. 内存对齐
    3. vector
      1. vector<vector<int>> result
      2. 区别普通数组、std::array、vector
    4. >><<
    5. delete
      1. ※delete后的指针tmp的变化
    6. unordered_set
    7. 范围for循环
    8. iterator
      1. begin()&end()
      2. 迭代器
        1. 通用功能
        2. 类型
        3. 常用容器的迭代器
        4. 实例
        5. 辅助函数
  2. 红黑树
  1. LeetCode知识补充
    1. 时间复杂度
    2. 内存管理
      1. 计算程序占用多大内存
      2. 内存对齐
    3. vector
      1. vector<vector<int>> result
      2. 区别普通数组、std::array、vector
    4. >><<
    5. delete
      1. ※delete后的指针tmp的变化
    6. unordered_set
    7. 范围for循环
    8. iterator
      1. begin()&end()
      2. 迭代器
        1. 通用功能
        2. 类型
        3. 常用容器的迭代器
        4. 实例
        5. 辅助函数
  2. 红黑树