课程大纲：从构建一个简单的搜索引擎项目出发，介绍构建过程中需要用到的技术，大致分为三个部分：

1. 爬取数据

2. 建立索引

3. 页面排序

第一单元

开始你的第一行代码

课程前三个单元的目标是创建一个网络爬虫。从一个种子链接开始，跟着链接一步步爬取越来越多的页面，为搜索引擎创建数据集。第一单元主要介绍了Python的基本语法，包括变量、字符串等内容，完成quiz就行。后面单元要用到主要是字符串的find函数：

<string>.find(<string>)             //若找到字符串就返回第一次出现的位置，否则-1。注意不论字符串内容是什么，一定有空字符串
<string>.find(<string>，int x)        //查找下标x以后的<string>串

比较值得分析的是下面这个题：注意第三个选项在未找到支付串，返回-1时的情况。

本单元的最终练习是从一个字符串中提取链接：由于我的做法每次都是用find(string)，故每次得到的下标都是相对子串的，故最后要提取两次。若用find(string，x)则可直接用得到的下标提取。

page =('<div id="top_bin"><div id="top_content" class="width960">'
'<div class="udacity float-left"><a href="http://udacity.com">')

//先找到链接标志'<a href='的位置
start_link = page.find('<a href=')

l = int(page[start_link:].find('"'))       //从start_link以后的子串中找到链接起始引号
r = int(page[start_link:].find('"', l + 1))       //找到链接结束引号

url = page[start_link:][l+1:r]           //提取子串的子串
print url

搜索引擎和网络 && 字符串练习

这两节都是Python语法的练习，第二节最后一个练习是给一个小数，要求四舍五入后再转为字符串，不用round

x = 3.14159

#ENTER CODE BELOW HERE
x += 0.5
s = str(x)
l = s.find('.')
#取小数点前的整数
print s[:l]

第二单元

怎样重复

首先是get_next_target函数的编写，就是将从一个网页中不停地提取其中的URL的过程编成函数以供调用。讲解了get_next_target函数的设计过程——输入、返回值的设置

def get_next_target(page):
    start_link = page.find('<a href=')
    if start_link == -1:              #注意，页面没有链接的情况直接返回，否则就会造成处理混乱
        return None, 0
    #提取URL
    start_quote = page.find('"', start_link)
    end_quote = page.find('"', start_quote + 1)
    url = page[start_quote + 1:end_quote]
    #end_quote标记页面位置查找下一个URL
    return url, end_quote

在没有返回值的情况下，传入的参数不会改变，如：

def sum(a, b)            #无返回值，什么也不会输出
      a = a + b
a = 2, b = 123
print sum(a, b)
print a

=>
None
2

下面这个例子是带返回值的情况，会得到正确输出，但并不会改变输入的值，也就是说接着print s会输出 “Hello”。对照上图可知每个函数内部会重新设形参变量指到实参的值。

实际上，不可能编写一个更改整数类型或字符串类型输入值的过程，因为这些类型是不可变的。这样说的意思是，一旦我们创建一个整数或字符串类型的对象，就没有任何办法可以改变该对象的值。比如说：

x = 17
z = 'hello'
any_mysterious_procedure(x, z)
#在这段代码之后，我们知道x的值仍然是17，z的值仍然是'hello'，尽管我们不知道过程 any_mysterious_procedure 是做什么的。

接下来是几个函数包括阶乘编写的小练习，然后讲解if、or、while、break的用法，几个小quiz。结尾的多重赋值练习

s, t = t, s         #交换 s 与 t 的值

第六、七、八节是Udacify 函数 && 可选编程练习，都是函数的编写问题的练习

怎样解决问题

利用计算两个日期之间的天数这个问题讲解怎样解决问题

1. 理解问题，包括弄清问题的输入、输出。包括输入什么、输入如何表现，这个例子中是两个日期，应思考两日期的关系、合法性，及在不合法输入情况下的输出。

2. 通过举一些例子来充分理解输入输出的关系，在手动计算的过程中分析算法的步骤过程，思考如何系统化解决问题。

3. 简化机械求解过程。写出伪代码的思路后不要急着实现，思考能否简化算法、边界情况、特殊情况。本例中直接简化为一天一天累加。

两日期之间的天数，分为两个过程：计算nextday，判断是否到达目标日期。加入了输入合法性判断。一开始可以只给出大致正确的思路即可，具体如闰年这种细致的问题可以在大致思路正确的基础上调整。

