算法,数据结构,Python,剑指offer,机器学习,leetcode.zip

# 尝试用Python实现一些简单的算法和数据结构 之前的算法和数据结构基本都是用Swift写的，现在尝试用Python实现一些简单的算法和数据结构。 ## update 20160704 准备加入[《剑指offer》](https://www.amazon.cn/%E5%9B%BE%E4%B9%A6/dp/B00L5LKMVU?ie=UTF8&*Version*=1&*entries*=0)的习题python实现,以及机器学习过程中的一些算法 ## update 20160717 加入leetcode部分 ~~## update 20160730~~ ## update 20160814 整理 如果对你有帮助，请记得点击github工程上的star，^_^ 现在总结如下： [数据结构markdown格式](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84.md) [链表及常见操作](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Lists.py) [平衡查找树AVL](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/AVL.py) [三种方法检测变位词Anagram](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/AnagramDetection.py) [构建堆](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/BinaryHeap.py) [二分查找](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/BinarySearch.py) [二叉查找树](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/BinarySearchTree.py) [二叉树](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/BinaryTree.py) [冒泡排序](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/BubbleSort.py) [英语单词拼写检查算法](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/CheckErrorWord.py) [几个小的动态规划问题](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Dynamic%20Programming.py) [Hash及常见操作](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Hash.py) [插入排序](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/InsertionSort.py) [归并排序](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/MergeSort.py) [解析树ParseTree](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/ParseTree.py) [队列](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Queue.py) [快排](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/QuickSort.py) [基数排序](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/RadixSort.py) [一些递归算法](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Recursion.py) [选择排序](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/SelectionSort.py) [希尔排序](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/ShellSort.py) [栈及常见应用](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Stack.py) [分治算法](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/divideAndConquer.py) [堆排序](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/heapSort.py) [正则表达式和一个使用正则表达式的图片爬虫](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/tree/master/regularExpression) [剑指offer](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/tree/master/Target%20Offer) [面试题2：实现Singleton模式](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Target%20Offer/Singleton.py) [面试题3：二维数组中的查找](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Target%20Offer/%E4%BA%8C%E7%BB%B4%E6%95%B0%E7%BB%84%E6%9F%A5%E6%89%BE.py)：对于在一个每一行从左到右依次递增，每一列从上到下依次递增的二维数组查找一个元素，可以选择从数组左上角开始查找array[i]\[j]，如果目标元素大于array[i]\[j]，i+=1，如果元素小于array[i]\[j]，j-=1，依次循环直至找到这个数。 [面试题4：替换空格](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Target%20Offer/%E6%9B%BF%E6%8D%A2%E7%A9%BA%E6%A0%BC.py)：如果直接每次遇到空格添加'%20'，那么空格后面的数字就需要频繁向后移动。遇到这种移动问题，我们可以尝试先给出最终需要的长度，然后从后向前扫描，同时给定两个指针来保证定位。**逆向思维** [面试题5：从头到尾打印链表](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Target%20Offer/%E5%8F%8D%E5%90%91%E6%89%93%E5%8D%B0%E9%93%BE%E8%A1%A8.py)：从头到尾遍历链表，并用一个栈存储每个结点的值，之后出栈输出值即可。 [面试题6：重建二叉树](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Target%20Offer/%E9%87%8D%E5%BB%BA%E4%BA%8C%E5%8F%89%E6%A0%91.py)：利用二叉树前序遍历和中序遍历的特性。前序遍历的第一个值一定为根节点，对应于中序遍历中间的一个点。在中序遍历序列中，这个点左侧的均为根的左子树，这个点右侧的均为根的右子树。这时可以利用递归，分别取前序遍历[1:i+1]和中序遍历的[:i]对应与左子树继续上一个过程，取前序遍历[i+1:]和中序遍历[i+1]对应于右子树继续上一个过程，最终得以重建二叉树。 [面试题7：用两个栈实现队列](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Target%20Offer/%E7%94%A8%E4%B8%A4%E4%B8%AA%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.py)：需要两个栈Stack1和Stack2，push的时候直接push进Stack1。pop需要判断Stack1和Stack2中元素的情况，Stack1空的话，直接从Stack2 pop，Stack1不空的话，把Stack1的元素push进入Stack2，然后pop Stack2的值。[推广：用两个队列实现栈](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Target%20Offer/%E7%94%A8%E4%B8%A4%E4%B8%AA%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.py) [面试题8：旋转数组的最小数字](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Target%20Offer/%E6%97%8B%E8%BD%AC%E6%95%B0%E7%BB%84%E7%9A%84%E6%9C%80%E5%B0%8F%E6%95%B0%E5%AD%97.py)：二分查找的变形，注意到旋转数组的首元素肯定不小于旋转数组的尾元素，设置中间点。如果中间点大于首元素，说明最小数字在后面一半，如果中间点小于尾元素，说明最小数字在前一半。依次循环。同时，当一次循环中首元素小于尾元素，说明最小值就是首元素。但是当首元素等于尾元素等于中间值，只能在这个区域顺序查找。 [面试题9：斐波那契数列](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Target%20Offer/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97.py)：如何不使用递归实现斐波那契数列，需要把前面两个数字存入在一个数组中。斐波那契数列的变形有很多，如青蛙跳台阶，一次跳一个或者两个；铺瓷砖问题。**变态青蛙跳**，每次至少跳一个，至多跳n个，一共有f(n)=2^n-1种跳法。考察数学建模的能力。 [面试题10：二进制中1的个数](https://github.com/Jack-Lee-Hiter/AlgorithmsByPython/blob/master/Target%20Offer/%E4%BA%8C%E8%BF%9B%E5%88%B6%E4%B8%AD1%E7%9A%84%E4%B8%AA%E6%95%B0.py)：注意到每个**非零**整数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