说不清楚，只能看代码理解的用红色标出
查找算法：查找较排序来说较简单，不外乎顺序查找和二分查找、哈希表查找和二叉排序树查找。（很多面试官喜欢让应聘者写出二分查找（如test53）的代码）【注意：二分查找传入的必须是排好序的数组】
排序算法：面试官经常会要求应聘者比较插入排序、冒泡排序、归并排序、快速排序等不同算法的优劣，作者强烈建议应聘者在准备面试时，一定要对各种排序算法的特点烂熟于心，能够从额外的空间消耗、平均时间复杂度和最差时间复杂度等方面取标胶他们的优缺点。（很多面试官喜欢让应聘者写出快速排序、归并排序(test51考察的就是归并排序)的代码）
树的遍历：通常分为两种：深度优先和广度优先。深度优先又细分为三种：前序遍历、中序遍历和后序遍历，对应的程序可以用递归实现，也可以用循环实现（循环实现的方法有点难）。一种有特殊顺序的二叉树称为二叉搜索树。（很多面试官喜欢让应聘者写出红黑树、B+树的代码）
面试题7：重建二叉树
先考虑一般情况，用递归的方式创建二叉树，再考虑特殊的，两种情况：先/中序遍历都是空；先/中序遍历都只有一个节点；
创建好二叉树后，进行特殊情况的测试，两种特殊情况：①根节点为空；②先序遍历和中序遍历序列不匹配；
最后用先序遍历的方式打印一下二叉树（在本代码中遍历二叉树时，会出现空值，可在打印前加个条件语句判断一下，具体原因在demo中有解释）
思路：先根据前序遍历找到根节点，然后再根据根结点的将中序遍历且分为左右两颗子树，再根据子树的长度切分前序遍历，从而切分出小的先序遍历和中序遍历，然后循环以递归的方法解题
面试题8：二叉树的下一个节点
题目：给定一颗二叉树和其中的一个节点，找出中序遍历的下一个节点。其中已知该节点的左右子节点和该节点的父节点。
思路：
先在纸上画一颗满二叉树
情况1：如果该节点有右子树，则下一个节点就是右子树的最左节点(用while寻找右子树的最左节点)；情况2：如果该节点没有右子树，且其是左子树下的，则下一个节点就是其父节点；或者其是右子树下的，则下一个节点就要一直往上溯源，否则返回None
面试题9：用两个栈实现队列
题目：用两个栈实现一个队列。队列的声明如下，实现它的两个函数appendTail和deleteHead, 分别完成在队列尾部插入节点和在队列头部删除节点。
思路：
首先清除一点：列表类似于栈，所以可以用列表创建两个栈stack；其次，在添加元素时都添加到stack1；在输出时，判断stack2是否为空，为空则把stack1的元素pop进stack2，若stack2不为空，则直接pop stack2的元素；
这样就通过两个栈构造出了队列。
面试题10：斐波那契数列
题目一：求斐波那契数列的第n项。写一个函数，输入n，求斐波那契数列(Fibonacci)的第n项。（结合第二部分的12，也是斐波那契数列但是多了一种临时变量的解法）
【斐波那契数列：f_0=0, f_1=1, f_2=f_0+f_1=1, f_3=f_2+f_1=1+1=2, f_4=f_3+f_2=2+1=3, 以此类推】
题目二：青蛙跳台阶问题。一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶，求一只青蛙跳上n级台阶总共有多少总跳法。
思路：
题目一：
首先想到的方法就是用递归的方式，从上至下的求解，而且递归的方式demo简捷，但是递归的方式每次都会重新计算一遍，会增加徒劳的计算量；进一步升级用循环的方式从下至上求解，前面的值可以保存下来供后面使用，算法复杂度为O(n), 而且性能更优计算n=3000都没问题，而递归n=30就开始卡了;
题目二：
这道题的关键在于怎么把该问题转换为斐波那契数列的问题。
把n级台阶的跳法看作n的函数，记为f(n), 若第一次跳1级，剩下f(n-1); 若第一次跳2级，剩下f(n-2), 所以n级台阶的跳法为f(n)=f(n-1)+f(n-2)
相关题目：用一个2*1的矩形去覆盖2*8的矩形，问有多少种覆盖方法？(类似于unknow3矩形覆盖这个题)
总结（仅供参考）：可以转换为斐波那契数列的问题通常具有以下特征：
涉及1或2（倍数也行）；最后问有多少种方法；遇到满足上述条件的，一定要用循环去解题，用递归性能严重不足。
面试题11：旋转数组中的最小数字
旋转数组中的最小数字。把一个数组最开始的若干元素搬到数组的末尾，则称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素，如[3,4,5,1,2]为[1,2,3,4,5]的旋转，该数组的最小元素为1.
思路：
先考虑较为一般的情况，[4,5,6,1,2,3]，找两个游标，分别标在第一个、最后一个元素，再找一个游标标在中间元素，根据旋转数组的本身特点，中间元素与cur1、cur2比较，若大于等于cur1的元素，则将cur1重标在此位置；若小于等于cur2的元素，则将cur2重标在此位置，以此循环缩小范围；在进一步考虑特殊情况：①把0个元素搬到数组的末尾，这种只要确定cur1的元素小于cur2的元素且cur1的元素不等于mid的元素(为保证该数组的数字不全相同), 则输出cur1；②cur1、cur2、mid指向的元素都相等，此时只能使用顺序查找的方法寻找最小元素【注意：在进入顺序查找进行分析之前，先用set判断一下该数组是否只有一类元素】
面试题12：矩阵中的路径
矩阵中的路径。设计一个函数用来判断一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵的任意一格开始，每一步都可以在矩阵中向左、右、上、下移动一格。如果一条路径中包含了矩阵的某一格，那么该路径不能进入该格子。【提示：用的是回溯法，回溯法适合有多个步骤且每个步骤都有很多选项的问题，通过遍历式的尝试找到最优的可行方案】
思路：采用回溯法进行解题，每到一个格子都有上下左右四步走法，用循环用第一行第一列的元素开始往下寻找，若该位置的元素等于要寻找的元素时进入递归以查看其上下左右是否能匹配下一个元素，否则返回上一级；其实就是找到首字母后才会进入递归，进一步判断其上下左右是否有符合的，否则重新返回到for循环，寻找下一个匹配成功的首字母。【稍微有点绕】
面试题13：机器人的运动范围。
机器人的运动范围。地上有一个m行n列的格子。一个机器人从坐标(0,0)的位置开始移动，每次可以向左右上下移动一格，但不能进入行坐标和列坐标位数之和大于k的格子。如k=18时，机器人可以进入(35,37), 但不能进入(35,38)。问该机器人能到达多少个格子？
思路：对比：矩阵中的路径中使用了for循环先匹配首字母，匹配成功后在其上下左右匹配下一个字母，匹配成功后，再匹配下一个字母；否则表明该路径不通，重新用for匹配首字母； 机器人的运动范围中没有使用for，因为这个题不用先匹配首字母再匹配下一个，相当于首字母给出，需要不断以上下左右的方式寻找满足条件的下一个，直至到路的尽头为止，具体还得结合demo理解。问题：movingCountCore()的递归没有绕明白，check通过进入一个点后，开始上下左右测试，先上递归，上面如果通过check，在这一个点再上下左右递归，直到到达尽头为止【有点不撞南墙不回头的意思，在一个满足的点上，没有找到尽头是不会结束递归的】
面试题14：剪绳子。
剪绳子。给你一根长度为n的绳子，请把绳子剪成m段(m、n都是整数，m、n>1, 【可知：m的取值范围为大于等于2，小于等于n】)，每段绳子的长度记为k[0]、k[1]、k[2]、...、k[m]。请问k[0]*k[1]*k[2]*...*k[m]的最大乘积是多少？例如当绳子的长度为8时，可以剪长度为为2、3、3的三段，此时得到的最大乘积为18。
思路：两种方法。①用动态规划的方法，自下而上的解题(也可以用递归的方式自上而下解题)，关键在于li的定义及其存放的元素的定义(li里的第i个元素指长度为i时的最大乘积，其中0,1,2,3给出的是剪0刀时的最优解)，循环中的i表示当前绳子的长度，j表示剪一刀下去，其中一段的长度，则i-j表示另一端的长度；②用贪婪算法进行解题。难点：要能把一个具体的场景抽象成一个能用动态规划或贪婪算法解决的模型，具体参考书中6.4节。
贪婪算法解题时，为什么是3的k次方，如下图所示：
面试题15：二进制中1的个数
二进制中1的个数。实现一个函数，输入一个整数，输出该数二进制中1的个数。如9的二进制为1001，有2位是1，因此返回2。
注：Python中没法做，用书上的左移解题时，python中并不会说到64/32结束，会一直左移下去，那么这个数就会一直变大；关键是负数不好处理，牛客网的题中标明负数用补码表示，也有网友给出了2**32+n(n<0时)(可以转为补码)，但是这是针对32位计算机的，64位的就是64，而且当这个数非常大时，加2**32还是负数，此时就不再适用了；我在写出的demo为负数还是统计原码中1的个数，针对补码时就不对了。
new method
================================================================================================
题目：实现一个函数，输入一个整数，输出该数二进制中1的个数。如9的二进制为1001，有2位是1，因此返回2。(其中负数用补码表示)
思路：
python比较特殊，不管数有多大都不会溢出，所以在此只取前32位(n = 0xFFFFFFFF&n 一个F是4个1)
①将截取的32位数字转换为二进制，再转换为字符串统计1的个数；
②将数字左移统计；
③在while中n=n&(n-1),count+=1, 每次n&(n-1)都会减去二进制中的一个1
面试题16：数值的整数乘方
数值的整数次方。求base值得整数次方，不得使用库函数，同时不用考虑最大数的问题。
思路：
①要考虑全面。有正整数次方，也有0和负整数次方，正整数直接相乘即可，0直接返回1，负整数在正数的基础上取倒数②方法一，直接使用循环e个数相乘解题，但是时间复杂度较高③方法二，用递归解题逐层递归自上而下，时间复杂度好像第一点, 当n为偶数时，, 当n为奇数时，,例如，若 exponent 为 32，按照上面 power 函数的做法，for 循环中要进行31次乘法。若是换一种思路思考：base^{32}等于base^{16}的二次方，base^{16}又是base^{8}的二次方。以此类推，做32次方只需5次乘法，先求2次方，然后4次方, 然后8次方，再然后16次方，最终求得32次方。
面试题17：打印1到最大的n位数
题目：输入数字n，按顺序打印出从1到最大的n位十进制数。如输入3，，则打印出1,2,3,...,999
思路：关键在于怎么设置循环结束的条件（在其他语言中要考虑大数，防止溢出，但是在python中不用考虑溢出的问题）
面试题18：删除链表的节点
题目一：在O(1)时间内删除列表节点，返回最终链表的头节点。给定单向列表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点。
思路：
因为最终要返回的是链表的头节点，所以需要借助空间复制一个新的链表，但是新的链表比原链表的在头节点处多一个元素，然后接下来的操作在新链表上进行，最终返回新链表的next。需要借助两个指针用来标记前后位置，如果前面的节点发现了目标节点，则后面的指针指向前面节点的下一个节点，从而实现删除节点；要注意删除节点不存在的情况
题目二：删除链表中的重复节点。在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
思路：
因为最终要返回的是链表的头节点，所以需要借助空间复制一个新的链表，但是新的链表比原链表的在头节点处多一个元素，然后接下来的操作在新链表上进行，最终返回新链表的next。需要借助两个指针用来标记前后位置，先找到重复的节点的值，然后再去删除从该节点起等于删除节点值的节点
面试题20：表示数值的字符串
题目：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符"+100"、"5e2"、"-123"、"3.1416"及"-1E-16"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"、"12e+5.4"都不是
思路：
（反面解题，针对不合规的情况讨论，剩下的就是合规的情况）表示数字的字符串遵循A[.[B]][e|EC]或.B[e|EC]，其中A和C都是整数（可以有正负号，也可以没有），而B只能是一个无符号整数找三个辅助变量分别表示正负号、小数点、E/e是否出现或出现的位置是否合适。遍历整个字符串，每个字符进行判断, 正负号只能出现在整数部分的前面或者是e/E的后面；小数点只能出现一次, 且在e/E的部分不能出现小数；e/E只能在数字的后面且其前面不能没有数字，且只能出现一次
面试题21：调整数组顺序使奇数位于偶数前
题目：输入一个整数数组，实现一个函数调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于后半部分。
思路：
从头开始遍历，遇到偶数就移到最后面。时间复杂度和空间复杂度都为O(n)，但是是稳定的，即移动后奇数相对于奇数、偶数相对偶数位置是不变的；找两个指针分别放在头部cur1和尾部cur2，若cur1指的是偶数，cur2指的是奇数，则交换元素，时间复杂度为O(log n )，但是是不稳定的特殊用例：传入的是空数组；传入的列表只有一个元素；所有的偶数都在前半部分
变体：
改成负数都在非负数前面能被3整除的数都在不能被3整除数的前面
面试题22：链表中倒数第k个节点
面试题22：输入一个(单向)链表，输出该链表中倒数第k个节点。如链表为[1,2,3,4,5], k=2时，输出倒数第二个节点为4
思路：
先遍历一次列表获得链表的长度n，再从头遍历到n-k+1个值，输出即可，但是这样时间复杂度高找两个指针cur1(第i个位置)、cur2(第i+k个位置)，并另二者的间隔为k，当cur2走到链表尾部时，cur1所指的就是倒数第k个值。【注意：输入的链表为空或者链表的长度小于k时，会直接报错】防爆措施：1、当输入的k小于1时，返回None；2、链表为空，返回None；3、链表长度小于k，返回None
面试题23：链表中环的入口节点
题目：给定一个链表，若其中包含环，请找出该链表的环的入口节点，否则输出null
思路：
找一个set，记录下环中的每一个节点，如果遇到None，则无环，如果再次遇到相同的节点，则表明有环，且该该节点为环的入口节点；（先判断是否有环，无环则return None，有环再去寻找环的入口）找两个指针fastPointer、slowPointer，f每次走两步，s每次只走一步，如果f遇到none表明无环，否则有环（注意当f==s时，说明，f在环里面追上了s，表明有环）；在判断环的入口位置，经过数学公式证明，当两个指针在环中第一次相遇后，此时找一个新的指针从头开始一步一步移动，s也一步一步往前移，二者相遇的位置就是入口节点
证明过程如下（假设链表中有环）：
假设s与f第一次相遇时，s已经走了l步，则f走了2l步；
假设入环前的步长为a，s进环后与f相遇又走了b步，则l=a+b，相遇的位置距离环的入口为c;
则f所走的步长2l=a+n*(b+c)+b, 其中n表示f在环中所绕的圈数
有2*(a+b)=a+n*(b+c)+b, 化简得a=c+(n-1)*(b+c),（其中b+c表示环的长度）
面试题24：反转链表
题目：定义一个函数，输入链表的头节点，反转该链表并输出反转后链表的头节点。（就是要求把一个单向链表有正序变为倒序）
思路：
需要找三个指针指定位置左中右做标记，然后三个指针依次往下走特殊测试：空链表、只有一个节点的链表
面试题25：合并两个链表
题目：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是按递增排序的。输出合并后的链表
思路：
建立一个新的链表，找两个游标作为标记, 再找一个指针指向新链表的前一个节点，每次两个游标进行比较从而判断指针的下一个节点
面试题26：树的子结构
题目：输入两颗二叉树A和B，判断B是不是A的子结构（注意：约定空树不是任意树的子结构）
思路：
主要是分为三种情况处理：第一种，二者的根节点就相同；第二种，B是A的左子树的一部分；第三种，B是A的右子树的一部分；针对每一种情况再判断B是否是A的子结构（如何判断：先判断根节点是否相等，如果相等，再分别去判断左、右两边是否相等，整体相等才能返回True，否则只能返回false）
面试题27：二叉树的镜像
题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像
思路：
采用递归的方式，每次对调根节点下的左右子节点
面试题28：对称的二叉树
题目：请实现一个函数，用来判断一颗二叉树是不是对称的。如果一颗二叉树和它的镜像一样，那么它就是对称的，否则不是
思路：
采用递归的方法，判断左子树的左边是否与右子树的右边相等，左子树的右边是否与右子树的左边相等
面试题30：包含min函数的栈
题目：定义栈的数据结构，在栈的原有功能上添加一个能够得到栈的最小元素的min函数，要求：在该栈中，调用min、push及pop的时间复杂度都是O(1)
思路：
栈的特点是先进后出，后进先出。栈的功能主要有：push（进栈）、pop（出栈）、top（栈顶元素）；遍历栈去寻找元素，时间复杂度为O(n)，题中要求是O(1)，所以考虑用空间换时间，创建一个存放最小值的列表，在每次进栈时都比较，对应放入最小值，从而栈有多长（假设为n），则最小元素的列表也为n
面试题31：栈的弹出与压入
题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字都不相等。例如1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
思路：
每压入一个元素，都会考虑弹出或不弹出的情况，不弹出则继续压入；弹出则弹出，下一个元素接着考虑是否弹出，不弹出则压入，由此得到第二个序列，即第二个序列是出栈方式中的一种可能结果
面试题32：从上到下打印二叉树
题目：从上往下打印出每个二叉树的节点，同一层的节点按照从左到右的顺序打印
思路：
将树的每一个左右节点都按照左右的顺序放入队列中，然后再按照先进先出的顺序打印出该节点的值，再将它的左右子节点放入队列中
面试题33：二叉搜索树的后序遍历序列
题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回True，否则输出False。假设输入数组的任意两个数字都互不相同
（名词解释：二叉搜索树————左子树的值必然小于根节点，右子树的值必然大于根节点的值；或者是一颗空树）
思路：
二叉搜索树的后序遍历，如5 7 6 9 11 10 8，8是根节点，根据二叉树的性质判断出5 7 6 是左子树的（都小于8），9 11 10是右子树的（都大于8），再递归进行判断，如果应该是右子树的部分出现小于根结点的（如小于8），则输出False
面试题34：二叉树中和为某一值的路径
题目：输入一颗二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点往下一直到叶节点所经过的结点形成一条路径
（注意：第一，路径指的是从根节点到叶子节点的一条完整的路径）
思路：
根据广度优先的方法，依次去寻找路径和为输入整数的路径(看代码吧，不太明白)
面试题36：二叉搜索树与双向链表
题目：输入一颗二叉搜索树，将该二叉搜索树转换为一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向
思路：
参考网址：/u010005281/article/details/79657259作者讲的很详细。
借用两个辅助变量分别标记双向链表的头节点和尾节点，按照中序遍历的思路，用递归进行解题。尾部节点得每次移动到尾部，从而每次都是尾部标识。
面试题37：序列化二叉树
题目：请实现两个函数，分别用来序列化和反序列化二叉树
思路：
序列化的过程就是对树进行前序遍历，但是要注意找一个记号（如'#'）标记叶子结点；
反序列化的过程将序列转换为树结构。先将字符串且分为列表格式，再根据所做的叶子结点的标记采用递归的方法，找出左右子节点从而还原为一棵树
面试题38：字符串的排列（所有字符串可能的排列组合）
题目：输入一个字符串，打印出该字符串中字符的所有排列。例如，字符串a、b、c所能排列出的所有字符串有abc、acb、bac、bca、cab和cba
思路：
看不懂,死记吧
面试题39：出现次数超过一半的数字
题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如一个输入长度为9的数组{1,2,3,2,2,2,5,4,2}, 由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2（注意：这个题主要考察的是时间复杂度和空间复杂度）
思路：
创建一个字典，记录下每一个数字出现的次数，并判断其出现次数是否超过数组长度的一半（时间复杂度和空间复杂度都为O(n)）每次抵消两个前后两个不相同的数字，从而得到最后一个剩下的一个数字；再判别该数字的出现次数是否超过数组的一半（时间复杂度为O(n), 空间复杂度为O(1))）
面试题40：最小的k个数
题目：输入n个数，找出其中最小的k个数。例如，输入4 5 1 6 2 7 3 8这8个数字，则最小的4个数字是1 2 3 4
（这个题主要是考察时间复杂度；知识点：最大最小堆）
提示：找k个最小的数，需要用到最大堆；找k个最小的数，需要用到最小堆；最大最小堆必须是一个完全二叉树；堆插入一个值的时间复杂度为O(lgn), 删除一个
值得时间复杂度为O(lgn), 创建一个堆的时间复杂度为O(n); 完全二叉树找到其父节点的索引的公式为(index-1)//2，index为当前值的索引，注这里的索引顺序是
按照广度优先排序的，反过来也可以找到其子节点，左子节点索引为index*2+1, 右子节点索引为index*2+2,
思路：
可以使用各种排序算法，先对数组进行排序，然后再选出最小的k个数（但是如果数据达到亿级别时，直接排序可能内存放不下）借鉴最大最小堆的思路进行解题，要找k个最小的数，首先需要建立一个含有k个数的最大堆，然后再依次遍历去修改已经建立好的最大堆。最大堆并不需要建立真实的一棵树，而是根据最大堆是完全二叉树的一些性质，将数放在列表里面即可（这种方法的时间复杂度为O(nlogk)）
面试题41：数据流中的中位数
题目：
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值，如果数据流中读出偶数个数值，那么中位数就是所有数值排序后中间两个数字的平均值。我们使用insert()方法读取数据流，使用getMedia()方法获取当前读取数据流的中位数
思路：
将数组里的数交替放入最大堆最小堆中，这样中位数只能是最大堆的堆顶或者最大最小堆堆顶元素的均值。首先编写最大堆最小堆的创建及修改的函数（共4个），交替的往最大最小堆添加数字（添加数字的过程是重点），从而保证最大最小堆里的元素个数要么相等，要么相差一个，从而实现了实时获取数据流的中位数。
面试题42：连续数组的最大和
题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组，求所有子数组和的最大值。例如，{6,-3,-2,7,-15,1,2,2}, 连续子向量的最大和为8(从第0个开始到第三个为止)。要求时间复杂度为O(n)【题目的意思是找出连续的数字中那几个加起来是最大的，只需要找到子数组和最大的那个和就行，不需要找出子数组】
思路：
找两个辅助变量，一个记录最大和，另一个记录加到第i个数之前的和，通过遍历数组，从而找到连续子数组的最大和
面试题43：统计1~n整数中1出现的次数
题目：输入一个正整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1的数字有1，10，11和12，1一共出现了5次
（这道题主要是考察时间复杂度）
思路：
（暴力方法）每个数遍历并去判断其是否含有1从个位、十位、百位到最高位，依次判断该位数字为1时可能出现的情况，再将其相加就得到了最终结果，难以口述清楚，还是看代码吧
面试题44：数字序列中的某一位数
题目：数字以012345678910111213141516……的格式序列化到一个字符序列中，在这个序列中，第五位（从0开始计数）是5，第十三位是1，第十九位是4等。写一个函数，求任意n位对应的数字。
思路：
①枚举法，从第0位开始遍历。一直找到第k位②从1开始，个位数（只有一位的数字）有九个，占位9个；两位数有90个，占位90*2个；三位数有900个，占位900*3个；以此类推，如果要找的第k位大于占位的累加和，则再增加一个位数，看目标数字是否在是这个位数，如果是则查找这个数，不是则再增加一个位数
面试题45：把数组排成最小的数
题目：输入一个正整数数组，把数组里面所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如，输入数组{3,32,321}，则打印出这3个数字能排成的最小数字321323（321 32 3）
思路：
(有点类似于面试题38————字符串的排列，n个数字共有n!种排列，但是如果使用这种方法的话，还是很慢)
参考网址：/u010005281/article/details/80085476
使用了快排的思路，但是不太理解，和书上讲的那一长串有点不一样
面试题46：把数字翻译为字符串
题目：给定一个数字，我们按照如下规则把它翻译为字符串："0"翻译为"a"，"1"翻译为"b"，"2"翻译为"c"，……，"25"翻译为"z"。一个数字可能有多个翻译。例如，"12258"有五种不同的翻译，分别是"bccfz"、"bwfi"、"bczi"、"mcfi"、"mzi"。写一个函数，计算一个数字有多少种不同的翻译。
思路：
采用递归的思路, 从后往前或从前往后，依次判断一位与两位（两位数必须小于26才行），有点类似于斐波那契数列递归的方法f(n)=f(n-1)+f(n-2)
6
5 25
2 12 1 11
1 11 1 1
1
面试题47：礼物的最大价值
题目：在一个m*n的棋盘的每一格都放一个礼物，每个礼物都有一定的价值（价值大于0）.你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下
移动一格，直到到达棋盘的右下角。给定一个棋盘及其上面的礼物，请计算你最多拿到多少价值的礼物
思路：
动态规划。（看不明白，还是看代码死记）
参考网址：/p/71bc21981090
变体：礼物的最大价值及其取得最大价值的路径
面试题48：最长不含重复字符的子字符串
题目：请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度，假设字符串中只包含"a"~"z"的字符。例如，在字符串'arabcacfr'中，最长的不含重复字符的子字符串为acfr，长度为4
思路：
先找出所有的子字符串，再去判断子字符串是否重复，去掉重复的，再找到最长的子字符串，时间效率为O(n^3)遍历整个字符串，记录下当前无重复的最长子字符串，如果发现字符串i已经在记录的最长子字符串中，那么记录从字符串i第一次出现的下一个位置开始重新开始动态规划。（动态规划的解法没大看懂）
面试题49：丑数
题目：把因子只包含2、3、5的称为丑数(ugly number)。求按从小到大第N个丑数，例如6、8都是丑数，但是14不是，因为它的因子包含7，习惯上把1当做
第一个丑数（注意：主要考虑时间复杂度）
思路：
（暴力方法）从1一直判断下去，知道找到第N个丑数（判断丑数的方法：先无限整除2，再无限整除3，最后再无限整除5，如果最终得到1则就是丑数，否则不是）【时间复杂度太高，而且N越大越慢】找3个指针，分别表示*2、*3、*5，都从1开始，判断大小找到小的数存放起来，并且对应的指针往前移一位，如1 *2、*3、*5，对应的最小的数为2，则将2添加到列表里，并将*2的指针往前移动一位，依次类推，知道找到第N个丑数为止
面试题50：第一个只出现一次的字符
题目一：字符串中第一个只出现一次的字符。在字符串中找出第一个只出现一次的字符。如输入"abaccdeff"，则输出'b'
思路：
拿第i个字符分别与其后面的字符串比较，如果其后面没有出现相同的，则输出，否则继续比较下一个字符。时间复杂度为O(n)用一个字典来统计出现的次数，用一个列表记录字典中的键先后的出现次数，最后通过列表记录下的键，寻找字典中值为1的键
题目二：字符流中第一个只出现一次的字符。写一个函数，找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"；当从该字符流中读出前6个字符"google"时，第一个只出现一次的字符是"l"
思路：
可以根据题目一的思路改一下即可，每输入一个数据流字符串，都判断一下当前第一个出现的子字符串，为了避免每次重复计算，可以将字典和列表定义在类下的init中
面试题51：数组中的逆序对
题目：在数组中的两个数字如果前面一个数字大于后面一个数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。例如，{7,5,6,4}中，一共有(7,5), (7,6), (7,4), (5,4), (6,4) 5个逆序对（注：输入的数组中没有相同的数字）
思路：
每遍历一个数字，都拿去与其后面的数字进行比较，但是这样的时间复杂度为O(n^2);按照归并排序的思路，先将数组折半分，直到分出单个元素，然后在合并的过程中统计发生调序的次数，此时的时间复杂度为O(nlogn)，空间复杂度为O(n),是典型的空间换时间
面试题53：在排序数组中查找数字
题目一：数字在排序数组中出现的次数。统计一个数字在排序数组中出现的次数。例如，输入排序数组{1,2,3,3,3,3,4,5}和数字3，由于3出现了4次，所以输出4
思路：
直接从头遍历，但是这种方法的时间复杂度为O(n)根据二分查找的思路，先找到数字k首次出现的位置，再分别从前半段后半段找出k第一次和最后一次出现的位置(索引)，从而统计出k出现的次数,这种方法的时间复杂度为O(logn)。编写两个函数分别寻找k首次出现和左后依次出现的索引位置，寻找k首次出现的位置，需要用到递归，为了能够保证找到位置，所以每次需要传入原数组，用两个辅助变量firstIndex, lastIndex来表示每次的变动，这样就能准确找到首次出现的索引位置
题目二：0~n-1中缺失的数字。一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字范围都在0~n-1之内。在范围0~n-1内的n个数字中，有且只有一个数字不再该数组中，请找出这个数字。
思路：
从头遍历，找到缺失值，时间复杂度为O(n)采用二分查找的方法，时间复杂度可以为O(logn)
面试题54：二叉搜索树的第k大结点
题目：给定一颗二叉搜索树，请找出其中第k个最小结点值（书上的意思还是找出第k个最小值）。例如(5,3,7,2,4,6,8)中，按结点数值大小顺序第三小结点的值为4（补充：二叉搜索树：左子树都小于父节点，右子树都大于父节点）
思路：
等价于中序遍历找第k个值，先对给定的二叉搜索树进行中序遍历，将序列放于列表中，再去寻找是否有第k个元素
面试题55：二叉树的深度
题目一：二叉树的深度。输入一颗二叉树的根节点，求该树的深度，从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
思路：
参考网址：/dailu11/article/details/80609416?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task
自己做不会，但是一看别人的（哦，好像是那么回事；对递归理解还是不到位）
题目二：平衡二叉树。输入一颗二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树深度相差不超过1，那么它就是一颗平衡二叉树
思路：
根据二叉树深度的思路，判断其左右子树的最大深度并进行比较，如果大于1，直接返回False，否则再进一步判断其子树是否满足, 这种方法每个节点只需要遍历一次即可
面试题56：数组中只出现一次的数字
题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n), 空间复杂度是O(1)(这个题目比较难，难以口述清除，要结合代码进行理解)
思路：
使用异或这个位运算进行解题（首先异或运算也具有交换律）。
因为数组中除了两个只出现依次的数字外，其他的数字都是出现了两次，使用异或运算可以使出现两次的数字的异或结果为0(如(1,1,2,2,3,4,4,5,5,6),整体进行异或后，结果为5==101)，从而找出两个只出现一次数字的异或结果x，再找到x的二进制码中1首次出现的位置，并截取其右半段为y（如5的右半段为1，再如异或结果为20==10100，截取的右半段为100）；再用截取的右半段y与数组中的每个数字进行与操作，可以将数组分为两段，并且每段中有一个只出现一次的数字，再分别对每段进行异或操作，从而找到了两个只出现一次的数字
面试题57：和为s的数字
题目一：和为s的两个数字，输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得他们的和正好是s。如果有多对数字和胃s，输出任意一对即可。
思路：
找两个指针，一个指向头，一个指向尾，从而去找s，这样的时间复杂度为O(1)
题目二：和为s的连续正数序列。输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。例如，输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以打印出3个连续序列1~5、4~6和7~8
思路：
找两个指针，指向1和2，如果cur1到cur2的和小于targetSum，那么cur2加1；如果大于targetSum，则cur1加1；等于，则记录下来，cur2加1，循环判断直到没有为止（终止条件：cur1的值小于(1+targetSum)/2时一直满足条件）
面试题58：翻转字符串
题目一：翻转单词顺序。输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如，输入字符串"I am a student."，则输出"student. a am I"
思路：
先切分开，翻转后再用空格链接回去
题目二：左旋转字符串。字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。例如，输入字符串'abcdefg'和数字2，该函数将返回左旋转两位得到的结果'cdefgab'
思路：将前面的n个字符串移动到后面即可
面试题59：滑动窗口的最大值
题目一：滑动窗口的最大值。给定一个数组和滑动窗口，请找出所有滑动窗口的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一个存在6个滑动窗口，它们的最大值分别为{4,4,6,6,6,5}
思路：
每次选取k个数里面最大的，但是这样的时间复杂度大，为O(n^2)双向队列，时间复杂度为O(n)。遍历整个数组，先删除超出窗口数的索引；再删除小于numbers[i]的数的索引；从第k-1个索引开始添加
题目二：队列的最大值。请定义一个队列并实现函数max得到队列里的最大值。要求函数max、push_back、pop_front的时间复杂度都是O(1)
思路：（没整明白题目是什么意思）
面试题60：n个骰子的点数之和
题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率
思路：
动态规划问题。f(n, s) = f(n-1, s-1) + f(n-1, s-2) + f(n-1, s-3) + f(n-1, s-4) + f(n-1, s-5) + f(n-1, s-6)。初始条件，f(1,1)=f(1,2)
=f(1,3)=f(1,5)=f(1,6)=1
参考网址：/A/1O5EVXAWd7/
面试题61：扑克牌中的顺子
题目：从扑克牌中随机抽5张牌，判断是不是一个顺子，即这五张牌是不是连续的，A为1，J为11，Q为12，K为13，而大小王可以看作任意数字。
思路：
大小王可以看成是任意数字，假设为0。先对数组进行排序，然后统计0的个数，再统计连续数字出现间隔的个数，如果0的个数大于等于出现间隔的个数，则可以认为是连续的；否则，认为是不连续的
面试题62：圆圈中最后剩下的数字
题目：0,1,...,n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字，求出这个圆圈里剩下的最后一个数字。如0,1,2,3,4这五个数字组成一个圆圈，从0开始每次删除第三个数字，则删除的前四个数字依次是2、0、4、1，因此最后剩下的数字是3
思路：
依次遍历，从而找到剩下的最后一个数字，但是其时间复杂度为O(n^2)找规律，但是没搞明白，这种方法的时间复杂度为O(n)，空间复杂度为O(1)【死记】
面试题63：股票的最大利润
题目：假设把某股票的价格按照时间先后顺序存储在数组里，请问买卖该股票一次可能获得的最大利润是多少？例如，一只股票在某些时间节点的价格为{9,11,8,5,7,12,16,14}。如果我们能在价格为5的时候买入并在价格为16时卖出，则能收获的最大利润是11
思路：
（实际上是找数组的最大差值）
面试题64：求1+2+……+n
题目：求1+2+……+n，要求不能用乘除法、for、while、if、else等关键字及条件判断语句
思路：
发散性思维，在实际中不太可能出现。
面试题65：不用加减乘除做加法
题目：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号（这个题只能死记，技巧性太强）
思路：
进行位运算，进行按位与、异或运算
将十进制数转换为二进制，
第一步，先进行两者间先进行按位与运算，如果结果为0，那么二者再进行的异或结果转换为十进制就是最终结果；
第二步，如果按位与结果不为0，说明有地方需要进一位，对其右补一位0并记为x(左移1位)，原来的两者间进行异或操作得到y；第三步，将x与y重复前面的步骤
面试题66：构建乘积数组
题目：给定一个数组A[0,1,...,n-1]，请构建一个数组B[0,1,...,n-1]，其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法
思路：
最暴力的方法，每个B[i]都从头计算，时间复杂度为O(n)B[i]的计算拆分为两部分，记C[i]=A[0]*A[1]*...*A[i-1]，D[i]=A[i+1]*...*A[n-1]，其中C[i]可以自上而下的计算，D[i]可以自下而上的计算，而C[i]=C[i-1]*A[i-1], D[i]=D[i+1]*A[i+1], 时间复杂度为O(n)
面试题67：把字符串转换为数字（建议先死记，然后理解）
# 限制数字的范围[-2^32, 2^32-1]，超过范围则返回左或右区间值；首字符不为'+'、'-'、' '时，直接返回0；# 当首次遇到字母时直接返回当前已经得到的数# 思路：借助三个辅助变量用来记住正负号、当前的数字、for循环遍历开始的位置，res=10*res+(ord(strs[i])-ord('0'))
unknown1：按之字形顺序打印二叉树
题目：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三层按照从左到右的顺序打印，依次类推
思路：
①（行不通）按照广度优先的思路执行不通，因为很难区分清楚打印到第几层，从而没办法及时调整方向（从左到右还是从右到左）
②找两个栈，将奇数层的结点从右到左append进去，将偶数层的结点从左到右append进去，最后再从尾部pop出来
unknow2：把二叉树打印成多行
题目：从上到下打印二叉树，同一层结点从左到右输出，每一层输出一行
思路：
与上一个按之字形打印二叉树的题目高度相似，只是把上一个题用的栈换为队列
unknow3：矩形覆盖
题目：用2*1的小矩形横着或竖着覆盖更大的矩形，请问用n个2*1的小矩形无重叠的覆盖一个2*n的大矩形，总共有多少种方法
思路：
原理就是斐波那契数列，如果第一块是竖着放的，那么剩下的就相当于n-1的情况，如果第一块是横着放的，那么第二块的方法就确定了，就相当于是n-2的情况
水平线以上的是剑指offer的题，水平线以下也是算法题（但不是剑指offer上的）
1、洗牌问题
洗牌问题。用Array编写洗牌问题？如何测试？(一个好的洗牌是每一张牌出现在一个地方的概率是相同的)
解题方法：
直接调用python的自带包random.shuffle()；【注意：random.shuffle()没有返回值】用概率的方法来解题使得一张牌出现在任意一个地方的概率都是，具体思路如下：先考虑第一个位置：随机从n张牌中抽取一张放在第一个位置，在该过程中每张牌被抽中的概率是1/n；再开率第二个位置：从剩下的n-1张牌抽取一张放在第二个位置，在该过程中每张牌被抽中的概率是1/(n-1)，但是第一次没被抽中，概率为(n-1)/n，两个一乘为1/(n-1) * (n-1)/n = 1/n;接下来考虑第三个位置1/(n-2) * (n-2)/(n-1) * (n-1)/n = 1/n;以此类推，可以得出每张牌出现在一个位置的概率是1/n（图中就是详细的过程）
2、计算质数的个数
题目：计算质数。给一个数n，返回它里面的所有质数的个数；如17，它的质数个数为7（包含17），则返回7。
思路：
1~n中的每一个数，都用其除以以内的数，比如17，从1遍历到17，对于17个数中的每一个数都去除以是以内的数，如5就去除以以内的整数，来判断5是不是质数。缺点：时间复杂度较高，每一个数都需要遍历一次。用空间换取时间，先找一个长度为n的bool数组，里面全设置为true，从2开始，判断2，是2的倍数（倍数大于1）则全部赋值为false；然后再判断3；因为4被划掉了，所以下一个考虑5；接下来再考虑7，一直到bool数组的后面全部转换为false为止
注意：
倍数从2开始，因为1倍数就是它自己；bool数组的true可以换成1，false换为0，这样可以减少时间复杂度；因为用ture/false的话，最后需要遍历取统计true的个数，如果换为1的话，直接sum求和即可；
3、“证明巴德赫猜想”
题目：证明巴德赫猜想。任意大于2的偶数都可以写成两个质数（素数）之和，如16=3+13。（这道题换句话表达：将任意一个大于2的偶数表示为两个质数之和）
思路：
首先，根据上一道题，计算n以内的所有素数个数，可以得到这个偶数范围内的所有素数，而且是排好序的；其次，有两种方法解题：①用两个for循环，将两个素数加起来，判断其是否等于输入的这个偶数；②找两个指针，分别指向第一步得到的有序素数列表的头尾记为i、j，如果i、j所指向的数之和大于这个偶数，那么j往左移一位再次判断；如果i、j所指向的数之和小于这个偶数，那么i往右移一位；如果等于这个偶数，则返回所指的两个质数。
注意：
第一种方法的时间复杂度为O(n^2)；第二种方法的时间复杂度为O(n)
4、扫雷游戏
题目：扫雷游戏。程序接收三个参数M,N,p，然后生成一个M*N的矩阵每一个cell都有p的概率是地雷，生成矩阵后，然后再计算每一个cell周围地雷的数量。
思路：
难度2星。因为边界的判断是个问题，在边上的格子只有5个邻居，在角上的格子只有三个邻居，只有在内部的才有八个邻居，可以直接写程序，但是这样有些太麻烦。所以应用了一个小技巧（技巧），在边界加上一层框，即行数和列数各增加2行/列，且和真正棋盘上的元素都不一样，用以区分。首先，先创建一个棋盘；然后再依次挨个遍历；
5、矩阵0变换
题目：矩阵0变换。给定一个m*n的矩阵，如果有一个元素为0，则把该元素对应的行和列全部转换为0
思路：
【误区：遇到0直接就立马将其所在行与列都转变为0，结果会导致整个矩阵都变为0】先定义两个列表来记录有0的行和列，通过遍历每一行去找0，如果遇到0则记录下其行号和列号，然后再去将对应的行和列转为0
6、九宫图和验证9*9的数独
题目1：九宫图(与数独规则不一样)。每一行每一列以及对角线的元素加起来和相等（注：九宫图的行数与列数必然为奇数）
思路：
首先要了解一个算法，每次把1放在最后一行的中间位置，然后另其右下方的数为2，超出边界，则对应找对角线上的位置，再在右下角填3，依次类推，如果发现下一个位置是1，则把下一个数填在这一对角线结束的上方的那个格子里，再与之前的循环操作类似，直至把最后一个数填进格为止【注：知道了这个解题方法后，关键是怎么用程序写出来】
注意：
首先，要搞清楚游戏规则；其次，（技巧）要处理好越界问题，当下一个元素的位置超出边界时，通过取余让其重新回到边界内；最后，写出程序的时间复杂度为O(n)游戏规则如下图解：
题目2：数独。在9*9的格子里，每一行每一列以及每一个切分好的3*3的格子里，1~9都仅出现一次。给一个填好的数独，验证其是否正确。
思路：
用for循环，然后再判断行列以及3*3的单元里面元素是否为1~9，用set(这个题我已经绕懵圈了)。反正就是看代码吧
7、旋转数组：将一个数组旋转90度
题目：旋转数组。给定一个n*n的数组，将其顺时针旋转90度。
思路：
创建一个n*n的数组，将对应的元素存入新数组中，但是有O(n^2)的空间复杂度；先转置再左右翻转，优点：没有占用新空间；【注意：根据这种方法可以求出旋转90度、180度（先上下翻转再左右翻转）、270度（就是逆时针旋转90度）等】
参考网址：/shahuzi/article/details/97825167
8、反转字符串
题目：反转字符串
思路（这个题目还是很简单的）：
直接str[::-1];自己手写一个，也很简单，从第0个位置遍历到第n/2个位置[注意：string是一个不可变的数据类型]
9、最长连续子串
题目：最长连续子串。给定一个只包含0和1的数组，找出只包含1的最长子串。
思路：
（自己的解法，不仅找到了最长子数组，也找到了它的位置）用while从头到尾遍历一遍，把一个包含1的子数组用元组记下其头索引和长度只判断出最长子数组是多长，代码相对比我的简洁很多
10、最大数
题目：最大数。给定一个数组，数组里有且只有一个最大数，判断这个数是否是其他数的两倍或更大，如果存在这个数，则返回其index，否则返回-1
注意：
没有必要先找到最大的数，再去和每一个数进行比较，会增加时间复杂度；第二，如果直接用sort排序，再让第一大和第二大的数比较，代码够简洁，但是排序的时间复杂度为O(nlogn)
思路：
(核心)遍历一次数组，找出最大和第二大的数，及第一大的数的索引，再去比较满足返回最大数的索引，不满足返回-1
11、消失的数字
题目：找到数组中消失（没有出现）的数。给定一个长度为n的数组，里面数字的范围为[1,n]，有的数字出现了多次，有的一次也没有出现，找到没有出现的数字。要求：不能占用其他的空间，时间复杂度不鞥超过O(n)
思路：
既然要求不能占用新的空间，那就只能修改原来数组，从而标记[1,n]中那个数没有出现，出现的则将这个数对应的索引上的数字记为负数，那么最后哪个索引位置的数字为正就说明该索引（即该数字）没有出现
12、斐波那契数列
注意：
在递归里面仍然会把整个函数执行一遍，自下而上
思路(3种方法)：
普通的递归方式，时间复杂度为O(2^n)，n=40时，直接执行不了；用for循环，每次把上一次的结果放入列表中，下一次计算时直接用列表中寻找上一次的结果；找两个临时变量存储上两次的值用于计算下一次的结果，这样可用for，也可以用递归；
13、打印对称的尺子
题目：打印对称的尺子。如n=1时，输出1；n=2时，输出1 1 2 1；n=3时，输出1 1 2 1 1 2 1 3 1 2 1；n=4时，输出1 1 2 1 1 2 1 3 1 2 1 1 2 1 3 1 4 1 3 1 2 1；……
思路：
用for，找个空列表存入前半段数，后半段列表的前n-1个顺序反转一下即可, 这种还是有点慢，每一层还需要重新计算用递归的方式：f(n) = f(n-1) + 'n' + f(n-1)
14、数学表达式
题目：数学表达式。给定a和b两个数，a<=b，把b以a乘2或者加1的最快的方式表示出来。（只能在a的基础上乘2或者加1）
思路：主要分析b>2a以及b%2=0是否成立, 当b<2a时，只能通过加1达到b，当b为奇数时通过加减1使b变为偶数
15、找出一个集合的所有子集
题目：（重要）找出一个集合的所有子集。打印出来即可。（leetcode上的：https://leetcode-/problems/subsets/）
思路：
有n个数字的集合共有2^n个子集。（技巧）第一个为空集，选出集合的第一个元素放在已有的子集中，再选出第二个元素分别放入已有的子集中，依次遍历，就找到了所有的子集。如原集合为{3,2}，第一个子集为空集，接下来取出第一个元素3，放入所有已有子集中，形成新的子集，{} + 3 => {3}，现在所有的子集为{}、{3}，再取出2放入所有已有的子集中形成新的子集，形成了{2}、{3,2}，一共就有了4子集（这种解法是利用了python的特性）回溯法(非常重要，死记)。感觉有点绕，不太理解。直接用一个for循环解决问题
变体：该集合中有重复的元素（可以直接用set去重）。
16、寻找旋转有序数组的最小值
这个题和剑指offer上的那一道一样，本文上面也有，这次的解题代码
变体，题目二：在旋转的有序数组中寻找某个值。【有难度】
思路：
这个题目是有难度的，需要分类讨论的情况比较多，本人也是在不断试错的情况下解出来的，但明显没有答案优秀
17、搜索插入位置
题目：给定有序数组和一个目标值，如果在数组中找到此目标值则返回与目标值相等的值的index，如果没有找到，则返回目标值按顺序应该被插入的位置。（注：假设该数组中不存在重复数）
思路：有点类似于插入排序。
实际上就是找到第一个大于等于item的数的位置，没有找到则放在最后的位置上
18、搜索一个重复数字的区间
题目：搜索一个区间。给定一个排好序的有重复数字的array，找到一个给定目标值的起始位置和结束位置。如果都没有，返回(-2,-2)
思路：
就是先找到第一次出现的位置，再找到第二次出现的位置。【用的是18中的经典二分搜索的方法】
这种解法的时间复杂度为log(n)+log(n),用for从头到尾遍历的时间复杂度为O(n)
19、在有空字符串隔开的有序array中查找元素
题目：在有空字符串隔开的有序array中查找元素。给定一个有序的字符串序列，这个序列中的字符串用空字符串隔开，请写出找到给定字符串位置的方法。如[' ', ' ', 1, ' ', ' ',' ', 2, ' ',3]
思路：
没有什么好的办法，第一种办法直接直接遍历；第二种方法二分搜索，先从左右两端找到非空字符串的位置，然后如果运气好，碰到中间为非空比较大小，缩小范围；如果中间恰好是个非空字符串，则往前（或往后）找到非空字符，比较，再缩小范围。【个人觉得不是专门搞算法的，这个题没必要在那点时间复杂度上较劲】
20、最长的公共子序列
题目：求出两个序列（或数组）中的公共子序列的个数，其中公共子序列可以不连续，但是是有顺序的【是leetcode的1143题，重点题目★★★】
思路：
动态规划问题，array[i][j]表示s1序列的前i个元素、s2序列的前j个序列的公共子序列数量，# 当i=0或j=0时，array[i][j]=0；# 当x_i=y_j时，array[i][j]=array[i-1][j-1]+1；# 当x_i不等于y_j时，array[i][j]=max(array[i-1][j],array[i][j-1])
21、实现sqrt函数（leetcode69）
思路：方法有很多种，如二分法、拟牛顿法等。这里的解法是二分法：设置一个区间[left, right]，left初始化为0，right初始化为num，如果num小于1，则令right=1；然后根据abs(mid^2-num)大于小于或等于0.001来进行调整区间，从而在满足一定精度的情况下返回最终值。
22、三数之和(leetcode15)
思路：先对列表里的数进行排序，再找三个指针，cur1是跟着for循环变化，cur2、cur3是动态变化
注意：这种解法时间复杂度还是挺高的，无法通过leetcode上的时间限制
23、二叉树的最大路径和（leetcode124）
思路：这道题的路径的起始点可以是任意节点（只要不违背前、中、后序遍历的原则即可）；相关题目是test34二叉树中和为某一值的完整路径
24、Matrix(leetcode542)
题目：找出数组中每个元素距离最近的0的步长，只能是上下左右行走
思路：有两种解题方法，一是图论中的广度优先搜索方法（不懂图论）；二是动态规划进行解题，因为考虑到是上下左右，所以先从左上角执行一遍，最后再从右下角执行一遍，从而达到上下左右，先定义一个dp函数，避免重复写动态规划
25、最长回文子序列（leetcode516）
题目：输入一个序列，找到其所有的回文子序列（这里的回文子序列可以不连续）
思路：动态规划，先列出转移方程，再解决问题。 d[i][j]表示s[i]……s[j]间的最长回文子序列数量，当i=j是,d[i][j]=1; 当i不等于j时，d[i][j]=max{d[i+1][j], d[i][j-1]}# 相关题目：最长公共子序列
相关题目：leetcode5最长回文子串，这道题目中要求的是回文子串是连续的
26、顺时针打印一个二维数组（面试题29）
思路：不断取数组的第一行放入结果列表中，每放一次，就把剩下的数组逆时针旋转90度，以把最后一列变为新数组的第一行，然后接着把第一行pop出来放入结果列表中
参考网址：/Lynette_bb/article/details/73414119
相关题目：旋转数组，将一个数组旋转90度（第7个）
27、leetcode977有序数组的平方及变体求出有序数组中平方中不同的值的个数
思路：输入一个有序数组，要求返回的平方也是有序的，注意处理平方和相同的情况；
它的变体与之解决办法类似，只是稍微有些改动（完整代码有些长35行左右，但是思路还是挺简单，就是要处理各种特殊情况比较复杂点）
28、最长的连续重复子串
关键有两点：①最长的；②连续重复最快时间复杂度为O(n^2),需要借助四个辅助变量来记录最终/临时的最长子串及其重复次数
29、航班预定统计（leetcode1109）
题目路径：1109. 航班预订统计
方法一：双循环暴力解决，但是时间复杂度为O(n^2)，无法通过；
方法二：差分法（模拟公交上下车）,这样的时间复杂度为O(n*m)，空间复杂度为O（1）
30、电话号码的字符组合
题目路径：leetcode17电话号码的字母组合
解题思路：有点类似与字符串的所有子集
31、单词拆分
题目路径：leetcode单词拆分
思路：动态规划的问题，dp[i]表示s[0:i]的字符串是否可拆分
32、重复的DNA序列（leetcode187）
题目路径：leetcode重复DNA序列
思路1：使用list，遍历字符串，但是无法通过时间复杂度；
思路2：改用set，遍历字符串，可以通过时间复杂度。
33、打家劫舍（leetcode198）
题目路径：打家劫舍（leetcode198）
思路1：使用递归的方式解题，但是无法通过时间复杂度；
思路2：动态规划，dp[i]表示前i-1间房子的最大收益，dp[i]=max(dp[i-1],nums[i]+dp[i-2])
测试用例：[2,1,1,2]
变体：打家劫舍2（leetcode213）
题目路径：打家劫舍2，此时的房子是一个环形，即首尾不能同时都光顾；
思路：既然首尾都不能光顾，那就比较分别首、尾去掉时所能获得的最大收益。
34、股票最大收益（面试题）
题目如下：
给定一个数组，它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。注意：你不能同时参与多笔交易（你必须在再次购买之前出售掉之前的股票）。
example1:输入[3,3,5,0,0,3,1,4] 输出：6
解释：在第4天（股票价格=0）的时候买入，在第6天（股票价格=3）的时候卖出，这笔交易所能获得利润=3-0=3.随后，在第7天（股票价格=1）的时候买入，在第8天（股票价格=4）的时候卖出，这笔交易所能获得利润=4-1=3。
example2：输入[1,2,3,4,5] 输出：4
解释：在第1天（价格=1）的时候买入，在第5天（价格=5）的时候卖出，这笔交易所能获得利润=5-1=4.注意你不能在第1天和第2天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买之前出售掉之前的股票。
example3：输入[7,6,4,3,1] 输出：0
解释：在这个情况下，没有交易完成，最大利润为0
思路：类似于差分法（29、航班预定统计（leetcode1109）；33、打家劫舍（leetcode198）），先计算相邻两天的交易的收益，再计算连续相邻正数的和（因为是正数，说明交易可以获取收益，通过连续正数，从而获得这笔交易的最大收益）
相关题目：股票的最大利润（仅交易一次）【剑指offer63或leetcode121】
35、去除重复字母
题目：leetcode316去除重复字母
思路：借用栈、字典可以解题，方法还是比较巧妙的。
36、火柴拼正方形
题目：leetcode43火柴拼正方形
思路：深度优先算法（递归）+遍历每个数组的每个元素，有点难
37、子域名访问计数
题目：leetcode811 子域名访问计数
思路：遍历+split，此题比较简单
38、有效的数独
题目：leetcode36 有效的数独
思路：
首先数独自己的特征：①同一行无重复数字1-9；②同一列无重复数字；③9个33的格子中无重复数字。所以一共有27组需要验证；
然后从对角线（9个元素）开始，每次遍历并验证对应的行、列以及第i个33的格子是否满足，只要有一个不满足直接return False
39、递减元素使数组呈锯齿状
题目：leetcode1144 递减元素使数组呈锯齿状
思路：本题的隐性要求：①只能使用减法变动元素，从而满足条件；②要比较奇数或偶数位置，这两种可能的情况满足要求时的最小变动；（奇数位置的元素都小于偶数位置的元素，或者偶数位置的元素都小于奇数位置元素）【解法还是比较巧妙的】
