安装docker

1. ubunut install Docker CE

更新包信息

1
sudo apt-get update

添加GPS密钥

1
sudo apt-get install apt-transport-https ca-certificates

添加源
在文件/etc/apt/sources.list.d/docker.list中添加相应的源。

1
deb https://apt.dockerproject.org/repo ubuntu-trusty main

更新APT包索引

1
sudo apt-get update

如果以前安装过,先清除旧的包

1
sudo apt-get purge lxc-docker

确保 APT现在是从设置的仓库中下载Docker的

1
apt-cache purge docker-engine

安装

1
sudo apt-get install -y docker-engine

开启守护线程:

1
sudo service docker start

LeetCode_71 Climbing Staris

题意:对于一个n层的阶梯,从地面开始网上走,每次走一步或者每次走两步,请问一共有多少种走法。
思路:“计算走法“可以归纳为DP问题。每次走一步或者走两步,状态转移方程为sum[i] = sum[i - 1] + sum[i - 2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int climbStairs(int n) {
if(n == 0){
return -1;
}
int[] sum = new int[n + 1];
sum[0] = 1;
sum[1] = 1;
for(int i = 2; i <= n; i++){
sum[i] = sum[i - 1] + sum[i -2];
}
return sum[n];
}

LeetCode_62 Unique Paths

题目:一个m * n大小的地图,从地图左上角走到地图右下角,计算一共有多少种走法。

思路:题目的目的就是寻找多少种做法,很容易想到就是使用DP来解决。第一步:设计f[],设计比较适合的f[];第二步:初始化矩阵边缘;第三部:设计转移方程。
点出了向下就是向右,所以sum[i][j] = sum[i][j - 1] + sum[i - 1][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int uniquePaths(int m, int n) {
if(m == 0 || n == 0){
return -1;
}
int[][] sum = new int[m][n];
for(int i = 0; i < m; i++){
sum[i][0] = 1;
}
for(int i = 0; i < n; i++){
sum[0][i] = 1;
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
sum[i][j] = sum[i][j - 1] + sum[i - 1][j];
}
}
return sum[m - 1][n - 1];
}

About DP

从triangle这道题开始

LeetCode 120. Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.For example, given the following triangle

1
2
3
4
5
6
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
爬楼梯问题:
int dfs(int x){
if(x == n){
return 1;
}
if(x >= n){
return 0;
}
if(hash[x] != -1){
return hash[x];
}
hash[x] = def(x + 1) + dfs(x + 2);
return hash[x];
}
这个二维矩阵在计算机的存储格式应该是这样的:
1
2 3
4 5 6
7 8 9 10
int dfs(int x, int y){
if(x >= n){
return 0;
}
//记忆化搜索 Memorize Search.
if(minSum[x][y] == Integer.MAX_VALUE){
return minSum[x][y];
}
minSum[x][y] = Math.min(dfs(x + 1, y), dfs(x + 1, y + 1)) + a[x][y]
return minSum[x][y];
}
//O(2^n) -> O(n^2)
dfs[1,1] //从1,1出发往下走得最短路径(记住当前状态到终点的值,让让这种值可以被重复利用,这是一种经验)
dfs[x,y] //表示从x,y出发往下走的最短路径
1,1 -> 2,1 2,2
2,1 -> (3,2)
2,2 -> (3,2)

动态规划的本质就是记忆化搜索,把上次计算的东西保存下来,可以重复利用。不用每次都从头到尾走一遍,因此动态规划比搜索要快。
Advantage: Easy to think and implement.
Disadvantage: Expensice memory cost.

triangle的两种解法:
解法一:从上往下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//sum[i][j]代表从triangle[0][0]走到triangle[i][j]使用的最小路程
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0){
return -1;
}
int n = triangle.size();
int[][] sum = new int[n][n];
//initialize
sum[0][0] = triangle.get(0).get(0);
for (int i = 1; i < n; i++) {
sum[i][0] = sum[i - 1][0] + triangle.get(i).get(0);
sum[i][i] = sum[i - 1][i - 1] + triangle.get(i).get(i);
}
for (int i = 1; i <= n - 1; i++) {
for (int j = 1; j <= i - 1; j++) {
sum[i][j] = Math.min(sum[i - 1][j - 1], sum[i - 1][j]) + triangle.get(i).get(j);
}
}
int res = Integer.MAX_VALUE;
for(int i = 0; i < n; i++){
res = res < sum[n - 1][i] ? res : sum[n - 1][i];
}
return res;
}

解法二:从下往上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//sum[i][j]代表从triangle[i][j]走到triangle最底层的最小距离
public static int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null || triangle.size() == 0) {
return -1;
}
if (triangle.get(0) == null || triangle.get(0).size() == 0) {
return -1;
}
int n = triangle.size();
int[][] sum = new int[n][n];
//initialize
for (int i = 0; i < n; i++) {
sum[n - 1][i] = triangle.get(n - 1).get(i);
}
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
sum[i][j] = Math.min(sum[i + 1][j], sum[i + 1][j + 1]) + triangle.get(i).get(j);
}
}
return sum[0][0];

动态规划的四种类型

  • Matrix DP

  • Sequence DP

  • Two Sequence Dp
  • Interval DP

线索:如何想到使用DP

  1. 找最大最和最小值
  2. 判断一件事情是否可行
  3. 计算所有方案的总数

Matrix DP

Climbing Stairs

Decode Ways

Jump Game I, II

Palindrome partitoning II

Word Break

