题目描述 假设你有一个数组，其中第 i 个元素是股票在第 i 天的价格。你有一次买入和卖出的机会。（只有买入了股票以后才能卖出）。请你设计一个算法来计算可以获得的最大收益。示例1输入：[1,4,2]返回值：3 题目分析 在只有一次买入和卖出的机会的情况下，选择第 i 天买入，第 j 天卖出，则收益为 prices[j]-prices[i]，需要找到能够获得的收益最大值，如下图，计算出的最大值是3。  解题思路 方法1：暴力法暴力遍历数组从 i 到 j （0<=i<j<n）的收益值（prices[j]-prices[i]），使用max记录出现的最大收益值；想要遍历所有的i和j，...

题目描述 给定一个二叉树和一个值 sum，请找出所有的根节点到叶子节点的节点值之和等于 sum 的路径，例如：给出如下的二叉树，sum=22，返回[[5,4,11,2],[5,8,9]] 题目分析 遍历树的所有路径，统计路径和，若有路径和与指定值相等，则将路径记录下来。题目的示例中有两条路径的和是符合条件的[[5,4,11,2],[5,8,9]]。  解题思路 使用dfs遍历树要点：1.在dfs的过程中，使用List类型的path记录走过的结点值, List类型res记录满足条件的路径path；2.使用sum记录path的结点值和；3.当遍历到叶子结点时，判断当前和满足条件，满足则加入res中...

题目描述 给定一个二叉树，请计算节点值之和最大的路径的节点值之和是多少。这个路径的开始节点和结束节点可以是二叉树中的任意节点。例如：给出以下的二叉树，返回的结果为6示例1输入：{-2,1}返回值：1 题目分析 题目描述的路径可以从任意节点开始到任意节点结束，与之前必须要从根节点到叶子结点的路径不同，如下图，最大和的路径为2 -> 1 -> 3 -> 1。遍历树的结点可以使用dfs，后序遍历。 解题思路 方法：后序遍历树结点，统计可以获得的最大路径和思路过程：1.从叶子结点开始遍历，计算从任意节点开始的路径和值 int cur = node.val;2.对于结点的路径来说，可以...

题目描述 给定一个仅包含数字0-9的二叉树，每一条从根节点到叶子节点的路径都可以用一个数字表示。例如根节点到叶子节点的一条路径是 1→2→3,那么这条路径就用 123 来代替。找出根节点到叶子节点的所有路径表示的数字之和例如：这颗二叉树一共有两条路径，根节点到叶子节点的路径 1→2 用数字 12 代替，根节点到叶子节点的路径 1→3 用数字 13 代替所以答案为 12+13=25示例1输入：{1,0}返回值：10 题目分析 想要获得所有的路径和，首先使用 dfs深度遍历（先序） 来遍历整个树，当遍历到叶子结点时，可说明遍历完一条路径，统计这条路径的结点和，最后将每条路径的和相加即为结果。  解...

题目描述 判断给定的链表中是否有环。如果有环则返回true，否则返回false。你能给出空间复杂度的解法么？输入分为2部分，第一部分为链表，第二部分代表是否有环，然后回组成head头结点传入到函数里面。-1代表无环，其他的数字代表有环，这些参数解释仅仅是为了方便读者自测调试示例1输入：{3,2,0,-4},1返回值：true说明：第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1，即-4->2存在一个链接，组成传入的head为一个带环的链表 ,返回true  题目分析 有环的链表，在遍历时会在环中一直循环，直观地想，可以使用hash法保存出现的结点，在遍历过程时，碰...

题目描述 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。输入描述：输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台将这2个会组装成一个有环或者无环单链表返回值描述：返回链表的环的入口结点即可。而我们后台程序会打印这个节点示例1输入：{1,2},{3,4,5}返回值：3说明：返回环形链表入口节点，我们后台会打印该环形链表入口节点，即3  题目分析 有环的链表，在遍历时会在环中一直循环，想要获得环的入口结点，直观地想，可以使用hash法保存出现的结点，当重复环的遍历过程时，第一次碰到重复的结点即为环入口结点B。 解题思路 方法1：hash法，记录第一次...

