题目地址：[链接]题目描述： {代码...} 解答：这一题如果用两个for循环是可以做出来的，但是复杂度过大。面试的时候一定是让用更快的方法解这个题，那么该怎么办？ 只要归并的时候从大到小归并即可，每次都选择两个数组结尾处最大的元素插入新数组，这样一遍扫描即可完成。 java ac代码： {代码...}

题目地址：[链接]题目描述：给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（Int） 和其邻居的列表（list[Node]）。

解答：这一题，看上去，根本不可能做出来！为什么呢？因为这里的路径和很特别，它可以是从任意点到任意点的路径，搜索我都搜索不出来，按照定义路径可以是从一个叶子到另一个叶子，比如这样：

方法二，自顶向下搜索(深度优先搜索)，搜索过程中维护一个当前累加值，一旦搜索到叶子节点，就将现在的当前累加值加入结果中。这样可以每个节点只访问一遍，并且没有额外空间消耗。java ac代码：

解答：利用二叉搜索树的中序遍历是有序的特性。可以中序遍历的时候用一个数组去存，然后取出数组的第k个数。不过这样似乎有些浪费空间。因此优化的方法是，可以在中序遍历的时候记录每次遍历到第几个节点。如果该节点正是第k个节点，那么记录。并且停止之后所有的遍历。

解答：这一题比较有技巧，如果求任意一点到任意一点的距离，那么会时间复杂度会很大。比较高效的做法是，每次把叶子节点从图(把树转换为图结构)删掉。直到只剩下1个或者2个点的时候输出。

题目地址：[链接]题目描述：现在你总共有 n 门课需要选，记为 0 到 n-1。 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1] 给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？ 示例 1: 输入: 2, [[1,0]] 输出: true解释: 总共有 2 ...

题目地址：[链接]题目描述：给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

题目地址：[链接]题目描述：你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

题目地址：[链接]题目描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

解答：和第55题一样，首先试一下动态规划dp[i]代表到坐标为i的节点所用的最短步骤。那么dp[0] = 0，dp[i] = min(dp[i-k]+1) , k >= 0 并且 k <= i-1,并且nums[k]+k >= i。不过可惜的是复杂度过大，为O(N²)，用例不通过。

题目地址：[链接]题目描述：给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例 1: 输入: [2,3,1,1,4]输出: true解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。示例 2: 输入: [3,2,1,0,4]输出: false解释: ...

题目地址：[链接]题目描述：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2: 输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3: 输入: "pwwkew"输出: 3解释: 因...

题目地址：[链接]题目描述：给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。 示例 1: 输入: "abc"输出: 3解释: 三个回文子串: "a", "b", "c".示例 2: 输入: "aaa"输出: 6说明: 6个回文子串: "a", "a", "a", "aa", "...

解答：层次遍历二叉树我们都会，就是用一个队列，每一次都先取出一层，然后把这一层的子节点(也就是下一层)在放入队列中，能够获得每一层是因为每次取出一层都要先把这层的几点数量读出来，然后才能取出这一层所有元素。这一题也一样，只不过这一题是从右到左层次遍历，并且每次把该层第一个元素的值放入结果集中。

题目地址：[链接]题目描述：在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚...

题目地址：[链接]题目描述：给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 说明: 叶子节点是指没有子节点的节点。 示例:给定如下二叉树，以及目标和 sum = 22， {代码...} 返回: [ [5,4,11,2], [5,8,4,5]] 解答：递归。求以root为根并且和为sum的路径等于。1root为空，那么为...

什么是回溯算法？回溯法是一种系统搜索问题解空间的方法。为了实现回溯，需要给问题定义一个解空间。说到底它是一种搜索算法。只是这里的搜索是在一个叫做解空间的地方搜索。而往往所谓的dfs，bfs都是在图或者树这种数据结构上的搜索。根据定义来看，要实现回溯，需要两点1搜索，2解空间先看什么是解空间。就是形如数组...

push(x) -- 将元素 x 推入栈中。pop() -- 删除栈顶的元素。top() -- 获取栈顶元素。getMin() -- 检索栈中的最小元素。示例:

题目地址：[链接]题目描述：运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

题目地址：[链接]题目描述：在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在104个气球。

输入: [[1,3],[2,6],[8,10],[15,18]]输出: [[1,6],[8,10],[15,18]]解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].示例 2:

输入: nums = [1,2,3]输出:[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], []]解答：这一题用回溯法。对于长度为n的nums数组，它的解空间应该是这样的[x1,x2,x3...,xn]这里的xn=0或者1，代表第n个数放或者不放入子集。java ac代码：

题目地址：[链接]题目描述：给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下： "123""132""213""231""312""321"给定 n 和 k，返回第 k 个排列。 说明： 给定 n 的范围是 [1, 9]。给定 k 的范围是[1, n!]。示例 1: 输入: n = 3, k = 3输出: "213"...

输入: [1,1,2]输出:[ [1,1,2], [1,2,1], [2,1,1]]解答：这一题可以利用求下一个排列算法来求解，对原数组排序，然后加入一个结果，接着不断求下一个排列，直到没有下一个排列为止。而下一个排列的求解,可以参考下一个排列

题目地址：[链接] 题目描述：实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。 必须原地修改，只允许使用额外常数空间。 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。1,2,3 → 1,3,23,2,1 ...

输入: 2输出: 91 解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。即这个数最多n位。

网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

题目地址：[链接]题目描述：字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。

题目地址：[链接]题目描述：写一个 RecentCounter 类来计算最近的请求。 它只有一个方法：ping(int t)，其中 t 代表以毫秒为单位的某个时间。 返回从 3000 毫秒前到现在的 ping 数。 任何处于 [t - 3000, t] 时间范围之内的 ping 都将会被计算在内，包括当前（指 t 时刻）的 ping。 保证每次对 ping 的调用都使用比之前...