目录

可迭代对象

要想理解python中的生成器,得先从可迭代对象Iterable说起。什么是可迭代对象呢?

定义了可以返回一个迭代器的iter方法的对象,或者定义了可以支持下标索引的getitem方法的对象,就是一个可迭代对象

所以我们可以用如下方法来判断一个实例是否为可迭代对象

1
2
3
4
5
6
7
hasattr((1,2,3), '__iter__') # True

hasattr([1,2,3], '__iter__') # True

hasattr({}, '__iter__') # True

hasattr('abc', '__getitem__') # True

知道了可迭代对象的定义,那么可迭代对象又有什么用呢,如下列所示,我们经常在python中使用for…in循环,那么for…in循环能在所有对象上使用吗?

阅读全文 »

最近在看一本基于pyhton的Design Pattern方面的书,其中涉及到了python的多态,也就是polymorphism。用python来解释,到底什么是多态(polymorphism)呢?StackOverflow上有一个很好的答案,下面便是答案中举的例子

阅读全文 »

目录

作为一个游戏发烧友,同时也是小白全栈开发程序员我买了Alienware却只用来打游戏是在是太可惜了。为了搞搞开发,昨天配置了一天WSL (Windows Subsystems for Linxu),用了Hyper+zsh的终端组合。其中在zsh中输入atom能启动windows的Atom也着实把我惊艳了一把,但其实也就算仅限于打开而已。事实是Windows中的文本编辑器并不能直接编辑其子系统中的文件。所以这个子系统在某些方便我觉得还没有Vagrant方便,没有图形界面,意味着不能使用Atom,Visual Studio Code这样代表先进生产力的工具,于是配置WSL搞搞开发的想法就此作罢。

子系统搞不成,于是有了直接在Ubuntu上工作的想法。其实Alienware上安装Ubuntu不是很难,除了一些蓝牙和Wi-Fi方面的兼容问题,安装过程非常顺利。接下来step by step记录安装过程。

阅读全文 »

目录

安装IBus中文输入法

最近又重新安装了Ubuntu系统。因为要写中文博客,没有中文输入法实在是麻烦。在Ubuntu上安装中文输入法确实没有Windows上显而易见,所以写下步骤方便自己将来参考。

  1. 首先进入系统设置选择language support,如果没有完整安装该功能,先根据系统提示完成安装

  2. 点击install/remove language 来安装中文支持

  3. 接下来在Terminal中手动安装下面任何一个输入法

    sudo apt-get install ibus-pinyin

    sudo apt-get install ibus-sunpinyin

  4. 重启IBus daemon

    ibus restart

  5. 再进入系统设置选择Text Entry,点击左下角的小加号并在add input source界面中搜索Chinese,选择一款拼音输入法

  6. 使用吧

安装搜狗中文输入法

使用了几天IBus的中文输入发,使用体验简直弱爆了。首先4k屏适配有问题,待选框时刻游离在屏幕之外,然而最致命的是,IBus拼音输入法竟然有切换到双拼就无法再切换回来的bug。早年间我在ubuntu 14上使用过搜狗输入法,用户体验良好,于是试着在ubuntu 16.04上安装。虽然安装步骤比在ubuntu 14上稍稍复杂一些,但是搜狗输入法完美适配4k屏幕而且一如既往的好用。安装步骤如下:

阅读全文 »

算法复杂度分析

情况 时间复杂度 空间复杂度
最优 O(N) O(1)
平均 O(N) O(1)
最差 O(N) O(1)

设输入数组长度为N,最优情况在输入数组的最大值不等于N时达成

算法分析

permutation 被定义为长为N的数组,包含整数1到N,且每个整数包含有且仅有一次。根据定义,我们必须遍历完输入数组才能知道是否1到N的每个整数包含有且仅有一次,所以算法复杂度为O(N)且无法继续优化。如何检测输入数组中1到N的每个整数出现有且仅有一次呢?一个比较直观的方法是用一个长度为N的数组作标记,遍历输入数组并在标记数组的对应项作标记,一旦该标记数组所有项均被标记,则说明输入数组满足permutation定义。但是该方法有一个缺点,就是需要成比例于输入数组长度N的存储空间。有没有不需要额外存储空间的算法呢?答案当然是有的,技巧在于利用输入数组,在遍历输入数组的同时,利用输入数组做标记。由于输入数组各项均为正整数,我们可以将某一项置为负值来标记该项索引+1对应的正整数出现过一次。

源代码

1
2
3
4
5
6
7
8
9
def solution(A):
# write your code in Python 2.7
for i in xrange(len(A)):
index = A[i] if A[i] > 0 else -A[i]
if index > len(A) or A[index - 1] < 0:
return 0
else:
A[index - 1] = -A[index - 1]
return 1

算法复杂度分析

情况 时间复杂度 空间复杂度
最优 O(N) O(1)
平均 O(N) O(1)
最差 O(N) O(1)

算法分析

