题目：那些插队的人描述：你有一个长度为 n 的队伍，从左到右依次为 1~n，有 m 次插队行为，用数组 cutIn 进行表示，cutIn 的元素依次代表想要插队的人的编号，每次插队，这个人都会直接移动到队伍的最前方。你需要返回一个整数，代表这 m 次插队行为之后，有多少个人已经不在原来队伍的位置了。示例1：输入：3,[3, 2, 3]，返回值：2说明：初始队伍为 [1, 2, 3]3 开始插队 [3, 1, 2]2 开始插队 [2, 3, 1]3 开始插队 [3, 2, 1]所以2还在原来的尾置，3和1两个人已经不在原来的位置了。 解法一：思路分析：这道题应该属于一道非常有趣的数学问题，在此说...

题目：单调栈描述：给定一个可能含有重复值的数组arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。位置信息包括：两个数字 L 和 R，如果不存在，则值为 -1，下标从 0 开始。示例1：输入：[3,4,1,5,6,2,7]，返回值：[[-1,2],[0,2],[-1,-1],[2,5],[3,5],[2,-1],[5,-1]] 解法一：思路分析：首先分析题目，题目的意思是通过将一个给定的数组arr，找到每一个数组中的元素，然后将其左边与右边位置最近且小于arr[i]值的位置返回，一个元素包含两个位置信息L为左边的较小值位置，R为右边的较...

题目：牛妹的蛋糕描述：众所周知，牛妹非常喜欢吃蛋糕。第一天牛妹吃掉蛋糕总数三分之一（向下取整）多一个，第二天又将剩下的蛋糕吃掉三分之一（向下取整）多一个，以后每天吃掉前一天剩下的三分之一（向下取整）多一个，到第n天准备吃的时候只剩下一个蛋糕。牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？示例1：输入：2，返回值：3示例2：输入：4，返回值：10 解法一：思路分析：这道题应该典型的属于一道数学分析题，告诉你第n天准备吃的时候只剩下一个蛋糕，那么刚开始吃的时候一共有多少个蛋糕呢，以实例1为例，当第二天只剩下一个蛋糕，那么第一天就应该是3个，因为第一天吃掉蛋糕总数的三分之一向下取整1还多1个，所以1...

题目：最小生成树描述：一个有n户人家的村庄，有m条路连接着。村里现在要修路，每条路都有一个代价，现在请你帮忙计算下，最少需要花费多少的代价，就能让这n户人家连接起来。示例1：输入：3,3,[[1,3,3],[1,2,1],[2,3,1]]，返回值：2 解法一：思路分析：通过观察这道题，有n户人家，需要m条路，代价值用cost数组给出，这里需要解释一下关于这个cost数组，根据实例1分析，数组为[[1,3,3],[1,2,1],[2,3,1]]，该数组的意思是，数组中的第一个数组值代表第1条路到第3条路的权值为3，第二个数组值代表第1条路到第2条路的权值为1，第三个数组值代表第2条路到第3条路的...

题目：二分查找描述：请实现无重复数字的升序数组的二分查找给定一个元素有序的（升序）整型数组nums和一个目标值target ，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1示例1：输入：[-1,0,3,4,6,10,13,14],13，返回值：6说明：13 出现在nums中并且下标为 6示例2：输入：[],3，返回值：-1说明： nums为空，返回-1示例3：输入：[-1,0,3,4,6,10,13,14],2，返回值：-1说明：2不存在nums中因此返回-1 解法一：思路分析：该题中明确规定数组有序且为升序，且题目已经告诉我们用二分法解决问题，所以可以思考二分法...

