課程大綱：從構(gòu)建一個(gè)簡單的搜索引擎項(xiàng)目出發(fā)，介紹構(gòu)建過程中需要用到的技術(shù)，大致分為三個(gè)部分：
爬取數(shù)據(jù)
建立索引
頁面排序
第一單元
開始你的第一行代碼
課程前三個(gè)單元的目標(biāo)是創(chuàng)建一個(gè)網(wǎng)絡(luò)爬蟲。從一個(gè)種子鏈接開始，跟著鏈接一步步爬取越來越多的頁面，為搜索引擎創(chuàng)建數(shù)據(jù)集。第一單元主要介紹了Python的基本語法，包括變量、字符串等內(nèi)容，完成quiz就行。后面單元要用到主要是字符串的find函數(shù)：
<string>.find(<string>) //若找到字符串就返回第一次出現(xiàn)的位置，否則-1。注意不論字符串內(nèi)容是什么，一定有空字符串
<string>.find(<string>，int x) //查找下標(biāo)x以后的<string>串
比較值得分析的是下面這個(gè)題：注意第三個(gè)選項(xiàng)在未找到支付串，返回-1時(shí)的情況。
本單元的最終練習(xí)是從一個(gè)字符串中提取鏈接：由于我的做法每次都是用find(string)，故每次得到的下標(biāo)都是相對子串的，故最后要提取兩次。若用find(string，x)則可直接用得到的下標(biāo)提取。
page =('<div id="top_bin"><div id="top_content" class="width960">'
'<div class="udacity float-left"><a )
//先找到鏈接標(biāo)志'<a href='的位置
start_link = page.find('<a href=')
l = int(page[start_link:].find('"')) //從start_link以后的子串中找到鏈接起始引號
r = int(page[start_link:].find('"', l + 1)) //找到鏈接結(jié)束引號
url = page[start_link:][l+1:r] //提取子串的子串
print url
搜索引擎和網(wǎng)絡(luò) && 字符串練習(xí)
這兩節(jié)都是Python語法的練習(xí)，第二節(jié)最后一個(gè)練習(xí)是給一個(gè)小數(shù)，要求四舍五入后再轉(zhuǎn)為字符串，不用round
x = 3.14159
#ENTER CODE BELOW HERE
x += 0.5
s = str(x)
l = s.find('.')
#取小數(shù)點(diǎn)前的整數(shù)
print s[:l]
第二單元
怎樣重復(fù)
首先是get_next_target函數(shù)的編寫，就是將從一個(gè)網(wǎng)頁中不停地提取其中的URL的過程編成函數(shù)以供調(diào)用。講解了get_next_target函數(shù)的設(shè)計(jì)過程——輸入、返回值的設(shè)置
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標(biāo)記頁面位置查找下一個(gè)URL
return url, end_quote
在沒有返回值的情況下，傳入的參數(shù)不會改變，如：
def sum(a, b) #無返回值，什么也不會輸出
a = a + b
a = 2, b = 123
print sum(a, b)
print a
=>
None
2
下面這個(gè)例子是帶返回值的情況，會得到正確輸出，但并不會改變輸入的值，也就是說接著print s會輸出 “Hello”。對照上圖可知每個(gè)函數(shù)內(nèi)部會重新設(shè)形參變量指到實(shí)參的值。
實(shí)際上，不可能編寫一個(gè)更改整數(shù)類型或字符串類型輸入值的過程，因?yàn)檫@些類型是不可變的。這樣說的意思是，一旦我們創(chuàng)建一個(gè)整數(shù)或字符串類型的對象，就沒有任何辦法可以改變該對象的值。比如說：
x = 17
z = 'hello'
any_mysterious_procedure(x, z)
#在這段代碼之后，我們知道x的值仍然是17，z的值仍然是'hello'，盡管我們不知道過程 any_mysterious_procedure 是做什么的。
接下來是幾個(gè)函數(shù)包括階乘編寫的小練習(xí)，然后講解if、or、while、break的用法，幾個(gè)小quiz。結(jié)尾的多重賦值練習(xí)
s, t = t, s #交換 s 與 t 的值
第六、七、八節(jié)是Udacify 函數(shù) && 可選編程練習(xí)，都是函數(shù)的編寫問題的練習(xí)
怎樣解決問題
利用計(jì)算兩個(gè)日期之間的天數(shù)這個(gè)問題講解怎樣解決問題
理解問題，包括弄清問題的輸入、輸出。包括輸入什么、輸入如何表現(xiàn)，這個(gè)例子中是兩個(gè)日期，應(yīng)思考兩日期的關(guān)系、合法性，及在不合法輸入情況下的輸出。
通過舉一些例子來充分理解輸入輸出的關(guān)系，在手動計(jì)算的過程中分析算法的步驟過程，思考如何系統(tǒng)化解決問題。
簡化機(jī)械求解過程。寫出偽代碼的思路后不要急著實(shí)現(xiàn)，思考能否簡化算法、邊界情況、特殊情況。本例中直接簡化為一天一天累加。
兩日期之間的天數(shù)，分為兩個(gè)過程：計(jì)算nextday，判斷是否到達(dá)目標(biāo)日期。加入了輸入合法性判斷。一開始可以只給出大致正確的思路即可，具體如閏年這種細(xì)致的問題可以在大致思路正確的基礎(chǔ)上調(diào)整。
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()
- 一小步一小步地寫出可測試的小部分解答。如本例自定義的nextday函數(shù)，可以先寫一個(gè)小測試，舉一些例子測試其正確性，在保證其正確的基礎(chǔ)上再完成整個(gè)程序的正確性測試。
第三單元
怎樣管理數(shù)據(jù)
本單元要構(gòu)建爬蟲，首先講解了如何使用結(jié)構(gòu)化數(shù)據(jù)，主要是列表的使用。字符串不可更改，只會生成新的字符串，而列表可改。這一點(diǎn)可以通過設(shè)定別名來發(fā)現(xiàn)區(qū)別：
+合并兩個(gè)列表，是要生成一個(gè)新列表的，原列表不發(fā)生改變
接下來介紹了存儲器的層次結(jié)構(gòu)，以及while、for兩種循環(huán)方式。
<list>.index(x) //返回元素x在列表中的下標(biāo)，若不存在會報(bào)錯(cuò)
//判斷元素是否在列表中
in
not in
<list>.pop() //移除列表最后一個(gè)元素，并返回此元素
接下來就是獲取頁面的所有鏈接的函數(shù)編寫。主要是三個(gè)函數(shù)，除了第二單元的從一個(gè)網(wǎng)頁中不停地提取其中URL的get_next_target函數(shù)，還有調(diào)用get_next_target獲取一個(gè)頁面所有鏈接并保存的get_all_links函數(shù)，以及從種子頁面出發(fā)，將要爬取的頁面加入索引的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送入構(gòu)建索引的add_page_to_index函數(shù)，這是第四單元將做的事，這里直接給出完整版
add_page_to_index(index, page, content)
union(tocrawl, get_all_links(content)) #將content中所有鏈接提取出來加入要爬取列表
crawled.append(page)
#返回已建好的索引
return index
編程練習(xí)
控制爬取頁面最大數(shù)
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: #已爬去的頁面等于最大數(shù)
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為空說明本層頁面已經(jīng)爬完
tocrawl, next_depth = next_depth, []
depth += 1
return crawled
判斷二維列表是否是數(shù)獨(dú)。一個(gè)n * n的數(shù)獨(dú)滿足：
- 每行每列只包含1～n的數(shù)字
- 每行每列出現(xiàn)1～n的數(shù)字一次且僅一次
def check_sudoku(s):
n = len(s)
a = []
for i in range(1,n+1):
a.append(i) #記錄每行每列應(yīng)該含有的元素
#print a
#檢查每行是否滿足這兩點(diǎn)
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
#檢查每列是否滿足這兩點(diǎn)
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的數(shù)字的角度判斷每行每列是否出現(xiàn)過，且只出現(xiàn)了一次
def check_sudoku(s):
n = len(s)
digit = 1
while digit <= n: #循環(huán)判斷每個(gè)數(shù)字
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
輸入一個(gè)數(shù)字字符串，對每個(gè)數(shù)字，若其比其前面的數(shù)字小則加入子數(shù)組，否則加入原數(shù)組
def numbers_in_lists(string):
# YOUR CODE
a = [] #總數(shù)組
l = len(string)
b = [] #子數(shù)組
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
