码创造者

这个屌丝很懒，什么也没留下！

热门标签

Python面试--编程题_python面试编程题

作者：码创造者 | 2024-08-20 04:11:18

踩

python面试编程题

1 台阶问题/斐波纳挈

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1	fib = lambda n : n if n <= 2 else fib ( n - 1 ) + fib ( n - 2 )

第二种记忆方法

def memo ( func ) :

cache = { }

def wrap ( * args ) :

if args not in cache :

cache [ args ] = func ( * args )

return cache [ args ]

return wrap

@ memo

def fib ( i ) :

if i < 2 :

return 1

return fib ( i - 1 ) + fib ( i - 2 )

第三种方法

def fib ( n ) :

a , b = 0 , 1

for _ in xrange ( n ) :

a , b = b , a + b

return b

2 变态台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1	fib = lambda n : n if n < 2 else 2 * fib ( n - 1 )

3 矩形覆盖

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

第2*n个矩形的覆盖方法等于第2*(n-1)加上第2*(n-2)的方法。

1	f = lambda n : 1 if n < 2 else f ( n - 1 ) + f ( n - 2 )

4 杨氏矩阵查找

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

5 去除列表中的重复元素

用集合

1	list ( set ( l ) )

用字典

l1 = [ 'b' , 'c' , 'd' , 'b' , 'c' , 'a' , 'a' ]

l2 = { } . fromkeys ( l1 ) . keys ( )

print l2

用字典并保持顺序

l1 = [ 'b' , 'c' , 'd' , 'b' , 'c' , 'a' , 'a' ]

l2 = list ( set ( l1 ) )

l2 . sort ( key = l1 . index )

print l2

列表推导式

l1 = [ 'b' , 'c' , 'd' , 'b' , 'c' , 'a' , 'a' ]

l2 = [ ]

[ l2 . append ( i ) for i in l1 if not i in l2 ]

面试官提到的,先排序然后删除.

6 链表成对调换

1->2->3->4转换成2->1->4->3.

class ListNode :

def __init__ ( self , x ) :

self . val = x

self . next = None

class Solution :

# @param a ListNode

# @return a ListNode

def swapPairs ( self , head ) :

if head != None and head . next != None :

next = head . next

head . next = self . swapPairs ( next . next )

next . next = head

return next

return head

7 创建字典的方法

1 直接创建

1	dict = { 'name' : 'earth' , 'port' : '80' }

2 工厂方法

items = [ ( 'name' , 'earth' ) , ( 'port' , '80' ) ]

dict2 = dict ( items )

dict1 = dict ( ( [ 'name' , 'earth' ] , [ 'port' , '80' ] ) )

3 fromkeys()方法

dict1 = { } . fromkeys ( ( 'x' , 'y' ) , - 1 )

dict = { 'x' : - 1 , 'y' : - 1 }

dict2 = { } . fromkeys ( ( 'x' , 'y' ) )

dict2 = { 'x' : None , 'y' : None }

8 合并两个有序列表

知乎远程面试要求编程

尾递归

def _recursion_merge_sort2 ( l1 , l2 , tmp ) :

if len ( l1 ) == 0 or len ( l2 ) == 0 :

tmp . extend ( l1 )

tmp . extend ( l2 )

return tmp

else :

if l1 [ 0 ] < l2 [ 0 ] :

tmp . append ( l1 [ 0 ] )

del l1 [ 0 ]

else :

tmp . append ( l2 [ 0 ] )

del l2 [ 0 ]

return _recursion_merge_sort2 ( l1 , l2 , tmp )

def recursion_merge_sort2 ( l1 , l2 ) :

return _recursion_merge_sort2 ( l1 , l2 , [ ] )

循环算法

def loop_merge_sort ( l1 , l2 ) :

tmp = [ ]

while len ( l1 ) > 0 and len ( l2 ) > 0 :

if l1 [ 0 ] < l2 [ 0 ] :

tmp . append ( l1 [ 0 ] )

del l1 [ 0 ]

else :

tmp . append ( l2 [ 0 ] )

del l2 [ 0 ]

tmp . extend ( l1 )

tmp . extend ( l2 )

return tmp

9 交叉链表求交点

去哪儿的面试,没做出来.

class ListNode :

def __init__ ( self , x ) :

self . val = x

self . next = None

def node ( l1 , l2 ) :

length1 , lenth2 = 0 , 0

# 求两个链表长度

while l1 . next :

l1 = l1 . next

length1 += 1

while l2 . next :

l2 = l2 . next

length2 += 1

# 长的链表先走

if length1 > lenth2 :

for _ in range ( length1 - length2 ) :

l1 = l1 . next

else :

for _ in range ( length2 - length1 ) :