题目：二叉树的中序遍历描述：给定一个二叉树的根节点root，返回它的中序遍历。示例1：输入：{1,2,#,#,3}返回值：[2,3,1]说明：  解法一：思路分析：这道题大部分人应该很熟悉了，首先我们了解一下关于二叉树的中序遍历概念，什么是中序遍历呢，中序遍历（LDR）是二叉树遍历的一种，也叫做中根遍历、中序周游。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。——给定一个序列{A,B,C,D,E,F,G}，下面进行分析：——在该二叉树中，首先访问左子树，因为根节点的左子树结点B还有左子树，所以继续往下遍历得到最左边的一个元素为D，然后寻找D的根节点为B，最后寻找B的右子树...

题目：随时找到数据流的中位数描述：有一个源源不断的吐出整数的数据流，假设你有足够的空间来保存吐出的数。请设计一个名叫MedianHolder的结构，MedianHolder可以随时取得之前吐出所有数的中位数。[要求]  如果MedianHolder已经保存了吐出的N个数，那么将一个新数加入到MedianHolder的过程，其时间复杂度是O(logN)。 取得已经吐出的N个数整体的中位数的过程，时间复杂度为O(1)每行有一个整数opt表示操作类型若opt=1，则接下来有一个整数N表示将N加入到结构中。若opt=2，则表示询问当前所有数的中位数  示例1：输入：[[1,5],[2],[1,3],[...

接雨水问题   问题描述：给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。   示例：   输入：[3,1,2,5,2,4]   返回值：5   说明：数组 [3,1,2,5,2,4] 表示柱子高度图，在这种情况下，可以接 5个单位的雨水，蓝色的为雨水 ，使用图形解释如下：        方法一   思路分析   相信每个人都知道木桶原理，就是说一只木桶能盛多少水并不取决于桶壁上最长的那块木板，而恰恰取决于最短的那块。通过类比发现，每一根柱子所能承受的雨水=其左侧最高柱子与右侧最高柱子中的较小值-其自身柱子高度。因此最...

最长公共子串 问题描述：给定两个字符串str1和str2,输出两个字符串的最长公共子串，题目保证str1和str2的最长公共子串存在且唯一。 示例1 输入："1AB2345CD","12345EF" 返回："2345" 问题分析 子串要求这串字符串在原字符串中是连续的，要区别于子序列的概念。  方法一 思路分析 本题如果采用手动求解的方法，即从第一个子串的起始位置str1[i]（i=0,1,2...）出发，与第二个子串的起始位置str2[j](j=0,1,2...)字符开始比较，直到找到相同的字符，接着记录此时的m=i,n=j，继续在...

换钱的最少货币数  问题描述：给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。 如果无解，请返回-1。【要求】时间复杂度O(n×aim)，空间复杂度O(n)。 示例1 输入：[5,2,3],20 返回值：4 说明：目标是值为aim=20,当组成的货币值为4张5元时，货币数量是最小的。 示例2 输入：[5,2,3],0 返回值：0 示例3 输入：[3,5],2 返回值：-1   方法一   思路分析  本题求解我们直接想到的是能否使用贪心算法，即每次寻找货币中的最大面值，利用a...

题目：分糖果问题 描述：一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：  每个孩子不管得分多少，起码分到一个糖果。 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)给定一个数组arr代表得分数组，请返回最少需要多少糖果。[要求]：时间复杂度为On, 空间复杂度为O1  示例1**：**输入：[1,1,2]，返回值：4 说明：最优分配方案为1, 1,2 解法一： 思路分析：看似该题目应该属于一个小游戏，感觉可能会很难，下面我们进行分析，因为题目规定，每个人至少需要分一个糖果，所以初始化每个人给一个糖果，接下来我们就从左往右进行遍历，如果右边的孩子得分高，就加...

题目：阶乘末尾零的数量 描述：给定一个非负整数N，返回N!结果的末尾为0的数量。 N!是指自然数N的阶乘,即:N!=1∗2∗3…(N−2)∗(N−1)∗N。 示例1：输入：3，返回值：0 说明：3!=6 示例2：输入：5，返回值：1 说明：5!=120 示例3：输入：1000000000，返回值：249999998 解法一：思路分析：在思考这个问题的时候，我们很容易想到的一种方法是暴力法破解，就是直接将阶乘的结果计算出来，然后再计算末尾0的数量，但是这种方法导致开销非常大，就比如11！= 39916800，然后再设计程序去判断末尾0的个数，虽然很简单，但是其阶乘计算相当复杂，会占用大量的内存空...