一、题目描述 NC3链表中环的入口结点题目描述：给定一条链表，若链表存在环，就请找到环的入口并返回入口的指针；若不存在环就返回null 二、算法1（哈希集合） 解题思路： 一个直观的想法就是用哈希表存下我们从链表头往下走路径所见过的节点指针，当出现已经记录过的节点时，这个节点就是环的入口节点 代码实现（C++11） class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { unordered_set<ListNode*> st; // 哈希集合 while(pHead){ if(st.count(pH...

一、题目描述 JZ67 剪绳子题目描述：给一根长度为n的绳子，请把绳子剪成整数长度的m段（m、n都是整数，m>1），使得每段长度的乘积最大注意审题：m、n都是整数，剪出的绳子长度也是整数，因此不用考虑浮点数的情况，并且m要求大于1，即只要要剪成两段 二、算法1（动态规划） 解题思路  将绳子分割的最优方案可以从比他短的绳子的最优最优方案中推出来，因此我们可以想到用动态规划来解决本题 将绳子的长度作为状态，定义数组f[x]表示将长度为x的绳子分割成至少两段所能得到的最大乘积，假设已知f[2~x-1]的结果，那么我们可以枚举切出的第一段的长度j，故需考虑两种方案：   将x拆分为j和(x -...

一、题目描述 JZ63 数据流中的中位数题目大意：设计一个类，它有两个方法，Insert(num)可以插入一个数num，GetMedian()返回所有插入的数中的中位数（若一共插入了偶数个，则取中间两个数的平均值；若一共插入了奇数个，则取中间一个即可） 二、算法1（暴力法） 解题思路 用一个数组来存放所有数，每次GetMedian之前都排序一下，再根据数组的大小确定中位数 代码实现（C++11） class Solution { public: vector<int> arr; void Insert(int num) { arr.push_back(num); } double ...

一、题目描述 JZ62 二叉搜索树的第k个结点题目大意：给定一颗二叉搜索树，请找出其中第k小的TreeNode节点注意审题：二叉搜索树，第k小 二、算法1 （中序遍历（递归）） 解题思路  二叉搜索树的一个性质就是它的中序遍历顺序得到的序列是有序的 根据这个性质我们可以想到一个办法就是先将中序遍历序列存下来，最后返回第k的数即可，但是会用到额外的空间，我们可以用一个全局变量记录当前节点是第第几个，在中序遍历的过程中更新即可，当遍历到第k个节点时记录一下结点指针即可  代码实现 （C++11） class Solution { public: TreeNode* ans = nullptr; i...

一、题目描述 JZ25 复杂链表的复制题目大意：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头节点注意审题：我们需要对链表进行深拷贝 二、算法1（哈希表） 解题思路  假如链表没有随机指针, 我们的拷贝方式很简单, 只要先创建一个哨兵节点, 然后遍历一下给定链表, 创建新节点, 并不断和上个节点连接 本题的难点就在于每个节点还有一个指向空或其它节点的指针, 一种比较直观的想法就是先把整条链表连起来, 然后再挨着改变指针, 因此我们可以用哈希表来存放指针的映射关系, 然后根据将随机指针指...

一、题目描述 JZ26 二叉搜索树与双向链表题目大意：输入一棵二叉搜索树, 将该二叉搜索树转换成一个排序的双向链表注意审题：1. 要求不能创建任何新的节点, 只能原地调整树中节点指针的指向(暗示我们不能够采用先存下二叉树的所有值再重新创建链表) 2. 转化完成后树中节点的左指针要指向比它小的上一个结点, 右指针要指向比它大的下一个节点 3. 头尾指针不用连接起来, 即返回的不是双向循环链表 4. 返回链表中第一个节点的指针 二、算法（二叉树的中序遍历） 解题思路  读完题目之后我们就能知道, 这道题只能使用原地算法, 而又要使链表从小到大排序, 首先一种思路是想办法将二叉树连接成一个双向链表,...

一、题目描述 JZ23 二叉搜索树的后序遍历序列题目大意：输入一个序列, 判断它是不是某二叉搜索树的后序遍历结果注意审题：假设输入序列的任意两个数字都互不相同且空树不是二叉搜索树 二、算法1（分治） 解题思路  二叉树的后序遍历顺序是：左子树 -> 右子树 -> 根节点 因此序列的最后一个数代表了根节点 因此我们可以将一个序列划分为3段, 左子树+右子树+根, 例如[4, 8, 6, 12, 16, 14, 10]可以根据根节点的值将其划分为左子树[4, 8, 6], 右子树[12, 16, 14], 根[10], 由于我们是先确定的右子树区间, 因此当左子树区间中出现大于根节点的...

一、题目描述 JZ27 字符串的排列题目大意：输入一个字符串, 按字典序打印出该字符串中字符的所有排列注意审题：可能有重复字符并且需要按照字典序打印出该字符串的所有排列 二、算法1（回溯） 解题思路  本题是一个经典的全排列的问题, 可以使用回溯算法来解决. 不过与一般的全排列问题不同的地方是它可能有重复字符, 那么按照一般的递归法可能会有多种重复的情况, 例如"aa" 就得到"aa"和"aa"这两种情况 一种解决的方法就是使用哈希集合来去重, 将所有可能的结果都存放下来, 最后对结果进行排序    代码实现（C++11） class...

一、题目描述 JZ24 二叉树中和为某一值的路径题目大意：输入一颗二叉树的根节点和一个整数, 按字典序打印出二叉树中节点值的和为输入整数的所有路径. 路径定义为从数的根节点开始往下一直到叶节点形成一条路径.注意审题：1. 按字典序打印出所有路径 2. 路径一定是从根结点到某个叶子节点的路径 二、算法（深度优先搜索） 解题思路  要求从根到叶子节点的路径, 我们可以想到深度优先搜索, 它可以依次遍历所有的路径, 我们只要在递归时同时维护路径和即可 实现技巧：首先, 为了使递归函数更简洁, 我们可以将用于临时保存路径的数组和结果数组定义为成员; 检查是否满足条件时, 我们不必维护路径和, 而是用目...

一、题目描述 JZ30 连续子数组的最大和题目大意：输入一个整型数组,数组里有正数也有负数.数组中的一个或连续多个整数组成一个子数组.求所有子数组的和的最大值.要求时间复杂度为 O(n).注意审题：要求时间复杂度为O(n) 二、算法1（前缀和） 解题思路  连续子数组问题可以联想到区间, 连续子数组的和就是区间和, 区间和就顺其自然地想到的前缀和这个知识点 前缀和的核心是前缀和数组sum, 其中sum[i]表示array[0...i]的和, 显然, 要求区间array[j...i]的和, 实际上就是 sum[i] - sum[j - 1], 用到了集合运算的思想 要求连续子数组的最大和, 我们...

一、题目描述 JZ28 数组中出现次数超过一半的数字题目大意：数组中有一个数字出现的次数超过数组长度的一半, 找出这个数字注意审题：假设数组是非空的, 故给定的数组中有且只有一个满足条件的数 二、算法1（排序） 解题思路  我们知道, 对一个数组进行排序之后, 则相同的元素一定是连续的, 因此, 我们可以先对数组从小到大排序, 然后遍历一次排序后的数组, 记录当前数出现的频率, 若出现次数超过数组长度的一半, 则直接返回 实现细节：由于数组的长度可能是奇数, 因此我们判断时可以把除法转换成乘法  代码实现（C++11） class Solution { public: int MoreThan...

一、题目描述 JZ29 最小的K个数题目大意：给定一个数组, 找出其中最小的k个数注意审题：若k大于数组的长度, 就返回空数组 二、算法1（排序） 解题思路  说到求最小(或最大)的k个数这一类问题, 我们一般是想法就是先对数组进行排序,然后取边缘连续的k个数即可 要求最小的k个数, 我们可以将数组从小到大排序, 然后取前k个数为答案即可  代码实现 (C++11) class Solution { public: vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { vector<int...

一、题目描述 JZ22 从上往下打印二叉树题目大意：从上往下打印出二叉树的每个节点, 同层节点从左至右打印 二、算法（二叉树的层序遍历） 解题思路  本题是一道经典的二叉树层序遍历题, 考察了BFS搜索算法 算法步骤：首先创建一个存放二叉树节点指针的队列, 并将根节点入队(若根为空, 直接返回空序列), 由于每层从左至右打印, 故对于每次取出的指针, 我们首先考虑它的左儿子是否存在, 再考虑它的右儿子是否存在, 这样可以保证出队序列满足题意    代码实现 (C++11) /* struct TreeNode { int val; struct TreeNode *left; struct T...

一、题目描述 JZ21 栈的压入、弹出序列题目大意：给出两个序列, 一个是元素入栈的序列, 一个是元素出栈的序列, 判断按照第一个序列入栈是否可以得到给定的第二个出栈序列注意审题：这两个序列的长度是相等的, 因此不用考虑长度不相等的情况, 并且题目假设压入的所有数字都不同 二、算法（栈模拟、双指针） 解题思路  首先栈的弹出序列是指在插入元素的途中我们可以弹出若干元素, 直到栈空为止, 因此一个压入序列可以对应多个弹出序列 根据题意, 我们可以用栈来模拟整个过程, 同时用两个指针i, j分别指向两个序列的头部, 每次我们先将i所指向的元素压入栈中, 然后i向后移动一步, 之后再检查当前栈顶, ...