def isl(x):
    return x % 4 ==0 and x % 100 !=0 or x % 400 ==0

def nextDay(year, month, day):
    """Simple version: assume every month has 30 days"""
    if day < 28:
        return year, month, day + 1
    else:
        if month == 2:
            if isl(year):
                if day == 28:
                    return year, month, day + 1
                else:
                    return year, month + 1, 1
            else :
                return year, month + 1, 1
        elif month in [1,3,5,7,8,10,12]:
            if day < 31:
                return year, month, day + 1
            else:
                if month == 12:
                    return year + 1, 1, 1
                else :
                    return year, month + 1, 1
        else:
            if day < 30:
                return year, month, day + 1
            else:
                return year, month + 1, 1
        
def dateIsBefore(year1, month1, day1, year2, month2, day2):
    """Returns True if year1-month1-day1 is before
       year2-month2-day2. Otherwise, returns False."""
    if year1 < year2:
        return True
    if year1 == year2:
        if month1 < month2:
            return True
        if month1 == month2:
            return day1 < day2
    return False        

def daysBetweenDates(year1, month1, day1, year2, month2, day2):
    """Returns the number of days between year1/month1/day1
       and year2/month2/day2. Assumes inputs are valid dates
       in Gregorian calendar."""
    # program defensively! Add an assertion if the input is not valid!
    assert dateIsBefore(year1, month1, day1, year2, month2, day2)                 
    #except: "failure"
    days = 0
    while dateIsBefore(year1, month1, day1, year2, month2, day2):
        year1, month1, day1 = nextDay(year1, month1, day1)
        days += 1
    return days

def test():
    test_cases = [((2012,9,30,2012,10,30),30), 
                  ((2012,1,1,2013,1,1),360),
                  ((2012,9,1,2012,9,4),3),
                  ((2013,1,1,1999,12,31), "AssertionError")]
    
    for (args, answer) in test_cases:
        try:
            result = daysBetweenDates(*args)
            if result != answer:
                print "Test with data:", args, "failed"
            else:
                print "Test case passed!"
        except AssertionError:
            if answer == "AssertionError":
                print "Nice job! Test case {0} correctly raises AssertionError!\n".format(args)
            else:
                print "Check your work! Test case {0} should not raise AssertionError!\n".format(args)            
test()

4. 一小步一小步地写出可测试的小部分解答。如本例自定义的nextday函数，可以先写一个小测试，举一些例子测试其正确性，在保证其正确的基础上再完成整个程序的正确性测试。

第三单元

怎样管理数据

本单元要构建爬虫，首先讲解了如何使用结构化数据，主要是列表的使用。字符串不可更改，只会生成新的字符串，而列表可改。这一点可以通过设定别名来发现区别： 列表三个函数append、len、+的使用：
+合并两个列表，是要生成一个新列表的，原列表不发生改变
故以下操作不会改变原列表，即实参不会发生改变，形参在函数调用结束后销毁。 两个小练习区别+、append：

接下来介绍了存储器的层次结构，以及while、for两种循环方式。

<list>.index(x)    //返回元素x在列表中的下标，若不存在会报错
//判断元素是否在列表中
in
not in
<list>.pop()          //移除列表最后一个元素，并返回此元素

接下来就是获取页面的所有链接的函数编写。主要是三个函数，除了第二单元的从一个网页中不停地提取其中URL的get_next_target函数，还有调用get_next_target获取一个页面所有链接并保存的get_all_links函数，以及从种子页面出发，将要爬取的页面加入索引的crawl_web。

def get_next_target(page):
    start_link = page.find('<a href=')
    if start_link == -1:
        return None, 0
    start_quote = page.find('"', start_link)
    end_quote = page.find('"', start_quote + 1)
    url = page[start_quote + 1:end_quote]
    return url, end_quote

def get_all_links(page):
    links = []
    while True:
        url, endpos = get_next_target(page)
        if url:
            links.append(url)
            page = page[endpos:]
        else:
            break
    return links