题目描述 将给定的单链表L： L_0→L_1→…→L_{n-1}→L_n重新排序为：L_0→L_n →L_1→L_{n-1}→L_2→L_{n-2}→…要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。示例1输入：{1,2,3,4}返回值：{1,4,2,3}说明：给定head链表1->2->3->4, 重新排列为 1->4->2->3,会取head链表里面的值打印输出  题目分析 题目排序的意思可以理解为：将链表的尾部结点插入到链表中的头部结点之间，直到头部结点与尾部结点重合（奇数结点链表）或者之间没有其他结点（偶数结点链表）。将链表分为（...

题目描述 以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。（字符串长度不大于100000，保证字符串仅由'0'~'9'这10种字符组成）示例1输入："1","99"返回值："100"说明：1+99=100  题目分析 根据加法的运算过程可知，需要从字符串的低位开始依次进行加法运算，记录每一位的结果，最后拼接成字符串，如下图。这里主要需要解决两个问题：①用什么保存计算结果②明确最后拼接的结果顺序 解题思路 方法1：从字符串尾部计算结果，依次拼接直接使用StringBuilder来保存计算结果，若是直接使用appe...

题目描述 给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。输入描述：输入一个数n，意义见题面。（2 <= n <= 60）返回值描述：输出答案。示例1输入：8返回值：18 题目分析 当绳子的长度长于2时，可以被剪成若干段，而这些段的长度可以是从1 ~ (绳子的长度-1)，可以使用暴力法，遍历绳子的所有切割方法，求出里面最大的乘积。...

题目描述 地上有一个rows行和cols列的方格。坐标从 [0,0] 到 [rows-1,cols-1]。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于threshold的格子。 例如，当threshold为18时，机器人能够进入方格[35,37]，因为3+5+3+7 = 18。但是，它不能进入方格[35,38]，因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？示例1输入：1,2,3返回值：3 题目分析 对于计算该机器人能够到达多少格子，首先可以采取暴力的遍历方法，遍历所有的格子，计算能够满足条件的格子数...

题目描述 输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).示例1输入：[1,-2,3,10,-4,7,2,-5]返回值：18说明：输入的数组为{1,-2,3,10,—4,7,2,一5}，和最大的子数组为{3,10,一4,7,2}，因此输出为该子数组的和 18。  解题思路 方法1：连续的子数组，即数组中从i下标到j下标（0<=i<=j<数组长度）的数据，想要获得所有的子数组和，可以通过暴力法，两次循环获得，但时间复杂度为O(n^2)，效率不高。 方法2：动态规划，设动态规划列表 dp，dp...

题目描述 给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。如果K>数组的长度，那么返回一个空的数组示例1输入：[4,5,1,6,2,7,3,8],4返回值：[1,2,3,4] 题目分析 这类题目又称TopK问题，在面试中较为常见，表述为给定一个数组，找出其中最大或最小的k个数，直观的做法是，将整个数组排好序后，取数组前k个或最后k个数，但这种方法时间复杂度较高(O(n*log(n)))，在数据量很大的情况不适用。 解题思路 方法1：堆排序，可以维持一个大小为k的大顶堆，若是后面有比大顶堆堆顶数据小的数，则可以放...

题目描述 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。你可以假设数组是非空的，并且给定的数组总是存在多数元素。1<=数组长度<=50000示例1输入：[1,2,3,2,2,2,5,4,2]返回值：2 题目分析 因为数组长度（length）是确定的，可以计算出数组长度的一半(length/2)是多少，直观的想，可以遍历数组，统计数字出现的次数，若是不小于length/2，即目标数字。 解题思路 方法1：使用hashMap，保存数字数值和出现...

题目描述 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。输入描述：输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。示例1输入："ab"返回值：["ab","ba"] 题目分析 这是一个典型的排列问题，形如“给定一组数据，求这些数据所有的排列情况”，在这里一组数据就是字符串的字符。字符串的排列情况就是，每次需要选择一个字符（不能重复选择），按照顺序将选择的字符连接起来，可以用如下的...