首页 / 算法 / python语言编程算法
python语言编程算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python语言编程算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含9555字,纯文字阅读大概需要14分钟。
内容图文
![python语言编程算法](/upload/InfoBanner/zyjiaocheng/628/064db4294add42ffb15966df4e89e55a.jpg)
编程题
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 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级的台阶总共有多少种跳法。
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) - 1 n = len(l[0]) - 1 r = 0 c = n while c >= 0 and r <= m: value = get_value(l, r, c) if value == x: return True elif value > x: c = c - 1 elif value < x: r = r + 1 return False
5 去除列表中的重复元素
用集合
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]
sorted排序并且用列表推导式.
l = ['b','c','d','b','c','a','a'] [single.append(i) for i in sorted(l) if i not in single] print single
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 直接创建
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
pop弹出
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 c print 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 i==1 and (a[-1] != b[-1]): print "No" break else: if a[-i] != b[-i]: print "交叉节点:",a[-i+1] break else: pass
另外一种比较正规的方法,构造链表类
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
修改了一下:
#coding:utf-8 class ListNode: def __init__(self, x): self.val = x self.next = None def node(l1, l2): length1, length2 = 0, 0 # 求两个链表长度 while l1.next: l1 = l1.next#尾节点 length1 += 1 while l2.next: l2 = l2.next#尾节点 length2 += 1 #如果相交 if l1.next == l2.next: # 长的链表先走 if length1 > length2: for _ in range(length1 - length2): l1 = l1.next return l1#返回交点 else: for _ in range(length2 - length1): l2 = l2.next return l2#返回交点 # 如果不相交 else: return
思路: http://humaoli.blog.163.com/blog/static/13346651820141125102125995/
10 二分查找
#coding:utf-8 def binary_search(list, item): low = 0 high = len(list) - 1 while low <= high: mid = (high - low) / 2 + low # 避免(high + low) / 2溢出 guess = list[mid] if guess > item: high = mid - 1 elif guess < item: low = mid + 1 else: return mid return None mylist = [1,3,5,7,9] print binary_search(mylist, 3)
参考: http://blog.csdn.net/u013205877/article/details/76411718
11 快排
#coding:utf-8 def quicksort(list): if len(list)<2: return list else: midpivot = list[0] lessbeforemidpivot = [i for i in list[1:] if i<=midpivot] biggerafterpivot = [i for i in list[1:] if i > midpivot] finallylist = quicksort(lessbeforemidpivot)+[midpivot]+quicksort(biggerafterpivot) return finallylist print quicksort([2,4,6,7,1,2,5])
更多排序问题可见:数据结构与算法-排序篇-Python描述
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,money+1): minCoins = cents #把所有的硬币面值遍历出来和钱数做对比 for kind in range(0,valuesCounts): if (values[kind] <= cents): temp = coinsUsed[cents - values[kind]] +1 if (temp < minCoins): minCoins = temp coinsUsed[cents] = minCoins print ('面值:{0}的最少硬币使用数为:{1}'.format(cents, coinsUsed[cents]))
思路: http://blog.csdn.net/wdxin1322/article/details/9501163
方法: http://www.cnblogs.com/ChenxofHit/archive/2011/03/18/1988431.html
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): 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: return print root.data deep(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 = value self.left = left self.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 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
思路: http://blog.csdn.net/feliciafay/article/details/6841115
方法: http://www.xuebuyuan.com/2066385.html?mobile=1
22 两个字符串是否是变位词
class Anagram: """ @:param s1: The first string @:param s2: The second string @:return true or false """ def Solution1(s1,s2): alist = list(s2) pos1 = 0 stillOK = True while pos1 < len(s1) and stillOK: pos2 = 0 found = False while pos2 < len(alist) and not found: if s1[pos1] == alist[pos2]: found = True else: pos2 = pos2 + 1 if found: alist[pos2] = None else: stillOK = False pos1 = pos1 + 1 return stillOK print(Solution1('abcd','dcba')) def Solution2(s1,s2): alist1 = list(s1) alist2 = list(s2) alist1.sort() alist2.sort() pos = 0 matches = True while pos < len(s1) and matches: if alist1[pos] == alist2[pos]: pos = pos + 1 else: matches = False return matches print(Solution2('abcde','edcbg')) def Solution3(s1,s2): c1 = [0]*26 c2 = [0]*26 for i in range(len(s1)): pos = ord(s1[i])-ord('a') c1[pos] = c1[pos] + 1 for i in range(len(s2)): pos = ord(s2[i])-ord('a') c2[pos] = c2[pos] + 1 j = 0 stillOK = True while j<26 and stillOK: if c1[j] == c2[j]: j = j + 1 else: stillOK = False return stillOK print(Solution3('apple','pleap'))
23 动态规划问题
内容总结
以上是互联网集市为您收集整理的python语言编程算法全部内容,希望文章能够帮你解决python语言编程算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。