def crawl_web(seed):
    tocrawl = [seed]          #将爬取的页面链接
    crawled = []                #已爬取的页面链接
    index = []
    while tocrawl:
        page = tocrawl.pop()
        if page not in crawled:
            content = get_page(page)
            #将content送入构建索引的add_page_to_index函数，这是第四单元将做的事，这里直接给出完整版
            add_page_to_index(index, page, content)
            union(tocrawl, get_all_links(content))           #将content中所有链接提取出来加入要爬取列表
            crawled.append(page)
    #返回已建好的索引
    return index

编程练习

控制爬取页面最大数

def crawl_web(seed, max_pages):
    tocrawl = [seed]
    crawled = []
    while tocrawl:
        page = tocrawl.pop()
        if page not in crawled:
            union(tocrawl, get_all_links(get_page(page)))
            crawled.append(page)
        if len(crawled) == max_pages:           #已爬去的页面等于最大数
            break
        
    return crawled

控制爬虫深度

def crawl_web(seed,max_depth):
    tocrawl = [seed]
    crawled = []
    next_depth = []            #下一层要爬取的页面列表
    depth = 0
    while tocrawl and depth <= max_depth:
        page = tocrawl.pop()
        if page not in crawled :
            union(next_depth, get_all_links(get_page(page)))           #新页面先存入next_depth
            crawled.append(page)
        if not tocrawl:                       #tocrawl为空说明本层页面已经爬完
            tocrawl, next_depth = next_depth, []
            depth += 1
    return crawled

判断二维列表是否是数独。一个n * n的数独满足：

1. 每行每列只包含1～n的数字
2. 每行每列出现1～n的数字一次且仅一次

def check_sudoku(s):
    n = len(s)
    a = []
    for i in range(1,n+1):
        a.append(i)              #记录每行每列应该含有的元素
    #print a

    #检查每行是否满足这两点
    for i in range(n):
        rr = []
        for j in range(n):
            if s[i][j] not in rr and s[i][j] in a:
                rr.append(s[i][j])
            else:
                return False

    #检查每列是否满足这两点            
    for i in range(n):
        ll = []
        for j in range(n):
            if s[j][i] not in ll and s[i][j] in a:
                ll.append(s[j][i])
            else:
                return False
    return True

原视频给的答案：从1～n的数字的角度判断每行每列是否出现过，且只出现了一次

def check_sudoku(s):
    n = len(s)
    digit = 1
    while digit <= n:            #循环判断每个数字
        i = 0
        while i < n:
            rc = 0
            lc = 0
            j = 0
            while j < n:
                if s[i][j] == digit:
                    rc += 1
                if s[j][i] == digit:
                    lc += 1
                j += 1
            if rc != 1 or lc != 1:
                return False
            i += 1
        digit += 1
    return True

判断对称/反对称方阵

def symmetric(s):
    # Your code here
    if s == []:
        return True
    l = len(s)
    c = len(s[0])
    
    if c != l :
        return False
    for i in range(l):
        for j in range(i):
            if s[i][j] != s[j][i]:     #反对称改为s[i][j] != -s[j][i]
                return False
    return True

判断单位矩阵

def is_identity_matrix(matrix):
    #Write your code here
    if not matrix:
        return False
    r = len(matrix)
    c = len(matrix[0])
    if r != c:
        return False
    for i in range(r):
#        print matrix[i]
        for j in range(r):
            if i != j and matrix[i][j] != 0:
                return False
            elif i == j and matrix[i][j] != 1:
                return False
                
    return True

输入一个数字字符串，对每个数字，若其比其前面的数字小则加入子数组，否则加入原数组

def numbers_in_lists(string):
    # YOUR CODE
    a = []                  #总数组
    l = len(string)
    b = []                  #子数组
    a.append(int(string[0]))
    mx = int(string[0])
    for i in range(1,l):
        #print i, a
        if int(string[i]) <= mx:
            b.append(int(string[i]))
        else:
            #print b
            if b:
                a.append(b)
                b = []
            a.append(int(string[i]))
            mx = int(string[i])
    if b:
        a.append(b)
    print a
    return a

#testcases
string = '543987'
result = [5,[4,3],9,[8,7]]
print repr(string), numbers_in_lists(string) == result
string= '987654321'
result = [9,[8,7,6,5,4,3,2,1]]
print repr(string), numbers_in_lists(string) == result
string = '455532123266'
result = [4, 5, [5, 5, 3, 2, 1, 2, 3, 2], 6, [6]]
print repr(string), numbers_in_lists(string) == result
string = '123456789'
result = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print repr(string), numbers_in_lists(string) == result