变向   描述  牛牛准备在一个3行n列的跑道上跑步。一开始牛牛可以自己选择位于(1,1)还是(2,1)还是(3,1)，跑道的每一格都有一些金币，当牛牛跑到一个格子，他会获得这个格子的所有金币。 当牛牛位于第i行第j列时，他可以的下一步最多可能有三种选择： 1. 不花费金币跑到第i行第j+1列 2. 花费的金币跑到第i-1行第j+1列（如果i=1则不可以这么跑）。 3. 花费的金币跑到第i+1行第j+1列（如果i=3则不可以这么跑）。 （牛牛是一个富豪，本身带了很多的金币，所以你不用担心他钱不够用） 现在告诉你所有格子的金币数量和每一列的金币花费，牛牛想知道他跑到第n列最多可以赚得多少金币（赚...

牛牛的和平年代   问题描述  我们定义一个整数可重集合是好的，当且仅当对于集合中任意两个元素 a, b () ，所有满足 的元素 c 都在集合中出现过。  现在，给你一个数组 mSet，你需要做的是，对于这个数组的每一个前缀，判断这个前缀是不是一个好的集合。所以，你将计算出的是一个数组，为布尔类型。   示例   输入：[3,5,4,6]   返回值：[true,false,true,true]   说明：第一个前缀只有一个元素3，按照好的集合的定义，它显然是连续的。 第二个前缀有一个3和一个5，位于3和5之间的元素4却不在集合中，所以它不是连续的。 第三个前缀添加了一个4，弥补了第二个集合...

三色球   问题描述：有红、黄、蓝三种颜色的气球。在牛客王国，1个红气球+1个黄气球+1个蓝气球可以兑换一张彩票。  2个红气球+1个黄气球可以兑换1个蓝气球。 2个黄气球+1个蓝气球可以兑换1个红气球。 2个蓝气球+1个红气球可以兑换1个黄气球。  现在牛牛有a个红气球，b个黄气球， c个蓝气球，牛牛想知道自己最多可以兑换多少张彩票。   示例   输入：1,7,5   返回值：3   说明：可以用4个黄气球和2个蓝气球换2个红气球，这样就有了3个红气球，3个黄气球，3个蓝气球，可以换3个彩票。      方法一   思路分析         首先找到三种气球中...

火柴拼图   问题描述：牛妹有n根火柴，她想用这些火柴去拼正三角形或者正四边形。牛妹想让最后拼出的总面积尽可能大的，请你帮帮她。 返回一个Vector，Vector中存有两个数字。其中最大面积 示例   输入：4,[1,1,1,1]   返回值：[0,1]   说明：构成一个边长为1的正四边形面积总和最大，值为1。所以Vector[0]=0，Vector[1]=1        方法一   思路分析      因为要构成正三角形或者正四边形，那么首先对给定的火柴，对不同长度的火柴进行计数统计，对不同长度的火柴，先判断火柴数是否大于等于四，如果大于等于四，那么可以构...

最大子三角形   问题描述：给你一个边长为 a 的六边形 01 矩阵，请找到一个最大的全 1 子三角形，输出三角形的边长 b。   示例   输入：2,[0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1]   返回值：2  说明：如下图，可以找到一个边长为2的子三角形，但并不唯一。       备注：   对于所有的输入数据，满足 。描述这个六边形 01 矩阵 maps 的数组下标，每个数字依次从左到右，再从上到下对应每一个区域。详见下图：        方法一   思路分析   图解   核心代码  ...

最大四边形面积   问题描述：给定大小为n的整数集合A，代表n根木棍的长度。从A中任选4根木棍组成一个四边形，求其面积最大为多少。数据保证有解。程序返回结果与正确答案的误差应小于0.00001   示例   输入：[1,2,3,4,5]   返回值：10.95445       方法一   思路分析      本题可以直接使用暴力搜索的办法，即设置四层循环，每次找到四条边的长度，先判断是否可以构成四边形，而后计算四边形的面积。 判断构成四边形的条件：三边之和大于第四边 四边形的最大面积：        图解   四层循环遍历找到符合条件的最优解     C++核心代码   ...

