网络推广有哪些网站,服务器ip域名解析,黄岛区做网站多少钱,环境设计专业作品集编程题1 台阶问题/斐波那契一只青蛙一次可以跳上1级台阶#xff0c;也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。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:cac…编程题1 台阶问题/斐波那契一只青蛙一次可以跳上1级台阶也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。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 wrapmemodef fib(i):if i 2:return 1return fib(i-1) fib(i-2)第三种方法def fib(n):a, b 0, 1for _ in xrange(n):a, b b, a breturn b2 变态台阶问题一只青蛙一次可以跳上1级台阶也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。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)的方法。f lambda n: 1 if n 2 else f(n - 1) f(n - 2)4 杨氏矩阵查找在一个m行n列二维数组中每一行都按照从左到右递增的顺序排序每一列都按照从上到下递增的顺序排序。请完成一个函数输入这样的一个二维数组和一个整数判断数组中是否含有该整数。使用Step-wise线性搜索。def get_value(l, r, c):return l[r][c]def find(l, x):m len(l) - 1n len(l[0]) - 1r 0c nwhile c 0 and r m:value get_value(l, r, c)if value x:return Trueelif value x:c c - 1elif value x:r r 1return False5 去除列表中的重复元素用集合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(keyl1.index)print l2列表推导式l1 [b,c,d,b,c,a,a]l2 [][l2.append(i) for i in l1 if not i in l2]sorted排序并且用列表推导式.l [b,c,d,b,c,a,a] [single.append(i) for i in sorted(l) if i not in single] print single6 链表成对调换1-2-3-4转换成2-1-4-3.class ListNode:def __init__(self, x):self.val xself.next Noneclass Solution:# param a ListNode# return a ListNodedef swapPairs(self, head):if head ! None and head.next ! None:next head.nexthead.next self.swapPairs(next.next)next.next headreturn nextreturn head7 创建字典的方法1 直接创建dict {name:earth, port:80}2 工厂方法items[(name,earth),(port,80)]dict2dict(items)dict1dict(([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 tmpelse: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 tmppop弹出a [1,2,3,7]b [3,4,5]def merge_sortedlist(a,b):c []while a and b:if a[0] b[0]:c.append(b.pop(0))else:c.append(a.pop(0))while a:c.append(a.pop(0))while b:c.append(b.pop(0))return cprint merge_sortedlist(a,b)9 交叉链表求交点其实思想可以按照从尾开始比较两个链表如果相交则从尾开始必然一致只要从尾开始比较直至不一致的地方即为交叉点如图所示# 使用a,b两个list来模拟链表可以看出交叉点是 7这个节点a [1,2,3,7,9,1,5]b [4,5,7,9,1,5]for i in range(1,min(len(a),len(b))):if i1 and (a[-1] ! b[-1]):print Nobreakelse:if a[-i] ! b[-i]:print 交叉节点,a[-i1]breakelse:pass另外一种比较正规的方法构造链表类class ListNode:def __init__(self, x):self.val xself.next Nonedef node(l1, l2):length1, lenth2 0, 0# 求两个链表长度while l1.next:l1 l1.nextlength1 1while l2.next:l2 l2.nextlength2 1# 长的链表先走if length1 lenth2:for _ in range(length1 - length2):l1 l1.nextelse:for _ in range(length2 - length1):l2 l2.nextwhile l1 and l2:if l1.next l2.next:return l1.nextelse:l1 l1.nextl2 l2.next修改了一下:#coding:utf-8class ListNode:def __init__(self, x):self.val xself.next Nonedef node(l1, l2):length1, length2 0, 0# 求两个链表长度while l1.next:l1 l1.next#尾节点length1 1while l2.next:l2 l2.next#尾节点length2 1#如果相交if l1.next l2.next:# 长的链表先走if length1 length2:for _ in range(length1 - length2):l1 l1.nextreturn l1#返回交点else:for _ in range(length2 - length1):l2 l2.nextreturn l2#返回交点# 如果不相交else:return10 二分查找#coding:utf-8def binary_search(list, item):low 0high len(list) - 1while low high:mid (high - low) / 2 low # 避免(high low) / 2溢出guess list[mid]if guess item:high mid - 1elif guess item:low mid 1else:return midreturn Nonemylist [1,3,5,7,9]print binary_search(mylist, 3)11 快排#coding:utf-8def quicksort(list):if len(list)2:return listelse:midpivot list[0]lessbeforemidpivot [i for i in list[1:] if imidpivot]biggerafterpivot [i for i in list[1:] if i midpivot]finallylist quicksort(lessbeforemidpivot)[midpivot]quicksort(biggerafterpivot)return finallylistprint quicksort([2,4,6,7,1,2,5])12 找零问题#coding:utf-8#values是硬币的面值values [ 25, 21, 10, 5, 1]#valuesCounts 钱币对应的种类数#money 找出来的总钱数#coinsUsed 对应于目前钱币总数i所使用的硬币数目def coinChange(values,valuesCounts,money,coinsUsed):#遍历出从1到money所有的钱数可能for cents in range(1,money1):minCoins cents#把所有的硬币面值遍历出来和钱数做对比for kind in range(0,valuesCounts):if (values[kind] cents):temp coinsUsed[cents - values[kind]] 1if (temp minCoins):minCoins tempcoinsUsed[cents] minCoinsprint (面值:{0}的最少硬币使用数为:{1}.format(cents, coinsUsed[cents]))13 广度遍历和深度遍历二叉树给定一个数组构建二叉树并且按层次打印这个二叉树14 二叉树节点class Node(object):def __init__(self, data, leftNone, rightNone):self.data dataself.left leftself.right righttree Node(1, Node(3, Node(7, Node(0)), Node(6)), Node(2, Node(5), Node(4)))15 层次遍历def lookup(root):row [root]while row:print(row)row [kid for item in row for kid in (item.left, item.right) if kid]16 深度遍历def deep(root):if not root:returnprint root.datadeep(root.left)deep(root.right)if __name__ __main__:lookup(tree)deep(tree)17 前中后序遍历深度遍历改变顺序就OK了#coding:utf-8#二叉树的遍历#简单的二叉树节点类class Node(object):def __init__(self,value,left,right):self.value valueself.left leftself.right right#中序遍历:遍历左子树,访问当前节点,遍历右子树def mid_travelsal(root):if root.left is not None:mid_travelsal(root.left)#访问当前节点print(root.value)if root.right is not None:mid_travelsal(root.right)#前序遍历:访问当前节点,遍历左子树,遍历右子树def pre_travelsal(root):print (root.value)if root.left is not None:pre_travelsal(root.left)if root.right is not None:pre_travelsal(root.right)#后续遍历:遍历左子树,遍历右子树,访问当前节点def post_trvelsal(root):if root.left is not None:post_trvelsal(root.left)if root.right is not None:post_trvelsal(root.right)print (root.value)18 求最大树深def maxDepth(root):if not root:return 0return max(maxDepth(root.left), maxDepth(root.right)) 119 求两棵树是否相同def isSameTree(p, q):if p None and q None:return Trueelif p and q :return p.val q.val and isSameTree(p.left,q.left) and isSameTree(p.right,q.right)else :return False20 前序中序求后序def rebuild(pre, center):if not pre:returncur 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 curdef deep(root):if not root:returndeep(root.left)deep(root.right)print root.data21 单链表逆置class Node(object):def __init__(self, dataNone, nextNone):self.data dataself.next nextlink Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9)))))))))def rev(link):pre linkcur link.nextpre.next Nonewhile cur:tmp cur.nextcur.next prepre curcur tmpreturn preroot rev(link)while root:print root.dataroot root.next22 两个字符串是否是变位词class Anagram::param s1: The first string:param s2: The second string:return true or falsedef Solution1(s1,s2):alist list(s2)pos1 0stillOK Truewhile pos1 len(s1) and stillOK:pos2 0found Falsewhile pos2 len(alist) and not found:if s1[pos1] alist[pos2]:found Trueelse:pos2 pos2 1if found:alist[pos2] Noneelse:stillOK Falsepos1 pos1 1return stillOKprint(Solution1(abcd,dcba))def Solution2(s1,s2):alist1 list(s1)alist2 list(s2)alist1.sort()alist2.sort()pos 0matches Truewhile pos len(s1) and matches:if alist1[pos] alist2[pos]:pos pos 1else:matches Falsereturn matchesprint(Solution2(abcde,edcbg))def Solution3(s1,s2):c1 [0]*26c2 [0]*26for i in range(len(s1)):pos ord(s1[i])-ord(a)c1[pos] c1[pos] 1for i in range(len(s2)):pos ord(s2[i])-ord(a)c2[pos] c2[pos] 1j 0stillOK Truewhile j26 and stillOK:if c1[j] c2[j]:j j 1else:stillOK Falsereturn stillOKprint(Solution3(apple,pleap))23 动态规划问题
