算法分享之二分查找 在有序序列之中要找到某一个数，一般暴力的方法就是遍历这个序列，查找是否符合，当然这对于常规数组而言就是一个而已，不算大，但是如果每次检查都要花费很多时间而非，那么从优化到就显得很重要了。 二分查找的常规思路是，对将序列从中间分成大小两份，然后判断中点，根据中点与所求值的大小判断所有应该在左边的小区间还是右边的大区间，并重复如此的操作。因此区间不断连除2，而区间大小为，则相当于最坏情况下复杂度就是对连除2到最小，即. 牛客网应用二分法的题目很多，比如求解立方根 、牛牛晾衣服 、Redraiment的走法 、二维数组中的查找 。 当然二分的思想不仅可以应用于一维序列，也可以应用...

算法分享之图的dfs和bfs dfs即深度优先搜索，在遍历的图的时候每次从一个点到不重复访问的它能前往的最深处的点，然后再访问该点的另一条边。 而bfs即广度优先搜索，在遍历图的时候每次将与这个点连接的所有点都访问了，再进入子节点的子节点。 dfs常采用递归，递归进入与之连接的结点，然后到叶结点时，能够回到父问题即父结点，然后继续遍历其他的边。而bfs常借助队列，将与根结点连接的结点依次加入队列，然后依次访问队列，加入队列，每次则会优先访问与该结点连接的所有结点。 图的dfs和bfs的题在牛客网可以参考最多结点数 ，树的bfs和dfs的题在牛客网上可以参考二叉树的深度 。 下面以图的dfs和b...

算法分享之01背包问题 01背包问题是最简单的背包问题，一般形式是问一共有件物品，第件物品的重量为，价值为，问在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？这类问题可以自顶向下分解为子问题，也可以直接子问题相加，因此可以考虑递归或者动态规划。 牛客网上的01背包问题可以参考01背包 、购物单 、牛能和牛可乐的礼物 等问题，我们考虑的最简单的01背包题解可以具体参考这篇题解 。   方法一：递归 递归是一种分治法，我们可以如下考虑：  为1或0，表示对于物品取或者不取，表示物品的体积，表示物品的质量，是物品总数，是背包总体积 问题求： 限定条件为：  对于的问题，如果最后一...

