AlgorithmsByPython
算法/数据结构/Python/剑指offer/机器学习/leetcode
Install / Use
/learn @Jack-Lee-Hiter/AlgorithmsByPythonREADME
尝试用Python实现一些简单的算法和数据结构
之前的算法和数据结构基本都是用Swift写的，现在尝试用Python实现一些简单的算法和数据结构。
update 20160704
准备加入《剑指offer》的习题python实现,以及机器学习过程中的一些算法
update 20160717
加入leetcode部分
~~## update 20160730~~
update 20160814
整理
如果对你有帮助，请记得点击github工程上的star，^_^ 现在总结如下：
面试题3：二维数组中的查找：对于在一个每一行从左到右依次递增，每一列从上到下依次递增的二维数组查找一个元素，可以选择从数组左上角开始查找array[i][j]，如果目标元素大于array[i][j]，i+=1，如果元素小于array[i][j]，j-=1，依次循环直至找到这个数。
面试题4：替换空格：如果直接每次遇到空格添加'%20'，那么空格后面的数字就需要频繁向后移动。遇到这种移动问题，我们可以尝试先给出最终需要的长度，然后从后向前扫描，同时给定两个指针来保证定位。逆向思维
面试题5：从头到尾打印链表：从头到尾遍历链表，并用一个栈存储每个结点的值，之后出栈输出值即可。
面试题6：重建二叉树：利用二叉树前序遍历和中序遍历的特性。前序遍历的第一个值一定为根节点，对应于中序遍历中间的一个点。在中序遍历序列中，这个点左侧的均为根的左子树，这个点右侧的均为根的右子树。这时可以利用递归，分别取前序遍历[1:i+1]和中序遍历的[:i]对应与左子树继续上一个过程，取前序遍历[i+1:]和中序遍历[i+1]对应于右子树继续上一个过程，最终得以重建二叉树。
面试题7：用两个栈实现队列：需要两个栈Stack1和Stack2，push的时候直接push进Stack1。pop需要判断Stack1和Stack2中元素的情况，Stack1空的话，直接从Stack2 pop，Stack1不空的话，把Stack1的元素push进入Stack2，然后pop Stack2的值。推广：用两个队列实现栈
面试题8：旋转数组的最小数字：二分查找的变形，注意到旋转数组的首元素肯定不小于旋转数组的尾元素，设置中间点。如果中间点大于首元素，说明最小数字在后面一半，如果中间点小于尾元素，说明最小数字在前一半。依次循环。同时，当一次循环中首元素小于尾元素，说明最小值就是首元素。但是当首元素等于尾元素等于中间值，只能在这个区域顺序查找。
面试题9：斐波那契数列：如何不使用递归实现斐波那契数列，需要把前面两个数字存入在一个数组中。斐波那契数列的变形有很多，如青蛙跳台阶，一次跳一个或者两个；铺瓷砖问题。变态青蛙跳，每次至少跳一个，至多跳n个，一共有f(n)=2<sup>n-1</sup>种跳法。考察数学建模的能力。
面试题10：二进制中1的个数：注意到每个非零整数n和n-1进行按位与运算，整数n的二进制数中最右边的1就会变成0，那么二进制数中的1的个数就会减少一个，因此可以利用一个循环，使得 n = n&(n-1) ，计算经过几次运算减少到0，就是有几个1。注意：书中给了另外两种方法，分别是原始n左移一位和右移一位的方法，因为Python不会出现整数溢出的情况，这里就不再考虑着两种方法。扩展：判断一个数值是不是2得整数次方，如果是的话，这个数的二进制数中有且只有一个1，那么这个数n会有 n&(n-1) == 0。或者求两个整数m和n需要改变m二进制中的多少位才能得到n，可以先做 m^n 的异或运算，然后求这个数中有多少个1。
面试题11：数值的整数次方：如果采用常规解法，需要注意的地方:当指数为负数的时候；当底数为零且指数为负数的情况；在判断底数base是不是等于0的时候,不能直接写base==0, 因为计算机内表示小数时有误差,只能判断他们的差的绝对值是不是在一个很小的范围内。如果采用递归解法，当n为偶数, a<sup>n</sup> = a<sup>n/2</sup> * a<sup>n/2</sup>，当n为奇数, a<sup>n</sup> = a<sup>(n-1)/2</sup> * a<sup>(n-1)/2</sup> * a，利用右移一位代替除2运算，利用 &1 判断是否为奇数。同时需要注意递归终止条件，exponent = 1的话，return base，exponent = -1的话，return 1.0/base。再次提醒！必须写成 1.0/base，否则 1/base，返回一个integer 0！
面试题12：打印1到最大的n位数：该题的要点是注意输入的n位数是否会导致溢出，因此利用字符串模拟整数的加法。注意：在打印函数中，需要判断打印的数字是否是以0开头的，同时判断条件是 num[i] != "0"，不能写作 num[i] != 0，因为是使用str类型的，后面一种写法导致判断无法成功。
面试题13：在O(1)时间删除链表结点：当要删除的结点不是尾结点而且不是仅有一个结点的头结点，可以把该结点i的下一个结点j的内容复制到结点i，同时把i结点的next指向j结点的next，然后再删除结点j。如果要删除的链表为单结点链表且待删除的结点就是头结点，需要把头结点置为None，如果删除的结点为链表的尾结点，那么就需要顺序遍历链表，找到尾节点前面一个结点，然后将其next置空。
面试题14：调整数组顺序使奇数位于偶数前面：注重函数的扩展性能。把函数中的判断条件写成一个判断条件的函数，方便与函数的扩展。对于奇数位于偶数前面的情况，类似于快排，在头和尾分别设置一个指针，头指针指向奇数则后移，尾指针指向偶数则前移。
面试题15：链表中倒数第k个结点：代码的鲁棒性。需要注意：如果输入的链表为空；k大于链表的长度；k为0的情况。对于正常情况，设置两个指针分别指向头结点，第一个指针向前走k-1步，走到正数第k个结点，同时保持第二个指针不动，然后第一个指针和第二个指针每次同时前移一步，这样第一个指针指向尾结点的时候，第二个指针指向倒数第k个结点。判断尾结点的条件是 pNode.next == None。
面试题16：递归以及非递归实现反转链表：需要注意三个问题：输入的链表头指针为None或者整个链表只有一个结点时，反转后的链表出现断裂，返回的翻转之后的头节点不是原始链表的尾结点。因此需要引入一个翻转后的头结点，以及一个指向当前结点的指针，一个指向当前结点前一个结点的指针，一个指向当前结点后一个结点的指针，防止出现断裂。推广：递归实现反转链表
面试题17：合并两个排序的链表：要注意特殊输入，如果输入是空链表，不能崩溃。
面试题18：树的子结构:多出需要判断指针是不是None，避免访问空指针而造成程序崩溃。
面试题19：二叉树的镜像：需要判断输入的结点为空或者输入的结点没有子树的情况。
面试题20：顺时针打印矩阵：首先需要判断每一步开始是的坐标点是否满足小于行数的一半且小于列数的一半，在最后一圈中，可能出现仅能向右走一行，仅能向右走一行向下走一列，向右走一行向下走一列向左走一行，能走完整一圈，一共四种情况。其中只有能向左走一行必然发生，不必判断，剩余的都需要判断发生条件。
面试题21：包含min函数的栈：引入两个栈，一个栈每次push实际的数字，另一个minStack，如果push的数字小于minStack栈顶的数字，push新的数字，繁殖，把栈顶的数字再压入一遍。
面试题22：栈的压入、弹出序列：建立一个辅助栈，把push序列的数字依次压入辅助栈，每次压入后，比较辅助栈的栈顶元素和pop序列的首元素是否相等，相等的话就推出pop序列的首元素和辅助栈的栈顶元素，若最后辅助栈为空，则push序列可以对应于pop序列。
面试题23：从上往下打印二叉树：引入一个队列即可。推广：有向图的广度优先遍历也是基于队列的。
面试题24：二叉搜索树的后续遍历序列：根据后续遍历的性质，尾元素必定是树的根，同时小于尾元素的值是左子树，大于尾元素的值为右子树，且序列前半部分均小于尾元素，后半部分均大于尾元素（如果同时存在左右子树的话），可以将序列划分左子树序列和右子树序列，然后递归比较师妹每一段均满足此性质。可以减少递归深度的办法：某段的元素个数如果<=3，则返回True；某整段的最小元素不小于尾元素或者整段的最大元素不大于尾元素，说明仅有左子树或者右子树，返回True。
[面试题26：复杂链表的复制](https://github.com
