Jackie's Blog
LeetCode知识补充
Jackie
  2025-01-24   2025-08-05  8k 字  33 分钟

LeetCode知识补充

对还不清楚的知识作补充，每个点中自己熟悉的部分已略过（有的part为了知识完整性即使已知也会补充）

  • 部分参考资料

Hello算法

王道数据结构

代码随想录

时间复杂度

前言

  • 稳定：如果a原本在b前面，且a=b，排序之后a仍然在b的前面
  • 不稳定：如果a原本在b的前面，且a=b，排序之后a可能会出现在b的后面

image

村里有两只做事很稳的动物：插帽龟和统计鸡。插帽龟喜欢去插人家堆起来的帽子，统计鸡喜欢做加减乘除。但有天插帽龟挑选帽子插的时候，恩姓长老看见就慌了，恩老大喊：“快点归还给堆”

image

O(1)常数阶<O(log2n)对数阶<O(n)线性阶<O(nlog2n)线性对数阶<O(n2)平方阶<O(n3)立方阶<O(2n)指数阶<O(n!)阶乘阶<O(nn)

常对幂指阶

  • 顺序执行的代码只会影响常数项，可以忽略
  • 只需挑循环中的一个基本操作分析它的执行次数与n的关系即可
  • 如果有多层嵌套循环，只需关注最深层循环循环了几次

练习

  1. 计算该算法的时间复杂度T(n)
void loveYou(int n){//n为问题规模
    int i=1;
    while(i<=n){
        i=i*2;//每次翻倍
        printf("I Love You %d\n",i);
    }
    printf("I Love You More Than %d\n",n);
}

设最深层循环的语句频度（总共循环的次数）为x，则由循环条件可知，循环结束时刚好满足2x>n

x=log2n+1

T(n)=O(x)=O(log2n)

  1. 计算该算法的时间复杂度T(n)
void loveYou(int flag[], int n){//n为问题规模
    printf("I Am Iron Man\n");
    for(int i=0; i<n; i++){//从第一个元素开始查找
        if(flag[i]==n){//找到元素n
            printf("I Love You %d\n",n);
            break;//找到后立即跳出循环
        }
    }
}
//flag数组中乱序存放了1~n这些数
int flag[n]={1...n};
loveyou(flag,n);

最好情况：元素n在第一个位置——最好时间复杂度T(n)=O(1)

最坏情况：元素n在最后一个位置——最坏时间复杂度T(n)=O(n)

平均情况：假设元素n在任意一个位置的概率相同为1n\frac{1}{n}——平均时间复杂度T(n)=O(n)

循环次数x=(1+2+3+...+n)1n=n(1+n)2⋅1n=1+n2x=(1+2+3+...+n)\frac{1}{n}=\frac{n(1+n)}{2}\cdot\frac{1}{n}=\frac{1+n}{2}

内存管理

以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

红黑树

常见的三种哈希结构

  • 定义

满足如下红黑性质的二叉排序树：

  1. 每个结点或是红色，或是黑色的
  2. 根节点是黑色的
  3. 叶结点（虚构的外部结点、NULL结点、失败结点）都是黑色的
  4. 不存在两个相邻的红结点 （红结点的父节点和孩子结点都是黑色的）
  5. 对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同

左根右，根叶黑，不红红，黑路同

结点的黑高bh：从某结点出发（不含该结点）到达任一空叶结点的路径上黑结点总数

  • 性质
    • 从根节点到叶结点的最长路径不大于最短路径的2倍
    • 有n个内部节点的红黑树高度h≤2log2(n+1)
    • 新插入红黑树中的结点初始着色为红色

红黑树查找操作时间复杂度=O(log2n)

  • 红黑树的插入

image

详见BV1b7411N798——7.3.3_2_红黑树的插入

  • 红黑树的插入示例

image

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

continue

反转字符串II

