python术语中英对照栈图_Python常用技术栈总结
在python的基礎(chǔ)上，加入了自己的理解，修改一些錯誤。最近準備去一線城市謀求發(fā)展，所以打算重新整理一下，順便加深一下記憶。
Table of Contents
Python語言特性
1 Python的函數(shù)參數(shù)傳遞
看兩個例子:
a = 1
def fun(a):
a = 2
fun(a)
print a # 1
a = []
def fun(a):
a.append(1)
fun(a)
print a # [1]
所有的變量都可以理解是內(nèi)存中一個對象的“引用”，或者，也可以看似c中void*的感覺。
通過id來看引用a的內(nèi)存地址可以比較理解：
a = 1
def fun(a):
print "func_in",id(a) # func_in 41322472
a = 2
print "re-point",id(a), id(2) # re-point 41322448 41322448
print "func_out",id(a), id(1) # func_out 41322472 41322472
fun(a)
print a # 1
注：具體的值在不同電腦上運行時可能不同。
可以看到，在執(zhí)行完a = 2之后，a引用中保存的值，即內(nèi)存地址發(fā)生變化，由原來1對象的所在的地址變成了2這個實體對象的內(nèi)存地址。
而第2個例子a引用保存的內(nèi)存值就不會發(fā)生變化：
a = []
def fun(a):
print "func_in",id(a) # func_in 53629256
a.append(1)
print "func_out",id(a) # func_out 53629256
fun(a)
print a # [1]
這里記住的是類型是屬于對象的，而不是變量。而對象有兩種,“可更改”（mutable）與“不可更改”（immutable）對象。在python中，strings, tuples, 和numbers是不可更改的對象，而 list, dict, set 等則是可以修改的對象。(這就是這個問題的重點)
當(dāng)一個引用傳遞給函數(shù)的時候,函數(shù)自動復(fù)制一份引用,這個函數(shù)里的引用和外邊的引用沒有半毛關(guān)系了.所以第一個例子里函數(shù)把引用指向了一個不可變對象,當(dāng)函數(shù)返回的時候,外面的引用沒半毛感覺.而第二個例子就不一樣了,函數(shù)內(nèi)的引用指向的是可變對象,對它的操作就和定位了指針地址一樣,在內(nèi)存里進行修改.
2 Python中的元類(metaclass)
即類生成器
Python中的元素從上至下分別為type -> metaclass(元類) -> class -> instance
了解元類之前我們看一下創(chuàng)建類的另一種方法：
#定義一個函數(shù)
def fn(self, name = 'world'):
print('Hello', %s'.%name)
#使用type方法創(chuàng)建一個類
#type中的三個參數(shù)分別為：類名，父類，包含的方法。
#與用class創(chuàng)建沒有區(qū)別。
Hell0 = type('Hello', (object, ), dict(say_hello = fn))
接下來我們看一下如何創(chuàng)建一個元類： 。。。。。。。。。
#元類的命名后綴為Metaclass
class SayMetaClass(type):
#__new__后面的三個參數(shù)依舊是類名，父類，包含的方法。
def __new__(cls, name, bases, attrs):
attrs['say_'+name] = lambda self, value, saying = name:print(saying+','+value+'!')
return type.__new__(cls, name, bases, attrs)
最后我們用剛才創(chuàng)建的元類創(chuàng)建類來看一下：
class Hello(object, MetaClass=SayMetaClass):
pass
#因為元類中定義的方法，雖然我們的Hello中并沒有定義方法，它自動生成了一個say_Hello方法。
#在上面的__new__函數(shù)中，我們用attrs['say_'+name]定義了方法。里面使用name變量，所以根據(jù)類名生成了不同的方法。
hello = Hello()
hello.say_Hello('world')#輸出Hello,world!
3 @staticmethod和@classmethod
Python其實有3個方法,即靜態(tài)方法(staticmethod),類方法(classmethod)和實例方法,如下:
def foo(x):
print "executing foo(%s)"%(x)
class A(object):
def foo(self,x):
print "executing foo(%s,%s)"%(self,x)
@classmethod
def class_foo(cls,x):
print "executing class_foo(%s,%s)"%(cls,x)
@staticmethod
def static_foo(x):
print "executing static_foo(%s)"%x
a=A()
這里先理解下函數(shù)參數(shù)里面的self和cls.這個self和cls是對類或者實例的綁定,對于一般的函數(shù)來說我們可以這么調(diào)用foo(x),這個函數(shù)就是最常用的,它的工作跟任何東西(類,實例)無關(guān).對于實例方法,我們知道在類里每次定義方法的時候都需要綁定這個實例,就是foo(self, x),為什么要這么做呢?因為實例方法的調(diào)用離不開實例,我們需要把實例自己傳給函數(shù),調(diào)用的時候是這樣的a.foo(x)(其實是foo(a, x)).類方法一樣,只不過它傳遞的是類而不是實例,A.class_foo(x).注意這里的self和cls可以替換別的參數(shù),但是python的約定是這倆,還是不要改的好.
對于靜態(tài)方法其實和普通的方法一樣,不需要對誰進行綁定,唯一的區(qū)別是調(diào)用的時候需要使用a.static_foo(x)或者A.static_foo(x)來調(diào)用.
\
實例方法
類方法
靜態(tài)方法
a = A()
a.foo(x)
a.class_foo(x)
a.static_foo(x)
A
不可用
A.class_foo(x)
A.static_foo(x)
更多關(guān)于這個問題:
4 類變量和實例變量
類變量：
?是可在類的所有實例之間共享的值（也就是說，它們不是單獨分配給每個實例的）。例如下例中，num_of_instance 就是類變量，用于跟蹤存在著多少個Test 的實例。
實例變量：
實例化之后，每個實例單獨擁有的變量。
class Test(object):
num_of_instance = 0
def __init__(self, name):
self.name = name
Test.num_of_instance += 1
if __name__ == '__main__':
print Test.num_of_instance # 0
t1 = Test('jack')
print Test.num_of_instance # 1
t2 = Test('lucy')
print t1.name , t1.num_of_instance # jack 2
print t2.name , t2.num_of_instance # lucy 2
補充的例子
class Person:
name="aaa"
p1=Person()
p2=Person()
p1.name="bbb"
print p1.name # bbb
print p2.name # aaa
print Person.name # aaa
這里p1.name="bbb"是實例調(diào)用了類變量,這其實和上面第一個問題一樣,就是函數(shù)傳參的問題,p1.name一開始是指向的類變量name="aaa",但是在實例的作用域里把類變量的引用改變了,就變成了一個實例變量,self.name不再引用Person的類變量name了.
可以看看下面的例子:
class Person:
name=[]
p1=Person()
p2=Person()
p1.name.append(1)
print p1.name # [1]
print p2.name # [1]
print Person.name # [1]
5 Python自省
這個也是python彪悍的特性.
自省就是面向?qū)ο蟮恼Z言所寫的程序在運行時,所能知道對象的類型.簡單一句就是運行時能夠獲得對象的類型.比如type(),dir(),getattr(),hasattr(),isinstance().
a = [1,2,3]
b = {'a':1,'b':2,'c':3}
c = True
print type(a),type(b),type(c) #
print isinstance(a,list) # True
6 字典推導(dǎo)式
可能你見過列表推導(dǎo)時,卻沒有見過字典推導(dǎo)式,在2.7中才加入的:
d = {key: value for (key, value) in iterable}
7 Python中單下劃線和雙下劃線
>>> class MyClass():
... def __init__(self):
... self.__superprivate = "Hello"
... self._semiprivate = ", world!"
...
>>> mc = MyClass()
>>> print mc.__superprivate
Traceback (most recent call last):
File "", line 1, in
AttributeError: myClass instance has no attribute '__superprivate'
>>> print mc._semiprivate
, world!
>>> print mc.__dict__
{'_MyClass__superprivate': 'Hello', '_semiprivate': ', world!'}
__foo__:一種約定,Python內(nèi)部的名字,用來區(qū)別其他用戶自定義的命名,以防沖突，就是例如__init__(),__del__(),__call__()這些特殊方法
_foo:一種約定,用來指定變量私有.程序員用來指定私有變量的一種方式.不能用from module import * 導(dǎo)入，其他方面和公有一樣訪問；
__foo:這個有真正的意義:解析器用_classname__foo來代替這個名字,以區(qū)別和其他類相同的命名,它無法直接像公有成員一樣隨便訪問,通過對象名._類名__xxx這樣的方式可以訪問.
8 字符串格式化:%和.format
.format在許多方面看起來更便利.對于%最煩人的是它無法同時傳遞一個變量和元組.你可能會想下面的代碼不會有什么問題:
"hi there %s" % name
但是,如果name恰好是(1,2,3),它將會拋出一個TypeError異常.為了保證它總是正確的,你必須這樣做:
"hi there %s" % (name,) # 提供一個單元素的數(shù)組而不是一個參數(shù)
但是有點丑..format就沒有這些問題.你給的第二個問題也是這樣,.format好看多了.
你為什么不用它?
不知道它(在讀這個之前)
為了和Python2.5兼容(譬如logging庫建議使用%(issue #4))
9 迭代器和生成器
這里有個關(guān)于生成器的創(chuàng)建問題面試官有考：
問： 將列表生成式中[]改成() 之后數(shù)據(jù)結(jié)構(gòu)是否改變？
答案：是，從列表變?yōu)樯善?/p>
>>> L = [x*x for x in range(10)]
>>> L
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
>>> g = (x*x for x in range(10))
>>> g
at 0x0000028F8B774200>
通過列表生成式，可以直接創(chuàng)建一個列表。但是，受到內(nèi)存限制，列表容量肯定是有限的。而且，創(chuàng)建一個包含百萬元素的列表，不僅是占用很大的內(nèi)存空間，如：我們只需要訪問前面的幾個元素，后面大部分元素所占的空間都是浪費的。因此，沒有必要創(chuàng)建完整的列表（節(jié)省大量內(nèi)存空間）。在Python中，我們可以采用生成器：邊循環(huán)，邊計算的機制—>generator
10 *args and **kwargs
參數(shù)組
用*args和**kwargs只是為了方便并沒有強制使用它們.
當(dāng)你不確定你的函數(shù)里將要傳遞多少參數(shù)時你可以用*args.例如,它可以傳遞任意數(shù)量的參數(shù):
>>> def print_everything(*args):
for count, thing in enumerate(args):
... print '{0}. {1}'.format(count, thing)
...
>>> print_everything('apple', 'banana', 'cabbage')
0. apple
1. banana
2. cabbage
相似的,**kwargs允許你使用沒有事先定義的參數(shù)名:
>>> def table_things(**kwargs):
... for name, value in kwargs.items():
... print '{0} = {1}'.format(name, value)
...
>>> table_things(apple = 'fruit', cabbage = 'vegetable')
cabbage = vegetable
apple = fruit
你也可以混著用.命名參數(shù)首先獲得參數(shù)值然后所有的其他參數(shù)都傳遞給*args和**kwargs.命名參數(shù)在列表的最前端.例如:
def table_things(titlestring, **kwargs)
*args和**kwargs可以同時在函數(shù)的定義中,但是*args必須在**kwargs前面.
當(dāng)調(diào)用函數(shù)時你也可以用*和**語法.例如:
>>> def print_three_things(a, b, c):
... print 'a = {0}, b = {1}, c = {2}'.format(a,b,c)
...
>>> mylist = ['aardvark', 'baboon', 'cat']
>>> print_three_things(*mylist)
a = aardvark, b = baboon, c = cat
就像你看到的一樣,它可以傳遞列表(或者元組)的每一項并把它們解包.注意必須與它們在函數(shù)里的參數(shù)相吻合.當(dāng)然,你也可以在函數(shù)定義或者函數(shù)調(diào)用時用*.
11 面向切面編程AOP和裝飾器
做測試的同學(xué)會經(jīng)常用到，要提前了解。
這個AOP一聽起來有點懵,同學(xué)面阿里的時候就被問懵了...
裝飾器是一個很著名的設(shè)計模式，經(jīng)常被用于有切面需求的場景，較為經(jīng)典的有插入日志、性能測試、事務(wù)處理等。裝飾器是解決這類問題的絕佳設(shè)計，有了裝飾器，我們就可以抽離出大量函數(shù)中與函數(shù)功能本身無關(guān)的雷同代碼并繼續(xù)重用。概括的講，裝飾器的作用就是為已經(jīng)存在的對象添加額外的功能。
我也寫過一個關(guān)于裝飾器的文章，(Python裝飾器)[http://139.224.13.65/post/2/]
12 鴨子類型
“當(dāng)看到一只鳥走起來像鴨子、游泳起來像鴨子、叫起來也像鴨子，那么這只鳥就可以被稱為鴨子。”
我們并不關(guān)心對象是什么類型，到底是不是鴨子，只關(guān)心行為。
比如在python中，有很多file-like的東西，比如StringIO,GzipFile,socket。它們有很多相同的方法，我們把它們當(dāng)作文件使用。
又比如list.extend()方法中,我們并不關(guān)心它的參數(shù)是不是list,只要它是可迭代的,所以它的參數(shù)可以是list/tuple/dict/字符串/生成器等.
鴨子類型在動態(tài)語言中經(jīng)常使用，非常靈活，使得python不想java那樣專門去弄一大堆的設(shè)計模式。
13 Python中重載
函數(shù)重載主要是為了解決兩個問題。
可變參數(shù)類型。
可變參數(shù)個數(shù)。
另外，一個基本的設(shè)計原則是，僅僅當(dāng)兩個函數(shù)除了參數(shù)類型和參數(shù)個數(shù)不同以外，其功能是完全相同的，此時才使用函數(shù)重載，如果兩個函數(shù)的功能其實不同，那么不應(yīng)當(dāng)使用重載，而應(yīng)當(dāng)使用一個名字不同的函數(shù)。
好吧，那么對于情況 1 ，函數(shù)功能相同，但是參數(shù)類型不同，python 如何處理？答案是根本不需要處理，因為 python 可以接受任何類型的參數(shù)，如果函數(shù)的功能相同，那么不同的參數(shù)類型在 python 中很可能是相同的代碼，沒有必要做成兩個不同函數(shù)。
那么對于情況 2 ，函數(shù)功能相同，但參數(shù)個數(shù)不同，python 如何處理？大家知道，答案就是缺省參數(shù)。對那些缺少的參數(shù)設(shè)定為缺省參數(shù)即可解決問題。因為你假設(shè)函數(shù)功能相同，那么那些缺少的參數(shù)終歸是需要用的。
好了，鑒于情況 1 跟 情況 2 都有了解決方案，python 自然就不需要函數(shù)重載了。
14 新式類和舊式類
這個面試官問了,我說了老半天,不知道他問的真正意圖是什么.
新式類很早在2.2就出現(xiàn)了,所以舊式類完全是兼容的問題,Python3里的類全部都是新式類.這里有一個MRO問題可以了解下(新式類繼承是根據(jù)C3算法,舊式類是深度優(yōu)先),里講的也很多.
一個舊式類的深度優(yōu)先的例子
class A():
def foo1(self):
print "A"
class B(A):
def foo2(self):
pass
class C(A):
def foo1(self):
print "C"
class D(B, C):
pass
d = D()
d.foo1()
# A
按照經(jīng)典類的查找順序從左到右深度優(yōu)先的規(guī)則，在訪問d.foo1()的時候,D這個類是沒有的..那么往上查找,先找到B,里面沒有,深度優(yōu)先,訪問A,找到了foo1(),所以這時候調(diào)用的是A的foo1()，從而導(dǎo)致C重寫的foo1()被繞過
一個新式類的C3算法的例子
class A(o):pass
class B(o):pass
class C(o):pass
class E(A, B):pass
class F(B, C):pass
class G(E, F):pass
當(dāng)對類E進行查找時，我們會得到這么一個式子：
# 最終操作序列 + 當(dāng)前操作序列
mro(E) = [E] + merge(mro(A), mro(B), [A, B]) = [E] + merge([A, O], [B, O], [A, B])
處理規(guī)則如下：
(1)當(dāng)?shù)谝粋€序列的第一個元素是后續(xù)序列的第一個元素，或者不在后續(xù)序列中再出現(xiàn)，則將這個元素合并到最終的方法解析順序序列中，并從當(dāng)前操作的全部序列中刪除。
(2)如果不符合上一條，則跳過此元素，查找下一個列表的第一個元素，重復(fù)上一條的判斷規(guī)則。
按照上述的規(guī)則處理后我們會得到:
#首先查找第一個序列的第一個元素A，符合規(guī)則
mro(E) = [E, A] + merge([0], [B,0], [B])
#隨后查找O，不符合，跳過，查找B， 查找O， 完成。
mro(E) = [E, A, B] + merge([0], [0]) = [E, A, B, 0]
15 __new__和__init__的區(qū)別
這個__new__確實很少見到,先做了解吧.
__new__是一個靜態(tài)方法,而__init__是一個實例方法.
__new__方法會返回一個創(chuàng)建的實例,而__init__什么都不返回.
只有在__new__返回一個cls的實例時后面的__init__才能被調(diào)用.
當(dāng)創(chuàng)建一個新實例時調(diào)用__new__,初始化一個實例時用__init__.
ps: __metaclass__是創(chuàng)建類時起作用.所以我們可以分別使用__metaclass__,__new__和__init__來分別在類創(chuàng)建,實例創(chuàng)建和實例初始化的時候做一些小手腳.
16 單例模式
?單例模式是一種常用的軟件設(shè)計模式。在它的核心結(jié)構(gòu)中只包含一個被稱為單例類的特殊類。通過單例模式可以保證系統(tǒng)中一個類只有一個實例而且該實例易于外界訪問，從而方便對實例個數(shù)的控制并節(jié)約系統(tǒng)資源。如果希望在系統(tǒng)中某個類的對象只能存在一個，單例模式是最好的解決方案。
__new__()在__init__()之前被調(diào)用，用于生成實例對象。利用這個方法和類的屬性的特點可以實現(xiàn)設(shè)計模式的單例模式。單例模式是指創(chuàng)建唯一對象，單例模式設(shè)計的類只能實例
這個絕對常考啊.絕對要記住1~2個方法,當(dāng)時面試官是讓手寫的.
1 使用__new__方法
class Singleton(object):
def __new__(cls, *args, **kw):
if not hasattr(cls, '_instance'):
orig = super(Singleton, cls)
cls._instance = orig.__new__(cls, *args, **kw)
return cls._instance
class MyClass(Singleton):
a = 1
2 共享屬性
創(chuàng)建實例時把所有實例的__dict__指向同一個字典,這樣它們具有相同的屬性和方法.
class Borg(object):
_state = {}
def __new__(cls, *args, **kw):
ob = super(Borg, cls).__new__(cls, *args, **kw)
ob.__dict__ = cls._state
return ob
class MyClass2(Borg):
a = 1
3 裝飾器版本
def singleton(cls):
instances = {}
def getinstance(*args, **kw):
if cls not in instances:
instances[cls] = cls(*args, **kw)
return instances[cls]
return getinstance
@singleton
class MyClass:
...
4 import方法
作為python的模塊是天然的單例模式
# mysingleton.py
class My_Singleton(object):
def foo(self):
pass
my_singleton = My_Singleton()
# to use
from mysingleton import my_singleton
my_singleton.foo()
17 Python中的作用域
Python 中，一個變量的作用域總是由在代碼中被賦值的地方所決定的。
當(dāng) Python 遇到一個變量的話他會按照這樣的順序進行搜索：
本地作用域（Local）→當(dāng)前作用域被嵌入的本地作用域（Enclosing locals）→全局/模塊作用域（Global）→內(nèi)置作用域（Built-in）
18 GIL線程全局鎖
線程全局鎖(Global Interpreter Lock),即Python為了保證線程安全而采取的獨立線程運行的限制,說白了就是一個核只能在同一時間運行一個線程.對于io密集型任務(wù)，python的多線程起到作用，但對于cpu密集型任務(wù)，python的多線程幾乎占不到任何優(yōu)勢，還有可能因為爭奪資源而變慢。
解決辦法就是多進程和下面的協(xié)程(協(xié)程也只是單CPU,但是能減小切換代價提升性能).
19 協(xié)程
知乎被問到了,呵呵噠,跪了
簡單點說協(xié)程是進程和線程的升級版,進程和線程都面臨著內(nèi)核態(tài)和用戶態(tài)的切換問題而耗費許多切換時間,而協(xié)程就是用戶自己控制切換的時機,不再需要陷入系統(tǒng)的內(nèi)核態(tài).
Python里最常見的yield就是協(xié)程的思想!可以查看第九個問題.
20 閉包
閉包(closure)是函數(shù)式編程的重要的語法結(jié)構(gòu)。閉包也是一種組織代碼的結(jié)構(gòu)，它同樣提高了代碼的可重復(fù)使用性。
當(dāng)一個內(nèi)嵌函數(shù)引用其外部作作用域的變量,我們就會得到一個閉包. 總結(jié)一下,創(chuàng)建一個閉包必須滿足以下幾點:
必須有一個內(nèi)嵌函數(shù)
內(nèi)嵌函數(shù)必須引用外部函數(shù)中的變量
外部函數(shù)的返回值必須是內(nèi)嵌函數(shù)
感覺閉包還是有難度的,幾句話是說不明白的,還是查查相關(guān)資料.
重點是函數(shù)運行后并不會被撤銷,就像16題的instance字典一樣,當(dāng)函數(shù)運行完后,instance并不被銷毀,而是繼續(xù)留在內(nèi)存空間里.這個功能類似類里的類變量,只不過遷移到了函數(shù)上.
閉包就像個空心球一樣,你知道外面和里面,但你不知道中間是什么樣.
21 lambda函數(shù)
其實就是一個匿名函數(shù),為什么叫l(wèi)ambda?因為和后面的函數(shù)式編程有關(guān).
推薦: 知乎
22 Python函數(shù)式編程
這個需要適當(dāng)?shù)牧私庖幌掳?畢竟函數(shù)式編程在Python中也做了引用.
推薦: 酷殼
python中函數(shù)式編程支持:
filter 函數(shù)的功能相當(dāng)于過濾器。調(diào)用一個布爾函數(shù)bool_func來迭代遍歷每個seq中的元素；返回一個使bool_seq返回值為true的元素的序列。
>>>a = [1,2,3,4,5,6,7]
>>>b = filter(lambda x: x > 5, a)
>>>print b
>>>[6,7]
map函數(shù)是對一個序列的每個項依次執(zhí)行函數(shù)，下面是對一個序列每個項都乘以2：
>>> a = map(lambda x:x*2,[1,2,3])
>>> list(a)
[2, 4, 6]
reduce函數(shù)是對一個序列的每個項迭代調(diào)用函數(shù)(先對序列中的第1,2個元素進行操作，得到的結(jié)果在與第三個元素操作。)，下面是求3的階乘：
>>> reduce(lambda x,y:x*y,range(1,4))
6
23 Python里的拷貝
引用和copy(),deepcopy()的區(qū)別
import copy
a = [1, 2, 3, 4, ['a', 'b']] #原始對象
b = a #賦值，傳對象的引用
c = copy.copy(a) #對象拷貝，淺拷貝
d = copy.deepcopy(a) #對象拷貝，深拷貝
a.append(5) #修改對象a
a[4].append('c') #修改對象a中的['a', 'b']數(shù)組對象
print 'a = ', a
print 'b = ', b
print 'c = ', c
print 'd = ', d
輸出結(jié)果：
a = [1, 2, 3, 4, ['a', 'b', 'c'], 5]
b = [1, 2, 3, 4, ['a', 'b', 'c'], 5]
c = [1, 2, 3, 4, ['a', 'b', 'c']]
d = [1, 2, 3, 4, ['a', 'b']]
24 Python垃圾回收機制
Python GC(Gabage Collection)主要使用引用計數(shù)（reference counting）來跟蹤和回收垃圾。在引用計數(shù)的基礎(chǔ)上，通過“標記-清除”（mark and sweep）解決容器對象可能產(chǎn)生的循環(huán)引用問題，通過“分代回收”（generation collection）以空間換時間的方法提高垃圾回收效率。
1 引用計數(shù)
PyObject是每個對象必有的內(nèi)容，其中ob_refcnt就是做為引用計數(shù)。當(dāng)一個對象有新的引用時，它的ob_refcnt就會增加，當(dāng)引用它的對象被刪除，它的ob_refcnt就會減少.引用計數(shù)為0時，該對象生命就結(jié)束了。
優(yōu)點:
簡單
實時性
缺點:
維護引用計數(shù)消耗資源
循環(huán)引用
2 標記-清除機制
基本思路是先按需分配，等到?jīng)]有空閑內(nèi)存的時候從寄存器和程序棧上的引用出發(fā)，遍歷以對象為節(jié)點、以引用為邊構(gòu)成的圖，把所有可以訪問到的對象打上標記，然后清掃一遍內(nèi)存空間，把所有沒標記的對象釋放。
3 分代技術(shù)
分代回收的整體思想是：將系統(tǒng)中的所有內(nèi)存塊根據(jù)其存活時間劃分為不同的集合，每個集合就成為一個“代”，垃圾收集頻率隨著“代”的存活時間的增大而減小，存活時間通常利用經(jīng)過幾次垃圾回收來度量。
Python默認定義了三代對象集合，索引數(shù)越大，對象存活時間越長。
舉例：
當(dāng)某些內(nèi)存塊M經(jīng)過了3次垃圾收集的清洗之后還存活時，我們就將內(nèi)存塊M劃到一個集合A中去，而新分配的內(nèi)存都劃分到集合B中去。當(dāng)垃圾收集開始工作時，大多數(shù)情況都只對集合B進行垃圾回收，而對集合A進行垃圾回收要隔相當(dāng)長一段時間后才進行，這就使得垃圾收集機制需要處理的內(nèi)存少了，效率自然就提高了。在這個過程中，集合B中的某些內(nèi)存塊由于存活時間長而會被轉(zhuǎn)移到集合A中，當(dāng)然，集合A中實際上也存在一些垃圾，這些垃圾的回收會因為這種分代的機制而被延遲。
25 Python的List
26 Python的is
is是對比地址,==是對比值
27 read,readline和readlines
read 讀取整個文件
readline 讀取下一行,使用生成器方法
readlines 讀取整個文件到一個迭代器以供我們遍歷
28 Python2和3的區(qū)別
29 super init
super() lets you avoid referring to the base class explicitly, which can be nice. But the main advantage comes with multiple inheritance, where all sorts of fun stuff can happen. See the standard docs on super if you haven't already.
Note that the syntax changed in Python 3.0: you can just say super().__init__() instead of super(ChildB, self).__init__() which IMO is quite a bit nicer.
30 range and xrange
都在循環(huán)時使用，xrange內(nèi)存性能更好。
for i in range(0, 20):
for i in xrange(0, 20):
What is the difference between range and xrange functions in Python 2.X?
range creates a list, so if you do range(1, 10000000) it creates a list in memory with 9999999 elements.
xrange is a sequence object that evaluates lazily.
操作系統(tǒng)
1 select,poll和epoll
其實所有的I/O都是輪詢的方法,只不過實現(xiàn)的層面不同罷了.
這個問題可能有點深入了,但相信能回答出這個問題是對I/O多路復(fù)用有很好的了解了.其中tornado使用的就是epoll的.
基本上select有3個缺點:
連接數(shù)受限
查找配對速度慢
數(shù)據(jù)由內(nèi)核拷貝到用戶態(tài)
poll改善了第一個缺點
epoll改了三個缺點.
2 調(diào)度算法
先來先服務(wù)(FCFS, First Come First Serve)
短作業(yè)優(yōu)先(SJF, Shortest Job First)
最高優(yōu)先權(quán)調(diào)度(Priority Scheduling)
時間片輪轉(zhuǎn)(RR, Round Robin)
多級反饋隊列調(diào)度(multilevel feedback queue scheduling)
實時調(diào)度算法:
最早截至?xí)r間優(yōu)先 EDF
最低松弛度優(yōu)先 LLF
3 死鎖
原因:
競爭資源
程序推進順序不當(dāng)
必要條件:
互斥條件
請求和保持條件
不剝奪條件
環(huán)路等待條件
處理死鎖基本方法:
預(yù)防死鎖(摒棄除1以外的條件)
避免死鎖(銀行家算法)
檢測死鎖(資源分配圖)
解除死鎖
剝奪資源
撤銷進程
銀行家算法：
允許進程動態(tài)地申請資源，但系統(tǒng)在進行資源分配之前，應(yīng)先計算此次分配資源的安全性，若分配不會導(dǎo)致系統(tǒng)進入不安全狀態(tài)，則分配，反之則不分配。
當(dāng)進程對資源的最大需求量不超過系統(tǒng)現(xiàn)有資源時即可分配。
4 程序編譯與鏈接
Bulid過程可以分解為4個步驟:預(yù)處理(Prepressing), 編譯(Compilation)、匯編(Assembly)、鏈接(Linking)
以c語言為例:
1 預(yù)處理
預(yù)編譯過程主要處理那些源文件中的以“#”開始的預(yù)編譯指令，主要處理規(guī)則有：
將所有的“#define”刪除，并展開所用的宏定義
處理所有條件預(yù)編譯指令，比如“#if”、“#ifdef”、 “#elif”、“#endif”
處理“#include”預(yù)編譯指令，將被包含的文件插入到該編譯指令的位置，注：此過程是遞歸進行的
刪除所有注釋
添加行號和文件名標識，以便于編譯時編譯器產(chǎn)生調(diào)試用的行號信息以及用于編譯時產(chǎn)生編譯錯誤或警告時可顯示行號
保留所有的#pragma編譯器指令。
2 編譯
編譯過程就是把預(yù)處理完的文件進行一系列的詞法分析、語法分析、語義分析及優(yōu)化后生成相應(yīng)的匯編代碼文件。這個過程是整個程序構(gòu)建的核心部分。
3 匯編
匯編器是將匯編代碼轉(zhuǎn)化成機器可以執(zhí)行的指令，每一條匯編語句幾乎都是一條機器指令。經(jīng)過編譯、鏈接、匯編輸出的文件成為目標文件(Object File)
4 鏈接
鏈接的主要內(nèi)容就是把各個模塊之間相互引用的部分處理好，使各個模塊可以正確的拼接。
鏈接的主要過程包塊 地址和空間的分配（Address and Storage Allocation）、符號決議(Symbol Resolution)和重定位(Relocation)等步驟。
5 靜態(tài)鏈接和動態(tài)鏈接
靜態(tài)鏈接方法：靜態(tài)鏈接的時候，載入代碼就會把程序會用到的動態(tài)代碼或動態(tài)代碼的地址確定下來
靜態(tài)庫的鏈接可以使用靜態(tài)鏈接，動態(tài)鏈接庫也可以使用這種方法鏈接導(dǎo)入庫
動態(tài)鏈接方法：使用這種方式的程序并不在一開始就完成動態(tài)鏈接，而是直到真正調(diào)用動態(tài)庫代碼時，載入程序才計算(被調(diào)用的那部分)動態(tài)代碼的邏輯地址，然后等到某個時候，程序又需要調(diào)用另外某塊動態(tài)代碼時，載入程序又去計算這部分代碼的邏輯地址，所以，這種方式使程序初始化時間較短，但運行期間的性能比不上靜態(tài)鏈接的程序
6 虛擬內(nèi)存技術(shù)
虛擬存儲器是指具有請求調(diào)入功能和置換功能,能從邏輯上對內(nèi)存容量加以擴充的一種存儲系統(tǒng).
7 分頁和分段
分頁: 用戶程序的地址空間被劃分成若干固定大小的區(qū)域，稱為“頁”，相應(yīng)地，內(nèi)存空間分成若干個物理塊，頁和塊的大小相等。可將用戶程序的任一頁放在內(nèi)存的任一塊中，實現(xiàn)了離散分配。
分段: 將用戶程序地址空間分成若干個大小不等的段，每段可以定義一組相對完整的邏輯信息。存儲分配時，以段為單位，段與段在內(nèi)存中可以不相鄰接，也實現(xiàn)了離散分配。
分頁與分段的主要區(qū)別
頁是信息的物理單位,分頁是為了實現(xiàn)非連續(xù)分配,以便解決內(nèi)存碎片問題,或者說分頁是由于系統(tǒng)管理的需要.段是信息的邏輯單位,它含有一組意義相對完整的信息,分段的目的是為了更好地實現(xiàn)共享,滿足用戶的需要.
頁的大小固定,由系統(tǒng)確定,將邏輯地址劃分為頁號和頁內(nèi)地址是由機器硬件實現(xiàn)的.而段的長度卻不固定,決定于用戶所編寫的程序,通常由編譯程序在對源程序進行編譯時根據(jù)信息的性質(zhì)來劃分.
分頁的作業(yè)地址空間是一維的.分段的地址空間是二維的.
8 頁面置換算法
最佳置換算法OPT:不可能實現(xiàn)
先進先出FIFO
最近最久未使用算法LRU:最近一段時間里最久沒有使用過的頁面予以置換.
clock算法
9 邊沿觸發(fā)和水平觸發(fā)
邊緣觸發(fā)是指每當(dāng)狀態(tài)變化時發(fā)生一個 io 事件，條件觸發(fā)是只要滿足條件就發(fā)生一個 io 事件
數(shù)據(jù)庫
1 事務(wù)
數(shù)據(jù)庫事務(wù)(Database Transaction) ，是指作為單個邏輯工作單元執(zhí)行的一系列操作，要么完全地執(zhí)行，要么完全地不執(zhí)行。
徹底理解數(shù)據(jù)庫事務(wù): http://www.hollischuang.com/archives/898
2 數(shù)據(jù)庫索引
聚集索引,非聚集索引,B-Tree,B+Tree,最左前綴原理
3 Redis原理
Redis是什么？
是一個完全開源免費的key-value內(nèi)存數(shù)據(jù)庫
通常被認為是一個數(shù)據(jù)結(jié)構(gòu)服務(wù)器，主要是因為其有著豐富的數(shù)據(jù)結(jié)構(gòu) strings、map、 list、sets、 sorted sets
Redis數(shù)據(jù)庫
?通常局限點來說，Redis也以消息隊列的形式存在，作為內(nèi)嵌的List存在，滿足實時的高并發(fā)需求。在使用緩存的時候，redis比memcached具有更多的優(yōu)勢，并且支持更多的數(shù)據(jù)類型，把redis當(dāng)作一個中間存儲系統(tǒng)，用來處理高并發(fā)的數(shù)據(jù)庫操作
速度快：使用標準C寫，所有數(shù)據(jù)都在內(nèi)存中完成，讀寫速度分別達到10萬/20萬
持久化：對數(shù)據(jù)的更新采用Copy-on-write技術(shù)，可以異步地保存到磁盤上，主要有兩種策略，一是根據(jù)時間，更新次數(shù)的快照（save 300 10 ）二是基于語句追加方式(Append-only file，aof)
自動操作：對不同數(shù)據(jù)類型的操作都是自動的，很安全
快速的主--從復(fù)制，官方提供了一個數(shù)據(jù)，Slave在21秒即完成了對Amazon網(wǎng)站10G key set的復(fù)制。
Sharding技術(shù)： 很容易將數(shù)據(jù)分布到多個Redis實例中，數(shù)據(jù)庫的擴展是個永恒的話題，在關(guān)系型數(shù)據(jù)庫中，主要是以添加硬件、以分區(qū)為主要技術(shù)形式的縱向擴展解決了很多的應(yīng)用場景，但隨著web2.0、移動互聯(lián)網(wǎng)、云計算等應(yīng)用的興起，這種擴展模式已經(jīng)不太適合了，所以近年來，像采用主從配置、數(shù)據(jù)庫復(fù)制形式的，Sharding這種技術(shù)把負載分布到多個特理節(jié)點上去的橫向擴展方式用處越來越多。
Redis缺點
是數(shù)據(jù)庫容量受到物理內(nèi)存的限制,不能用作海量數(shù)據(jù)的高性能讀寫,因此Redis適合的場景主要局限在較小數(shù)據(jù)量的高性能操作和運算上。
Redis較難支持在線擴容，在集群容量達到上限時在線擴容會變得很復(fù)雜。為避免這一問題，運維人員在系統(tǒng)上線時必須確保有足夠的空間，這對資源造成了很大的浪費。
4 樂觀鎖和悲觀鎖
悲觀鎖：假定會發(fā)生并發(fā)沖突，屏蔽一切可能違反數(shù)據(jù)完整性的操作
樂觀鎖：假設(shè)不會發(fā)生并發(fā)沖突，只在提交操作時檢查是否違反數(shù)據(jù)完整性。
5 MVCC
?全稱是Multi-Version Concurrent Control，即多版本并發(fā)控制，在MVCC協(xié)議下，每個讀操作會看到一個一致性的snapshot，并且可以實現(xiàn)非阻塞的讀。MVCC允許數(shù)據(jù)具有多個版本，這個版本可以是時間戳或者是全局遞增的事務(wù)ID，在同一個時間點，不同的事務(wù)看到的數(shù)據(jù)是不同的。
MySQL的innodb引擎是如何實現(xiàn)MVCC的
innodb會為每一行添加兩個字段，分別表示該行創(chuàng)建的版本和刪除的版本，填入的是事務(wù)的版本號，這個版本號隨著事務(wù)的創(chuàng)建不斷遞增。在repeated read的隔離級別（事務(wù)的隔離級別請看這篇文章）下，具體各種數(shù)據(jù)庫操作的實現(xiàn)：
select：滿足以下兩個條件innodb會返回該行數(shù)據(jù)：
該行的創(chuàng)建版本號小于等于當(dāng)前版本號，用于保證在select操作之前所有的操作已經(jīng)執(zhí)行落地。
該行的刪除版本號大于當(dāng)前版本或者為空。刪除版本號大于當(dāng)前版本意味著有一個并發(fā)事務(wù)將該行刪除了。
insert：將新插入的行的創(chuàng)建版本號設(shè)置為當(dāng)前系統(tǒng)的版本號。
delete：將要刪除的行的刪除版本號設(shè)置為當(dāng)前系統(tǒng)的版本號。
update：不執(zhí)行原地update，而是轉(zhuǎn)換成insert + delete。將舊行的刪除版本號設(shè)置為當(dāng)前版本號，并將新行insert同時設(shè)置創(chuàng)建版本號為當(dāng)前版本號。
其中，寫操作（insert、delete和update）執(zhí)行時，需要將系統(tǒng)版本號遞增。
?由于舊數(shù)據(jù)并不真正的刪除，所以必須對這些數(shù)據(jù)進行清理，innodb會開啟一個后臺線程執(zhí)行清理工作，具體的規(guī)則是將刪除版本號小于當(dāng)前系統(tǒng)版本的行刪除，這個過程叫做purge。
通過MVCC很好的實現(xiàn)了事務(wù)的隔離性，可以達到repeated read級別，要實現(xiàn)serializable還必須加鎖。
隔離級別由高到低：
READ_UNCOMMITTED
讀未提交，即能夠讀取到?jīng)]有被提交的數(shù)據(jù)，所以很明顯這個級別的隔離機制無法解決臟讀、不可重復(fù)讀、幻讀中的任何一種，因此很少使用
READ_COMMITED
讀已提交，即能夠讀到那些已經(jīng)提交的數(shù)據(jù)，自然能夠防止臟讀，但是無法限制不可重復(fù)讀和幻讀
REPEATABLE_READ
重復(fù)讀取，即在數(shù)據(jù)讀出來之后加鎖，類似"select * from XXX for update"，明確數(shù)據(jù)讀取出來就是為了更新用的，所以要加一把鎖，防止別人修改它。REPEATABLE_READ的意思也類似，讀取了一條數(shù)據(jù)，這個事務(wù)不結(jié)束，別的事務(wù)就不可以改這條記錄，這樣就解決了臟讀、不可重復(fù)讀的問題，但是幻讀的問題還是無法解決
SERLALIZABLE
串行化，最高的事務(wù)隔離級別，不管多少事務(wù)，挨個運行完一個事務(wù)的所有子事務(wù)之后才可以執(zhí)行另外一個事務(wù)里面的所有子事務(wù)，這樣就解決了臟讀、不可重復(fù)讀和幻讀的問題了
6 MyISAM和InnoDB
MyISAM 適合于一些需要大量查詢的應(yīng)用，但其對于有大量寫操作并不是很好。甚至你只是需要update一個字段，整個表都會被鎖起來，而別的進程，就算是讀進程都無法操作直到讀操作完成。另外，MyISAM 對于 SELECT COUNT(*) 這類的計算是超快無比的。
InnoDB 的趨勢會是一個非常復(fù)雜的存儲引擎，對于一些小的應(yīng)用，它會比 MyISAM 還慢。他是它支持“行鎖” ，于是在寫操作比較多的時候，會更優(yōu)秀。并且，他還支持更多的高級應(yīng)用，比如：事務(wù)。
網(wǎng)絡(luò)
1 三次握手
客戶端通過向服務(wù)器端發(fā)送一個SYN(同步序列編號synchronize sequence numbers)來創(chuàng)建一個主動打開，作為三次握手的一部分。客戶端把這段連接的序號設(shè)定為隨機數(shù) A。
服務(wù)器端應(yīng)當(dāng)為一個合法的SYN回送一個SYN/ACK。ACK(確認字符Acknowledgement) 的確認碼應(yīng)為 A+1，SYN/ACK 包本身又有一個隨機序號 B。
最后，客戶端再發(fā)送一個ACK。當(dāng)服務(wù)端受到這個ACK的時候，就完成了三路握手，并進入了連接創(chuàng)建狀態(tài)。此時包序號被設(shè)定為收到的確認號 A+1，而響應(yīng)則為 B+1。
2 四次揮手
注意: 中斷連接端可以是客戶端，也可以是服務(wù)器端. 下面僅以客戶端斷開連接舉例, 反之亦然.
客戶端發(fā)送一個數(shù)據(jù)分段, 其中的 FIN(結(jié)束標志) 標記設(shè)置為1. 客戶端進入 FIN-WAIT 狀態(tài). 該狀態(tài)下客戶端只接收數(shù)據(jù), 不再發(fā)送數(shù)據(jù).
服務(wù)器接收到帶有 FIN = 1 的數(shù)據(jù)分段, 發(fā)送帶有 ACK = 1 的剩余數(shù)據(jù)分段, 確認收到客戶端發(fā)來的 FIN 信息.
服務(wù)器等到所有數(shù)據(jù)傳輸結(jié)束, 向客戶端發(fā)送一個帶有 FIN = 1 的數(shù)據(jù)分段, 并進入 CLOSE-WAIT 狀態(tài), 等待客戶端發(fā)來帶有 ACK = 1 的確認報文.
客戶端收到服務(wù)器發(fā)來帶有 FIN = 1 的報文, 返回 ACK = 1 的報文確認, 為了防止服務(wù)器端未收到需要重發(fā), 進入 TIME-WAIT 狀態(tài). 服務(wù)器接收到報文后關(guān)閉連接. 客戶端等待 2MSL 后未收到回復(fù), 則認為服務(wù)器成功關(guān)閉, 客戶端關(guān)閉連接.
3 ARP協(xié)議
地址解析協(xié)議(Address Resolution Protocol)，其基本功能為透過目標設(shè)備的IP地址，查詢目標的MAC地址，以保證通信的順利進行。它是IPv4網(wǎng)絡(luò)層必不可少的協(xié)議，不過在IPv6中已不再適用，并被鄰居發(fā)現(xiàn)協(xié)議（NDP）所替代。
4 urllib和urllib2的區(qū)別
在Python3中，統(tǒng)一為urllib
這個面試官確實問過,當(dāng)時答的urllib2可以Post而urllib不可以.
urllib提供urlencode方法用來GET查詢字符串的產(chǎn)生，而urllib2沒有。這是為何urllib常和urllib2一起使用的原因。
urllib2可以接受一個Request類的實例來設(shè)置URL請求的headers，urllib僅可以接受URL。這意味著，你不可以偽裝你的User Agent字符串等。
四個模塊：
(1)urllib.request 用來發(fā)送request和獲取request的結(jié)果
(2)urllib.error 包含了urllib.request產(chǎn)生的異常
(3)urllib.parse 用來解析和處理URL
(4)urllib.rebotparse 用來解析頁面的robots.txt文件
5 Post和Get
6 Cookie和Session
Cookie
Session
儲存位置
客戶端
服務(wù)器端
目的
跟蹤會話，也可以保存用戶偏好設(shè)置或者保存用戶名密碼等
跟蹤會話
安全性
不安全
安全
時效
可以很久
不能很久，服務(wù)器壓力問題
session技術(shù)是要使用到cookie的，之所以出現(xiàn)session技術(shù)，主要是為了安全。
7 apache和nginx的區(qū)別
nginx 相對 apache 的優(yōu)點：
輕量級，同樣起web 服務(wù)，比apache 占用更少的內(nèi)存及資源
抗并發(fā)，nginx 處理請求是異步非阻塞的，支持更多的并發(fā)連接，而apache 則是阻塞型的，在高并發(fā)下nginx 能保持低資源低消耗高性能
配置簡潔
高度模塊化的設(shè)計，編寫模塊相對簡單
社區(qū)活躍
apache 相對nginx 的優(yōu)點：
rewrite ，比nginx 的rewrite(實現(xiàn)URL重寫，可以用于限制特定IP訪問網(wǎng)站) 強大
模塊超多，基本想到的都可以找到
少bug ，nginx 的bug 相對較多
超穩(wěn)定
8 網(wǎng)站用戶密碼保存
明文保存
明文hash后保存,如md5。md5:嚴格來說是摘要算法，通過hash后無法重新復(fù)原原始數(shù)據(jù)。
MD5+Salt方式,這個salt可以隨機。salt:俗稱"加鹽"，在字符串后面再拼接一段隨機字符。
知乎使用了Bcrypy(好像)加密
關(guān)于加密強烈推薦一篇文章：給用戶的密碼加點鹽吧
9 HTTP和HTTPS
狀態(tài)碼
定義
1xx 報告
接收到請求，繼續(xù)進程
2xx 成功
步驟成功接收，被理解，并被接受
3xx 重定向
為了完成請求,必須采取進一步措施
4xx 客戶端出錯
請求包括錯的順序或不能完成
5xx 服務(wù)器出錯
服務(wù)器無法完成顯然有效的請求
403: Forbidden
404: Not Found
HTTPS握手,對稱加密,非對稱加密,TLS/SSL,RSA
SSL是TLS的前身
SSL:secure sockets layer 安全套接層 TLS:transport layer security 安全傳輸層協(xié)議
對稱加密:加解密共用一個秘鑰
非對稱加密:一對秘鑰，包括公鑰和私鑰，發(fā)送方使用接受方的公鑰加密數(shù)據(jù)傳輸，接受方使用自己的私鑰解密。
10 XSRF和XSS
CSRF(Cross-site request forgery)跨站請求偽造
XSS(Cross Site Scripting)跨站腳本攻擊
CSRF重點在請求,XSS重點在腳本
11 冪等 Idempotence
HTTP方法的冪等性是指一次和多次請求某一個資源應(yīng)該具有同樣的副作用。(注意是副作用)
GET http://www.bank.com/account/123456，不會改變資源的狀態(tài)，不論調(diào)用一次還是N次都沒有副作用。請注意，這里強調(diào)的是一次和N次具有相同的副作用，而不是每次GET的結(jié)果相同。GET http://www.news.com/latest-news這個HTTP請求可能會每次得到不同的結(jié)果，但它本身并沒有產(chǎn)生任何副作用，因而是滿足冪等性的。
DELETE方法用于刪除資源，有副作用，但它應(yīng)該滿足冪等性。比如：DELETE http://www.forum.com/article/4231，調(diào)用一次和N次對系統(tǒng)產(chǎn)生的副作用是相同的，即刪掉id為4231的帖子；因此，調(diào)用者可以多次調(diào)用或刷新頁面而不必擔(dān)心引起錯誤。
POST所對應(yīng)的URI并非創(chuàng)建的資源本身，而是資源的接收者。比如：POST http://www.forum.com/articles的語義是在http://www.forum.com/articles下創(chuàng)建一篇帖子，HTTP響應(yīng)中應(yīng)包含帖子的創(chuàng)建狀態(tài)以及帖子的URI。兩次相同的POST請求會在服務(wù)器端創(chuàng)建兩份資源，它們具有不同的URI；所以，POST方法不具備冪等性。
PUT所對應(yīng)的URI是要創(chuàng)建或更新的資源本身。比如：PUT http://www.forum/articles/4231的語義是創(chuàng)建或更新ID為4231的帖子。對同一URI進行多次PUT的副作用和一次PUT是相同的；因此，PUT方法具有冪等性。
URL:(uniform/universal resource locator)統(tǒng)一資源定位符
URI:(uniform resource identifier)統(tǒng)一資源標識符(一種標準)
12 RESTful架構(gòu)(SOAP,RPC)
一種軟件架構(gòu)風(fēng)格、設(shè)計風(fēng)格，而不是標準。
(1)每一個URI代表一種資源。
(2)客戶端和服務(wù)器之間，傳遞這種資源的某種表現(xiàn)層。
(3)客戶端通過四個HTTP動詞，對服務(wù)器端資源進行操作，實現(xiàn)"表示層狀態(tài)轉(zhuǎn)化">
13 SOAP
SOAP（原為Simple Object Access Protocol的首字母縮寫，即簡單對象訪問協(xié)議）是交換數(shù)據(jù)的一種協(xié)議規(guī)范，使用在計算機網(wǎng)絡(luò)Web服務(wù)（web service）中，交換帶結(jié)構(gòu)信息。SOAP為了簡化網(wǎng)頁服務(wù)器（Web Server）從XML數(shù)據(jù)庫中提取數(shù)據(jù)時，節(jié)省去格式化頁面時間，以及不同應(yīng)用程序之間按照HTTP通信協(xié)議，遵從XML格式執(zhí)行資料互換，使其抽象于語言實現(xiàn)、平臺和硬件。
14 RPC
RPC（Remote Procedure Call Protocol）——遠程過程調(diào)用協(xié)議，它是一種通過網(wǎng)絡(luò)從遠程計算機程序上請求服務(wù)，而不需要了解底層網(wǎng)絡(luò)技術(shù)的協(xié)議。RPC協(xié)議假定某些傳輸協(xié)議的存在，如TCP或UDP，為通信程序之間攜帶信息數(shù)據(jù)。在OSI網(wǎng)絡(luò)通信模型中，RPC跨越了傳輸層和應(yīng)用層。RPC使得開發(fā)包括網(wǎng)絡(luò)分布式多程序在內(nèi)的應(yīng)用程序更加容易。
總結(jié):服務(wù)提供的兩大流派.傳統(tǒng)意義以方法調(diào)用為導(dǎo)向通稱RPC。為了企業(yè)SOA,若干廠商聯(lián)合推出webservice,制定了wsdl接口定義,傳輸soap.當(dāng)互聯(lián)網(wǎng)時代,臃腫SOA被簡化為http+xml/json.但是簡化出現(xiàn)各種混亂。以資源為導(dǎo)向,任何操作無非是對資源的增刪改查，于是統(tǒng)一的REST出現(xiàn)了.
進化的順序: RPC -> SOAP -> RESTful
15 CGI和WSGI
CGI(common gateway interface)是通用網(wǎng)關(guān)接口，是連接web服務(wù)器和應(yīng)用程序的接口，用戶通過CGI來獲取動態(tài)數(shù)據(jù)或文件等。
CGI程序是一個獨立的程序，它可以用幾乎所有語言來寫，包括perl，c，lua，python等等。
WSGI, Web Server Gateway Interface，是Python應(yīng)用程序或框架和Web服務(wù)器之間的一種接口，WSGI的其中一個目的就是讓用戶可以用統(tǒng)一的語言(Python)編寫前后端。
16 中間人攻擊
在GFW里屢見不鮮的,呵呵.
中間人攻擊（Man-in-the-middle attack，通常縮寫為MITM）是指攻擊者與通訊的兩端分別創(chuàng)建獨立的聯(lián)系，并交換其所收到的數(shù)據(jù)，使通訊的兩端認為他們正在通過一個私密的連接與對方直接對話，但事實上整個會話都被攻擊者完全控制。
DNS欺騙，會話劫持
17 c10k問題
所謂c10k問題，指的是服務(wù)器同時支持成千上萬個客戶端的問題，也就是concurrent 10 000 connection（這也是c10k這個名字的由來）。
推薦: https://my.oschina.net/xianggao/blog/664275
18 socket
應(yīng)用層與TCP/IP協(xié)議族通信的中間軟件抽象層，它是一組接口。
(1)服務(wù)器端先初始化socket
(2)與端口綁定
(3)監(jiān)聽端口
(4)調(diào)用accept阻塞，等待客戶端連接
(5)客戶端初始化一個socket，連接服務(wù)器
Socket=Ip address+ TCP/UDP + port
19 瀏覽器緩存
Expires:HTTP1.O/cache-control:1.1(使用多)
cache-control{
Last-Modified(最后修改時間)：用于記錄修改，判斷是否需要返回整片資源(包體)
If-modified-since：表示請求時間，與上方對比，確定是否有新的改動
Etag：當(dāng)前資源在服務(wù)器的唯一標識，更精確的判斷是否修改
If-None-Match：包含Etag值，與服務(wù)器對比
Max-age：客戶機可以接收生存期不大于指定時間（以秒為單位）的響應(yīng)
}
304 Not Modified
20 HTTP1.0和HTTP1.1
請求頭Host字段,一個服務(wù)器多個網(wǎng)站
長鏈接(一次鏈接多次請求)
文件斷點續(xù)傳
身份認證,狀態(tài)管理,Cache緩存
HTTP請求8種方法介紹
HTTP/1.1協(xié)議中共定義了8種HTTP請求方法，HTTP請求方法也被叫做“請求動作”，不同的方法規(guī)定了不同的操作指定的資源方式。服務(wù)端也會根據(jù)不同的請求方法做不同的響應(yīng)。
GET
GET請求會顯示請求指定的資源。一般來說GET方法應(yīng)該只用于數(shù)據(jù)的讀取，而不應(yīng)當(dāng)用于會產(chǎn)生副作用的非冪等的操作中。
GET會方法請求指定的頁面信息，并返回響應(yīng)主體，GET被認為是不安全的方法，因為GET方法會被網(wǎng)絡(luò)蜘蛛等任意的訪問。
HEAD
HEAD方法與GET方法一樣，都是向服務(wù)器發(fā)出指定資源的請求。但是，服務(wù)器在響應(yīng)HEAD請求時不會回傳資源的內(nèi)容部分，即：響應(yīng)主體。這樣，我們可以不傳輸全部內(nèi)容的情況下，就可以獲取服務(wù)器的響應(yīng)頭信息。HEAD方法常被用于客戶端查看服務(wù)器的性能。
POST
POST請求會 向指定資源提交數(shù)據(jù)，請求服務(wù)器進行處理，如：表單數(shù)據(jù)提交、文件上傳等，請求數(shù)據(jù)會被包含在請求體中。POST方法是非冪等的方法，因為這個請求可能會創(chuàng)建新的資源或/和修改現(xiàn)有資源。
PUT
PUT請求會身向指定資源位置上傳其最新內(nèi)容，PUT方法是冪等的方法。通過該方法客戶端可以將指定資源的最新數(shù)據(jù)傳送給服務(wù)器取代指定的資源的內(nèi)容。
DELETE
DELETE請求用于請求服務(wù)器刪除所請求URI（統(tǒng)一資源標識符，Uniform Resource Identifier）所標識的資源。DELETE請求后指定資源會被刪除，DELETE方法也是冪等的。
CONNECT
CONNECT方法是HTTP/1.1協(xié)議預(yù)留的，能夠?qū)⑦B接改為管道方式的代理服務(wù)器。通常用于SSL加密服務(wù)器的鏈接與非加密的HTTP代理服務(wù)器的通信。
OPTIONS
OPTIONS請求與HEAD類似，一般也是用于客戶端查看服務(wù)器的性能。 這個方法會請求服務(wù)器返回該資源所支持的所有HTTP請求方法，該方法會用’*’來代替資源名稱，向服務(wù)器發(fā)送OPTIONS請求，可以測試服務(wù)器功能是否正常。JavaScript的XMLHttpRequest對象進行CORS跨域資源共享時，就是使用OPTIONS方法發(fā)送嗅探請求，以判斷是否有對指定資源的訪問權(quán)限。 允許
TRACE
TRACE請求服務(wù)器回顯其收到的請求信息，該方法主要用于HTTP請求的測試或診斷。
HTTP/1.1之后增加的方法
在HTTP/1.1標準制定之后，又陸續(xù)擴展了一些方法。其中使用中較多的是 PATCH 方法：
PATCH
PATCH方法出現(xiàn)的較晚，它在2010年的RFC 5789標準中被定義。PATCH請求與PUT請求類似，同樣用于資源的更新。二者有以下兩點不同：
但PATCH一般用于資源的部分更新，而PUT一般用于資源的整體更新。
當(dāng)資源不存在時，PATCH會創(chuàng)建一個新的資源，而PUT只會對已在資源進行更新。
21 Ajax
AJAX,Asynchronous JavaScript and XML（異步的 JavaScript 和 XML）, 是與在不重新加載整個頁面的情況下，與服務(wù)器交換數(shù)據(jù)并更新部分網(wǎng)頁的技術(shù)。
*NIX
unix進程間通信方式(IPC)
管道（Pipe）：管道可用于具有親緣關(guān)系進程間的通信，允許一個進程和另一個與它有共同祖先的進程之間進行通信。
命名管道（named pipe）：命名管道克服了管道沒有名字的限制，因此，除具有管道所具有的功能外，它還允許無親緣關(guān)系進程間的通信。命名管道在文件系統(tǒng)中有對應(yīng)的文件名。命名管道通過命令mkfifo或系統(tǒng)調(diào)用mkfifo來創(chuàng)建。
信號（Signal）：信號是比較復(fù)雜的通信方式，用于通知接受進程有某種事件發(fā)生，除了用于進程間通信外，進程還可以發(fā)送信號給進程本身；linux除了支持Unix早期信號語義函數(shù)sigal外，還支持語義符合Posix.1標準的信號函數(shù)sigaction（實際上，該函數(shù)是基于BSD的，BSD為了實現(xiàn)可靠信號機制，又能夠統(tǒng)一對外接口，用sigaction函數(shù)重新實現(xiàn)了signal函數(shù)）。
消息（Message）隊列：消息隊列是消息的鏈接表，包括Posix消息隊列system V消息隊列。有足夠權(quán)限的進程可以向隊列中添加消息，被賦予讀權(quán)限的進程則可以讀走隊列中的消息。消息隊列克服了信號承載信息量少，管道只能承載無格式字節(jié)流以及緩沖區(qū)大小受限等缺
共享內(nèi)存：使得多個進程可以訪問同一塊內(nèi)存空間，是最快的可用IPC形式。是針對其他通信機制運行效率較低而設(shè)計的。往往與其它通信機制，如信號量結(jié)合使用，來達到進程間的同步及互斥。
內(nèi)存映射（mapped memory）：內(nèi)存映射允許任何多個進程間通信，每一個使用該機制的進程通過把一個共享的文件映射到自己的進程地址空間來實現(xiàn)它。
信號量（semaphore）：主要作為進程間以及同一進程不同線程之間的同步手段。
套接口（Socket）：更為一般的進程間通信機制，可用于不同機器之間的進程間通信。起初是由Unix系統(tǒng)的BSD分支開發(fā)出來的，但現(xiàn)在一般可以移植到其它類Unix系統(tǒng)上：Linux和System V的變種都支持套接字。
數(shù)據(jù)結(jié)構(gòu)
1 紅黑樹
紅黑樹與AVL的比較：
AVL是嚴格平衡樹，因此在增加或者刪除節(jié)點的時候，根據(jù)不同情況，旋轉(zhuǎn)的次數(shù)比紅黑樹要多；
紅黑是用非嚴格的平衡來換取增刪節(jié)點時候旋轉(zhuǎn)次數(shù)的降低；
所以簡單說，如果你的應(yīng)用中，搜索的次數(shù)遠遠大于插入和刪除，那么選擇AVL，如果搜索，插入刪除次數(shù)幾乎差不多，應(yīng)該選擇RB。
編程題
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 變態(tài)臺階問題
一只青蛙一次可以跳上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列二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
使用Step-wise線性搜索:
從右上角開始，每次將搜索值與右上角的值比較。如果大于右上角的值，則直接去除1行，否則去掉1列。
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 去除列表中的重復(fù)元素
用集合
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={}.fromkeys(l1).keys()
l2.sort(key=l1.index)
print l2
列表推導(dǎo)式
l1 = ['b','c','d','b','c','a','a']
l2 = []
[l2.append(i) for i in l1 if not i in l2]
sorted排序并且用列表推導(dǎo)式.
l = ['b','c','d','b','c','a','a']
[single.append(i) for i in sorted(l) if i not in single]
print single
6 鏈表成對調(diào)換
1->2->3->4轉(zhuǎn)換成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
雙指針交換值
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def swapPairs(self, head):
try:
prev = head
tail = prev.next
while True:
prev.value, tail.value = tail.value, prev.value
prev = tail.next
tail = prev.next
finally:
return head
測試
head1 = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
print(head1.value, head1.next.value, head1.next.next.value, head1.next.next.next.value, head1.next.next.next.next)
solu = Solution()
head2 = solu.swapPairs(head1)
print(head2.value, head2.next.value, head2.next.next.value, head2.next.next.next.value, head2.next.next.next.next)
7 創(chuàng)建字典的方法
1 直接創(chuàng)建
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, [])
循環(huán)算法
思路：
定義一個新的空列表
比較兩個列表的首個元素
小的就插入到新列表里
把已經(jīng)插入新列表的元素從舊列表刪除
直到兩個舊列表有一個為空
再把舊列表加到新列表后面
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這個節(jié)點
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 "交叉節(jié)點：",a[-i+1]
break
else:
pass
構(gòu)造鏈表類(原作者所寫有錯誤，以下代碼沒有問題，指針在計算長度時已經(jīng)走到了尾，下面無法再查找了。)
class ListNode:
def __init__(self, x, next = None):
self.value = x
self.next = next
def node(l1, l2):
length1, length2 = 0, 0
#計算鏈表長度
l11 = l1
l22 = l2
while l11:
l11 = l11.next#尾節(jié)點
length1 += 1
while l22:
l22 = l22.next
length2 += 1
print(length1, length2)
#是否相交
#長鏈表先行
if length1 > length2:
for _ in range(length1 - length2):
l1 = l1.next
print(l1.value)
else:
for _ in range(length2 - length1):
l2 = l2.next
print(l2.value)
while l1 and l2:
if l1.next == l2.next:
return l1.next
else:
l1 = l1.next
l2 = l2.next
head1 = ListNode(1)
head12 = ListNode(2)
head13 = ListNode(3)
head14 = ListNode(4)
head1.next = head12
head12.next = head13
head13.next = head14
head2 = ListNode(5, head13)
conclusion = node(head1, head2)
print(conclusion, conclusion.value)
10 二分查找
#coding:utf-8
def binary_search(list,item):
low = 0
high = len(list)-1
while low<=high:
mid = (low+high)/2
guess = list[mid]
if guess>item:
high = mid-1
elif guess
low = mid+1
else:
return mid
return None
mylist = [1,3,5,7,9]
print binary_search(mylist,3)
11 快排
選取一個數(shù)作為關(guān)鍵字，進過一趟排序?qū)?shù)據(jù)分割成兩部分，一部分比關(guān)鍵字小，一部分大。重復(fù)進行。
#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])
12 找零問題
動態(tài)規(guī)劃：逐步進行，從小問題開始遞進，用小問題的答案合成大問題的答案。
我們用d(i) = j 表示湊夠i元最少需要0個硬幣。
d(0) = 0
d(1) = d(n-1)(拿起一個一元硬幣剩余的錢數(shù))+ 1(這個1是拿取的那枚一元硬幣)
d(2) = d(2-1) + 1 = d(1) + 1
d(3) = d(3-1) + 1 = d(2) + 1 或 d(3) = d(3-3) + 1 = d(0) + 1
以此類推....
#coding:utf-8
#values是硬幣的面值values = [ 25, 21, 10, 5, 1]
#valuesCounts 錢幣對應(yīng)的種類數(shù)
#money 找出來的總錢數(shù)
#coinsUsed 對應(yīng)于目前錢幣總數(shù)i所使用的硬幣數(shù)目
def coinChange(values,valuesCounts,money,coinsUsed):
#遍歷出從1到money所有的錢數(shù)可能
for cents in range(1,money+1):
minCoins = cents
#把所有的硬幣面值遍歷出來和錢數(shù)做對比
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}的最少硬幣使用數(shù)為:{1}'.format(cents, coinsUsed[cents]))
13 廣度遍歷和深度遍歷二叉樹
給定一個數(shù)組，構(gòu)建二叉樹，并且按層次打印這個二叉樹
14 二叉樹節(jié)點
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
#二叉樹的遍歷
#簡單的二叉樹節(jié)點類
class Node(object):
def __init__(self,value,left,right):
self.value = value
self.left = left
self.right = right
#中序遍歷:遍歷左子樹,訪問當(dāng)前節(jié)點,遍歷右子樹
def mid_travelsal(root):
if root.left is not None:
mid_travelsal(root.left)
#訪問當(dāng)前節(jié)點
print(root.value)
if root.right is not None:
mid_travelsal(root.right)
#前序遍歷:訪問當(dāng)前節(jié)點,遍歷左子樹,遍歷右子樹
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)
#后續(xù)遍歷:遍歷左子樹,遍歷右子樹,訪問當(dāng)前節(jié)點
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 前序中序求后序
A B D G C E F H(前序)
D G B A E C H F(中序)
通過前序可知A為該二叉樹的根節(jié)點
1：BDG為該二叉樹左子樹的前序
2：DGB位該二叉樹左子樹的中序
3：遞歸
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 單鏈表逆置
(1)從第二個節(jié)點開始記錄當(dāng)前節(jié)點和前一節(jié)點，并將前一節(jié)點斷開。
(2)進入循環(huán)
(3)記錄當(dāng)前節(jié)點的下一節(jié)點，將當(dāng)前節(jié)點下一節(jié)點更改為前一節(jié)點。
(4)兩個指針向后移動，上一節(jié)點改為當(dāng)前節(jié)點，當(dāng)前節(jié)點改為下一節(jié)點。
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
22 兩個字符串是否是變位詞
class Anagram:
"""
@:param s1: The first string
@:param s2: The second string
@:return true or false
"""
#依次取s1中的字符，每次與s2的副本中的每個字符對比。一個字符找不到即False。
#找到后將s2的副本中的對應(yīng)字符改為None。避免因為有重復(fù)字符影響下次比較。
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'))
#將字符串轉(zhuǎn)為列表后排序，然后依次按位置對比。
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'))
#生成兩個26個位置的列表，因為差肯定在26以內(nèi)。(前提是全小寫字母)
#求出s1，s2列表中每一個字符與字符'a'ASCII碼的差。將其插入到列表中對應(yīng)差的位置。
#因為相同字符的差相同，所以會被插入到兩個空列表的相同位置，依次將c1按位置對比即可。
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 動態(tài)規(guī)劃問題
總結(jié)
以上是生活随笔為你收集整理的python术语中英对照栈图_Python常用技术栈总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python并发处理list数据_pyt
- 下一篇： docker 安装mysql_docke