一样的水   问题描述：有n个水桶，第i个水桶里面水的体积为$A_{i}$，你可以用1秒时间向一个桶里添加1体积的水。有q次询问，每次询问一个整数$p_{i}$,你需要求出使其中$p_{i}$个桶中水的体积相同所花费的最少时间。对于一次询问如果有多种方案，则采用使最终$p_{i}$个桶中水的体积最小的方案。   示例   输入：4,3,[1,2,3,4],[2,2,4]   返回值：[1,0,5]   说明： 第一次：花费一秒变为 2 2 3 4  第二次：已经存在两个水的体积一样的桶  第三次：花费五秒从2 2 3 4变为4 4 4 4       方法一   思路分析    &n...

数组求和统计   问题描述：牛牛有两个长度为$n$的数组$a$,$b$，牛牛希望统计有多少数对$(l,r)$满足：         示例   输入：[1,2,3,4],[2,1,4,5]   返回值：4   说明：满足条件的数对有$(0,1),(0,2),(1,1),(1,2)$，即存在这样四个等式:                   方法一   思路分析      此题我们可以直接使用暴力搜索的办法，即设置内外两层循环，也可理解为快慢指针，循环计算数组$a$中$i(i<n)$位置到$j$位置$(i<=j<=n-1)$之间的元素的和，并计算数组$b$中$...

最长回文子序列   问题描述：给定一个字符串，找到其中最长的回文子序列，并返回该序列的长度。字符串长度<=5000   示例   输入："abccsb"   返回值：4   说明：子序列bccb回文序列为bccb，因此最长的回文子序列长度为4      方法一   思路分析        最长回文子序列表示子序列在给定的序列中位置可以是不连续的。使用递归的办法，采用自上而下的办法，要求的string[0,n-1]中开始元素到末尾元素中间的最长回文子序列，有如下递归方程：   设置$lps(string ,i,j)$表示字符串string中...

信封嵌套问题   问题描述：给n个信封的长度和宽度。如果信封A的长和宽都小于信封B，那么信封A可以放到信封B里，请求出信封最多可以嵌套多少层。   示例1   输入：[[3,4],[2,3],[4,5],[1,3],[2,2],[3,6],[1,2],[3,2],[2,4]]   返回值：4   说明：从里到外分别是{1，2}，{2，3}，{3，4}，{4，5}。   示例2   输入：[[1,4],[4,1]]   返回值：1      方法一   思路分析        首先对所给的信封进行排序，我们需要按照信封的长度length进行升序排序，如果两个信封的长...

数的划分   问题描述：将整数n分成k份，且每份不能为空，任意两个方案不能相同(不考虑顺序)。  例如：n=7，k=3，下面三种分法被认为是相同的。 1，1，5; 1，5，1; 5，1，1; 问有多少种不同的分法。 输入：n，k ( 6 < n ≤ 200，2 ≤ k ≤ 6 )  输出：一个整数，即不同的分法。   示例   输入：7,3   返回值：4   说明：整数7分为3份有4种办法:[1,1,5][1,2,4][1,3,3][2,2,3]          方法一   思路分析         使用动态规划的...

分糖果问题   问题描述：一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：   1. 每个孩子不管得分多少，起码分到一个糖果。  2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)  给定一个数组arr代表得分数组，请返回最少需要多少糖果。   [要求] 时间复杂度为$O(N)$, 空间复杂度为$O(1)$   示例   输入：[1,1,2]   返回值：4  说明：最优分配方案为1,  1，2       方法一   思路分析        为使每个孩子都能得到一...

字典树的实现   问题描述：字典树又称为前缀树或者Trie树，是处理字符串常用的数据结构。假设组成所有单词的字符仅是‘a’～‘z’，请实现字典树的结构，并包含以下四个主要的功能。void insert(String word)：添加word，可重复添加；void delete(String word)：删除word，如果word添加过多次，仅删除一次；boolean search(String word)：查询word是否在字典树中出现过(完整的出现过，前缀式不算)；int prefixNumber(String pre)：返回以字符串pre作为前缀的单词数量。现在给定一个m，表示有m次操作，...

序列化二叉树   问题描述：请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。  二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。 二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。 例如，可以根据层序遍历并特定标志空结点...