continue是一条流程控制语句，用于提前结束当前循环迭代的剩余语句，并直接进入下一次循环的条件判断

  • continue不会跳出整个循环，只是跳过当前这次迭代

KMP算法

找出字符串中第一个匹配项的下标

最长公共前后缀

字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串

前缀表要求的就是相同前后缀的长度

以文本串：aabaabaafa和模式串：aabaaf举例

匹配过程在下标5的地方遇到不匹配，模式串是指向f

image

然后就找到了下标2，指向b，继续匹配

image

下标5之前这部分的字符串（aabaa）的最长相等的前缀和后缀字符串是子字符串aa，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么找到与其相同的前缀的后面重新匹配就可以了

前缀表

记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀，next数组就是一个前缀表（prefix table）

前缀表用来回退的，它记录了模式串与主串（文本串）不匹配的时候，模式串应该从哪里开始重新匹配，使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配

  • 求得的最长相同前后缀的长度就是对应前缀表的元素

image

可以看出模式串与前缀表对应位置的数字表示的就是：下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀

  • 利用前缀表找到当字符不匹配的时候应该指针应该移动的位置

image

当字符不匹配的时候看它的前一个字符的前缀表的数值是多少

为什么要前一个字符的前缀表的数值？

要找前面字符串的最长相同的前缀和后缀

next数组

以前缀表统一减一之后的next数组来做演示

image

  • 时间复杂度

n为文本串长度，m为模式串长度，匹配的过程中要根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)，之前还要单独生成next数组，时间复杂度是O(m)。所以整个KMP算法的时间复杂度是O(n+m)

暴力解法时间复杂度O(nm)，KMP在字符串匹配中极大地提高了搜索的效率

构造next数组

void getNext(int* next, const string& s)
  1. 初始化
  2. 处理前后缀不相同的情况
  3. 处理前后缀相同的情况
  1. 初始化

定义两个指针i和j，j指向前缀末尾位置，i指向后缀末尾位置，对next数组进行初始化赋值

int j=-1;
next[0]=j;

next[i]表示i（包括i）之前最长相等的前后缀长度（其实就是j），所以初始化next[0]=j

  1. 处理前后缀不相同的情况

j初始化为-1，那么i就从1开始，进行s[i]与s[j+1]的比较，所以遍历模式串s的循环下标i要从1开始

