一.知识点总结 1.sort函数：用于C++中，对给定区间所有元素进行排序，默认为升序，也可进行降序排序。 sort函数的介绍：sort函数用于C++中，对给定区间所有元素进行排序，默认为升序， 也可进行降序排序。sort函数进行排序的时间复杂度为n*log2n，比冒泡之类的排序算法效率要高 对于vector使用sort排序： sort(vec.begin(),vec.end()); //可以实现对vector从小到大的排序 sort(vec.begin(),vec.end(),greater<int>()); //可以实现对vector从大到小的排序 对于vector<...

一.知识点总结 1.单调栈：是一个栈，不过栈内元素保证单调性。即，栈内元素要么从小到大，要么从大到小。 而单调栈维护的就是一个数前(后)第一个大于(小于)他的数。 单调栈的伪代码： while(栈顶元素比入栈元素小且栈不空){ 栈顶元素弹出 } 元素入栈 首先要知道单调栈入栈的的是下标。对于入栈元素直接入栈会破坏单调性，所以需要栈顶元素出栈，后加入当前元素，使得我们当前的元素再加进去不会破坏它的单调性。 2.利用栈解决表达式求值的问题：我们要知道利用栈的先进后出的性质可以用来实现对于表达式求值，这也是栈的一个比较常见使用方式。 对于表达式求值需要引入三个有关表达式的基本概念：...

一.知识点总结 1.先简单的介绍两个数据结构： (1)栈：栈的主要特点就是先进后出，只在栈顶进行入栈和出栈操作 (2)队列：队列主要特点是先进先出，队列可以分为一般队列和双端队列，一般队列可以实现对队列的队头 访问、队头出队和队尾插入；双端队列可以实现对队头队尾元素的访问、插入和删除。 利用c++的STL来实现队列和栈： stack <type> name ; //栈的实现 type top() ; //栈顶元素访问 void pop() ; //出栈操作 void push(X) ; ///元素x入栈操作 queue <type> name ; //一般队列的实现 ...

一.题意整理 请实现两个函数，分别用来序列化和反序列化二叉树。 1.二叉树的序列化是指： 把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点，以某个符号表示一个结点值的结束。 2.二叉树的反序列化是指： 根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。 二.思路整理 序列化： 按照层次遍历将每个节点加入字符串中，当遇到空节点则加入null。 反序列化： 同样按照层次遍历的思想，首先构造头节点，然后再遍历节点的同时...