l2 = l2 . next

while l1 and l2 :

if l1 . next == l2 . next :

return l1 . next

else :

l1 = l1 . next

l2 = l2 . next

10 二分查找

def binarySearch ( l , t ) :

low , high = 0 , len ( l ) - 1

while low < high :

print low , high

mid = ( low + high ) / 2

if l [ mid ] > t :

high = mid

elif l [ mid ] < t :

low = mid + 1

else :

return mid

return low if l [ low ] == t else False

if __name__ == '__main__' :

l = [ 1 , 4 , 12 , 45 , 66 , 99 , 120 , 444 ]

print binarySearch ( l , 12 )

print binarySearch ( l , 1 )

print binarySearch ( l , 13 )

print binarySearch ( l , 444 )

11 快排

def qsort ( seq ) :

if seq == [ ] :

return [ ]

else :

pivot = seq [ 0 ]

lesser = qsort ( [ x for x in seq [ 1 : ] if x < pivot ] )

greater = qsort ( [ x for x in seq [ 1 : ] if x >= pivot ] )

return lesser + [ pivot ] + greater

if __name__ == '__main__' :

seq = [ 5 , 6 , 78 , 9 , 0 , - 1 , 2 , 3 , - 65 , 12 ]

print ( qsort ( seq ) )

12 找零问题

def coinChange ( values , money , coinsUsed ) :

#values T[1:n]数组

#valuesCounts 钱币对应的种类数

#money 找出来的总钱数

#coinsUsed 对应于目前钱币总数i所使用的硬币数目

for cents in range ( 1 , money + 1 ) :

minCoins = cents #从第一个开始到money的所有情况初始

for value in values :

if value <= cents :

temp = coinsUsed [ cents - value ] + 1

if temp < minCoins :

minCoins = temp

coinsUsed [ cents ] = minCoins

print ( '面值为：{0} 的最小硬币数目为：{1} ' . format ( cents , coinsUsed [ cents ] ) )

if __name__ == '__main__' :

values = [ 25 , 21 , 10 , 5 , 1 ]

money = 63

coinsUsed = { i : 0 for i in range ( money + 1 ) }

coinChange ( values , money , coinsUsed )

13 广度遍历和深度遍历二叉树

给定一个数组，构建二叉树，并且按层次打印这个二叉树

## 14 二叉树节点

class Node ( object ) :

def __init__ ( self , data , left = None , right = None ) :

self . data = data

self . left = left

self . right = right

tree = Node ( 1 , Node ( 3 , Node ( 7 , Node ( 0 ) ) , Node ( 6 ) ) , Node ( 2 , Node ( 5 ) , Node ( 4 ) ) )

## 15 层次遍历

def lookup ( root ) :

stack = [ root ]

while stack :

current = stack . pop ( 0 )

print current . data

if current . left :

stack . append ( current . left )

if current . right :

stack . append ( current . right )

## 16 深度遍历

def deep ( root ) :

if not root :

return

print root . data

deep ( root . left )

deep ( root . right )

if __name__ == '__main__' :

lookup ( tree )

deep ( tree )

17 前中后序遍历

深度遍历改变顺序就OK了

18 求最大树深

def maxDepth ( root ) :

if not root :

return 0

return max ( maxDepth ( root . left ) , maxDepth ( root . right ) ) + 1

19 求两棵树是否相同

def isSameTree ( p , q ) :

if p == None and q == None :

return True

elif p and q :

return p . val == q . val and isSameTree ( p . left , q . left ) and isSameTree ( p . right , q . right )

else :

return False

20 前序中序求后序

推荐: http://blog.csdn.net/hinyunsin/article/details/6315502

def rebuild ( pre , center ) :

if not pre :

return

cur = Node ( pre [ 0 ] )

index = center . index ( pre [ 0 ] )

cur . left = rebuild ( pre [ 1 : index + 1 ] , center [ : index ] )

cur . right = rebuild ( pre [ index + 1 : ] , center [ index + 1 : ] )

return cur

def deep ( root ) :

if not root :

return

deep ( root . left )

deep ( root . right )

print root . data

21 单链表逆置

class Node ( object ) :

def __init__ ( self , data = None , next = None ) :

self . data = data

self . next = next

link = Node ( 1 , Node ( 2 , Node ( 3 , Node ( 4 , Node ( 5 , Node ( 6 , Node ( 7 , Node ( 8 , Node ( 9 ) ) ) ) ) ) ) ) )

def rev ( link ) :

pre = link

cur = link . next

pre . next = None

while cur :

tmp = cur . next

cur . next = pre

pre = cur

cur = tmp

return pre

root = rev ( link )

while root :

print root . data

root = root . next

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/码创造者/article/detail/1005117