面试：python面试中手写代码的环节

1.如何反向迭代一个序列

#如果是一个list,最快的方法使用reverse tempList = [1,2,3,4] tempList.reverse() for x in tempList: print x #如果不是list,需要手动重排 templist = (1,2,3,4) for i in range(len(templist)-1,-1,-1): print templist[i]

2.如何查询和替换一个文本中的字符串

#最简单的方法使用replace() tempstr = "hello you hello python are you ok" print tempstr.replace("you","python") #还可以使用正则,有个sub() tempstr = "hello you hello python are you ok" import re rex = r'(hello|Use)' print re.sub(rex,"Bye",tempstr)

3.使用python实现单例模式

#方法一:可以使用__new__方法 #在__new__方法中把类实例绑定到类变量_instance上，如果cls._instance为None表示该类还没有实例化过，实例化该类并返回。如果cls_instance不为None表示该类已实例化，直接返回cls_instance class SingleTon(object): def __new__(cls,*args,**kwargs): if not hasattr(cls,'_instance'): cls._instance = object.__new__(cls,*args,**kwargs) return cls._instance class TestClass(SingleTon): #直接继承 a = 1 #方法二:使用装饰器,建立过实例的就放到instances里面,下次建立的时候先检查里面有没有 def SingleTon(cls,*args,**kwargs): instances = {} print instances def _singleton(): if cls not in instances: instances[cls] = cls(*args,**kwargs) print instances return instances[cls] return _singleton @SingleTon class LastClass(object): a = 1

4.闭包

常用的装饰器就是闭包的一种

def make_adder(addend): def adder(addend): return addend+addend return adder P1 = make_adder(5) P2= make_adder(4) print p1(10) #输出15 print p2(10) #输出14

5.给列表中的字典排序

alist = [{“name”:”a”,”age”:20},{“name”:”b”,”age”:30},{“name”:”c”,”age”:25}] 按照 age 从大到小排序 alist = [{"name":"a","age":20},{"name":"b","age":30},{"name":"c","age":25}] alist.sort(key=lambda:x:-x.get("age")) print alist

6.简单的实现一个栈结构 stack

class Stack(object): def __init__(self): self.value = [] def push(self,x): self.value.append(x) def pop(self): self.value.pop() stack = Stack() stack.push(1) stack.push(2) stack.push(3) print(stack.value) stack.pop() print(stack.value)

7.输入一个日期,返回时一年中的哪一天

from datetime import datetime def which_day(year,month,day): return (datetime(year,month,day)-datetime(year,1,1)).days+1 print(which_day(2017,1,15))

8.判断输入的值是否在矩阵之中(杨氏矩阵)

在一个二维数组之中,每一行都按照从走到右递增的顺序排序,每一列到按照从上到下的顺序排序.请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数

#处理数组矩阵 arr = [[1,4,7,10,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]] def get_num(num,data=None): while data: if num > data[0][-1]: del data[0] elif num<data[0][-1]: data = list(zip(*data)) del data[-1] data = list(zip(*data)) else: return True data.clear() return False print (get_num(18,arr))

9.获取最大公约数(欧几里得算法)

a = 25 b = 15 def max_common(a,b): while b: a,b=b,a%b return a

10.求两个数的最小公倍数(公式法)

两个数的乘积等于这两个数的 最大公约数与最小公倍数的积

a = 25 b = 15 def min_common(a,b): c= a*b while b: a,b=b,a%b return c//a

11.选择排序算法

def select_sort(origin_items): """ 选择排序算法 """ items = origin_items[:] for i in range(len(items) -1): min_index = i for j in range(i + 1, len(items)): if items[j] < items[min_index]: min_index = j items[i], items[min_index] = items[min_index], items[i] ​ return items

12.归并法/分治法排序

def merge_sort(arr): """ 归并法/分治法排序 """ if len(arr) < 2: return arr[:] mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) ​ def merge(left, right): print(left) print(right) print('\n') result = [] index_left, index_right = 0, 0 ​ while index_left < len(left) and index_right < len(right): if left[index_left] <= right[index_right]: result.append(left[index_left]) index_left += 1 else: result.append(right[index_right]) index_right += 1 result += left[index_left:] result += right[index_right:] return result

13.冒泡排序

def bubble_sort(origin_items): """ 冒泡排序算法 """ items = origin_items[:] for i in range(len(items) - 1): for j in range(0, len(items) - 1 -i): if items[j] > items[j + 1]: items[j], items[j + 1] = items[j + 1], items[j] return items

14.递归实现快排

class Solution(): def quicksort(self, list, low, high): if low >= high: return list left = low right = high num = list[low] while left < right: while list[right] >= num and left < right: right = right - 1 list[left] = list[right] while list[left] <= num and left < right: left = left + 1 list[right] = list[left] list[left] = num return self.quicksort(list, low, left-1) return self.quicksort(list, left+1, high)

15.二分查找（非递归）

def merge_search(self, li, item): start = 0 end = len(li) - 1 while start <= end: mid = (start + end) // 2 if li[mid] == item: return '要查找的元素为：{}，位置是：{}'.format(item, li.index(li[mid])) elif li[mid] > item: end = mid - 1 else: start = mid + 1

16.二分查找（递归）

def bin_serach(list, value, low , high): #递归出口 if low > high: return -1 mid = low + ((high - low)>>1) #避免大数溢出 if list[mid] > value: return bin_serach(list, value, low , mid-1) elif list[mid] < value: return bin_serach(list, value, mid+1, high) else: return mid

17.插入查找

def interpolation_search(nums, key): low = 0 high = len(nums) -1 while(nums[low]<= key <=nums[high] and nums[low] !=nums[high]): mid = low + int((key - nums[low])*(high - low)/(nums[high]-nums[low])) if nums[mid] < key: low = mid + 1 elif nums[mid] > key: high = mid - 1 else: return mid if key == nums[low]: return low else: return -1