Two Sequence DP

Distinct Subsequences

Edit Distance

Interleaving String

Matirx DP

Minimum Path Sum

Triangle

Unique Path I,II

Java多线程

进程与线程的区别:
进程: 每一个进程都有独立的代码和数据空间(进程上下文),进程间的切换有较大的开销,一个进程包含1-n个线程。进程是系统资源分配的最小单位。
线程: 线程相对于进程更加轻量,上下文信息更少,创建和销毁更加简单。多个线程共享一个进程的资源,OS的许多资源分配和管理都是进程级别的,线程是OS调度的最小单位。

I/O密集性的场景适合使用多进程,计算密集型的场景适合多线程。

Python高级特性

1. 切片

定义一个list

1
L = ['Michael', 'Sarch', 'tarcy', 'Bob', 'Jack']

取任意一个区间

1
2
print L[0:3]
# ['Michael', 'Sarch', 'tarcy']

取list最后2个数

1
2
print L[-2:]
# ['Bob', 'Jack']

取前面10个数

1
2
3
L = range(100)
print L[:10]
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

取后面10个数

1
2
print L[-10:]
# [90, 91, 92, 93, 94, 95, 96, 97, 98, 99]

取11-20个数

1
2
print L[10:20]
# [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

前10个数中,每两个取一个

1
2
print L[:10:2]
# [0, 2, 4, 6, 8]

所有的数每5个取一个

1
2
print L[::5]
# [0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95]

str也是list,可以进行切片操作

1
2
3
4
5
print 'ABCDEFG'[:3]
# 'ABC'
print 'ABCDEFG'[::2]
# 'ACEG'

2. 迭代

判断对象是否可迭代对象

1
2
3
4
5
6
7
8
9
from collections import Iterable
print isinstance('abc', Iterable)
# True
print isinstance([1, 2, 3], Iterable)
# True
print isinstance(123, Iterable)
# False

对list实现像Java那样的下表循环

1
2
3
4
5
for i, value in enumerate(['A', 'B', 'C']):
print i, value
# 0 A
# 1 B
# 2 C

在for循环里同时引用两个变量

1
2
3
4
5
for x, y in [(1, 1), (2, 4), (3, 9)]:
print x, y
# 1 1
# 2 4
# 3 9

3. 列表生成式

生成一个1-10的list

1
2
print range(1,11)
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

生成一个[11.22,…,10*10]的list

1
2
3
4
5
6
7
8
9
10
# 复杂写法
L = []
for x in range(1, 11):
L.append(x * x)
print L
# [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
# 一行写法
print [x * x for x in range(1, 11)]
# [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

后面可追加判断

1
2
print [x * x for x in range(1, 11) if x % 2 == 0]
# [4, 16, 36, 64, 100]

实现全排列

1
2
print [m + n for m in 'ABC' for n in 'XYZ']
# ['AX', 'AY', 'AZ', 'BX', 'BY', 'BZ', 'CX', 'CY', 'CZ']

打印出当前目录下所有的文件夹

1
2
3
import os
print [d for d in os.listdir('.')]
# ['.git', '.idea', '123.png', '23.jpg', '27.jpg', 'bayes.py', 'classifierStorage.txt', 'data_struct.py', 'datingTestSet.txt', 'datingTestSet2.txt', 'HuffmanCompression.py', 'image_v5_half.jpg', 'kmeans.py', 'kNN.py', 'kNN.pyc', 'lenses.txt', 'logistic.py', 'mydir', 'mydir000001_0.jpg', 'README.md', 'res.jpg', 'res1.jpg', 'ResizeImageAndMat.py', 'result_v5_half.png', 'RGB2HSV.py', 'save_alpha_image.py', 'test.py', 'test_v1.py', 'trees.py']

在for循环中同时使用多个变量

1
2
3
4
5
6
d = {'x': 'A', 'y': 'B','z': 'C'}
for k, v in d.iteritems():
print k, '=', v
# y = B
# x = A
# z = C

列表生成式使用多个变量生成list

1
2
print [k + '=' + v for k, v in d.iteritems()]
# ['y=B', 'x=A', 'z=C']

把list中所有字符换成小写

1
2
3
L = ['Hello', 'World']
print [s.lower() for s in L]
# ['hello', 'world']

4. 生成器

对于比较长的列表,占用内存较大。只访问部分数据的时候非常浪费内存。生成器只保存算法,每次调用next,计算下一个元素的值。直到计算最后一个元素的值,没有更多的元素的时候,抛出StopIteration的错误。

1
2
3
4
5
6
7
8
9
10
11
g = (x * x for x in range(10))
print g
print g.next()
# 0
print g.next()
# 1
print g.next()
# 2
print g.next()
# 3

使用for循环避免不停地使用next()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
g = (x * x for x in range(10))
print g
for n in g:
print n
"""
0
1
4
9
16
25
36
49
64
81
"""

当推算的算法比较复杂的时候,可以用函数实现。比如,就算斐波那契可数列。
列表生成式的写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def fib(max):
n, a, b = 0,0,1
while n < max:
print b
a, b = b, a + b
n = n + 1
fib(6)
"""
1
1
2
3
5
8
"""

生成器的写法, yield关键字替换print:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def fib(max):
n, a, b = 0,0,1
while n < max:
yield b
a, b = b, a + b
n = n + 1
for n in fib(6):
print n
"""
1
1
2
3
5
8
"""

参考链接

  1. 廖雪峰的Python教程之高级特性