1.堆结构是用数组实现的完全二叉树结构2.大根堆：每棵子树的最大值都在顶部（大根堆的根就是整棵树的最大值）3.小根堆：每棵子树的最小值都在顶部（小根堆的根就是整棵树的最小值）4.对任意i位置的节点，左孩子节点位置：2+i+1，右孩子节点位置：2i+2，父节点位置：(i-1)/2================================================================================C++(STL)中的堆结构是通过算法的形式提供的，包括以下几个函数(需要包含头文件algorithm)：make_heap:根据指定的迭代器区间以及一个可选的比较...

二叉树的遍历可以通过递归或不递归 二叉树的创建： 定义节点结构体： struct TreeNode { int val; struct TreeNode * left; struct TreeNode * right; TreeNode(int x) : //这两行是用来初始化的 val(x), left(NULL), right(NULL) { } };创建二叉树： struct TreeNode * CreateBTree() //动态地建了一个二叉树，有返回值，返回根节点的地址 { TreeNode* Head = new TreeNode(1); Head->left = new...

未做改进的快排 步骤：1.把数组的最后一个元素作为划分值2.使用荷兰国旗的partition算法划分为三部分（这个时候只有最后一个元素归位了）3.然后对左侧范围和右侧范围采用递归进行划分分析：划分值越靠近两端，复杂度越高，划分值越靠近中间，复杂度越低最差的时间复杂度为O（N2）注意一下：这里partition的时候，>区的初始位置要设置为最后一个元素，这个元素先不动，在划分结束后再把最后一个元素和大于区的第一个元素交换！！！如果把最后一个元素的后一个当做>区的初始位置的话会报错！！！因为我这里的递归是用的大于区的左边界，如果大于区没有元素的话，那这个边界就是无效元素了，没办法再进行...

荷兰国旗问题一：给定一个数组和一个目标值，请把<=目标值的数放在数组的左边，大于目标值的数放在数组的右边。 注意：<=区的起始点在-1处，它的下一个就是数组第一个元素 class HelanGuoQi1//划分成<=区和大于区 { public: void helanguoqi(vector<int>& v, int target) { int se = -1; int tmp = 0; for (int i = 0; i < v.size(); i++) { if (v[i] <= target) { tmp = v[i]; v[i] = v...

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。 方法1：用集合的方法遍历链表，如果集合中没有这个节点，就放进集合，如果集合中有这个节点，就返回这个节点（该节点就是链表环的入口节点）如果p为NULL了，证明该链表没有环，返回NULL /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { ...

方法1：通过集合的方式先遍历一个链表，并把节点全都放进一个集合（注意是节点，不是节点元素），然后遍历第二个链表，并且在集合中找有没有这个元素，如果有，就返回这个节点（该节点就是两个链表哦的第一个公共节点） /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { unor...

一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head 方法一：用unordered_map，key为原链表的每一个节点，value为对应节点的复制，步骤：1.遍历链表，对于每一个节点，复制一个一样的（只管值相同，先不管指针域）用RandomListNode* temp=new RandomListNode(p->label);进行复制2.再次遍历链表，对于每一个节点的next和random都可以去找map里的节点给我的节点加上去:m[p]->next=m[p->next] /* struct ...

输入两个单调递增的链表，输出两个链表合成后的链表，合成后的链表需要满足单调不减规则 思路：谁小取谁，谁小谁动步骤：1.定义指针：p1,p2用来分别遍历两个链表；定义一个p，一个pHead，一个进行存数，一个用来最终返回2.初始化p：取两个链表头结点中的较小值（别忘了让那个指针后移）3.循环比较两个链表元素，谁小就取谁，谁小就往后移动，直到某一个链表到了尾巴4.p再去加上另一个链表的剩余部分 /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ clas...

归并排序 归并排序的时间复杂度为O(N*log2N) 思路（递归）：1.左边排好序2.右边排好序3.合并到一起使得整体有序  class MergeSort { public: void myMergeSort(vector<int>& v) { if (v.size() < 2) return; int L = 0; int R = v.size()-1; process(v, L,R); } void process(vector<int>& v, int L,int R) { if (L == R) return; else { int M ...

输入一个链表，反转链表后，输出新链表的表头。 思路：定义一个pre,p,post，分别存p节点的前、当前、后的地址  /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solut...

输出链表中倒数第k个结点 思路：尺子思想，定义两个指针，先让p2走到正数第k个位置，然后p1和p2一起往前走，当p2指向最后一个节点的时候，p1就指向了倒数第k个节点注意！！！一定要考虑特殊情况，比如链表为空，k<=0的情况；比如k大于了链表的长度的情况（如果p2走到了最后）！！！  /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* FindKthToTail(ListNo...

输入一个链表，按链表从尾到头的顺序返回一个ArrayList 思路：这里要返回的是一个数组，所以可以直接先把链表里的元素取出来放进一个数组，然后再把这个数组进行逆转（不能用reverse）可以定义一个i=0，一个j=size-1；然后头尾进行交换，知道i=j或者i>j class Solution { public: vector<int> printListFromTailToHead(ListNode* head) { vector<int> v; ListNode* p; p=head; while(p!=NULL) { v.push_back(p->...

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。 思路：从前往后数空格数，从后往前进行移动（注意不能从前往后移，因为会把后面的覆盖）不能用string的字符串插入insert，因为这个不是C++的容器string  class ...

集合set 无序集合unordered_set(要包含头文件unordered_set) 定义：unordered_set<int>插入：s.insert(key)查找:s.find(key)（返回的是目标元素的迭代器，若没找到返回end()）统计：s.count(key)统计key的个数</int> 有序集合set(要包含头文件set) 注意：默认排序是从小到大，如果要从大到小，需要自己利用仿函数构造（类）比较器，在定义set的时候在尖括号里加上比较器的名称如果是自定义数据类型，则必须加比较器，否则编译器不知道如何进行排序[定义比较器时]一定要加两个const cla...