描述 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，并且调用 min函数、push函数 及 pop函数 的时间复杂度都是 O(1)push(value):将value压入栈中pop():弹出栈顶元素top():获取栈顶元素min():获取栈中最小元素 算法 用一个栈 st 存储所有进出的数据，用一个单调递减栈 dec 存储数据的大小。对于存储数据的栈 st 的 push 和 pop 操作都是直接把数据压入栈顶和从栈顶弹出，对于 dec 栈的 push，因为它是一个单调递减栈，所以只有当目标元素小于栈顶元素时才将它压入，而当要弹出的元素同时在 st 和 dec 的栈...

描述 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。 算法 我们的目标是按照图中的数字大小顺序访问每个位置的值，然后按顺序保存每个点。 方法一 我们定义一个从 (0, 0) 出发的点，当遇到边界或者访问过的点之后就向右转，已经访问过的点就把它的值赋为一个不可能的值 inf。如下图，我们访问到边界情况时就向右转如下图，当我们访问到 12 的下一个点的时候就向右转代码实现如下（python版代码注释参照c++版）： // c++ class Solution { public: const int inf = 0x3f3f3f3f; // 访问过的值标记为 inf ...

描述 操作给定的二叉树，将其变换为原二叉树的镜像。 算法思路 这道题采用的是自顶向下的递归蓝色子树是已经完成交换的子树，绿色子树是即将进行交换的左子树，绿色子树右边的橙色子树是将要和绿色子树交换的子树 对于当前的 root 交换左右子树 交换之后如下 对于每个子树的左右子树重复上面第一步的操作，相邻的绿色和橙色子树是将要交换的两个子树 交换相邻的绿色和橙色子树结果如下 代码实现 代码注释详见 c++ 版递归实现// c++ class Solution { public: // 返回镜像后的树 TreeNode* Mirror(TreeNode* p) { if (!p)...

描述 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） 基本思路 按照树 A 中每个节点的遍历顺序比较当前节点和 B 的根节点是否相同，如果相同就按照 B 的结构遍历他们的每个节点。例子是题目所给的样例： A : {8,8,#,9,#,2,#,5} B : {8,9,#,2} 1.两个节点都是 8 ，根节点相同，开始遍历其他节点。2. 第二个节点不相同函数结束3. 继续比较 A 中节点和 B 的根节点，再次发现相同4. 按照 B 的顺序遍历所有节点发现 B 是 A 的子树 复杂度分析 在最坏情况下， 把 A 遍历了一遍，并且对于每个根节点都把 B...

描述 输入一个链表，反转链表后，输出新链表的表头。 方法一 因为链表结尾是 null，所以让 pre 的值是 null, p 就表示我们的头部 因为 p 的 next 成员马上就要指向 pre, 如果不保存 p 的下一个节点就会使其丢失，所以通过临时变量 t 保存它 让 P 的 next 成员指向 pre pre 移动到 p 的位置，p 移动到 t 的位置，此时我们就回到了第一步中的情况 保持这个循环不变式直到 p 移动到原链表结尾我们就获得了翻转之后的链表。// c++ class Solution { public: ListNode* ReverseList(ListNode...

描述 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 算法 比较方便的做法是设置一个虚拟节点 fake，而它的 next 指向的地址才是真正的表头，然后开始的时候将它作为 pre 指针。在循环中，每次都将要接入的新节点接到 pre 后面，然后更新 pre，保持这个循环不变式。最后返回 fake 的 next 指向的地址，就是完整的结果。 // c++ class Solution { public: ListNode* Merge(ListNode* p1, ListNode* p2) { ListNode* fake =...

描述 输入一个链表，输出一个链表，该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。如果该链表长度小于k，请返回一个长度为 0 的链表。 数组法 把每个节点装进数组中，访问倒数第 k 个元素。 class Solution { public: ListNode* FindKthToTail(ListNode* pHead, int k) { vector<ListNode*> res; for (; pHead; pHead = pHead->next) res.emplace_back(pHead); ...

描述 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。 算法 题目要求图解：具体的做法就是把每个数加入符合条件的数组，如下图，橙色代表奇数数组，绿色代表偶数数组，最后再合并两个数组。因为我们是按照从左到右的顺序访问每个元素，容易证明奇数元素、偶数元素之间的相对位置是可以保证的，实现的代码如下： // c++ class Solution { public: vector<int> reOrderArray(vector<int>& ar...

描述 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 保证base和exponent不同时为0。不得使用库函数，同时不需要考虑大数问题，也不用考虑小数点后面0的位数。 实际上就是实现一个计算 a ^ b 的函数。 朴素算法 让 exponent 个 base 相乘，时间复杂度是 O(exponent)。 // c++ class Solution { public: double Power(double base, int exponent) { double res = 1; if (...

方法一：检查二进制每一位数字 我们通过右移操作消除第 i 位右边的数字，通过与 1 操作消除第 i 位左边的所有数字，对数字 n 重复32次这种操作就可以求得每一位的数字。当我们要提取从右往左数第3位数字时：c++代码如下： class Solution { public: int NumberOf1(int n) { int res = 0; for (int i = 0; i < 32; i++) res += (n >> i) & 1; return res; ...