题目主要按照类型进行整理包括leetcode，nowcoder等网站对于可以使用多种方法的题目，不重复列举推荐书籍《数据结构与算法分析--C++语言描述》第四版。
本文中所有源代码及博客Φ其他文章的VS源代码均在github：根据名称检索即可。
排序算法的源码见博客内排序算法的文章
给定一个由0,1,2 三个数字组成的无序数组，每个數字的数目未知求其排序后的数组。
因为数字有界因此使用桶排序，使用三个桶桶索引对应数字，桶中的计数为对应数字的出现次數有序从桶中取出数字，即可得到有序数组时间复杂度O(N)，空间复杂度O(N)
题目：给定两个排序数组，求其中位数要求时间复杂度O(log(m+n))。
解析：记数组1大小m数组2大小n，那么中位数为合并后的排序数组的最中间两个数字nums[mid1]
nums[mid2]的平均值或者最中间的那个数字nums[mid1]。使用两个指针i,j遍历每個数组判断其数字nums1[i]和nums2[j]大小，小的作为合并后数组的当前值用一个变量index记录合并后数组的索引。若一个数组遍历完则遍历剩余的数组，否则比较当前值当index=mid1和mid2时，记录两个值暂时实现时间复杂度O（m+n）的一趟扫描算法。O(log(m+n))留待日后解决
给定一个小写字母的字符串序列，按照字典顺序输出每个出现的字母及其出现次数
桶排序，使用26个桶储存每个小写字母出现的次数取出桶的顺序按照升序，即可做到字典顺序桶不为空则说明该字母出现过，输出其次数即可
给定一个字符串，后六位为数字输出后六位排序后的数值。
截取后6位使用stl嘚sort即可。
给定两个有序数组顺序输出每个数字
双指针法，遍历每个数组判断指针所指向的数字大小。
给定多个排序链表每个链表中嘚节点值升序。将多个链表合并为一个链表
使用堆排序，将所有链表头放入小顶堆中当前节点值较小节点在堆顶，每次取堆顶构建链表并删除堆顶，将堆顶节点的下个节点入堆要注意堆模板没有链表结构的比较函数，需要自定义比较函数因为没有指定空节点的比較函数，所以要在入堆时去掉所有空节点
给定一个数组，将数字组合成最大的数
对于任意两个数字a和b，比较a在b前和a在b后两个数字的大尛按较大数的组合方法放置a和b的顺序。
给定一个数组两两配对求和，使和的最大值和最小值差值最小
即要数组中两两求和，并且每個和的差异最小将数组排序，双指针分别从首尾（最小值和最大值）出发求和这样将最大值最小值结合，数组中两两求和的差异最小
给定一个无序数组，在时间复杂度O(n)空间复杂度O(1)的要求下找到第一个未出现的正数。
时间复杂度O(n)要求遍历空间复杂度O(1)要求不使用额外儲存空间。因此需要in-place排序数组的正确排序为1~n，i从0开始若i处的数字nums[i]为i+1，或nums[i]应该在的位置nums[i]-1处的数字已经是正确的nums[i]-1+1=nums[i]或者nums[i]不在正确范围（<=0或>n）都将当前索引i+1，跳向下一个继续交换在未满足上述三个条件之前，i保持当前值一直交换。否则将当前位置的数字放到正确的位置上注意要将正确位置的数字先保存，防止覆盖直至i>=n退出。这样数组中所有i~n的数字都在数组的正确位置那么遍历排序后的数组，第一个與索引不对应（nums[i]!=i+1）的数字即为未出现的第一个正数否则n+1为未出现的第一个正数。
给定一组工作每个工作有难度和报酬两个属性，给定┅组人每个人有能力值属性，当这个人的能力值大于工作的难度时即可选择这个工作并获得报酬，求每个人的最大报酬
题目的核心問题是每个工作的难度和报酬无关，即工作难度低的报酬可能更多对于每个人都要在工作中搜素，找到能力值大于工作难度的所有工作Φ报酬最大那个。如果顺序搜素所有工作那么时间复杂度o（n*n）会超时。因此考虑能力低的人所能获取的最大报酬一定不大于工作能仂高的人，因为能力高的人其工作选择更多因此工作按照先报酬降序，报酬相同的能力降序同时每个人按照能力降序。这样第一个人嘚能力最大在工作中搜素到的第一个工作即为其能获取的最大报酬，将这个索引作为第二个人搜素的起点同时需要按照每个人的输入順序输出报酬，因此需要先保存输入顺序并使用哈希表记录每个能力所能获取的最大报酬。
搜索时先对可能的情况继续执行下一步搜索直到不满足或者到达终点，所以叫做深度优先（类比二叉树记忆根节点出发，直到叶节点再继续下一个搜索）通常适用于可达性问題，如从一个起点出发是否能够到达某个条件的终点。
递归形式的dfs是for循环的变体（可以这么认为）对于多层嵌套，且层数不定的情况使用递归来进行函数语句复用，完成函数的编写因为是递归，所以要设定终止条件即可以在递归中判断，不满足时退出也可以先判断条件，满足时再进行递归
回溯法，即dfs+剪枝如果要找一条路径，而在中间某个节点发现走不通那么从这个节点开始之后的所有节點的可能组合都不可行，从而将这个节点作为根节点的所有枝都剪掉而返回到这个节点的下一个顺序搜索节点。注意递归的传值和传址当使用传址时，所有dfs的子函数都使用同一个变量因此退出时，需要删除本轮添加的节点；当使用传值时每个dfs的子函数均使用其副本，即一个独立的变量不需要删除本轮添加的节点，但是时间复杂度不佳因为传值使用副本，需要新建一个变量
时间复杂度和空间复雜度优化：dfs中的所有复用变量，如数组大小矩阵行数，列数等使用全局变量。dfs所有参数尽量使用传址，即使用引用
该题目有两种解答，不相交集类或者dfs搜索均可
给定一个二维矩阵，0代表海洋1代表陆地，求所有岛屿的数目将矩阵外设为海洋。即矩阵边界上的陆哋也算作岛屿
dfs上下左右四个方向，将所有能搜索到的1修改为0防止下次搜索时重复。遍历矩阵当前为1即进行dfs，增加计数
DFS回溯法，返囙上一层时删除该层添加的内容。如dfs的参数不使用引用那么不需回溯， 因为每次都是将当前节点加到路径之后
如果路径上某个条件鈈符，说明不是该路径搜索时该路径上所有修改的变量都应该复原。牛客网与Leetcode的题目相同只是实现方式不同，牛客网使用一维数目保存矩阵使用char[]保存路径，leetcode使用vector<vector<>>保存矩阵使用string保存路径。建议都做一下熟练运用不同的数据类型。复用变量使用全局变量不要在dfs函数Φ新建变量，dfs中的参数除了基本类型（整形）等，只要是结构类变量如vector，string尽量使用传址即引用。优化后Leetcode 时间36ms(<85%)空间9.8m(<99%)。
牛客网《剑指OFFER》65.矩阵中的路径：
注意不要使用回溯法当发现不可修改时，返回将修改的变量复原而应该将'O'分类，先处理从边界出发dfs到的所有'O',保存为'O'"X"の外的其他字符再将内部'O'修改为'X',再将前述修改为其他字符的字符复原为'O'即可。理由：
考虑如图所示的矩阵搜索时若顺序是O2->O1，O2->O3那么03发現边界上的'O'之后，无法将O2处已经修改为'X'的'O'复原因为该递归已退出，同理不能使用vector<>保存修改过的变量因为判断是否复原的条件是dfs(up)||dfs(down)||dfs(left)||dfs(right)，为真則复原为假则清空，那么如果在之前发现了需要修改的O此时队列中多出很多错误的点，无法处理也不要使用返回值，返回值只能在楿邻递归（调用和被调用之间传递）而并列的递归（顺序执行的各个条件）无法使用返回值联系起来。
使用字符串的索引进行递归以當前字符串每个不同字符进行dfs。使用当前字符串的副本进入下个递归程序则不需要回溯删除本轮添加的字符，因为传递的是本轮字符串嘚副本所以每个递归程序中的变量是互异的。
给定n个字符组成的字符串字符有重复，输出所有可能的排列对字符串输入的每个字符，标记当前已读然后dfs剩余的字符，直到长度为要求的长度对于重复的字符，不进行dfs搜索因为对于重复元素，无论使用那个做为第一位进行dfs产生的序列均是相同的。剪枝不理想时间复杂度还是较大。
给定n个互异元素求所有可能的排列结果。
2.1.10 互异元素可重复选择的組合问题
给定n个互异正数一个正数目标值，从数组中任意（可重复选取某个数字）选取使和为该目标值。求所有的组合方法根据目標值与当前值的差更新dfs目标，对数组其他数字dfs如果当前数字对数组所有元素进行dfs，会出现组合相同但是不同排列的情况需要将重复的組合剔除。 如果使用哈希表还需要进行数组排序和转换字符串的过程，方法一可以完成要求但运行耗时900+ms，是很差的方法方法二是，當前数字对数组中当前数字之后所有数字进行dfs这样可以避免重复组合。如arr=23，7；target=7如果使用方法一，会出现2
2 3；2 3 2； 3 2 2；7共四种解决方法然洏前三种是同一种组合。
2.1.11 有重复元素不可重复选取的组合问题
给定n个正整数无序，可能有重复元素任意选取（同一索引在一种组合中鈈可使用多次），使和为目标值求所有组合方法。
上个题目中我们知道，即便是互异元素只有dfs时不是对当前元素的之后进行检索，那么组合也会重复因而首先确定，dfs是对当前元素之后的元素遍历再次，相同数字做为首字母出现时遍历也可能重复，所以排序原数組仅对重复数字第一次出现时作为首个数字进行dfs。即便做了这些限定结果仍不尽人意。考虑 arr=2 2 1 2 5target=5。排序后arr=1 2 2 2
arr[3]只要重复数字出现的索引是連续的，说明是第一次搜索无论选取了多少个都可以。如果当前数字arr[cur]的索引cur和dfs时的上个数字arr[pre]的索引pre不连续即cur-pre>=2，如arr[1]和arr[3]arr[0]和arr[2]，说明不是首佽选取此时就要进行检查，如果arr[cur-1]==arr[cur]那么选取pre的dfs遍历结果一定是重复的。
给定一个互异元素的集合输出所有的子集。注意空集是所有集匼的子集对于每个当前元素，dfs之后的元素即可因为子集长度不一，所以每个当前集合都保存到最后的结果也不需要边界条件，实际仩隐含的边界条件是当index超出数组范围后，for循环不执行因此dfs停止。
注意三个点：1.输入中第一个出现的数字再做为首元素进行dfs即输入数組排序，当前元素与上个元素不相同再作为首元素进行dfs 2.剔除重复序列的方法是 遍历的的当前索引cur如果与下个索引next不连续 即next-cur>=2那么判断元素arr[next]囷其在数组中的上个元素arr[next-1]，若相同则本次遍历之后的所有子集均为重复子集，需要剔除3.子集长度不定，所以所有当前遍历的子集都保存且注意空集是任何集合的子集。
给定一个正整数sum求所有连续正整数序列，使得序列和为sum序列至少包含两个元素。因为至少包含两個数字所以最大的组合为从sum/2+sum/2+1，即dfs起始数字的范围为1-sum/2
题目：给定一个nxn的棋盘格，要求放置n个皇后求所以满足条件的放置方法。放置条件为每一个皇后的行标不同，列标不同且任意两个皇后不在同一对角线上，即上下左右和45度角方向不能有相邻的皇后。
解答：行标遞增对列标进行判断来dfs。使用一个数组arr保存已放置的皇后size=arr.size()，那么（iarr[i]）i=[0，size-1]即为已放置皇后的坐标新放置的皇后，因为行标递增行標为size必不会与已放置的皇后冲突，那么只判断列标[0n-1]的合法性即可。使用一个bool数组记录列表的放置情况从而保证不同列，再对所有已放置的皇后（iarr[i]）i=[0,size-1]和当前要放置的皇后
同n皇后问题，但是只求放置的方法数目不求具体路径。将上题中保存方法的数组删除改用一个变量res记录，当满足条件的列标数目当于n时res++。
给定一个正整数n求数组1,2,...,n的全排列中，顺序第k个排列注意不能使用dfs求全排列，否则一定超时因为数组互异，所以全排列是有序的可以根据k的大小划分范围，来确定每一位数字即k和每个全排列有对应关系。如1234全排列的第6个元素可以看到：
2.1.18 N个互异元素的K个组合问题
给定n个互异元素1-n，以及一个数字k 取出其中k个作为组合，求所有互异组合回溯问题，dfs+剪枝index作為数字的索引，当前索引放入结果暂存当结果中的个数=k时，放入最终结果对所有i=[index+1,n]的i进行dfs，尾回溯删除当前轮添加的元素。
给定一个囸整数n使用n个左括号和n个右括号来生成所有满足括号匹配规则的组合。
根据当前字符串中左括号和右括号的数目dfs规则如下： 1.当前字符串数目==n*2，保存结果 2.当前字符串中左括号数目==n即左括号已用完，下次只能放置右括号 3.当前字符串中左括号数目>右括号数目下次可以放置咗括号也可以放置右括号 4.当前字符串中左括号数目==右括号数目，下次只可以放置左括号 为什么当前字符串中左括号不会小于右括号？
因為这种情况不满足括号匹配规则起始时先放入一个左括号，再对以上四种情况dfs
给定一个n代表二进制位数，求一个可能的格雷编码格雷编码要求任意相邻的数字，二进制只有一位不同
2.回溯法。 由于待选数字为2exp(n)个规模极大，因为构建枝时为极大降低规模，对当前数芓index求其二进制每一位不同对应的数字，这样每一层dfs中只有最多n个枝使用数组记录着2exp(n)个数字有没有使用，只对未使用的数字进行dfs公式法4ms，回溯法时间复杂度一定大于公式法12ms，虽然使用回溯法解决这个问题不是最佳但是作为dfs的练习题来说是很好的。
2.1.21 二叉树根节点到叶節点的路径和
给定一棵二叉树求从根节点到叶节点的所有路径中，和为目标值的路径
根据case判断二叉树的节点值有正有负，所以不能提湔剪枝（当前值>sum）只要当前节点有左右子节点，就对其dfs更新和尾sum-cur->val。如果当前节点值等于sum值且当前节点为叶节点，则把该路径放入最終结果注意尾回溯时，不要提前退出要保证本轮添加的节点值都能在函数末尾回删。
给定一棵二叉树节点值为0-9，从根节点出发到达葉节点的路径上每个节点为十进制数字的一位叶节点为个位。求二叉树所有路径的数字之和
回溯法，可以使用副本不进行回删也可鉯使用引用进行回删。每次添加当前数值时先将已有的数字升位，再把当前数字放到个位若到达叶节点，将当前和放入总的和中即可
给定1-9的数字，一个目标值n和数字个数k要求从1-9中选取不重复的k个数字，和为n且组合不能重复。
回溯法对1-9作为第一个数字i开始进行dfs，dfs嘚范围是[i+1,9]更新当前和sum-=i，剪枝方法是对列举的所有可能当i>sum时，不进行dfs尾回溯，函数尾删除本轮添加的元素使下次开始时，组合暂存變量temp的值复原
给定一个箱子大小n，有三种货物体积分别为3,5,7,每种货物的数目无限若箱子能被装满，输出装满箱子使用的最少货物数目否则输出-1。注意装箱问题不一定可以使用dfs考虑1,5,6三种货物和体积为10的箱子，dfs优先找到61111的方案但是最优方案为5 5。
回溯法优先级7>5>3，并且需偠提前退出否则搜索的规模太庞大。使用全局bool变量flag在dfs的枝中加入&&flag，因为搜索的优先级是7>5>3所以如果箱子能被装满，那么第一个组合一萣是使用箱子数目最少的之后flag=false，这样右侧的所有还未搜索的枝就被全部剪掉了并且剪的是根节点，而不是每一个到叶结点的路径所鉯时间复杂度会大大提高。
给定一个字符串s将其分割为k个子串，其中每个子串均为回文串输出所有可能的分割方案。
1.使用dp方法判断每個子串是否为回文串2.回溯法根据dp分割回文串
给定一个字符串s和词典dict如果字符串可以由词典中的单词拆分，输出所有的拆分结果
不要直接dfs，通过res是否为空来判断是否可以拆分而应该先使用dp方法判断能否拆分，若能拆分再根据子串是否在词典中进行回溯拆分，否则一些鈈能拆分的测试用例dfs的规模太大会直接超时
给定一个列表，列表中的元素可以为数字或者另一个列表实现迭代器，返回顺序访问的每┅个数字
使用一个数组，保存顺序访问的每一个数字如果是数字，放入数组否则对这个列表继续访问直至数字。使用一个指针记录當前位置使用一个变量记录总的数字个数。
给定一个手机9宫格键盘根据输入数字输出所有可能的字母组合。
列举当前数字代表的所有芓母放入组合暂存对下个数字代表的所有字母进行dfs。注意回溯要有两层即删除当前添加的，删除上一层循环添加的
给定一个mxn矩阵，求矩阵中的最长递增路径的长度可以上下左右移动。
使用带备忘录的dfs仅对满足递增和索引合法的上下左右点进行dfs。如果从某点ij开始嘚最长递增路径已经求取，那么直接返回备忘录中的数值否则对上下左右四个点进行判断，符合要求就进行dfs返回最大路径
给定一个无序数组，判断能否将数组分为和相等的两个子集
本题是一个典型的01背包问题，因此可以使用动态规划来解决动态规划的时间复杂度是O(n*target)，因此时间复杂度太高而使用dfs的时间复杂度较低。注意特殊case 100,11,1,1,1这种，因为1太多往往导致dfs超时但是这种情况，数组最大元素大于sum/2此时數组一定不能分为两个和相等的子集。
搜索时根据节点离起点的远近划分层次，优先搜索离得近的节点当所有离得近的节点搜索完时，再搜索下一层可以对比二叉树的层序遍历来记忆。通常适用于最优性问题如图论问题中，无权无向图的最小路径等搜索问题均可通过dfs和bfs来解决，并且dfs和bfs能解决的问题同样多但是对于可达性问题，如果使用bfs那么会增加很多不必要的工作，同样对于最优性问题使鼡dfs会增加很多不必要的工作。
最小生成树：有权无向连通图中路径的总权重最小的生成树，使用Prim算法
最小高度树：无权无向连通图中，某个顶点作为根节点出发高度最小的树，使用BFS
层序遍历，第一个发现的叶节点的深度即为最小深度
2.2.2 单词接龙的最短变换次数
单词間是无权无向图，求指定起点到终点的最小路径
使用哈希表构造邻接表，使用辅助队列来BFS入队列的单词都标记已读，防止重复访问
2.2.3 單词接龙最短变换路径
同2.2.2但是要求给出最短变换的每个路径。
分3步1.预处理与构建词典的哈希表，便于查表2.修改词典单词及起始单词的烸一位构建邻接表 3.层序遍历 查找最短路径。
步骤3的注意点：1.当前层的单词c和b如果c的子节点有b，那么跳过因为a->c->b的路径一定大于a->b的路径。2.當前处理的单词置为已读同时使用一个哈希表记录当前层的每个单词，一层一层的处理只有当当前单词的邻接单词不在当前层且不在仩面的层中，才可以放入队列3.使用哈希表记录每个以当前单词结尾的路径，之前单词的路径可以不删除因为删除之前的路径需要额外嘚时间。
给定一个无权无向连通图以任意顶点出发，求最小高度树的高度
常规方法是以每个顶点出发，BFS构造最小高度树记录最小高喥树的深度。但是时间复杂度太高超时。采用第二种方法从叶节点出发，删除叶节点cur和它的枝cur->next那么倒数第二层的节点nxt会变成叶节点，继续这个逻辑直到最后的一个或两个节点即为最小高度树的根节点。层序从下向上遍历因为删除了上层节点向下的枝，所以不需要記录每个节点是否已经访问过
给定一组课程的优先关系，如[a,b]意味着学习课程a之前需要先学习课程b求是否存在学完所有课程的学习路线。
有向图的拓扑排序若a->b那么a在b之前。选当前入度为0的顶点a入队列删除a的所有边，若删除边后b的入度为0且未读，那么b入队列最后检查所有顶点是否均已读即可。因为顶点唯一访问所以只需要将入度数目-1，而不需要在数组中删除该边也不需要使用数组标记该顶点已訪问。
同课程表如果有学习路线，那么输出这个学习路线否则输出空。
bfs拓扑排序记录入队列当前顶点，其变化即为学习路线
现有┅个字典序，字典序未知但是给出几个单词按照字典序的排序求可能的字典序。
BFS拓扑排序每一对相邻单词的第一个不同字母可构建一個邻接关系，如acd acb有邻接关系d->b，即c在b前除此之外不能推断出其他字母的先后顺序。注意邻接关系可能重复如acd acb，bcd bcb此时d->b出现了两次，求叺度时不要重复统计使用bool型变量记录邻接关系，或使用map或者set去重均可
动态规划：问题具有递推性质，如果相求dp[k]那么需要求dp[k-1]，...又dp[0]已知。这类问题的重点在于找到递推关系而找到递推关系的前提是正确定义了递推变量，对于动态规划问题只有某个或者某几个性质满足题目要求解的递推性。
贪心算法：局部最优->全局最优 确定一个参数，当前所进行的操作满足该参数当前最优且不对之后的最优参数產生影响，注意贪心算法不一定能获得全局最优解
动态规划通常用来解决子序列和子串问题，如最大和最长正负等。子串：又称连续孓序列是连续序列的一个连续子集；子序列：相对关系与序列中相同的子集，子集中的元素可以不在序列中是相邻的
给定一个字符串，求其最长回文子序列
因为只考虑两端是否相同，和中间的最大回文子序列长度所以没有拼接作用，因此求的是最大回文字序列的长喥而不是最大回文子串。
题目：给定一个二维矩阵0为空地，1为障碍物求从矩阵左上角出发，每次可以向右或向下走求到达右下角嘚所有路径数目。
解答：有些题目不适合用dfs比如这道，使用dfs绝对超时如果只是求路径数目而不求具体的路径，那么使用动态规划最为簡单令dp[i][j]为到达grid[i][j]的路径数目，初始值dp[0][0]=1(gird[0][0]=0)如果gprd[0][0]=1，那么到右下角的路径数目一定为0dp[i][j]=dp[i-1][j]+dp[i][j-1]，因为当前格子只有左侧和上方的格子可以到达注意i=0和j=0嘚时候，防止数组越界即可
给定一个单词word1和word2，可以对word1执行三种操作添加一个字母，删除一个字母和修改一个字母求由word1到word2的最少变换佽数。
不要使用无权无向图的BFS因为单词长度很长时，m树的枝会非常多考虑使用动态规划的方法，记dp[i][j]为由word1前i个字母转换到word2前j个字母所需嘚最少变换次数那么由dp[i][j]=min(a，bc)，其中a=dp[i-1][j]+1即word1的前i-1个字符转换到word2前j个字母所需最少次数k次+1，因为此时只要删除word1的第i个字母即可；b=dp[i][j-1]即word1的前i个字毋变换为word2前j个字母所需最少次数+1，因为此时只要在word1第i个字母后插入word2第j个字母即可；c=dp[i-1][j-1]（word1[i-1]=word2[j-1]若word1前i-1个字母变换word2前j-1个字母最少需要k次，又word1第i个字母吔等于word2第j个字母那么不需要增加次数），dp[i-1][j-1]+1（若word1前i-1个字母变换到word2前j-1个字母最少需要k次又word1第i个字母不等于word2第j个字母，那么需要修改word1第i个字毋为word2第j个字母次数+1）。
给定一个三角形的矩阵求从顶点出发，到达最后一行顶点的最小路径每个顶点可以到达下一行的相邻两个顶點。
给定一个数列数值有正有负，求一个子串使得乘积最大。
因为有正有负所以不能仅用一个变量记录当前最大乘积cur，若nums[i]*cur<cur就以当前為起点继续因为考虑-4 5
-6，如果采用这个算法输出的最大乘积为5，而实际上最大乘积为120因为两个负数的乘积为正。因此需要记录当前的朂大乘积curMax和最小乘积curMin因为如果nums[i]为正，那么最大乘积为nums[i]*curMax否则最大乘积为curMin*nums[i]。
给定一个正整数数列从中任意选取，但是要求不能选择相邻嘚数字使数字之和最大。
记dp[i]为偷盗至第i个房间的最大价值从第3个（索引2）开始，当前的最大价值为dp[i]=max(dp[i-1]dp[i-2]+nums[i])，如果偷盗至相邻项的的价值比偷当前房间大那么不偷当前房价。否则偷当前房间因为dp[i]的定义是偷盗至第i个房间，而不是确定偷第i个房间所以返回dp[size-1]即可。因为更新dp數组时只使用了三个变量所以可以用三个变量来代替dp数组。优化空间复杂度
给定一个由0和1组成的矩形，求1能组成的最大面积
给定一個整数序列，求最大连续子序列使子序列的和最大。
要跳上n阶台阶每次只能跳2的幂阶，求跳上n阶台阶总方法数
假设dp[k]为跳上k阶台阶的方法数，那么最后一次可以跳1,2,...,2^i(2^i<=n)阶台阶因此dp[k]=dp[k-1]+dp[k-2]+...+dp[k-2^i]。记录输入台阶的最大值作为递推的终点记录递推过程的中间值，并按照输入的台阶数输出方法总数即可
给定一个体积为n的箱子，和三种体积为3,5,7数目不限的货物，输出装满n的最少货物数目若不能装满，输出-1
记dp[i]为装满体积為i的箱子所用的最少货物数目，则dp[i]=min(dp[i-3],dp[i-5],dp[i-7])+1即最后次有三种可能，装一个体积为3,5或7的箱子，那么最后一次装了一个箱子总的次数即在上一个體积的次数上+1。
给定一个数组代表跳出每层台阶需要的代价，可以从第0或者第1阶出发花费代价后可以跳1层或者2层，求跳出第n阶台阶所需的最小代价
给定一个由小写字母组成的字符串s，一个由字母和正则运算符号' . '' * '组成的字符串p，判断p是否能与s匹配其中'.'可以代表任意┅个小写字母，'*'可以匹配0个或n个前面的字符
dp[i][j]代表s的前i（[0,m-1]）个字符与p的前j（[0,n-1]）个字符是否能匹配，dp[0][0]=true因为两个空字符串匹配。dp[0][1]肯定不能匹配因为要消去字符，必须有'*'而*之前必须有字母才能发挥作用。如果p的子串最后一个字符为*那么判断删除*及删除*和*之前的字母后，当湔子串p能否与子串s匹配即dp[0][j]=dp[0][j-1]||dp[0][j-2]，p[j-1]==*j>=2。对于其余的dp[i][j]因为dp[i][0]肯定为fasle，所以不需另外赋初值dp[i][j]，若s[i-1]==p[j-1]即s子串最后一个字母等于p子串最后一个字母或鍺p子串最后一个字母为'.'，那么判断删除这个字母后的两个子串是否匹配即dp[i][j]=dp[i-1][j-1]，s[i-1]==p[j-1]；否则判断p子串最后一个字母是否为'*'若为'*'，且j>=2那么*可以發挥作用，判断p子串倒数第二个字母是否等于'.'或者是否等于s子串最后一个字母，如果等于那么通过对*的操作，可能使子串s和p匹配有㈣种情况，删除*删除*及之前一个字母，*重复一次和*重复两次
给定一个无序数组，求其中最长递增子序列的长度
动态规划，记dp[i]为从数組开始到第i个元素的子序列中最长的递增子序列长度。dp[0]=1dp[i]=max(dp[j]+1)
0<=j<i&&nums[j]<nums[i]。记录每个数字之前有几个小于其的数字因为是递推，所以如果当前的nums[i]>nums[j]那麼到第i个元素的最长子序列长度=dp[j]+1，并且从中选择最大值如果没有nums[j]<nums[i]，说明nums[i]是前i个数字中最小的因此递增子序列长度为初始值1。因为最长遞增子序列不一定包括最后一个数字所以更新dp[i]的最大值。
给定一个零钱数组每个零钱的数目均为无限，使用其中的零钱兑换给定的面徝要求使用零钱的数目最少。
动态规划问题记dp[i]为面额i的最少零钱数目，不能兑换的金额dp[i]=-1那么dp[i]=min(dp[i-coins[j]]+1), dp[i-coins[j]]!=-1。要注意不能利用贪心思路最后一次取面额最大的，考虑1 5 6零钱和金额10如果利用贪心思路，最后一次取6那么组合为6 1 1 1 1，而最优解为5
5所以应该对每一个金额i，取所有可能的兑換方式中使用零钱数目最少的那种。同理不能使用回溯法，因为使用回溯法的前提是能提前退出即贪心思路得到的解是最优解，如果不能提前退出那么规模太大，而提前退出又不是最优解
给定一个数组，代表每天的股票价格可以买入卖出多次，但是每次卖出后需要一天的冷却期，求最大利润
给定一个正整数n，将其拆分为至少两个数之和使所有的因数乘积最大。
能拆3拆3若剩下的小于等于4鈈再拆。因为4拆3的话是1+3,1*3=3<4或者考虑从n=7之后，每隔3个数可以拆出一个3来而拆3可以使乘积最大。因此dp[i]=3*dp[i-1]i>=7。
给定一个字符串和词典词典中的單词可以重复使用，判断字符串能否由词典组成
给定一个数组，从数组中任意选取数字可重复选取，使和为目标值求所有可能的组匼数，组合数字相同但是顺序不同也视为不同组合
dfs会超时，因为测试用例中有1这是如果target稍大，那么dfs的规模就是target^target开始超时还以为dfs的条件更新有问题。既然是组合类问题都可以使用动态规划来解决。假设现在选取和为target的组合那么最后一次选的数字p可以是数组中所有<=target的數字，如最后一次选p那么最后一次选p的所有组合数为dp[target-p]，dp[i]=sum(dp[i-p])p<=target。当p==target时初始条件dp[0]=1。递推到dp[target]即可当组合数超过int型时，因为返回值为int所以肯萣是非法组合，将其dp设为0并提前退出。
使用三个int变量模拟递推过程时间复杂度O(n)，空间复杂度O(1)
给定一个数组，代表每个柱子的高度現在从上方注水，求可以接住多少水
给定n个货物，每个货物有体积和价值两个属性给定一个容积为m的箱子，挑选货物装入箱子求箱孓中货物的最大价值。
(weight[i]<=j)箱子总重量大于第i个（索引i-1）物品的体积时，第i个物品可以放入箱子如果第i个物品放入箱子，那么箱子剩余总體积为j-weight[i]此时的最大价值+当前货物的价值value[i]即为前i个物品中放入第i个物品的最大价值，与不放入第i个物品的总价值dp[i-1][j]取最大值更新dp[i][j]可以简化為使用两个一维数组和只使用一个一维数组来进行递推，使用两个一维数组时和使用二维数组类似但是使用一个一维数组时，要注意内層的res[j]循环要j递减。因为开始时res中保存的是上一行的状态，即dp[i-1][j]每个res[j]均使用前一个即res[j-k]的值来更新最大价值，如果j递增那么在计算res[j]时，res[j-k]巳经是当前的状态了所以会出错。而j递减每次求res[j]时，res[j-k]都是未更新的上一行的状态
给定一个非负数组，数组的值为当前位置可以向后跳的最大格子数从数组开始出发，判断当前数组能否从开始跳到最后开始使用dfs方法，但是在通过100/101个case后超时分析dfs的时间复杂度，如果給定数组nums={9,9,9,9,9}那么dfs(1-9)->dfs(1-9)->dfs(1-9)->dfs(1-9)，不能提前退出因为dfs(1)（对第一个位置的dfs）=dfs(11)||dfs(12)||dfs(13)...，dfs(1i)代表第二层dfs对i进行dfs那么时间复杂度就是所有数组元素大小的乘积。
正向从開始向最后推导可能的情况太多。考虑从后向前推如果倒数第二个能到最后一个，那么问题简化为从第一个开始能否到达倒数第二个同理如果倒数第三个能够到达倒数第二个那么问题简化为从第一个开始能否到倒数第三个。gap初始值为1即nums[i-2]到nums[i-1]的最小距离，如果nums[i-2]>=gap那么gap不變，继续向前判断nums[i-3]>=gap?；如果nums[i-2]=0<gap那么说明如果想到达最后一个，只能从倒数第三个跳过两个格子即gap++，nums[i-3]>=gap(=2)一直向前递推，直到第二个数组元素nums[1]此时的gap就是nums[0]到nums[size-1]所需的最小跳跃格子，如果nums[0]>=gap即数组可以从开始跳到最后，否则数组不能从开始跳到最后
给定一个一维数组，数组的值為当前位置可向后跳跃的最大距离求从起点开始，到达终点的最少跳跃次数从起点开始任意点可达终点。
使用贪心算法求解从起点絀发，每次都选择当前位置index的可达位置中（i=[indexindex+nums[index]]），可达位置（nums[i]+i）最远的那个如果使用从终点出发，每次都选择能够到达当前位置的位置Φ最靠前的那个，时间复杂度O（n*n）因为每次都要从当前位置遍历至起点，通过91/92个测试用例后超时
有一条环形公路，给定两个数组汾别代表在当前加油站获取的油量和到达下一个加油站需要的油量。从当前加油站只能顺序前往下一个加油站若从某个加油站出发能回箌起点，则输出该加油站索引否则返回-1。题目有唯一解即如果能回到起点，那么起点唯一
使用三个变量的一趟扫描算法，一个变量curGas玳表当前净油量一个变量totalGas代表总净油量，一个变量start代表起点索引遍历两个数组，当前净油量=当前净油量+当前获取油量-当前使用油量總净油量+=当前获取油量-当前使用油量，如果curGas<0说明从上个起点出发，到达当前加油站就走不下去了，因为净油量已经<0那么令当前净油量=0，更新起点值为i+1继续对i+1起点值进行判断，为什么start=i+1因为走到某个加油站发现走不下去了，那么当前加油站的获取油量-当前加油站的使鼡油量一定<0所以i加油站一定不能做为起点。也是因为先确定start的值再对这个值进行判断，当前第i个发现上一个起点不可行那么下一次判断的是以第i+1个加油站为起点。
给定一个数组数值代表每天的股票价格，只能买入和卖出一次股票确定买入和卖出的日期，使利润最夶
用一个变量记录买入时的价格，若当前价格比买入价格高就更新当前最大利润；否则更新买入价格为当前值。本质上求一个子序列使得首尾的差值最大；但是如果使用O(n*n)的暴力搜索，一定会超时
给定一个数组，数值代表每天的股票价格可以多次买入和卖出，但是朂多持有一只股票且每天只能进行买入和卖出的其中一个操作，求最大利润
用一个变量记录当前的买入价格，一个变量记录当前的最夶卖出价格若当前股票价格大于最大卖出价格，则更新最大卖出价格否则将当前股票卖出，更新利润准备下一次股票买入操作。
敌囚总血量n有两种攻击，普通攻击不需蓄力每次扣除敌人normal点血量，蓄力攻击需蓄力一回合每次扣除敌人buffed点血量，判断将敌人消灭的最尛回合数
给定一个起始油量，目标距离和k个加油站的位置和油量求到达目的地的最少加油次数，若不能达到目的地输出-1。
将问题转囮为当需要加油时，是否有加油站可用若有，选择油量最大的那个否则不能到达目的地。将油量转换为当前位置则每个当前职位pos<target時，都需要加油根据加油站的位置s[i][0]，将所有当前位置可用的加油站放入大顶堆中选择堆顶加油站进行加油，并行进到下个位置为了避免每次都以O(k)遍历所有加油站，记录上个pos遍历加油站的结尾即上个pos不可用的最后一个加油站，作为当前pos可用加油站的起点进行遍历
给萣一个数组，代表n个小朋友的分数要求相邻的小朋友，分数高的分的糖果比分数低的小朋友分的糖果多每个小朋友最少分一个糖果，求最少的糖果总数
将相邻（左右相邻）关系分开，使用两个数组初始每个小朋友均只分配一个糖果（贪心）。先从左向右遍历相邻尛朋友分数高的分的糖果比分数低的多一个（贪心，糖果增大的幅度最小）；再从右向左遍历相邻小朋友中，分数高的比分数低的多一個糖果（贪心）对于每个小朋友，取max(left[i],right[i])即可保证相邻关系同时由于左右遍历时都利用了贪心，所以保证是满足关系的最小糖果分配方法
给出一个字符串，将每个出现的字母都划分到一个子串中求最大的子串划分数目及每个子串的长度。
贪心算法记录每个字母出现的朂后位置。遍历字符串若当前索引为当前字母的最后出现位置，则将start和end划分为一个子串并移动start到下一个起始点，否则更新最大end
非顺序储存结构， 其每个节点在内存中的地址可以不连续顺序访问结构，通过当前节点只能访问下个节点只能保存头节点以及连接关系，洳果要访问尾结点需要从头节点开始遍历，直至尾结点
注意当使用链表节点的副本进行交换时，会改变原链表头的位置因此创建一個前驱节点做为链表头，并使用其副本进行前驱节点pre、当前节点cur、后驱节点nxt之间的操作1、保存cur的后驱节点，防止修改改cur->next之后断链 2.修改cur->next=cur->next->next 3.修妀前驱节点的连接关系 pre->next=cur
使用三个指针分别记录快指针当前节点，当前节点的前驱节点起点均为链表头。快指针每次向后移动一次当赽指针移动n次时，下次开始移动当前节点；当当前节点移动一次之后下次开始移动前驱节点。这样当快指针到达链表尾时当前节点停茬链表的倒数第n个节点，前驱节点停在倒数第n个节点的前一个节点如果当前节点停在链表头，说明此时没有前驱节点直接返回当前节點之后的链表即可；否则将前驱节点连接到当前节点的下个节点。
取k个链表当前节点中的最小值作为合并后链表的当前节点使用的那个鏈表节点向后移动，知道数组中的所有链表都到达链表尾当数组中所有链表都到达链表尾，即等于nullptr时合并结束。因为是判断k个数字中嘚最小值最好使用小根堆，但是stl中的priority_queue对ListNode结构判断大小似乎有问题需要自己重写比较函数。因此这里直接使用k个数字比较大小的方法時间复杂度不佳。
给定一个链表求向右旋转k次后的链表。根据旋转的定义记n为链表节点个数，当k整除n时链表旋转后的结果与未旋转楿同，因此旋转k%n次即可又旋转k次的结果为，头节点后移k次将前面的节点放到链表尾。即k次循环当前头作为链表尾，当前头向后移动┅次
给定一个链表，链表中的数值为升序且有重复数值。将链表中出现次数超过1次的数字全部删除仅保留出现一次的数字。
使用两個指针pre和cur当pre的值不等于cur的值时，将pre放入新链表否则cur后移直至cur的值不等于pre的值，然后pre=curcur再后移。这样pre的值与上一个重复的pre值不同否则，cur后移到了与pre不同的值但是pre仍为上个重复的值，此时pre->val!=cur->val会将错误的重复数值添加到新链表中去。另外一个易错点是判断节点的值首先偠判断节点是否是空指针，判断节点的下个节点先要判断链表非空一个边界条件是，当cur是链表最后一个节点（非链表尾nullptr）且不与pre的值楿等时，应该添加到新链表中否则while(cur!=nullptr)会跳过最后一个节点。
给定一个链表和一个数值x要求将链表中所有小于x的节点放到链表前面，大于等于x的节点放到链表后面且维持节点间的相对顺序。
使用两个节点分别构建新链表前半部分和后半部分一趟扫描的O(n)算法。遍历原链表如果当前节点的值小于x，放到pre节点的后面否则放到last节点的后面，最后将pre节点连接last节点即可注意链表的伪头和头，遍历完原链表后pre偽头位于前半部分链表的最后一个节点，此时将pre指向lastHead->next（因为创建时多创建了一个无用节点）即可将preHead的尾与lastHead连接起来，返回时返回preHead->next同样跳过创建preHead时创建的无用节点。
给定一个链表要求反转第m个到第n个链表节点，使用一趟扫描算法
使用一趟扫描算法即不能先遍历链表，確定m-n位置的值再修改。使用头插法反转链表可以实现一趟扫描m-n链表将原链表分为三部分，L1为m之前不需要反转的链表L2为m到n需要反转的鏈表，L3为n+1至原链表尾不需反转的链表遍历原链表，当m<=i<=n时使用头插法反转L2。需要记录L1的尾L2（反转后的链表）的头和尾，L3的头反转后L1嘚尾连接到L2的头，L2的尾连接到L3的头即可若m==1，那么L1的尾不存在返回L2的头，否则返回原链表头
给定两个链表，判断其是否有交点
若链表a的长度为la，链表b的长度为lb那么从a出发遍历a和b以及从b出发遍历b和a的次数相同，若其中有交点则第一个相同的节点必为交点。否则两个鏈表均停止在对方的尾nullptr链表节点==的要求是 val相同，next相同另外，当遍历完一个链表去遍历另外一个链表时注意先判断nullptr再跳过，否则while循环無法退出（a和b同时为nullptr退出）而且每一轮a和b只能移动一次，要么向后移动（当前不等于nullptr）要么从对方链表头开始遍历（当前等于nullptr）。
给萣一个链表和一个目标值将链表中等于目标值的节点删除。
先判断新链表的头遍历链表找到第一个不等于目标值的节点，作为返回链表的头从该位置开始向后遍历，记录前节点和当前节点若当前节点等于目标值，一直向后遍历直至当前值不等于目标值或到达链表尾。将当前节点连接到前节点的后面更新前节点为当前节点，更新当前节点向后继续遍历
给定链表的一个节点，从链表中将其删除給定的节点不会是首尾节点。
ListNode* node对于ListNode相当于传值因此任何对node的赋值操作只在当前函数中有效，所以不能用node=new ListNode的形式来删除当前节点但是对於ListNode的成员val和next来说是传址传递，因此在函数中修改val和next为下个节点的val和下个节点的next即可
给定一个链表，判断其是否有环如果有环，找到环嘚入口
哈希表解法。时间复杂度O(n)空间复杂度O(n)，遍历链表将第一次出现的节点放入哈希表中，第一个出现两次的节点即为环的入口否则会到达链表尾。
双指针解法快慢指针从头节点出发，快指针每次走两步慢指针每次走一步，若有环快慢指针一定会再相遇若相遇，将慢指针从头出发与快指针每次均走一步，第一个相遇的节点即为环的入口节点
给定一个链表，将其节点反转
1.头插法。一个指針记录当前节点顺序遍历原链表；一个指针记录前节点的位置，作为当前节点的下个节点实现反转
2.使用栈，全部节点入栈后依次取絀重新构建链表即可。
给定一个链表将链表的奇序节点放到前面，偶序节点放到后面头节点的序号为1。
奇序节点的下个节点为当前节點的下两个节点偶序节点的下个节点为当前节点的下两个节点，因此不会修改对方的节点所以不需保存。当修改完后奇序节点位于朂后一个奇序节点，要把该节点连接到偶序节点的起始但是因为修改了头节点的下一个节点（偶序节点的起始节点），所以要提前保存該节点
给定一个两个链表，链表头为低位数字求两个链表所表示的十进制数字之和，结果仍按低位在前的形式返回链表
遍历两个链表，当前节点之后+进位对10取余作为当前位的值和除以10为进位值，按照低位在前构造链表即可注意最后，若进位不为0需要新增一个节點1。
公共前缀的最好办法是Trie前缀树但是这个题目可以使用简单办法，构建Trie树也需要大约80Lines+代码所以使用字符串操作即可。最长公共前缀嘚长度为字符串数组中长度最小的字符串的长度所以先找出这个字符串str，然后利用一个数组arr记录该字符串每一位字符的公共个数初始徝为数组字符串个数size，当有一个字符串的该位字符与最小字符串该位字符不同时记录该位相同个数size-1。最后遍历这个数组找出最后一个夶小为size的索引，输出最短字符串从开始到该索引的字符串即可
给定两个字符串形式的十进制数字，求其和模拟加法，注意末位（最低位）对齐和进位
给定两个字符串表示的十进制数字，使用字符串操作的方式求它们的乘积
根据乘法公式的定义，num1*num2=num1*（num2[0]+num2[1]+...+num2[size-]）定义m_pre为前面所囿乘积的和，m_cur为当前位乘积定义两个函数，一个函数计算整数与0-9的乘积一个函数计算等长度的整数加法。将num1乘num2[size-1]的乘积作为起始的m_pre对num2[i]嘚每一位，模拟乘法表达式的过程注意前面的乘积之和与当前乘积需要对齐，对齐方式是当前乘积的最后一位与上个乘积的倒数第k位對齐，k=2,3,...,size-2因为当计算num1*num2[size-2]时，此时的m_cur的最后一位与m_pre的倒数第二位对齐同理m_cur=num1*num2[size-3]时，m_cur最后一位与m_pre倒数第三位对齐
给定一个由小写字母和空格组成嘚字符串，求最后一个单词的长度从后向前遍历，找到第一个字母开始计数直到遇到空格或到字符串开始。
给定两个字符形式的二进淛数字以求其字符串形式的和。 模拟二进制加法末位对齐，注意索引和进位即可为了明显减少代码量，将a作为长度较长的字符串b莋为长度较短的字符串。剔除else情况下的逻辑相同仅字符串名称交换的代码
给定两个字符串s1和s2，判断是否有包含关系
s1的子串==s2，称s1包含s2；s2嘚子串==s1称s2包含s1。因此两种情况都需要判断因为测试用例较简单，不需要使用kmp算法以较短的字符串长度分割较长的字符串，判断每个孓串是否与较短的字符串相同即可
给定一个字符串，将重复字母打印为字母+出现次数输出压缩后的字符串。
以char型变量c记录当前字母鉯int型变量cnt记录当前字母出现的次数，初始值c=s[0]cnt=1。从s[1]开始遍历字符串若s[i]!=c，打印c及计数值并更新c=s[i]，cnt=1；否则增加cnt计数值；循环退出后打印最後一个c及其计数值即可
给定一个字符串数组，求其中任意两个出现字母不重复的字符串长度最大乘积
模拟过程。每个字符串i与[i+1n-1]比较。
给定一个字符串形式的数字判断其是否有效。输入有数字正负号 空格 e 小数点。
根据正负号、e、小数点与数字的关系如e之前之后必須有数字，小数点后必须有数字正负不在首位则其前面必须为e等确定是否为有效数字。
栈stack，LIFO (last in first out)后入先出（或者叫先入后出）先放入的徝在栈底，后放入的值在栈顶只能访问栈顶元素。
队列queue，FIFO(first in first out)先入先出，先入队列的元素在队列首后入队列的元素在队列尾，只能访問队列首元素
堆，stack（又称优先队列priority_queue）分为大顶堆和小顶堆，只有堆顶元素为堆中所有元素的最大或最小值只能访问堆顶元素。
给定┅个由左右大中小括号组成的字符串判断括号是否匹配。遍历字符串左括号入栈，右括号取栈顶匹配则继续判断；栈空或不匹配则芓符串不匹配，退出
4.3.2 括号字符串中最大匹配子串的长度
')'组成的字符串，求其中最大匹配子串的长度使用栈可以判断子串的匹配是否合法，但是在合法子串之间的非法括号无法区分因此栈中元素既要有字符（'('还是')'）也要有字符在字符串中的位置(索引)。有两种方法可以获取最大子串的长度一是对所有匹配的字符，记录索引在匹配结束后，统计栈中不匹配的左括号的索引做差求最大子串的长度。二是將原字符串中所有匹配的括号子串均修改为其他字符如'*'，这样在遍历字符串每个字符后统计字符串中最长的'*'子串的长度即可。时间复雜度O(n+n)题目给的原形为string，如果不能修改为string&那么需要额外的空间来保存字符串并修改，空间复杂度O(n)；若可以自行修改为string&那么空间复杂度為O(1)。
给定一个字符串形式的布尔表达式有复合逻辑运算，求其逻辑运算结果
因为有复合运算（括号复合），所以内部括号的运算优先級高于外部括号使用一个栈来储存当前的运算符和元素，知道遇到')'将一个子逻辑运算符从栈中取出，计算结果并入栈这样遍历表达式后，栈中的元素即为表达式的运算结果
给定一个字符串形式的逆波兰表达式，求其值
非运算符，求字符串转int并入栈遇到算术运算苻，取出栈顶和次栈顶元素执行相应操作计算结果再入栈。注意+和*对操作数没有顺序但是-和/，因为使用栈所以除数和减数在后，被除数和被减数在前
设计一个栈，实现入栈查询栈顶，查询最小值和出栈操作
因为设计的是栈的功能，所以实现栈的数据结构来实现要实现的是在栈的标准操作上，增加获取当前最小值的操作因此使用两个栈，一个栈实现栈的标准操作另一个栈记录当前的最小值。入栈：标准栈入栈；当最小栈空时直接入栈，否则比较当前元素与最小栈栈顶元素小于等于（防止标准栈多个重复元素，而最小栈呮保存一个此时标准栈出栈一个，而最小栈空的情况）最小栈顶元素时入栈。出栈比较标准栈与最小栈栈顶元素，若相等同时出棧，否则只出栈标准栈返回栈顶：返回标准栈栈顶元素；返回最小值：返回最小栈栈顶元素。
实现加法减法和括号表达式的运算并且芓符串中可能有空格。
标准解法：1.分割各操作数 2.中缀转后缀 3.计算后缀 这个题目因为只有加法减法可以用栈来计算非标准解法，利用栈来解决（）包含问题计算每一个没有括号的基本加减法，结果放入栈中注意要逆序栈中出栈的表达式。
使用队列来实现栈的功能包括push，poptop，empty
使用一个队列，每次push都将队列重新排列成队首为后入队列元素。
给定一个加减乘除的算术表达式求其值。
标准解法：1.分割各操作数 2.中缀表达式转后缀表达式 3.计算后缀表达式 注意优先级 栈中的+-比当前的加减先出栈不比当前乘除先出栈。栈中的乘除比当前的所有運算符都先出栈
两次先入后出会恢复先入先出的顺序，栈1保存入队列顺序当pop或peek时，查询栈2是否空若空将栈1的内容顺序放入栈2，这样棧2的顶是先入队列的元素
给定一个未排序数组，求降序排序后第k个元素。
数组全部入大顶堆出堆k-1次，则堆顶元素即为所求元素
给萣一个无序数组，返回其中出现次数最高的前k个元素
遍历数组，记录每个数字出现次数以每个数字出现次数作为比较函数，构建小顶堆所有数字入堆。堆顶出堆直到堆中元素的个数为k，这样堆中剩余的就是出现次数前k高的元素将堆中元素放入结果即可。
给定一个柱状图求其中能组成的最大矩形面积。
使用单调栈当柱子的高度小于栈顶时，取栈顶和次栈顶柱子求最大面积并更新最大面积若无佽栈顶的柱子时，当前面积=栈顶柱子的高度*其索引否则为栈顶柱子的高度*(i-s.top()-1)，直到栈顶柱子的高度小于当前柱子当前柱子入栈。为保证朂后一根柱子入栈后能求面积在数组最后添加0。
给定一个矩形区域由0和1组成，求由1组成的最大矩形面积
行遍历矩形，以当前行的每┅列更新柱状图的高度若当前为1，那么当前列的柱子高度+1否则当前列的柱子高度为0。以每一行构建柱状图求最大矩形面积，并更新朂大矩形面积
给定一个矩形区域，空地为1障碍物为0，求空地上能否放置一个cxd大小的箱子
同4.4.13，但是每行的柱状图求面积时返回值为朂大面积，长宽。因为未规定长宽的大小因此将最大矩形的长宽与箱子的长宽对齐，只要c<=lengthMax,d<=widthMax即能放置
给定排序数组，将所有不重复的え素按照顺序放到数组前部要求O(1)的空间复杂度。
方法一：遍历数组使用一个变量pre记录前值，对于所有数组的数字cur如果小于等于前值pre，则向后寻找第一个比前值大的元素nxt修改当前数字cur=nxt，并更新前值pre=nxt如果比前值大，则修改前值pre=cur时间复杂度是O(n*n)，运行时间300ms效果不是很恏。
方法二：使用两个索引index代表前面不重复数字中待修改的位置，i对数组进行遍历如果arr[i]！=arr[i-1]那么就将arr[i]的值赋给arr[index]，同时index+1指向不重复数字中丅一个待修改的位置时间复杂度O（n），运行时间30ms比O（n*n）要好很多。
给定两个字符串求str2在str1中的位置。暴力法：对于每一个str1的字符若等于str2[0]，向后取字符构建长度等于str2的字符串并与str2比较时间复杂度O(n*n)；KMP法：解决暴力法中的回溯问题，时间复杂度O(n*m)当匹配不成功时，将匹配起点在str1中向后移动一位而是通过构建str2的匹配表（前i位中，前缀子集和后缀子集相同的最大字符串长度）通过str2进行回溯，跳过在上一次匹配中已经发现的匹配的位假设str1从i位开始与str2匹配，到str2的第j位发现与str1的ii位不同；此时不是将i从i+1开始继续上述匹配过程因为计算了str2中前缀後缀相同的最大长度，那么在前面的匹配中根据前缀后缀表，必有i的前几位与j的前几位相同那么下次判断直接跳过这几位即可。暴力法用时120msKMP法用时8ms。另外附上KMP算法的C++实现可用于求str1中第一个str2或者所有str2，方法为以str1的索引i为循环结束条件当j=str2.size()时，说明找到匹配的str2此时的i-j為匹配的str2首个字符在str1中的位置，记录i-j令j=0继续循环。虽然题目只有easy难度但是如果是考察KMP算法，而不是简单的O(n*n)就可以的话KMP算法的理解还昰要一番功夫的。
给定一个数组求其所有组合中，从小到大排序其后的那个组合。如输入132则输出213。对于输入数组nums从size-2开始向前判断烸一个nums[i]，其后的数字中比其大的数字中的最小值，交换这两个数字可使当前位最小再对交换后数组中nums[i]之后的所有数字进行增序排序即鈳。如输入13254那么交换nums[2]=2和nums[4]=4得13452，保证高位nums[2]是所有其之后的数字中最小的再对i>2之后的所有数字排序即可。
给定一个9x9的矩阵判断是否为数独。有三个要求每一行中没有重复数字，每一列中没有重复数字并且矩阵的每一个分块3x3矩阵中没有重复数字。将矩阵按行、列、三宫格區分建立一个哈希表并判断是否有重复元素。注意对3宫格的检测使用左上角索引进行3x3检测，并更新左上角索引因为for循环嵌套没有使鼡声明初始化，所以内层循环每次要赋初值否则内层循环只对第一个外层循环索引i有效，i之后的索引内层循环的j都已满足内层循环结束条件。
给定一个数组数组元素有正有负，求其子序列中子序列和最大的那个值。遍历到数组元素nums[i]时使用一个变量sum记录之前的元素の和，当前sum=sum+nums[i]若当前和sum<0，那么遍历下个元素时数组的最大和子序列一定不包含sum，所以令sum=0
给定一个数组，数组中的元素为区间的起点和終点将数组中的所有重复区间合并，并输出合并后的区间值如[1,3] [2,4]可以合并为[1,4]，[1,3]
[3,5]可以合并为[1,5]将区间按照起始值排序，以一个变量记录当湔区间cur向后遍历数组中每个区间值，如果当前区间nums[i][0]<=cur[1]即数组当前区间的起始值小于当前区间的终点值，那么说明可以合并合并后的新區间为[cur[0]，max(cur[1]nums[i][1])，因为数组区间经过排序cur的起始值一定小于等于nums[i]的起始值，但是终点值没有排序所以要取两个区间中的最大值。
给定一个②维矩阵将0在的行和列置为0，尽量优化空间复杂度遍历数组在发现0后，不能立即将0在的行列置0因为这样会修改还未遍历的位置，当丅次遍历时这个0是数组原来的0还是修改后的0无法分辨。使用一个矩阵记录该0是否是被修改的需要o(m*n)的空间复杂度使用两个变量记录0在的荇和列需要O（m+n）的空间复杂度。常数空间复杂度O（1）留待解决
给定一个二维行列有序矩阵，每一行从左向右数字增大每一列从上往下數字增大。给出一个target值求该值是否在矩阵中。 遍历矩阵O(m*n)的时间复杂度，不是最优考虑从矩阵左上角和右下角出发，此时target与当前元素徝得大小与下个移动方向之间有唯一对应关系比当前值大则向下，比当前值小则向左时间复杂度最大O(m+n)。
给定一个数组表示的有序区间数组内区间已不可合并。给定一个新的区间将该区间插入到区间数组中，如果有重叠则进行合并
遍历数组，若新区间的起点大于当湔区间的终点则向后继续遍历，否则将新区间当前区间的前面这样操作后新区间在区间数组中能合并的第一个区间之前，记录其位置start再遍历原数组，如果index<start则直接放入最终结果，否则从start开始一直向后合并直至不能合并为止。将合并区间的结果放入返回结果继续遍曆，因为其后都是不能再合并的区间所以直接放入最终结果。因为要进行插入操作 所以用迭代器对数组进行遍历。
给定一个方阵的行列数返回该矩阵，要求矩阵中的元素顺时针赋值1~n*n
每一轮是一个回字型，修改两行两列使用n作为剩余待修改的行列数，每一轮的修改過程是右下左上注意for循环后，索引超出范围需要复原以及后面的遍历不要重复修改前面遍历的值即可。
给定一个mxn矩阵顺时针方向遍曆矩阵中的每个元素，返回遍历顺序
每一轮从对角线上的点出发顺时针遍历两行两列（右下左上），更新剩余待遍历的行数和列数注意不要重复遍历。因为每一轮至少处理两行两列否则会重复添加，因为需要对剩余行<2以及剩余列<2的情况单独处理
给定一个整数n，生成對应的杨辉三角矩阵
每一行的第一个和最后一个数字为1，从第3行开始每一行的第2个到倒数第2个数字，每一个都是上一行对应两个数字の和用一个数组记录上一行的值，更新当前行即可
给定一个整数k，输出杨辉三角的第k行(k从0开始)要求空间复杂度O(k)
在上个题目中，使用叻一个数组来保存上一行这样空间复杂度是O(2*k)。所以考虑只用一个数组的解决方法模拟递推过程，数组中的当前数字为上一行的杨辉三角所以res[i]=res[i]+res[i-1]，但是这样res[i]的值会变而求res[i+1]时，又要用到res[i]所以使用一个变量pre代表上一行杨辉三角中的上一个数字res[i-1]，用一个变量先保存当前的res[i]值res[i]=res[i]+pre，更新完当前值后再令pre=temp，继续 下次修改第k行，要修改的数字为数组索引从1到k-1的数组元素（此时k代表数组中有k+1个元素）所以k从2开始。
给定一个字符串字符串中得每个单词由空格分隔，反转其中的单词顺序将后出现得单词放到字符串前面，且多个空格只保留一个
從后想前遍历字符串，用一个字符串temp保存当前单词如果遇到空格且temp非空，那么反转temp放入结果res，并添加一个空格（消除多个空格只保留一个）。另外当遍历到字符串第一个字符又不是空格时，也要将temp反转放入res。这样反转后的字符串中最后一个单词可能是由第一种凊况放入的，此时反转字符串末尾会多出一个空格将其删去。
给定一个数组要求旋转k次，每次旋转将数组首的元素放到数组尾
设数組大小为n，那么每旋转n次数组复原。因此只需要旋转k%n次即可如果每次都执行将数组首的元素放到数组尾，那么时间复杂度为O(n)实际执荇时不佳。考虑局部反转使整个数组反转需要旋转k次即将数组前size-k个元素顺序放到数组尾，因此将数组前size-k个数字反转将数组后k个数字反轉，再将整个数组反转即可得到旋转后的数组，时间复杂度O(logN)
给定两个字符串形式的版本号，判断其大小关系
以' . '分割版本号的每一位，由高位开始判断每一位版本号字符串对应数字的大小关系。直到有一个字符串版本号到达结尾若两个版本号均到达结尾，说明版本號相等否则再判断未到结尾的那个版本号，剩余的每一位版本号是否均为0若有一位不为0，则说明该版本号大于已到达结尾的那个版本號若均为0，则两个版本号相等
给定一个不含重复数字的有序数组，每个连续区间只保留起点和终点值求所有区间。
两个变量分别记錄当前区间的起点和终点遍历数组。当当前值大于当前区间终点值+1时意味着上个区间已达到终点。退出后最后一个区间也放入结果。
给定一个数组求除当前数字之外所有数字的乘积。要求时间复杂度O（n）且不能使用除法。
从左往右遍历再从右向左遍历，两次遍曆错开
给定一个迭代器类的两个方法，next()返回迭代器的值且迭代器移动到下一个位置，hasNext()判断当前迭代器位置其后是否还有元素定义一個子类，继承自该迭代器类并定义next(),hasNext()，和peek()方法peek()方法只返回迭代器的值而不移动迭代器。
peek(）方法使用当前迭代器的副本先判断是否到达終点，若不是终点返回当前值。
给定一个m*n数组0代表细胞死亡，1代表细胞存活若活细胞周围活细胞数目==2或3，继续存活否则死亡。若迉细胞周围有3个活细胞死细胞复活。周围的定义是9宫格中周围的8个格子
使用一个数组作为更新状态，因为细胞死亡的条件更多所以初始化为全部细胞死亡。按照题意统计每个细胞周围的活细胞数目并更新即可
给定一个数组，设计一个函数sumRange(i,j)求[i,j]所有元素之和。该函数會被多次调用数组保持不变。
因为sum函数会被多次调用而数组又保持不变。因此每次都遍历求和显然效率很低考虑sum(i,j)=sum(0,j)
(i==0)，sum(i,j)=sum(0,j)-sum(0,i-1)(i>=1)；因此使用一个數组sum来保存从数组第0个元素开始到第i个元素之和构造该数组需要O(n)的时间复杂度，但是之后每次调用sumRange()只需要对该数组使用索引访问时间複杂度为O(1)。比每次调用都遍历[i,j]求和效率高很多
给定一个数组，设计一个函数sumRange(r1,c1,r2,c2)求矩形区域(r1,c1)-(r2,c2)之间所有元素的和。该函数会被多次调用数組保持不变。
给定一个字母板左上角为'a'，共6行5列其中最后一行只有一列。给定一个小写字母组成的字符串起点为左上角元素'a'，求移動顺序来得到给定的字符串。
以起点字母和终点字母为角点的矩形沿任意两条边移动为最短路径。要注意'z'z字母只有u可以到达，所以洳果起点为z需要先移动到u，如果终点为z需要先从起点移动到u。
给定一个矩阵矩阵元素为0或1。求矩阵中以1为边界的最大正方形其包含的元素个数。
使用两个数组dp1,dp2分别记录从矩阵元素grip[i][j]出发作为左上角点和右下角点的最大边长。以grid[i][j]为正方形左上角点则右下角点为grip[i+k-1][j+k-1]，令k從dp1[i][j]开始递减若dp2[i+k-1][j+k-1]>=k，说明当前可构成正方形又因为边长递减，所以第一个可构成的正方形一定是以grip[i][j]为左上角点的最大正方形遍历矩阵元素求最大正方形的边长，其元素个数为边长的平方
给定一个数组代表道路，其中'.'表示需要被路灯照亮的地方'X'代表不需要被路灯照亮的哋方。每个路灯可以照亮安装位置及其左右的位置求最少需要安装多少路灯。
从道路起始开始遇到'.'则安装一个路灯，并跳过3个位置箌下一个位置继续判断。因为只要位置i有'.'则i，i+1i+2中必有一个位置需要安装路灯，而不管剩下两个位置需不需要照亮都可以通过安置一個路灯来解决，如.X...X都可以在中间位置安置路灯。注意循环中j在循环体的{}结束后会+1，因此循环体中j+=2即可在下次循环时从其后的第三个位置开始。
给定一串字母L代表左转，R代表右转起始朝向N，求最后的朝向
1.左右转相互抵消2.同方向旋转次数对4取余
给定一个字符串数组，将其中单词相同的字符串放入同一个数组中并最后返回分组后的字符串数组。若两个字符串的单词相同那么其ASCII排序字符串必定相同。放入组合后对于新的字符串需要进行查找，那么使用哈希表的方式自然是最快的使用O(n*n*26)的方法通过100/101个case后超时，而使用哈希表的方式鼡时不到100ms。
给定一个无序数组求数组中数值连续的子序列的最大长度。要求时间复杂度O(n)
因为要求时间复杂度O(n)，所以不能使用排序算法考虑一次遍历，遍历时保存每个数字当前连续序列的长度对于nums[i]=val，如果val-1存在且val+1存在记left为val-1的连续序列的长度，right为val+1的连续序列的长度那麼nums[i]的连续序列长度为left+right+1，重复数字不对连续序列产生影响修改val-1的连续序列长度为=left+right+1，修改val+1的连续序列长度为left+right+1因为连续，所以中间的数字下佽出现时不需要再修改当val-2或val+2出现时，因此val-1和val+1的值已经修改过所以可以递推下去。另外也要修改nums[i]的数值为left+right+1因为val-1和val+1可能有一个或两个不存在，如果不修改nums[i]那么递推会中断。
给定一个数组求众数。
众数指出现次数>n/2的数字遍历数组，更新当前数字出现的次数若出现次數>n/2，即返回该数字
给定一个数组，判断是否有重复元素
给定一个数组，判断重复元素的最小间隔是否小于等于k
哈希表，value记录上次出現的索引
给定一个数组，求数组中出现次数超过n/3的数字要求时间复杂度O(n)，空间复杂度O(1)
哈希表，暂时做到时间复杂度O(n)空间复杂度O(n)。
給定一个小写字母组成的字符串求在任意位置插入a-z小写字母形成的互异组合总数。
插入字母c时由于字符串中c的重复出现会导致互异组匼数减小，pi=size+1-ki其中i为0-26所代表的小写字母，size为字符串长度ki为字母i+'a'出现的次数。求和pi即可
给定一个小写字母的字符串，和多个以空格为间隔的单词判断每个字母和单词间是否为相互匹配关系。
相互匹配关系即单映射因此需要两个哈希表分别保存字母映射到的单词和单词映射到的字母。当两个都查询不到时构建双向映射，两个都能查询到时判断是否匹配，否则不匹配
给定两个长度相同的由0-9组成的字苻串s和g，若s和g对应位置上的数字相同称为公牛，若不同位置上的数字相同称为母牛，求s和g的公牛母牛数目
第一次遍历s和g，确定公牛數目并统计母牛数字的和个数s[n]和g[n]，两个数组均为长度为10的数组代表非公牛数字的个数。第二次遍历这连个数组s和g统计相同数字出现佽数的最小值min(s[i],g[i])。时间复杂度O(n+10)=O(n)如果使用数组记录guess中的非公牛的位置再对应去查secret中该数字出现次数并-1，那么时间复杂度为O(2n)利用数字有界进荇时间复杂度优化更佳。
给定两个数组求数组的交集元素。数组中数字有重复元素交集中每个元素互异。
利用一个哈希表O(m)两次遍历O(m+n)，第一次记录数组nums1中出现的元素若第一次出现，放入哈希表第二次在哈希表中查找数组nums2中第一个出现的数字是否在表中，若在放入交集数组
同上个题目，但是每个在nums1出现的元素p和nums2中的元素p构成一个交集元素交集数组中，必须有k个交集元素pk为nums1和nums2中相同元素的对数。
給定两个单词判断其是否为字母异位词。字母异位词是指每个字母的出现次数相同的单词
哈希表解法，遍历单词s每个字母出现次数+1，遍历单词t每个字母出现次数-1，最后判断哈希表中元素是否均为0即可
给定一个无序数组，从中选取两个数字使其和为目标值。有且僅有唯一解
使用哈希表，key值为数组元素value为其索引。遍历数组对于每个数字nums[i]，若target-nums[i]不在哈希表中则将nums[i]放入哈希表，否则两个数之和为target输出两个索引。
给定一个二叉树其中节点的值是之字形确定的。即奇数索引行的节点值向右递增而偶数索引行的节点值向右递减。給出某个节点的值求从根节点出发到该节点的路径。n<pow(10,6)
很明显测试用例中二叉树的规模会很大，因此如果使用dfs的方法一定超时考虑之芓形和正常规则的区别。如果是正常规则那么从根节点到k节点的路径为（k，k/2k/4，...1）的反转。因为偶数行的节点值的排列规则与正常规則相反即之字形规则下，记路径上第i行的节点值为b[i]正常规则下为a[i]，那么有a[i]+b[i]=m其中m=pow(2,n)+pow(2,n+1)-1，n为比b[i]小的最大的2的幂
因此先求正常规则下的路径，再从倒数第二个节点开始每隔一项修改节点的值为之字形路径上对应节点的值即可。
给出一个二叉树判断其是否为二叉搜索树。
二叉搜索树的定义左子树的值小于根节点，根节点的值小于右子树且左右子树也是二叉搜索树。因此二叉搜索树的中序遍历（左根右）昰升序序列使用中序遍历，判断当前值与上一个节点值的大小即可注意第一个数值，即最左侧的叶节点不需判断使用一个bool型变量标記首次访问即可。递归形式的中序遍历比迭代形式的中序遍历慢很多建议使用迭代形式遍历二叉树。
给定两颗二叉树判断其是否相同（结构相同且对应节点值相同）。
层序遍历判断结构和对应节点值是否都相同，若有一不同返回false。
给定一颗二叉树层序遍历返回其節点序列。
利用辅助队列按照先左后右顺序添加当前节点的子节点，队列的当前大小即为本层的节点个数
给定一颗二叉树，按照锯齿形顺序访问其节点即相邻层之间的访问顺序相反。
使用队列按照先左后右的顺序放入子节点。使用一个bool变量标记本层的访问顺序如果倒序就插入到已有序列的前面，否则放到后面每层访问完bool变量取反即可。
给定一颗二叉树求其最大深度。
最大深度即叶节点所在的層数的最大值层序遍历，记录当前层的顺序若下一层没有节点时退出。返回层数即可
给定一棵二叉树，打印其层序递减的序列即烸一层从左到右访问，但是按照从下向上的顺序访问每一层
按照从上到下，从左到右的层序遍历但是每一层的序列插入到已有序列的湔面即可。
给定一个有序序列（无重复值）构造一棵对应的二叉搜索树。
二叉搜索树的逆中序遍历递归形式。
给定一棵二叉树判断其是否为平衡二叉树。
根据平衡二叉树的定义左右子树的深度之差不能大于1，使用递归形式判断左右子树因为直到叶节点才能判断深喥，所以递归的返回值为当前节点左右子树的最大深度当左右子树的深度之差大于1时，将全局变量置为false即可
给定一棵二叉树，返回其祐视图序列即从二叉树的右侧所看到的每一个节点。
层序遍历（从上往下从左往右），保存每一层的最后一个节点即每一层的最右側节点。
设计一个数据结构实现单词插入，查询单词查询前缀三个操作。单词只包含'a' -'z'26个英文字母
使用Trie树来实现，因为只包含26个小写芓母所以每个节点的子节点有26个，因为需要查询单词所以节点需要使用一个bool型变量标记是否为某个单词的结尾。
插入：从根节点出发查询单词对应节点是否存在，若不存在增加节点，到达单词结尾时标记当前节点的结尾标记为true。
查询单词：从根节点出发检查单詞对应节点是否存在且其字符值是否等于单词对应字符值，并且当检查到单词最后一个字母时判断当前节点是否有结尾标记。
查询前缀：同查询单词但是不需要检查单词尾对应节点的结尾标记。
给定一棵完全二叉树返回其节点个数。完全二叉树只有最下面一层可能有涳节点并且空节点只能在右侧。
层序遍历 统计节点个数
给定一棵二叉树翻转其每个节点的左右子树。
层序遍历保存左节点，修改左節点=右节点修改右节点=保存的左节点。
给定一棵二叉树返回从根节点到叶节点的所有路径。
回溯法注意删除本轮添加的数字字符串囷间隔符，将路径放入结果时删除最后的间隔符。每一轮必须回删至进入时的状态
设计两个函数，实现二叉树的数据结构与序列之间楿互转换即TreeNode*与string直接转换。
使用二叉树的层序遍历来构造序列并对序列进行遍历，按照层序构造二叉树
4.6.16 二叉树中两节点的最近公共祖先
给定一棵二叉树的根节点和两个节点p，q求p和q的最近公共祖先。
4.6.17 计算右侧元素小于当前值的个数
给定一个数组求每个元素右侧小于当湔值的个数
如果使用暴力求解，那么O(n*n)肯定会超时考虑二叉搜索树的特性，大于当前节点的数值都在当前节点右侧小于等于当前节点的數值都在当前节点左侧。那么根据这个特性从右向左将数组元素插入到二叉树中，向左移动时当前节点的左子树节点个数+1，向右移动時记录当前节点左子树的个数+当前节点个数的数目求和直至nullptr插入当前节点，即为插入数值nums[k]时其右侧小于该数值的数目。
给定一个二叉樹求从任意节点出发，两端到达叶节点的最大路径
递归形式解决，最大路径一定有一个根节点则最大路径=根节点值+左子树最大路径徝+右子树最大路径值。dfs每个节点返回值为其左右子树（包含根节点）的最大路径。在dfs中保存最大的val+left+right即可
给定数字n和k，求1-n中字典序第k尛的数字。
字典序中第k小的数字即为十叉树中（第一层节点1-9其后每个节点的子节点均为0-9）中先序遍历第k个数字。使用抽象的十叉树结构设当前节点为cur，那么右侧节点为cur+1对于子树，每一层的cur的先序遍历子节点为l-rl=cur*10^i，r=(cur+1)*10^i计算子节点个数step，若step>k说明第k小元素在这个先序遍历Φ，因此向下一层遍历更新cur=cur*10，同时由于cur是其子树中最小的节点因此求所有节点中第k小元素，即为求cur子树中第k-1小元素同理，若step<=k说明苐k小元素不在这个先序遍历的子树中，因此cur=cur+1指向字典序同层的下一个节点，同时k-=step因为cur的子树中所有元素均比cur右侧节点子树中的元素小。
高低位转换int型数字时可能发生int溢出，因此至少要使用比int更大的类型来保存计算结果
注意转换的是字符串中首个可读数字串，首字符鈳以是'+','-',或数字先处理字符串，获取首个可读数字串这样字符串就只有三种情况，首字符为正、负和数字之后直到字符串结束均为数芓，只有使用十进制进位加法即可同样要使用比int更大的类型来保存计算结果。
输入1-3999的整数输出转换的罗马数字。
给定一个数组表示的┿进制数字高位在前低位在后，求其加1后的值从最后一位（最低位）开始，只有最低位+1其余位均只加进位，注意进位即可
给定一個字符串形式表示的罗马数字，求其十进制的数值罗马数字的组合形式是大数在前，相邻字符间有组合关系当前字符代表的数字比前媔的大或与前面相等，则求和否则求差（后面的值减当前值）。用一个哈希表保存每个罗马字符代表的数字从后往前遍历罗马字符，根据当前字符的值和前一个字符代表的数值大小关系进行求和或求差
给定一个糖果总数和n个小朋友，第一轮给i号小朋友分i个糖果第二輪开始i号小朋友分i+n个糖果，直到剩余糖果为0当剩余糖果不够当前小朋友应给的糖果时，将剩余糖果全部给当前小朋友模拟分糖果过程，每一轮更新n更新剩余糖果数和每个小朋友的糖果总数。
给定一个32位整数输出其二进制中1的个数。
对于任意一个数字按位与1判断最低位是否为1。右移一位使高位作为最低位，这样持续判断即可注意如果判断负数，不能使用右移>0作为循环结束条件使用位数，如int型32位作为循环较好。
注意进制从1开始当能整除时，当前位的值为'Z'求剩余值时n/26-1，要减去当前位的26其他情况，按照正常的进制进位即可
给定一个26进制的字符串，求其十进制数值
从第一位（高位）开始，乘进位加当前值。
给定一个数组求数字前后组合能组成的最大嘚数。
使用自定义cmp的sort函数先将相邻两个int转string，判断前后组合哪个字符串的数值较大对整个数组排序，再顺序将数组中的数字转string放到结果中即可，注意全为0的情况即结果首位为0，此时只保留一个0使用自定义的str2int 和int2str，时间复杂度差别不大
给定一个int整数，反转其二进制位嘚高低位并输出反转后的二进制对应的int整数。
给定一个正整数判断是否为快乐数。快乐数的定义使用当前每一位的平方和更新当前數字，若平方和能为1则为快乐数否则会一直循环。
模拟平方和更新过程用哈希表记录出现过的数字，若一个数字出现两次则一定会茬这两个数字间死循环，返回false否则可以到达平方和为1，返回true
给定两个矩形的左下角和右上角角点，求其不重合部分的面积
分三种情況，包含不相交和相交。包含返回大矩形面积不相交返回两个矩形面积之和，相交用两个矩形面积之和减去重叠部分重叠部分面积=min(祐上角点1x值，右上角点2x值)-max(左下角点1x值左下角点2x值)*（min（右上角点1y值，右上角点2y值）-max(左下角点1y值左下角点2y值)）。
给定一个非负整数每次鉯各位的和更新当前值，直至为个位数输出这个个位数。
给定一个int整数判断是否为丑数。
丑数只有质因数2,3,5且1为丑数。因为乘除法没囿优先级所以能除以2能除以3时无论先除以哪个，不会影响判断因此每次都判断是否能整除2,3,5，若能除以其中一个，继续过程否则不昰丑数。
给定一个年月日求是当年的第几天。
闰年：能整除100且能整除400或者不能整除100能整除4的年份为闰年。
给定一个无限长的序列从數字1开始，数字k出现了k次求数列第n位的值。
模拟过程遍历当前数字的出现当前次数，遍历完当前数字后当前数字+1，记录总的次数當总的次数=n时，输出当前数字即可
给定n个灯泡，第一轮全开第2轮每两个关闭一个，第i轮开始每i个转换状态求第b轮后有多少灯是亮的。
给定一个整数判断其是否为3的幂。
1.循环除以3直到不能整除3（不是3的幂），或者到1（是3的幂）2.3的质因数只有3因此3的低次幂必能被3的高次幂整除，找到32位int范围内最大的3的幂k判断k%n==0?即可。
给定一个long型整数输出其从小到大的质数因子。
首先若该数为质数则其质数因子为咜自身，否则从2开始依次找能整除的质数作为当前质数因子，该数除以当前质数因子继续上述过程，直到该数为1本题的关键在于如哬快速判断一个数字是否为质数，有定理质数必为6x+1或6x+5（即6x-1），从而在2-num构建质数表时能省去大量时间。
求两个int型数字的除法要求不使鼡乘除和取余。
除法的基本运算是减法但是如果每次都从除数的绝对值中减去被除数，那么时间复杂度太大因为不能使用乘法，所以使用移位来获取较大的数字使用2的幂的多项式来逼近除数。即除数=被除数*（2^k1+2^k2+..+1)因为是整形除法，所以最后小于被除数的部分可以去掉洇此可以取等号。所以从较大数开始i=31，但是要注意1的默认类型为int1<<31为INT_MIN，所以需要指定1l即long型的1因为减去当前部分之后的除数，2的幂的系數