for(int i=1;i<s.size();i++){

如果s[i]与s[j+1]不相同，也就是遇到前后缀末尾不相同的情况，就要向前回退

next[j]就是记录着j（包括j）之前的子串的相同前后缀的长度

那么s[i]与s[j+1]不相同，就要找j+1前一个元素在next数组里的值（就是next[j]）

while(j>=0&&s[i]!=s[j+1]){//前后缀不相同
	j=next[j];//向前回退
}
  1. 处理前后缀相同的情况

如果s[i]与s[j+1]相同，说明找到了相同的前后缀，那么就同时向后移动i和j，同时还要将j（前缀的长度）赋给next[i]，因为next[i]要记录相同前后缀的长度

if(s[i]==s[j+1]){//找到相同的前后缀
	j++;
}
next[i]=j;
  • 完整代码
void getNext(int* next,const string& s){
    int j=-1;
    next[0]=j;
    for(int i=1;i<s.size();i++){//i从1开始
        while(j>=0&&s[i]!=s[j+1]){//前后缀不相同
            j=next[j];//向前回退
        }
        if(s[i]==s[j+1]){//找到相同的前后缀
            j++;
        }
        next[i]=j;//将j（前缀的长度）赋给next[i]
    }
}

image

使用next数组来做匹配

定义两个下标，j指向模式串起始位置，i指向文本串起始位置

j初始值为-1，i从0开始遍历文本串

for(int i=0;i<s.size();i++)

如果s[i]与t[j+1]不相同，j就要从next数组里寻找下一个匹配的位置

while(j>=0&&s[i]!=t[j+1]){
	j=next[j];
}

如果s[i]与t[j+1]相同，那么i和j同时向后移动

if(s[i]==t[j+1]){
	j++;//i的增加在for循环里
}

如果j指向模式串t的末尾，说明模式串t完全匹配文本串s里的某个子串

在文本串字符串中找出模式串出现的第一个位置（从0开始），所以返回当前在文本串匹配模式串的位置i减去模式串的长度，就是文本串字符串中出现模式串的第一个位置

if(j==(t.size()-1)){
    return(i-t.size()+1);
}
  • 完整代码
int j=-1;//next数组里记录的起始位置为-1
for(int i=0;i<s.size();i++){//i从0开始
    while(j>=0&&s[i]!=t[j+1]){//不匹配
        j=next[j];//j寻找之前匹配的位置
    }
    if(s[i]==t[j+1]){//匹配，j和i同时向后移动
        j++;//i的增加在for循环里
    }
    if(j==(t.size()-1)){//文本串s里出现了模式串t
        return(i-t.size()+1);
    }
}

前缀表减一C++代码实现

class Solution {
public:
    void getNext(int* next,const string& s){
        int j=-1;
        next[0]=j;
        for(int i=1;i<s.size();i++){//注意i从1开始
            while(j>=0&&s[i]!=s[j+1]){//前后缀不相同了
                j=next[j];//向前回退
            }
            if(s[i]==s[j+1]){//找到相同的前后缀
                j++;
            }
            next[i]=j;//将j（前缀的长度）赋给next[i]
        }
    }
    int strStr(string haystack, string needle) {
        if(needle.size()==0){
            return 0;
        }
        vector<int> next(needle.size());
        getNext(&next[0],needle);
        int j=-1;//因为next数组里记录的起始位置为-1
        for(int i=0;i<haystack.size();i++){//注意i就从0开始
            while(j>=0&&haystack[i]!=needle[j+1]){//不匹配
                j=next[j];//j寻找之前匹配的位置
            }
            if(haystack[i]==needle[j+1]){//匹配，j和i同时向后移动
                j++;//i的增加在for循环里
            }
            if(j==(needle.size()-1)){//文本串s里出现了模式串t
                return(i-needle.size()+1);
            }
        }
        return -1;
    }
};
  • 时间复杂度：O(n+m)
  • 空间复杂度：O(m)

前缀表减一C++代码实现详见《代码随想录》

堆

滑动窗口最大值

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值

父亲结点大于等于左右孩子（满足条件1）就是大顶堆，小于等于左右孩子（满足条件2）就是小顶堆

n个关键字序列L[1…n]满足：

  1. L(i)≥L(2i)且L(i)≥L(2i+1)或

  2. L(i)≤L(2i)且L(i)≤L(2i+1)

(1≤i≤⌊n2⌋)(1\le i\le\left\lfloor\frac{n}{2}\right\rfloor)

  • 二叉树中第i个节点的左孩子：2i
  • 二叉树中第i个节点的右孩子：2i+1
  • 二叉树中第i个节点的父节点：

⌊n2⌋\left\lfloor\frac{n}{2}\right\rfloor

  • i所在层次：

⌈log2(n+1)⌉\left \lceil log_2 (n+1) \right \rceil

或

⌊log2n⌋+1\left\lfloor log_2n\right\rfloor+1

  • 若完全二叉树有n个节点，

    • i是否有左孩子？2i≤n？

    • i是否有右孩子？2i+1≤n？

    • i是否是叶子节点？

      i>⌊n2⌋?i>\left\lfloor\frac{n}{2}\right\rfloor?

    • i是否是分支节点？

      i≤⌊n2⌋?i\le\left\lfloor\frac{n}{2}\right\rfloor?

构造初始堆

从后往前检查所有分支结点看是否满足堆的要求，若不满足则对以该分支结点为根的子树进行调整。n个节点的完全二叉树，最后一个结点是第

⌊n2⌋\left\lfloor\frac{n}{2}\right\rfloor

个结点的孩子。对以第

⌊n2⌋\left\lfloor\frac{n}{2}\right\rfloor

个结点为根的子树筛选（对于大根堆，若根结点的关键字小于左右孩子中关键字较大者，则交换），使该子树成为堆。之后向前依次对以各结点

⌊n2⌋−1∼1\left\lfloor\frac{n}{2}\right\rfloor-1\sim1

为根的子树进行筛选，看该结点值是否大于其左右子结点的值，若不大于，则将左右子结点中的较大值与之交换，交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止。反复利用上述调整堆的方法建堆，直到根结点

//建立大根堆
void BuildMaxHeap(int A[],int len){
    for(int i=len/2;i>0;i--){//从后往前调整所有非终端结点
        HeadAdjust(A,i,len);
    }
}

//将以k为根的子树调整为大根堆
void HeadAdjust(int A[],int k,int len){
    A[0]=A[k];//A[0]暂存子树的根结点
    for(int i=2*k;i<=len;i*=2){//沿key较大的子结点向下筛选
        if(i<len&&A[i]<A[i+1]){
            i++;//取key较大的子结点的下标
        }
        if(A[0]>=A[i]){
            break;//筛选结束
        }else{
            A[k]=A[i];//将A[i]调整到双亲结点上
            k=i;//修改k值，以便继续向下筛选
        }
    }
    A[k]=A[0];//被筛选结点的值放入最终位置
}

堆排序思想

堆排序的思路很简单：首先将存放在L[1…n]中的n个元素建成初始堆，因为堆本身的特点（以大顶堆为例），所以堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。如此重复，直到堆中仅剩一个元素为止

前 K 个高频元素

前 K 个高频元素中提到的优先队列也是利用了堆排序的思想

void HeapSort(ElemType A[],int len){
    BuildMaxHeap(A,len);//初始建堆
    for(int i=len;i>1;i--){//n-1趟的交换和建堆过程
        Swap(A[i],A[1]);//输出堆顶元素（和堆底元素交换）
        HeadAdjust(A,1,i-1);//调整，把剩余的i-1个元素整理成堆
    }
}
 评论
评论插件加载失败
正在加载评论插件
  1. LeetCode知识补充
    1. 时间复杂度
      1. 练习
    2. 内存管理
      1. 计算程序占用多大内存
      2. 内存对齐
    3. vector
      1. vector<vector<int>> result
      2. 区别普通数组、std::array、vector
    4. >><<
    5. delete
      1. ※delete后的指针tmp的变化
    6. 红黑树
    7. unordered_set
    8. 范围for循环
    9. iterator
      1. begin()&end()
      2. 迭代器
        1. 通用功能
        2. 类型
        3. 常用容器的迭代器
        4. 实例
        5. 辅助函数
    10. continue
    11. KMP算法
      1. 最长公共前后缀
      2. 前缀表
      3. next数组
        1. 构造next数组
        2. 使用next数组来做匹配
        3. 前缀表减一C++代码实现
    12. 堆
      1. 构造初始堆
      2. 堆排序思想
  1. LeetCode知识补充
    1. 时间复杂度
      1. 练习
    2. 内存管理
      1. 计算程序占用多大内存
      2. 内存对齐
    3. vector
      1. vector<vector<int>> result
      2. 区别普通数组、std::array、vector
    4. >><<
    5. delete
      1. ※delete后的指针tmp的变化
    6. 红黑树
    7. unordered_set
    8. 范围for循环
    9. iterator
      1. begin()&end()
      2. 迭代器
        1. 通用功能
        2. 类型
        3. 常用容器的迭代器
        4. 实例
        5. 辅助函数
    10. continue
    11. KMP算法
      1. 最长公共前后缀
      2. 前缀表
      3. next数组
        1. 构造next数组
        2. 使用next数组来做匹配
        3. 前缀表减一C++代码实现
    12. 堆
      1. 构造初始堆
      2. 堆排序思想