一.题意整理 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。也就是在层次遍历的基础上实现对整个树进行之字形顺序打印。 二.思路整理 先我们根据题目的描述，能够找到该题的解决模型为二叉树的层次遍历。只不过普通的层次遍历是针对每一层都只是从左到右遍历。这里题目要求奇数层是从左到右遍历，而偶数层则是从右到左遍历的。对于层序遍历我们知道可以利用队列来实现，给出层序遍历的模板： void LevelOrder(BTree *t){ //利用队列来实现 Queue Q; initQueue(Q...

一.题意整合 给定一个长度为n的可能含有重复值的数组arr，找到每一个i位置左边和右边离i位置最近且值比 arri小的位置，若不存在即返回值为-1。 二.思路整理 题目的意思很明了使用单调栈，借助单调性处理问题的思想在于即使排除了不可能的选项，保持策略集合的高度有效性和秩序性。 单调栈：单调栈就是使栈内元素单调递增或者单调递减的栈，单调栈也只能在栈顶操作。 while(栈顶元素比入栈元素小且栈不空){ 栈顶元素弹出 } 元素入栈 首先要知道单调栈入栈的的是下标。对于入栈元素直接入栈会破坏单调性，所以需要栈顶元素出栈，后加入当前元素，使得我们当前的元素再加进去不会破坏它的单调性。 让我...

一.题意整理 给定一个数组num和一个窗口大小size，求每个连续size序列的最大值。 二.思路整理 首先指出利用c++STL中的max_element也可以AC本题，但是很显然时间复杂度比较高。那么我们可以采用滑动窗口算法来解决，滑动窗口算法本质就是对区间进行扩张和放缩，下面给出滑动窗口的框架 int left = 0, right = 0; while (right < s.size()) { while (window needs shrink) {//对于是否需要进行缩小 // 缩小窗口 window.remove(s[left]); ...

一.题意整理 由题意可知本题要求对于每个输入的数据求出当前录入的数据的中位数。 二.思路整理 由于要求求出每一次输入数据的中位数，要知道求中位数首先想到就是排序，将每次数据进行排序，然后根据每一次数据个数求出中位数。当然这个思路是肯定可以的，但是时间复杂度偏高，每次利用sort排序的时间复杂度就已经达到了O(logn)O(logn)O(logn)，进一步我们可以利用堆这种数据结构来实现。我们想到中位数之和排序后数据中中间的一个或者两个数据有关，所以我们可以利用两个堆栈，分别去维护左边的最大值和最小值，进而求出中位数，同时也大大降低了时间复杂度。 建立两个堆左边是大根堆，右边是小根堆 分别返回左...

一.题意整理 给出一个含有加减乘除和括号的表达式的字符串，求出该字符串的值。(运算符合运算法则，先乘除后加减) 二.思路整理 利用栈来求表达式是栈的一种基本运用，下面我们将会介绍如何利用栈来解决表达式求值的问题： 对于算术表达式一般分成三种有：前缀、后缀和中缀 中缀表达式：救是我们常见的算术表达式，就是一眼看上去就能理解的表达式，例如：2*(5+8) 前缀表达式：形如"op A B"即操作数在两个运算数的前面 后缀表达式：形如"A B op"即操作数在两个运算数的后面 下面给出计算表达式的核心思路：对于一个表达式，也就是对于一个中缀表达式我们可以先将表达式转换成后缀表达式，然后对这个后缀表达...

一.题意整理 题目意思很简单就是给出一个组可能重复的数组，找到数组中不去重的K个最小数，然后返回。 二.思路整合 要找到数组中不去重的第k个最小数，首先我们想到的就是先排序，然后返回排序后的k个最小数。我们可以利用c++中的sort函数来实现对数组的排序，下面是对sort函数的一些介绍： sort函数的介绍：sort函数用于C++中，对给定区间所有元素进行排序，默认为升序， 也可进行降序排序。sort函数进行排序的时间复杂度为n*log2n，比冒泡之类的排序算法效率要高 对于vector使用sort排序： sort(vec.begin(),vec.end()); //可以实现对vector从...

一.题意整理 题目意思很简单就是给出一个组可能重复的数组，找到数组中不去重的第K个最大数。 二.思路整合 要找到数组中不去重的第k个最小数，首先我们想到的就是先排序，然后再找出数组中的第k小数。我们可以利用c++中的sort函数来实现对数组的排序，下面是对sort函数的一些介绍： sort函数的介绍：sort函数用于C++中，对给定区间所有元素进行排序，默认为升序， 也可进行降序排序。sort函数进行排序的时间复杂度为n*log2n，比冒泡之类的排序算法效率要高 对于vector使用sort排序： sort(vec.begin(),vec.end()); //可以实现对vector从小到大的...

一.题目描述 NC51合并k个已排序的链表 合并k个已排序的链表并将其作为一个已排序的链表返回。 二.思路整理 我们可以想到一种最朴素的方法：用一个变量ans来维护以及合并的链表，第i次循环把第i个链表和ans合并，答案保存到ans中。 对于合并两个链表我们可以这样操作实现：首先创建一个空的链表头，将两个链表的头结点进行比较，小的那个直接插入空的表头后，同时，指针分别指向链表的的头结点或头结点的下一个节点，当两个链表进行比较的元素都不为空的话，依次从下到大连接，若有一个链表中比较的节点开始为空时，则将另一个链表的剩余节点添加到合并链表的末尾，其实总结的来说就是比较当前两个节点的较小节点未插入新...

一.题意整理 NC45实现二叉树先序，中序和后序遍历 分别按照二叉树先序遍历、中序遍历和后序遍历打印所有的节点。 二.思路整理 以先序遍历来解释，首先我们需要了解什么是二叉树的先序遍历：按照访问根节点-左子树-右子树的方式遍历这棵树，而在访问左子树和右子树的时候我们按照同样的方式遍历，直到遍历整棵树。我们对先序遍历进行进一步分析： /* 若二叉树是空树，则什么都不做；否则： (1)访问根节点 (2)先序遍历左子树 (3)先序遍历右子树 */ void preorder(TreeNode* t){ if(t!=NULL) return ; visit(t);//...

一.题意整理 用两个栈来实现一个队列，分别完成在队列尾部插入整数(push)和在队列头部删除整数(pop)的功能。队列 中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。 二.思路整理 c++STL中的stack可以直接拿过来用，下面介绍一下STL中stack的用法: push(x)将x入栈，时间复杂度为O(1) top()获得栈顶元素，时间复杂度为O(1) pop()用以弹出栈顶元素，时间复杂度为O(1) empty()可以检测stack内是否为空，放回true为空，返回false为非空，时间复杂度为O(1) size()返回stack内元素的个数，时间复杂度为O(1)...