算法分享之斐波那契数列的高级解法 斐波那契数列数列，我们都知道，是一个非常简单的问题，最初由数学家斐波那契根据兔子的问题提出来，递推公式为，常规解法如果要求可以使用递归，不断计算子问题相加，但是这样其实是一个树型递归，会重复计算很多内容，因此很浪费时间，接下来我要介绍几种至多是复杂度的算法解决斐波那契数列问题。 斐波那契数列问题可以参考牛客网的跳台阶 、斐波那契数列 、不死神兔问题等问题。 我们这里讨论且的情况，具体可以参考这篇题解 。 方法一：动态规划/迭代 对于递推公式可以用一个数组记录每位的函数值，然后初始化前两位，后续不断由前面两个相加即可得到。 class Solution { pu...

算法分享之六种方法找出数组卧底 如果一个长度为的数组，包含了数字到的每个数字，但是有一个数字势必会重复出现，我们可以把这个唯一出现两次的数字看成卧底，如何找出这个卧底，下面提供6种思路，可以参考牛客网下面这道题 ，也可以参考这篇题解 。   方法一：排序法 要解决这个问题，我们首先想到的是将这个数组排序，然后重复的数字就会相邻，检查相邻两个数字是否重复就可以找到这个重复数字了。 利用sort函数对数组排序，遍历数组，相邻两个数相同则找到所求。  class Solution { public: int search(int n, vector<int>& a) { sort...

题目的主要信息：  实现一个简单的自动售货系统，实现投币、购买商品、退币、查询库存商品及存钱盒信息的功能 一共售卖6种商品，商品名称和售价如下，零钱盒中记录1元、2元、5元、10元4种零钱的数量。     商品名称 单价     A1 2   A2 3   A3 4   A4 5   A5 8   A6 6    其他信息太多了，在解题的时候一起说，不在此赘述 方法一：直接判断 具体做法： 需要实现5个功能，我们分成5个函数，输入的命令之间通过分号连接，我们可以通过字符串流输入获取分号间的子串，组成一个数组，然后遍历子串数组就是遍历每条命令，命令开头字母对应相应的功能及函数。  money表示...

题目的主要信息：  给出四张扑克牌的牌面，将其当成数字，询问能否通过加减乘除得到24，除法是整除，给出算术式 牌面2到10分别对应数字2到10，然后J、Q、K、A分别代表11、12、13、1 遇到大小王joker、JOKER要输出ERROR 运算中数字的顺序不定，但是不能包含括号 如有多个解输出一个即可，如无解输出NONE  方法一：暴力枚举 具体做法： 我们可以用两个哈希表做到字符串到数字的映射，通过哈希表可以将牌面字符串转换成数字，再将数字转换成牌面字符串。 对于输入的字符串先检查有无大小王，没有再转成数字，然后计算。计算的时候先排成最小的递增序，然后使用next_permutation枚...

题目的主要信息：  输入两手牌，两手牌之间用"-"连接，每手牌的每张牌以空格分隔，"-"两边没有空格 比较两手牌大小，输出较大的牌，如果不存在比较关系则输出ERROR 比较规则如下：  输入每手牌可能是个子、对子、顺子（连续5张）、三个、炸弹（四个）和对王中的一种，不存在其他情况，由输入保证两手牌都是合法的，顺子已经从小到大排列； 除了炸弹和对王可以和所有牌比较之外，其他类型的牌只能跟相同类型的存在比较关系，不考虑拆牌情况； 个子、对子、三个比较牌面大小，顺子比较最小牌大小，炸弹大于前面所有的牌，炸弹之间比较牌面大小，对王是最大的牌； 输入的两手牌不会出现相等的情况    方法一：空格统计法 ...

题目的主要信息：  将输入的两位小数的数字人民币转换成中文表示的人民币 中文大写金额数字前应标明“人民币”字样 中文大写金额数字应用壹、贰、叁、肆、伍、陆、柒、捌、玖、拾、佰、仟、万、亿、元、角、分、零、整等字样填写 中文大写金额数字到“元”为止的，在“元”之后，应写“整字，如果小数为0 阿拉伯数字中间有“0”时，中文大写要写“零”字，阿拉伯数字中间连续有几个“0”时，中文大写金额中间只写一个“零”字 10应写作“拾”，100应写作“壹佰” 十万以上的数字接千不用加“零”  方法一：迭代 具体做法： 我们用字符串的形式来接收输入的数字（和将输入的double型数字转变成字符串一样），然后遍历字...

题目的主要信息：  先给出mmm位候选人的名字，字符串表示 后续给出nnn张票，票上是候选人的名字，统计每位候选人的票数 票里出现非候选人的名字则是属于不合法 输出按照输入的候选人的顺序排序  方法一：暴力查找 具体做法： 我们可以用一个pair型的vector数组来存储这个每个候选人及其票数，输入候选人姓名的时候就初始化票数为0. 然后根据输入的票，遍历查找数组中候选人的名字刚好等于输入的票，再给那个人票数增加1。 最后按照顺序输出数组两部分即可，同时要统计输出的票数有多少，总票数减去输出的票数就是不合法的票数。 #include<iostream> #include<st...

题目的主要信息：  对输入的n个数，询问能否被分成两组，且两组的和相等 其中第一组必须包含所有5的倍数，第二组必须包含3的倍数（不含5的倍数） 其他数字任意放 可以分出空数组，因为正负数和可能为0  方法一：集合枚举 具体做法： 在输入的时候直接开始计算5的倍数的和与3的倍数的和，然后剩余的数字再加入数组，同时计算总和。 然后我们用unordered_set开始枚举剩余的数能够组成的全部和，因此可以有空数组，因此先加0加入集合，然后遍历剩余的数组，对于每一个元素，都有与当前集合每一个元素相加，然后加入集合，因此在加之前，用另一个集合记录当前集合，避免加入新元素后受影响。 最后遍历所有的枚举，检...

题目的主要信息：  对于输入的一个字符串，返回其最长的数字子串，以及其长度 如果最长有多个，都要输出  方法一：遍历截取拼接 具体做法： 可以遍历输入的字符串，检查每个字符，如果遇到数字我们开始循环计算这一段连续的数字子串的长度（直接循环直到非数字，然后首尾相减即可），比较这一段子串的长度与最大长度之间的大小关系，如果这一段更长，则要输出的字符串直接等于这一段子串，用substring方法截取，同时更新最大长度；如果这一段等于最大长度，则将其截取后拼接在要输出的字符串后面。  import java.util.*; import java.math.*; public class Main{ ...

题目的主要信息：  将一个字符中所有的整数前后加上符号“*”，其他字符保持不变 连续的数字视为一个整数  方法一：遍历添加 具体做法： 我们可以遍历字符串，每次遇到一个数字字符就在前面添加一个星号，然后使用循环连续遍历这个子串的所有数字字符，直到遇到第一个不是数字字符的，在其前面添加另一个星号即可。  #include<iostream> #include<string> using namespace std; int main(){ string s; while(cin >> s){ for(int i = 0; i < s.length(); ...