codemk

递归与分治策略[TOC] 分治策略解决问题的典型策略： 分而治之，将问题分为若干更小规模的部分，通过解决每一个小规模部分问题，并将结果汇总，得到原问题的解 递归算法与分治策略 递归三定律： 基本结束条件，解决最小规模问题 缩小规模，向基本结束条件演进 调用自身来解决已缩小规模的相同问题 体现了分治策略 问题解决依赖于若干缩小了规模的问题 汇总得到原问题的解 应用相当广泛 排序、查找、遍历、求值等等 找零兑换问题：递归解法 其次是减小问题的规模， 我们要对每种硬币尝试 1次， 例如美元硬币体系： 找零减去1分(penny)后，求兑换硬币最少数量（递归调用自身）； 找零减去5分(nikel)后，求兑换硬币最少数量 找零减去10分(dime)后，求兑换硬币最少数量 找零减去25分(quarter)后，求兑换硬币最少数量 上述4项中选择最小的一个。 1234567891011def recMC(coinValueList, change): minCoins = change if change in coinValueList: retur ...

链表定义与实例[TOC] 链表 定义： 采用链表实现无序表 为了实现无序表数据结构， 可以采用链接表的方案。 虽然列表数据结构要求保持数据项的前后相对位置， 但这种前后位置的保持， 并不要求数据项依次存放在连续的存储空间 采用链表实现无序表 如下图， 数据项存放位置并没有规则， 但如果在数据项之间建立链接指向， 就可以保持其-前后相对位置第一个和最后一个数据项需要显式标记出来，一个是队首，一个是队尾，后面再无数据了。 链表实现：节点Node 链表实现的最基本元素是节点Node,每个节点至少要包含2个信息： 数据项本身，以及指向下一个节点的引用信息,注意next为None的意义是没有下一个节点了，这个很重要 12345678910111213141516class Node: def __init__(self,initdata): self.data = initdata self.next = None def getData(self): return self.data def getNext ...

递归定义与实例[TOC] 递归是一种解决问题的方法， 其精髓在于将问题分解为规模更小的相同问题，持续分解，直到问题规模小到可以用非常简单直接的方式来解决。 递归的问题分解方式非常独特，其算法方面的明显特征就是：在算法流程中调用自身。 递归“三定律”为了向阿西莫夫的“机器人三定律”致敬， 递归算法也总结出“三定律”1，递归算法必须有一个基本结束条件（最小规模问题的直接解决）2，递归算法必须能改变状态向基本结束条件演进（减小问题规模）3，递归算法必须调用自身（解决减小了规模的相同问题） 实例应用：整数转换为任意进制以10进制为中间体，用整数除， 和求余数两个计算来将整数一步步拆开除以“进制基base”（// base）对“进制基”求余数（% base） 1234567891011121314151617from pythonds.basic.stack import Stackdef baseConverter(decNumber,base): digits = "0123456789ABCDEF" remstack = Stack() while decN ...

队列Queue 定义与实例队列Queue 定义： 队列是一种有次序的数据集合， 其特征是 新数据项的添加总发生在一端（通常称为“尾rear”端） 而现存数据项的移除总发生在另一端（通常称为 “首front”端） 当数据项加入队列， 首先出现在队尾， 随 着队首数据项的移除， 它逐渐接近队首。 新加入的数据项必须在数据集末尾等待，而等待时间最长的数据项则是队首,这种次序安排的原则称为（FIFO:First-in first-out） 先进先出或“先到先服务first-come first-served” 队列的例子出现在我们日常生活的方方面面：排队 队列仅有一个入口和一个出口,不允许数据项直接插入队中，也不允许从中间移 除数据项 抽象数据类型Queue由如下操作定义： Queue()：创建一个空队列对象，返回值为Queue对象； 123456789101112131415class Queue: def __init__(self): self.items = []#isEmpty()：测试是否空队列，返回值为布尔值 def isEmpty(sel ...

[TOC] 死锁在线程间共享多个资源的时候，如果两个线程分别占有一部分资源并且同时等待对方的资源，就会造成死锁。 尽管死锁很少发生，但一旦发生就会造成应用的停止响应。下面看一个死锁的例子 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#coding=utf-8import threadingimport timeclass MyThread1(threading.Thread): def run(self): # 对mutexA上锁 mutexA.acquire() # mutexA上锁后，延时1秒，等待另外那个线程 把mutexB上锁 print(self.name+'----do1---up----') time.sleep(1) # 此时会堵塞，因为这个mutexB已经被另外的线程抢先上锁了 mutexB.acquire() print(sel ...

[TOC] 互斥锁当多个线程几乎同时修改某一个共享数据的时候，需要进行同步控制 线程同步能够保证多个线程安全访问竞争资源，最简单的同步机制是引入互斥锁。 互斥锁为资源引入一个状态：锁定/非锁定 某个线程要更改共享数据时，先将其锁定，此时资源的状态为“锁定”，其他线程不能更改；直到该线程释放资源，将资源的状态变成“非锁定”，其他的线程才能再次锁定该资源。互斥锁保证了每次只有一个线程进行写入操作，从而保证了多线程情况下数据的正确性。 threading模块中定义了Lock类，可以方便的处理锁定： 123456789import threading# 创建锁mutex = threading.Lock()# 锁定mutex.acquire()# 释放mutex.release() 注意： 如果这个锁之前是没有上锁的，那么acquire不会堵塞 如果在调用acquire对这个锁上锁之前 它已经被 其他线程上了锁，那么此时acquire会堵塞，直到这个锁被解锁为止 使用互斥锁完成2个线程对同一个全局变量各加100万次的操作12345678910111213141516171819202122 ...

[TOC] 练习题： 1、打开中文字符的文档时，会出现乱码，Python自带的打开文件是否可以指定文字编码？还是只能用相关函数？ f = open(‘将进酒.txt’, ‘r+’, encoding=’UTF-8’) 2、编写程序查找最长的单词 输入文档: res/test.txt 题目说明: 12345678910111213""" Input file test.txt Output file ['general-purpose,', 'object-oriented,'] """def longest_word(filename): # your code here pass 1234567891011121314151617181920212223242526272829303132333435363738394041""" Input file test.txt Output file ['general-purpose,', 'object-oriented,'] """import os,collecti ...

[TOC] 线程-注意点 线程执行代码的封装通过使用threading模块能完成多任务的程序开发，为了让每个线程的封装性更完美，所以使用threading模块时，往往会定义一个新的子类class，只要继承threading.Thread就可以了，然后重写run方法 示例如下：123456789101112131415#coding=utf-8import threadingimport timeclass MyThread(threading.Thread): def run(self): for i in range(3): time.sleep(1) msg = "I'm "+self.name+' @ '+str(i) #name属性中保存的是当前线程的名字 print(msg)if __name__ == '__main__': t = MyThread() t.start() I'm Thread-6 @ 0 I'm Thread-6 @ 1 I'm Thread-6 @ 2 ...