剑指offer-python代码-第二章

刚开始用github: https://github.com/xiaohuang200706/coding-interviews-learning/blob/master/offer_python_ch2.md

开始看剑指offer，粗略的捋一捋里面的面试题：以下代码大多用python3写的，少部分会用C++ python代码看上去更加简洁明了，里面也穿插和补充了我的部分总结。

p38:二维数组中的查找：

从右上角或者左下角开始：

def searchMatrix( matrix, target): """ :type matrix: List[List[int]] :type target: int :rtype: bool """ if not matrix: return False m = len(matrix) n = len(matrix[0]) j, i = n - 1, 0 while i < m and j >= 0: key = matrix[i][j] if key == target: return True elif key < target: i += 1 else: j -= 1 return False

p40:替换空格

题目要求把空格，换成“ ”每次看到这种题，我都抑制不住体内的洪荒之力~

def repalace(s): return ' '.join(s.split())

p55:重建二叉树

给前序遍历和中序遍历，重构一颗二叉树，并且返回头节点： 例子： 前【1，2，4，7，3】 后【4，7，2，1，3】

则1就是头节点：从后续遍历可以看出【4，7，2】就是左自树，【3】就是右自树。

第一个想法，找到1的位置，递归的调用：

class Solution(object): def buildTree(self, preorder, inorder): """ :type preorder: List[int] :type inorder: List[int] :rtype: TreeNode """ L=len(preorder) if L<1:return None root=TreeNode(preorder[0]) x=inorder.index(preorder[0]) root.left=self.buildTree(preorder[1:1+x],inorder[:x]) root.right=self.buildTree(preorder[1+x:],inorder[x+1:]) return root

采用这样的思想,可以不断的从 preorder的前端pop出root节点：

def buildTree(self, preorder, inorder): if inorder: ind = inorder.index(preorder.pop(0)) root = TreeNode(inorder[ind]) root.left = self.buildTree(preorder, inorder[0:ind]) root.right = self.buildTree(preorder, inorder[ind+1:]) return root

p57:用两个栈实现队列

很简单，可以把pop和peek部分中重复的部分写成一个新的辅助函数：

class MyQueue(object): def __init__(self): """ Initialize your data structure here. """ self.stack1 = [] self.stack2 = [] def push(self, x): """ Push element x to the back of queue. :type x: int :rtype: void """ self.stack1.append(x) def pop(self): """ Removes the element from in front of queue and returns that element. :rtype: int """ if self.stack2: pass else: while self.stack1: self.stack2.append(self.stack1.pop()) return self.stack2.pop() def peek(self): """ Get the front element. :rtype: int """ if self.stack2: pass else: while self.stack1: self.stack2.append(self.stack1.pop()) return self.stack2[-1] def empty(self): """ Returns whether the queue is empty. :rtype: bool """ return (len(self.stack1) + len(self.stack2)) == 0

p61:两个队列实现一个栈

这个改天再做……pop()的实现不太一样

p64-p66:排序

第一个是快排，第二个是线性时间排序。 我之前见过的线性时间排序有两种：

计数排序：n个输入元素都是0到k区间的一个整数桶排序：假设输入的数据服从均匀分布

计数排序： python版本：

def counting_sort(a,k): #a为原始数组，范围：（0，n-1），k是数组中数的最大值n-1 b=a c=[0]*(k+1) for i in a: c[i]+=1 for j in range(1,k+1): c[j]+=c[j-1] for x in a[::-1]: b[c[x]-1]=x #小于等于x的有c[x]个数，从零数起就是 b中的下标为c[x]-1的为x c[x]-=1 a=b return

c++版本：

//计数排序 void counting_sort(vector<int>&a,int k){ auto b=a; vector<int>c(k+1,0); for(auto x:b){++c[x];} for (int i=1;i<=k;++i)c[i]+=c[i-1]; for (int j=b.size()-1;j>=0;--j){ b[c[a[j]]-1]=a[j];--c[a[j]];} a=b;}

旋转数组的最小数字

首先，什么叫做旋转数组，举个例子：【3，4，5，1，2】为【1，2，3，4，5】的一个旋转： 配合leetcode有关rotate的题目：

生成一个旋转数组 第189题

经典解法：分三个步骤

反转前 n-k个反转后 k个反转全部

代码：

class Solution(object): def rotate(self, nums, k): if k is None or k <= 0: return k, end = k % len(nums), len(nums) - 1 self.reverse(nums, 0, end - k) self.reverse(nums, end - k + 1, end) self.reverse(nums, 0, end) def reverse(self, nums, start, end): while start < end: nums[start], nums[end] = nums[end], nums[start] start, end = start + 1, end - 1

切片解法：

其中要注意nums[:]和nums[]之间的区别：

class Solution(object): def rotate(self, nums, k): n=len(nums) k%=n nums[:]=nums[n-k:] + nums[:n - k] return

p66-68:假定旋转array没有重复的情况下，寻找array的最小值

解决思路：

采用二分法查找取的nums[middle]只可能有两种情况，第一种：小于等于尾，这个时候把high=middle；第二种情况：大于等于头，这个时候low=middle+1 具体代码如下： class Solution(object): def findMin(self, nums): low=0 high=len(nums)-1 while low<high: m=(low+high)//2 if nums[m]<=nums[high]: high=m else: low=m+1 return nums[low]

下面的一个做法是第一次用C++的时候写的：

class Solution { public: int findMin(vector<int>& nums) { int n=nums.size(); if(n==1)return nums.front(); int low=0; int high=n-1; int mid; while(low<high){ mid=low+(high-low)/2; if(mid==low)break; if (nums[mid]>nums[high]){low=mid;} else { high=mid; }} return min(nums[low],nums[high]); } };

p69-71但是如果array有重复：

上述的解法就会有错误，如nums=[1,1,1,1,0,1,1,1] 这个时候只需要多判断：那两种情况之中相等情况：

class Solution(object): def findMin(self, nums): low=0 high=len(nums)-1 while low<high: if nums[low]<nums[high]:break m=(low+high)//2 mid=nums[m] if mid<nums[high]: high=m elif mid>nums[low]: low=m+1 elif mid==nums[low]: low+=1 else: high-=1 return nums[low]

如：输入为【3，1，3，3，3】这里，先把第一个3去掉【1，3，3，3】就是排好序的了，输出第一个； 再比如【3，3，3，1，3】，这里还是先去前面的3变成[3, 3, 1, 3]，[3, 1, 3]，[3, 1]输出1

p73:面试题9：斐波那契数列

递归和迭代都简单，python要注意 迭代器的使用： 举例：

def fib(max): n, a, b = 0, 0, 1 while n < max: yield b a, b = b, a + b n = n + 1 return 'done'

经典题目：跳台阶，一次可以跳1级也可以跳2级

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

class Solution(object): def climbStairs(self, n): a,b=1,1 for _ in range(n): a,b=b,a+b return a

面试题10：二进制中1的个数

先放python

def hammingWeight(self, n): return bin(n).count('1')

这里假定最长32bit:

def hammingWeight(self, n): rst = 0 mask = 1 for i in range(32): if n & mask: rst += 1 mask = mask << 1 return rst

经典做法：

def hammingWeight(self, n): ans=0 while n: n&=n-1 ans+=1 return ans

其中： “n &= n - 1” 是用来删除右边的1，而且每次只删除一个 如： n=111 则 n-1=110 ，与之后的结果为110 n=110 则 n-1=101 ，与之后的结果为100