创建检查数组check,遍历数组A的项,若某项的值为整数x,则以整数x作为索引,将check数组对应的项置1。在遍历check数组,寻找值为0时索引的最小值。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
def solution(A):
# write your code in Python 2.7
n=len(A)
max_A=100001
check=[0]*(max_A+1)
for i in xrange(n):
if(A[i]>=0 and A[i]<max_A and check[A[i]-1]==0):
check[A[i]-1]=1
for ind in xrange(max_A+1):
if(check[ind]==0):
return ind+1
return -1

算法复杂度分析

情况 时间复杂度 空间复杂度
最优 O(N+M) O(N)
平均 O(N+M) O(N)
最差 O(N+M) O(N)

算法分析

若要达到最差情况下的时间复杂度为O(N+M),那就意味着不能在A[K] = N + 1时依次将每个counter的值置为当前counters数组的最大值。因为max counter操作的复杂度为O(N)且需要嵌套在复杂度为O(M)的循环中,这样算法的复杂度至少为O(NM)。也就以为着当A[K] = N + 1时,我们不能立即执行max counter操作。借用下惰性求值的概念,只有在真的需要某个counter值的情况的下才执行计算。这就需要建立两个变量,max_A记录当前counters的最大值,lastUpdate记录上一次执行max counter操作时max_A的值。这样只有当A[K] = N + 1时,才把max_A的值赋值给lastUpdate。而当A[i] < N+1时,则要根据lastUpdate的值来更新countermax_A的值。

最后在返回所counters数组值之前,需要根据lastUpdate的值对每个counter的值进行计算

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def solution(N, A):
# each element of array A is an integer within the range [1..N + 1]
# N and M are integers within the range [1..100,000]
M = len(A)
max_A = 0
lastUpdate = 0
counters=[0]*N
for i in xrange(M):
if (A[i]==N+1):
lastUpdate = max_A
if (A[i]<N+1):
if (counters[A[i]-1]<lastUpdate):
counters[A[i]-1]=lastUpdate+1
if (counters[A[i]-1]>max_A):
max_A=counters[A[i]-1]
else:
counters[A[i]-1]=counters[A[i]-1]+1
if (counters[A[i]-1]>max_A):
max_A=counters[A[i]-1]
for j in xrange(N):
if (counters[j]<lastUpdate):
counters[j]=lastUpdate
return counters
# time complexity: O(N + M)

算法复杂度分析

情况 时间复杂度 空间复杂度
最优 O(1) O(1)
平均 O(N) O(X)
最差 O(N) O(X)

最优情况在输入数组长度小于河宽X下达成

算法分析

依次读取输入数组的项,当读取过的项的集合包含1到X在内的所有整数时,输出当前项的数组索引。对于记录读取过的项的集合,可以用一个长度为X+1的check数组来记录。若读取了整数z,就把整数z作为索引,将对应的项置1。对于判断读取过的项的集合是否包含1到X在内的所有整数,我们都可以遍历check数组,检查索引1到X对应的项是否全部为1,如果不是,则说明我们还没有包含1到X在内的所有整数。但是这样,该判断算法需要遍历check数组,复杂度为O(X)。不过有一个小技巧可以将该判断算法降为O(1),那就是在check数组的基础上,再使用step_left变量来记录还需要读取多少个不同的整数后读取过的项的集合才能包含1到X在内的所有整数。若读取了整数z,除了把整数z作为索引,将对应的项置1外,还要根据条件来更新step_left的值。此时,检查算法只需要判断step_left是否为0即可得知读取过的项的集合是否包含1到X在内的所有整数了。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def solution(X, A):
# write your code in Python 2.7
n = len(A)
if (n < X):
return -1
step_left = X
check = [0]*(X+1)
for i in xrange(n):
if (check[A[i]]==0):
check[A[i]]=1
step_left -=1
if (step_left==0):
return i
return -1

算法复杂度分析

情况 时间复杂度 空间复杂度
最优 O(N) O(1)
平均 O(N) O(1)
最差 O(N) O(1)

算法分析

构造数组前段总和first = A[0]以及数组后端总和last = sum(A) - A[0],第一个差值便是abs(first - last)。遍历数组时,不必每次都重新构造数组前段总和以及数组后端总和,只需向first增加当前遍历元素,想las减去当前遍历元素,另外,也只要一个变量min_diff来记录最小差值即可。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
def solution(A):
# write your code in Python 2.7
first = A[0]
last = sum(A) - A[0]
N = len(A)
min_diff = abs(first - last)
for i in xrange(1, N - 1):
num = A[i]
first += num
last -= num
min_diff = min(abs(first - last), min_diff)
return min_diff

算法复杂度分析

情况 时间复杂度 空间复杂度
最优 O(N) O(1)
平均 O(N) O(1)
最差 O(N) O(1)

算法分析

可以想象有一个数组长度为N+1,数组元素为1,2,…N,N+1,这样便可以用等差求和公式算出该数组的总和。用总和减去输入数组A的和便可以知道数组A缺失了哪个元素。注意python sum()的算法复杂度为O(N),故该算法的算法复杂度是O(N)。

源代码

1
2
3
4
5
6
def solution(A):
# write your code in Python 2.7
N = len(A)
start = 1
end = len(A)+1
return (N+1)*(start+end)/2 - sum(A)