MLP

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
45
46
47
48
49

import numpy
from keras.datasets import mnist
from keras.models import Sequential
from keras.layers import Dense
from keras.layers import Dropout
from keras.utils import np_utils
# fix random seed for reproducibility

seed = 7
numpy.random.seed(seed)
# load data
(X_train, y_train), (X_test, y_test) = mnist.load_data()
# flatten 28*28 images to a 784 vector for each image
num_pixels = X_train.shape[1] * X_train.shape[2]
X_train = X_train.reshape(X_train.shape[0], num_pixels).astype('float32')
X_test = X_test.reshape(X_test.shape[0], num_pixels).astype('float32')
# normalize inputs from 0-255 to 0-1
X_train = X_train / 255
X_test = X_test / 255
# one hot encode outputs
y_train = np_utils.to_categorical(y_train)
y_test = np_utils.to_categorical(y_test)
num_classes = y_test.shape[1]
# define baseline model


def baseline_model():
    # create model
    model = Sequential()

    # default value--init is error(exception)
    # model.add(Dense(num_pixels, input_dim=num_pixels, init='normal', activation='relu'))
    # model.add(Dense(num_classes, init='normal', activation='softmax'))

    model.add(Dense(num_pixels, input_dim=num_pixels, activation='relu'))
    model.add(Dense(num_classes, activation='softmax'))

    # Compile model
    model.compile(loss='categorical_crossentropy', optimizer='adam', metrics=['accuracy'])
    return model


# build the model
model = baseline_model()
# Fit the model
model.fit(X_train, y_train, validation_data=(X_test, y_test), epochs=10, batch_size=200, verbose=2)
# Final evaluation of the model
scores = model.evaluate(X_test, y_test, verbose=0)
print("MLP Error: %.2f%%" % (100-scores[1]*100))

CNN

Convolution Neural Network

卷积神经网络主要有三层构成包括：卷积层、线性整流层和池化层。完整的神经网络结构有以下构成，包括输入层（input layer）、卷积层（Convolutional Layer）、线性整流层（Rectified Linear Units Layer）又称activation function–Relu、池化层（Pooling Layer）又称（Down sampling Layer）、全连接层（Full Connected Layer）、输出层（output layer）。

The convolutional layer can turn the original data(for image) into feature map by convolutional kernel. Convolution Kernel designed by the mechanical learning and modified by the full connected layer based on back propagation algorithm.

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
45
46
47
48
49
50
51
52
53
54

import numpy
from keras.datasets import mnist
from keras.models import Sequential
from keras.layers import Dense
from keras.layers import Dropout
from keras.layers import Flatten
from keras.layers.convolutional import Convolution2D
from keras.layers.convolutional import MaxPooling2D
from keras.utils import np_utils
from keras import backend as K

# fix random seed for reproducibility

seed = 7
numpy.random.seed(seed)

# load data
(X_train, y_train), (X_test, y_test) = mnist.load_data()

# reshape to be [samples][pixels][width][height]
X_train = X_train.reshape(X_train.shape[0], 28, 28, 1).astype('float32')
X_test = X_test.reshape(X_test.shape[0], 28, 28, 1).astype('float32')

# normalize inputs from 0-255 to 0-1
X_train = X_train / 255
X_test = X_test / 255

# one hot encode outputs
y_train = np_utils.to_categorical(y_train)
y_test = np_utils.to_categorical(y_test)
num_classes = y_test.shape[1]


def baseline_model():
   # create model
   model = Sequential()
   model.add(Convolution2D(32, (5, 5), padding='valid', input_shape=(28, 28, 1), activation='relu'))
   model.add(MaxPooling2D(pool_size=(2, 2)))
   model.add(Dropout(0.2))
   model.add(Flatten())
   model.add(Dense(128, activation='relu'))
   model.add(Dense(num_classes, activation='softmax'))
   # Compile model
   model.compile(loss='categorical_crossentropy', optimizer='adam', metrics=['accuracy'])
   return model


# build the model
model = baseline_model()
# Fit the model
model.fit(X_train, y_train, validation_data=(X_test, y_test), epochs=10, batch_size=200, verbose=2)
# Final evaluation of the model
scores = model.evaluate(X_test, y_test, verbose=0)
print("CNN Error: %.2f%%" % (100-scores[1]*100))

Enhancement CNN

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

import numpy
from keras.datasets import mnist
from keras.models import Sequential
from keras.layers import Dense
from keras.layers import Dropout
from keras.layers import Flatten
from keras.layers.convolutional import Convolution2D
from keras.layers.convolutional import MaxPooling2D
from keras.utils import np_utils
from keras import backend as K

# fix random seed for reproducibility

seed = 7
numpy.random.seed(seed)

# load data
(X_train, y_train), (X_test, y_test) = mnist.load_data()

# reshape to be [samples][pixels][width][height]
X_train = X_train.reshape(X_train.shape[0], 28, 28, 1).astype('float32')
X_test = X_test.reshape(X_test.shape[0], 28, 28, 1).astype('float32')

# normalize inputs from 0-255 to 0-1
X_train = X_train / 255
X_test = X_test / 255

# one hot encode outputs
y_train = np_utils.to_categorical(y_train)
y_test = np_utils.to_categorical(y_test)
num_classes = y_test.shape[1]


def larger_model():
   # create model
   model = Sequential()
   model.add(Convolution2D(30, (5, 5), padding='valid', input_shape=(28, 28, 1), activation='relu'))
   model.add(MaxPooling2D(pool_size=(2, 2)))
   model.add(Convolution2D(15, 3, 3, activation='relu'))
   model.add(MaxPooling2D(pool_size=(2, 2)))
   model.add(Dropout(0.2))
   model.add(Flatten())
   model.add(Dense(128, activation='relu'))
   model.add(Dense(50, activation='relu'))
   model.add(Dense(num_classes, activation='softmax'))

   # Compile model
   model.compile(loss='categorical_crossentropy', optimizer='adam', metrics=['accuracy'])
   return model


# build the model
model = larger_model()

# Fit the model
model.fit(X_train, y_train, validation_data=(X_test, y_test), epochs=10, batch_size=200, verbose=2)

# Final evaluation of the model
scores = model.evaluate(X_test, y_test, verbose=0)
print("Larger CNN Error: %.2f%%" % (100-scores[1]*100))

Daily Python Problems

Weekly issues(start:2021/4/16)

Special Edition: Recursion7

Q7Levenshtein

在计算文本的相似性时，经常会用到编辑距离。编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。通常来说，编辑距离越小，两个文本的相似性越大。这里的编辑操作主要包括三种：

• 插入：将一个字符插入某个字符串；
• 删除：将字符串中的某个字符删除；
• 替换：将字符串中的某个字符替换为另外一个字符。

当两个字符串都为空串，那么编辑距离为0；

当其中一个字符串为空串时，那么编辑距离为另一个非空字符串的长度；

当两个字符串均为非空时(长度分别为 i 和 j )，取以下三种情况最小值即可：

• 长度分别为 i-1 和 j 的字符串的编辑距离已知，那么加1即可；
• 长度分别为 i 和 j-1 的字符串的编辑距离已知，那么加1即可；
• 长度分别为 i-1 和 j-1 的字符串的编辑距离已知，此时考虑两种情况，若第i个字符和第j个字符不同，那么加1即可；如果不同，那么不需要加1。

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
45
46
47
48
49
50
51

def minDistance(word1, word2):
    if not word1:
        return len(word2 or '') or 0

    if not word2:
        return len(word1 or '') or 0

    size1 = len(word1)
    size2 = len(word2)

    last = 0
    tmp = range(size2 + 1)
    value = None

    for i in range(size1):
        tmp[0] = i + 1
        last = i
        # print word1[i], last, tmp
        for j in range(size2):
            if word1[i] == word2[j]:
                value = last
            else:
                value = 1 + min(last, tmp[j], tmp[j + 1])
                # print(last, tmp[j], tmp[j + 1], value)
            last = tmp[j+1]
            tmp[j+1] = value
        # print tmp
    return value

==optimization==>

def editdistance(str1, str2):

    edit = [[i + j for j in range(len(str2) + 1)] for i in range(len(str1) + 1)]

    for i in range(1, len(str1) + 1):
        for j in range(1, len(str2) + 1):

            if str1[i - 1] == str2[j - 1]:
                d = 0
            else:
                d = 1

            edit[i][j] = min(edit[i - 1][j] + 1, edit[i][j - 1] + 1, edit[i - 1][j - 1] + d)

    return edit[len(str1)][len(str2)]


print(editdistance('hello', 'he'))
>>
3

Q6Pascal 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
31
32
33
34
35
36
37
38

# Function Method
def triangle():
    N = [1]
    while True:
        yield N     # generator特点在于：在执行过程中，遇到yield就中断，下次又继续执行
        N.append(0)  # 每次都要在最后一位加个0，用于后续的叠加
        N = [N[i]+N[i-1] for i in range(len(N))]
 
def print_triangle(x):
    a = 0
    for t in triangle():  # 这里可以每次调用一个N（得力于Yield函数）
        print(t)
        a += 1
        if a ==x:
             break
print_triangle(10) # 打印10行

# ----------------------------------------

N = [1]
for i in range(10):  # 打印10行
    print(N)
    N.append(0)
    N = [N[k] + N[k-1] for k in range(i+2)]
    
==optimization==>

N = [1]  # 先把第一行给定义好
for i in range(10):  # 打印10行
    # 从这里开始我们就要把list转换为一个居中的字符串打印出来
    L = N.copy()   # 我们需要吧N复制给L,而不能直接L = N，因为这样L和N会在同一个地址，后续算法就会出错
    for j in range(len(L)):   # 遍历和转化
        temp = str(L[j])
        L[j] = temp
    l = ' '.join(L).center(50)  # 组合和剧中一起写
    print(l)      # 这里就是打印l了
    N.append(0)   # 因为复制之后L是L，N是N，所以我们还是继续在N末尾加0
    N = [N[k] + N[k-1] for k in range(i+2)]

Q5River Crossing Problem【Unsolved】

写一个程序来解决这样一个问题:3只羚羊和3只狮子准备乘船过河，河边有一艘能容纳2只动物的小船。但是,如果两侧河岸上的狮子数量大于羚羊数量,羚羊就会被吃掉。找到运送办法，使得所有动物都能安全渡河。

1

Q4Least Common Multiple

1
2
3
4
5
6
7
8
9
10
11

def lcm(a, b):
    c = a
    while True:
        if c % a == 0 and c % b == 0:
            print(c)
            break
        c += 1

lcm(8, 2)
>>
8

Q3Gread Common Divisor

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

# recursion method
def gcd(self, x, y):
    if y == 0:
        return x
    else:
        return self.gcd(y, x % y)
==optimization==>>   
def gcd(a, b):
	if b == 0:return a
	return gcd(b, a % b)

# Euclid Algorithm(Toss and divide)
def gcd(m,n):
    """Euclid Algorithm:calculate the greatest common divisor"""
    while m % n != 0:
        oldm = m
        oldn = n
        
        m = oldn
        n = oldm % oldn
    return n
==optimization==>>
def gcd(m, n):
    """Euclid Algorithm:calculate the greatest common divisor"""
    while m % n != 0:
        m, n = n, m % n
    return n

Q2Three Water Problem

====essential===> target_number % gcd == 0

贝祖定理/裴蜀定理：对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y–>ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。

倒水问题属于数论应用题，可以运用丢番图方程进行解答。丢番图方程 ax+by=c (a、b、c是整数)有解，当且仅当c||gcd(a,b)成立

<<整数a、b和它们的最大公约数c。

一定存在整数x,y，使ax+by=c成立。

若d是c的倍数，显然也一定存在整数x,y，使得 ax+by=d成立。>>

实际上，两个容量互质的水杯，可以倒出任意容量的水。

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

class Solution:
    def canMeasureWater(self, x, y, z):
        """
        :type x: int
        :type y: int
        :type z: int
        :rtype: bool
        """
        tmp = self.gcd(x, y)
        if z == 0:
            return True
        if z > x + y:
            return False
        else:
            return z % tmp == 0

    def gcd(self, x, y):
        if y == 0:
            return x
        else:
            return self.gcd(y, x % y)

ans = Solution()
b = ans.canMeasureWater(5, 3, 4)
print(b)
>>
True

use recursion to calculate the sum of list

Q1Sum List

1
2
3
4
5
6
7
8
9
10
11
12
13

# common case
def sum(alist):
    ans = 0
    for x in alist:
        ans += x
    return ans

# recursive case
def sum(alist):
    if len(alist) == 1:
		return alist[0]
    else:
        return alist[0] + sum(alist[1:])

FirthIssue(5/22-27)4

Q4Binary Search

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

# Method one
def binary_search(alist, item):
    found = False
    while not found:
        n = len(alist) % 2

        if n != 0:
            base_num = (len(alist) + 1) // 2
        else:
            base_num = len(alist) // 2

        if len(alist) == 1:
            base_num = 0

        if alist[base_num] == item:
            found = True
        elif alist[base_num] > item:
            alist = alist[:base_num]
            print(alist)
        elif alist[base_num] < item:
            alist = alist[base_num:]
            print(alist)

    return found
# Merhod Two[the best way]
def binary_search(alist, item):
    first = 0
    last = len(alist) - 1
    found = False
    
    while first <= last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
	return found


# Method three: Recuesion
def binary_search_recursion(alist, item):
    if len(alist) == 0:
        return False
    else:
        midpos = len(alist) // 2
        if alist[midpos] == item:
            return True
        else:
            if item < alist[midpos]:
                return binary_search_recursion(alist[:midpos], item)
            else:
                return binary_search_recursion(alist[midpos+1:], item)

lst = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(binary_search(lst, 5))
>>
[1, 2, 3, 4, 5]
[4, 5]
True
>>test 100 tiems
method 1: 0.0007410999999999945
method 2: 3.929999999999212e-05
method 3(recursion): 1.1018111

Q3Fibonacci Sequence

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
45
46
47
48
49

#---- Recursion[the worst way*] ----
def Fibonacci_Recursion_tool(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        return Fibonacci_Recursion_tool(n - 1) + Fibonacci_Recursion_tool(n - 2)


def Fibonacci_Recursion(n):
    result_list = []
    for i in range(1, n + 1):
        result_list.append(Fibonacci_Recursion_tool(i))
    return result_list

#---- Loop [the best way****] ----
def Fibonacci_Loop_tool(n):
    a, b = 0, 1
    while n > 0:
        a, b = b, a + b
        n -= 1


def Fibonacci_Loop(n):
    result_list = []
    a, b = 0, 1
    while n > 0:
        result_list.append(b)
        a, b = b, a + b
        n -= 1
    return result_list

#---- Yield [the best way****] ----
def Fibonacci_Yield_tool(n):
    a, b = 0, 1
    while n > 0:
        yield b
        a, b = b, a + b
        n -= 1


def Fibonacci_Yield(n):
    # return [f for i, f in enumerate(Fibonacci_Yield_tool(n))]
    return list(Fibonacci_Yield_tool(n))

>>
print(Fibonacci_Recursion(5))
[1, 1, 2, 3, 5]

Q2Recursion List

1
2
3
4
5
6
7
8
9
10
11

def rev_list(l):
    if len(l) == 1:
        return l
    else:
        return [l[-1]] + rev_list(l[:-1])  # -1 才算是取最后一位之前的所有

lst = [1, 2, 3, 4, 5]
b = rev_list(lst)
print(b)
>>
[5, 4, 3, 2, 1]

Q1Greedy Algorithm

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

def dpmakechange(coinvaluelist, change, mincoins, coinsused):
    for cents in range(change+1):
        coincount = cents
        newcoin = 1
        for j in [c for c in coinvaluelist if c <= cents]:
            if mincoins[cents-j] + 1 < coincount:
                coincount = mincoins[cents - j] + 1
                newcoin = j
        mincoins[cents] = coincount
        coinsused[cents] = newcoin
    return mincoins

def printcoins(coinsused, change):
    coin = change
    while coin > 0:
        thiscoin = coinsused[coin]
        print(thiscoin)
        coin -= thiscoin

c1 = [1, 5, 10, 21, 25]
coinsused = [0] * 64
coincount = [0] * 64
dpmakechange(c1, 63, coincount, coinsused)
printcoins(coinsused, 63)
print('--------')
printcoins(coinsused, 52)
print('--------')
print(coinsused)

>>
21
21
21
--------
10
21
21
--------
[1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 21, 1, 1, 1, 25, 1, 1, 1, 1, 5, 10, 1, 1, 1, 10, 1, 1, 1, 1, 5, 10, 21, 1, 1, 10, 21, 1, 1, 1, 25, 1, 10, 1, 1, 5, 10, 1, 1, 1, 10, 1, 10, 21]

FourthIssue(5/14-22)6

Q6Tower of Hanoi

1
2
3
4
5
6
7
8

def movedisk(fp, tp):
    print('moving disk from %d to %d' % (fp, ))

def movetower(height, frompole, topole, withpole):
    if height > 1:
        movetower(height-1, frompole, withpole, topole)
        movedisk(frompole, topole)
        movetower(height-1, withpole, topole, frompole)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def hanoi(n, x, y, z):
    global count
    if n == 1:
        print('第%d步：从%s到%s' % (count, x, z))
        count += 1
    else:
        hanoi(n - 1, x, z, y)  # 将n-1个盘子由X移动到Y上
        print('第%d步：从%s到%s' % (count, x, z))  # 将最底下的盘子由X移动到Z上。
        count += 1
        hanoi(n - 1, y, x, z)  # 将Y上的n-1个盘子由Y移动到Z上

count = 1
n = 3
hanoi(n, 'X', 'Y', 'Z')
>>
第1步：从X到Z
第2步：从X到Y
第3步：从Z到Y
第4步：从X到Z
第5步：从Y到X
第6步：从Y到Z
第7步：从X到Z

Q5Integer to arbitary base string

key steps: tostr(n//base, base)

1
2
3
4
5
6
7
8
9
10

# uesing recursion
def tostr(n, base):
    convertstring = '0123456789ABCDEF'
    if n < base:
        return convertstring[n]
    else:
        return tostr(n//base, base) + convertstring[n % base]
tostr(8, 2)
>>
1000

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# useing stack 
def tostr(n, base):
    templist = []
    convertstring = '0123456789ABCDEF'
    if n < base:
        templist.insert(0, convertstring[n])
    else:
        templist.insert(0, convertstring[n % base])
        tostr(n//base, base)
    return ''.join(temlist)

tostr(8, 2)
>>
1000

Q4InfixExp convert PostExp

Q3Unordered Linked List

implement unordered linked list by python

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

class Node:

    def __init__(self, initdata):
        self.data = initdata
        self.next = None

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self, item):
        self.data = item

    def setNext(self, newnext):
        self.next = newnext

    def __repr__(self):
        return '%s--%s' % (self.data, self.next)


class Unorderlist:
    def __init__(self):
        self.head = None

    def isEmpty(self):
        return self.head is None

    def length(self):
        current = self.head
        count = 0
        while current is not None:
            current = current.getNext()
            count += 1

        return count

    def add(self, item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp

    def search(self, item):
        current = self.head
        found = False
        while current is not None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
        return found

    def remove(self, item):
        current = self.head
        previous = None
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
        if previous is None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())

    def __repr__(self):
        return 'the linked list is %s' % self.head

Q2Joseph ring problem

we can simulate a ring with Queue, the essential of joseph ring problem is Queue Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

print(listname)

def simulation_pass_potatoes(listname, num):

    while len(listname) != 1:
        for i in range(num):
            cur_ele = listname.pop()
            listname.insert(0, cur_ele)
        listname.pop()
        print(listname)
    print(listname)

simulation_pass_potatoes(listname, 7)
>>
['brad', 'kent', 'jane', 'susan', 'david', 'bill']
['bill', 'brad', 'kent', 'jane', 'susan']
['jane', 'susan', 'bill', 'brad']
['susan', 'bill', 'brad']
['brad', 'susan']
['susan']

Q1Fixed-Point Problem

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

def post_potatoes(namelist, num):
    cur_list = namelist.copy()
    print(cur_list)

    while len(cur_list) != 1:
        if len(cur_list) >= num:
            index = num - 1
            cur_list.pop(index)
            print(cur_list)
        else:
            index = num % len(cur_list) - 1
            cur_list.pop(index)
            print(cur_list)
    print(cur_list)
    return cur_list

name_list = ['drink', 'star', 'fire', 'drinking', 'drinkle', 'top']
num = 4

post_potatoes(name_list, num)
>>
['drink', 'star', 'fire', 'drinking', 'drinkle', 'top']
['drink', 'star', 'fire', 'drinkle', 'top']
['drink', 'star', 'fire', 'top']
['drink', 'star', 'fire']
['star', 'fire']
['star']

ThirdIssue(5/10-14)4

Q4:Convert list to String

use the builtin function:''.join(list)

1
2
3
4
5
6
7

temp_list = [chr(i) for i in range(65, 91)]
str = ''.join(temp_list)
str1 = '.'.join(temp_list)
print(str)
>>ABCDEFGHIJKLMNOPQRSTUVWXYZ
print(str1)
>>A.B.C.D.E.F.G.H.I.J.K.L.M.N.O.P.Q.R.S.T.U.V.W.X.Y.Z

Q3:Pre/Middle/PostExpression Conversion

The preorder expression requires all operators to appear before the two operands it acts on ps: pay attention to bracket

First in First out

InfixExp(中序表达式)转换PostfixExp(后序表达式)算法：

1）当输入的是操作数时候，直接输出到后序表达式PostfixExp序列中

2）当输入开括号时候，把它压栈

3）当输入的是闭括号时候，先判断栈是否为空，若为空，则发生错误并进行相关处理。若非空，把栈中元素依次弹出并输出到Postfix中，知道遇到第一个开括号，若没有遇到开括号，也发生错误，进行相关处理

4）当输入是运算符op（+、- 、×、/）时候

a)循环，当（栈非空and栈顶不是开括号and栈顶运算符的优先级不低于输入的运算符的优先级）时，反复操作：将栈顶元素弹出并添加到Postfix中

b)把输入的运算符op压栈

5）当中序表达式InfixExp的符号序列全部读入后，若栈内扔有元素，把他们依次弹出并放到后序表达式PostfixExp序列尾部。若弹出的元素遇到空括号，则说明不匹配，发生错误，并进行相关处理

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

# convert middle-expression to post expression
def infixToPostfix(infixerpr):
    temp_list = [chr(i) for i in range(65, 91)]
    alphabet = ''.join(temp_list)
    priority_dict = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}

    Operators = []
    AlphaBet = []

    input_str_to_list = infixerpr.split()

    for element in input_str_to_list:
        if element in alphabet:
            AlphaBet.append(element)
        elif element == '(':
            Operators.append(element)
        elif element == ')':
            tempelement = Operators.pop()
            while tempelement != '(':
                AlphaBet.append(tempelement)
                tempelement = Operators.pop()
        else:
            while (len(Operators) != 0) and (priority_dict[Operators[len(Operators)-1]] >= priority_dict[element]):
                AlphaBet.append(Operators.pop())
            Operators.append(element)

    while len(Operators) != 0:
        AlphaBet.append(Operators.pop())
    print(" ".join(AlphaBet))


infixToPostfix('( A + B ) * ( C + D )')
infixToPostfix('( A + B )')
>> A B + C D + *
>> A B +

Q2.1Calculate Post Expression

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

def post_calculateion_expression(postfixexpr):
    list1 = []

    tokenlist = postfixexpr.split()

    for token in tokenlist:
        if token in '0123456789':
            list1.append(int(token))
        else:
            operand2 = list1.pop()
            operand1 = list1.pop()
            result = doMath(token, operand1, operand2)
            list1.append(result)
    return list1.pop()


def doMath(op, op1, op2):
    if op == '*':
        return op1 * op2
    elif op == '/':
        return op1 / op2
    elif op == '+':
        return op1 + op2
    else:
        return op1 - op2


a = post_calculateion_expression('1 2 + 3 *')
print(a)
>>9

Q1:BaseConversion

Decimal Conversion

remainder number optimization by string`s index

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

def decimal(num):

    bin_num = []

    while num > 0:
        rem = num % 12
        num //= 12
        if rem in [10, 11, 12]:
            if rem == 10:
                bin_num.append('A')
            elif rem == 11:
                bin_num.append('B')
            elif rem == 12:
                bin_num.append('C')
        else:
            bin_num.append(rem)

    bin_num.reverse()

    ans = ''
    for x in bin_num:
        ans = ans + str(x)
    print(ans)
# remaind number`s optimization, Take hexadecimal as an example

def decimal_conversion(num):
    
    digits = '0123456789ABCDEF'
    
    con_num = []
    
    while num > 0:
        rem = num % 16
        num //= 16
        con_num.append(digits[rem])
    
    con_num.reserve()
    
    ans = ''
    for x in con_num:
        ans = ans + str(x)
    print(ans)

Second Issue(5/3-8)3

Q3:RegularExpression

https://deerchao.cn/tutorials/regex/regex.htm

注意：本题是整个面试流程中的第一道开卷试题。
请写一个 匹配 简历中 中英文本科学位名称 的 Python 正则表达式。
本题考察的技能和思维严谨性是这份工作最需要的，请仔细查一查想一想，最好上机调试一下，再作答。

简历中 描述本科学位，一般说：“Bachelor”, “本科”，等等。举几个从实际简历pdf提取的文字例子：
例1：
Education
Philippines University MBA
Pepperdine University – Malibu, CA Bachelor of Arts, Economics
要求正则匹配“Bachelor”。
例2：
学历教育
中国地质大学（武汉）地理信息系统专业——硕士
中国地质大学（武汉）地理信息系统专业——工学学士
要求正则匹配“学士”。
例3：
EDUCATION
Bachelor of Science in CSE/Bio-engineering; Bioinformatics, University of California, San Diego.
要求正则匹配“Bachelor”。

1
2
3
4
5
6
7
8
9
10
11

import re

text1 = 'Pepperdine University – Malibu, CA Bachelor of Arts, Economics'
text2 = '中国地质大学（武汉）地理信息系统专业——工学学士'
text3 = 'Bachelor of Science in CSE/Bio-engineering; Bioinformatics, University of California, San Diego.'

pattern0 = r'\bBachelor.*|\B专业.*|\bBachelor.*\b'

ans = re.search(pattern0, text1)

print(ans.group())

Q2:Match Brackets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import Stack

def match_brackets(str1):
    
    s = Stack()
    balanced = True
    index = 0
    while index < len(str1) and balanced:
        symbol = str1[index
        if symbol == '(':
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else: 
                s.pop()
        index += 1
    if balanced and s.isEmpty():
        retuen True
    else:
        

Q1:Heterologous Detection

Method1Counting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def counting_method(s1, s2):
    c1 = [0] * 26
    c2 = [0] * 26

    for i in range(len(s1)):
        pos = ord(s1[i]) - ord('a')
        c1[pos] += 1

    for i in range(len(s2)):
        pos = ord(s2[i]) - ord('a')
        c2[pos] += 1

    j = 0
    stillok = True
    while j < 26 and stillok:
        if c1[j] == c2[j]:
            j += 1
        else:
            stillok = False

    return stillok

ord(character) –return–>the ascii code

example: ord(‘a’)–return–> 97

Method2Sorting

1
2
3
4
5
6
7
8
9
10
11
12
13

def sortingmethod(s1, s2):
	list1 = list(s1)
	list2 = list(s2)
	
    list1.sort()
    list2.sort()
    
	if list1 == list2:
		print(list1)
        return True
    else:
        print(list1 '\n' list2)
        return False

First Issue(4/16-4/23)2

Q2:Fraction Class

create a instance to inplement the fraction`s add-method

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

def gcd(m, n):
    """Euclid Algorithm:calculate the greatest common divisor"""
    while m % n != 0:
        m, n = n, m % n
    return n

class Fraction():
    
    def __init__(self, top, bottom):
        self.top = top
        self.bottom = bottom
    
    def show(self):
        print(str(self.top) + '/' + str(self.bottom))
    
    def __add__(self, otherfraction)
    	newtop = self.top * otherfraction.bottom + \
        	self.bottom * otherfraction.top
        newbottom = self.bottom * otherfraction.bottom
        common = gcd(newtop, newbottom)
        return Fraction(newtop//common, newbottom//common)
    
    def __str__(self):
        return(str(self.top) + '/' + str(self.bottom))

f1 = Fraction(1, 5)
f2 = Fraction(2, 4)
f3 = f1 + f2 # __add__ ==> '+'
print(f3) # __str__ ==> return->str(Fraction) 

Q1:Split string into individual letters

1
2
3
4
5
6
7
8
9
10
11
12
13

string = 'ab_cdefg'
y = []
alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h',
            'i', 'j', 'q', 'l', 'm', 'n', 'o', 'p',
            'q', 'r', 's', 't', 'u', 'v', 'w', 'x',
            'y', 'z']
# another method about calling alphabet
# alphabet = [chr(i) for i in range(97, 123)]
for i in string:
    print(i)
    if i in alphabet:
        y.append(i)
print(y)

• number(0-9):the representation of ASCII is 48~57
• Lower case letters(a-z):the representation of ASCII is 97~122
• uppercase letters(A-Z):the representation of ASCII is 65~90

ASCII: American standard code for information interchange

Implement Data Structure

Part 1 Introduction

Short Sentences

Client server software:客户机-服务器软件
Shared file system:共享文件系统

A complete binary tree can be represented by a list instead of using ‘list nested list’ or ‘nodes and references’

The hierarchical nature of the tree derivesgenerate an important property, that is, part of the tree (subtree) can be moved to another position as a whole without affecting the layers below.

Implement the tree as a recursive data structure

Implement priority queue with stack

Hash Mapping Relations –> deal with conflicts

Open addressing <==> Linear detection

If there is no termination condition, it will enter an endless loop, the program will crash, and the stack will overflow

Complex recursion problem

Calculate the sum of a column of numbers

Three principles of recursion

The base case recursive algorithm must change the state and move closer to the base case

RecursionError: maximum recursion depth exceeded while getting the str of an object

Each element has a position relative to the other elements

lambda variable : variable operation code block

Calculate execution time

The realization of abstract data types is called data structure

Understand the pre-order, middle-order, and post-order expressions

By running the code 10,000 times to find the time required for each method, we conclude that the best method is list(range())

python data structure performance:数据结构的性能

Realize the inventory plan

Examples of heterologous word detection

The number in the computer is expressed in binary, and the leftmost bit is generally used to indicate whether the number is positive or negative. In this case, the number is a signed integer. If the leftmost bit is not used to indicate positive or negative, but is connected with the following to indicate an integer, then it cannot be distinguished whether the number is positive or negative, and it can only be a positive number, which is an unsigned integer.

Comparison with None performed with equality operators

Instance attribute pinA defined outside init

Lowercase variable imported as non lowercase :小写变量导入为非小写

categorical cross entropy ：分类交叉熵

Remove redundant parentheses

row –> 行 column |–列

hyper-parameter: parameters set manually

Relu:rectified linear units layer

The choice depends on the big data and full connected layer based on back propagation.(Convolution Kernel)

The selection of the convolution kernel is not manual operation, but mechanical learning with the help of big data. The key lies in the loss function of the fully connected layer and the principle of back propagation.

Rectified Linear Units layer == Modified linear unit(Relu layer)

back propagation –> down sampling

Modified linear unit(Relu layer)

Relu activation function–beneficial to–> Gradient descent

The relu function turns negative numbers in the feature map to zero

Activation function

The marginal area will be processed with zero padding

Ability to reduce the data volume of the feature map while retaining the original data

Convolution kernel

Convolutional Neural Network：CNN

gcd: greatest common divisor

Euclid Algorithm:欧几里得算法

1
2
3
4
5
6
7
8

def gcd(m, n):
    while m % n != 0:
        oldm = m
        oldn = n

        m = oldn
        n = oldm % oldn
    return n

A common example is to implement a data type of construct class fraction

library root：库根

Image recognition process

representation learning development history

Input layer ==> Hidden layer ==> Output layer

Professional Edition

enhanced CNN

download dataset

Paper framework

Introduction to unsupervised learning

Mechanical learning

Marked data

format specification ==> syntax specification

Exception handling contains[Syntax Error ==> logical error]

Separate ==> Delimiter(sep=””)

Control structure contains Iteration(while) and branch(if/elif/else)

Single branch structure

Absolute value

return a boolean value

Unordered collection

Set does not allow duplicate elements

Heterogeneous data

Tabs：制表符

Newline:换行符

Space:空格

Thought report:思想汇报

Experience:心得体会

Uppercase letter

Lower case letters

Built-in collection data type(set/list/dictionary/hash map/tuple/string)

Built-in atomic data type(binary data type/float/int/ : contains Numerical class Boolean value)

Take an integer ==> a//b

Take the remainder ==> a%b

Object-Oriented Programming

Data perspective independent of reality

The implementation of abstract data types is called data structure

Information hiding

How to learn data structure and abstract data types

Sequential execution == 顺序执行

Decision branch == 决策分支

Loop iteration == 循环迭代

control statement

data type

This is an example of process abstraction

What is programming

square root == Cube

what is the computer science

the process of solving questions

Word List

merge

Framework thinking awareness Hash table Mapping relations

Cache Cookies Recursive call Dynamic programming
Fractal basic situation Key term Programming exercises

Palindrome detector Linked list

logarithm time complexity index
Brute-force Ordinary situation Magnitude

magnitude Worst way List comprehension generate

Architecture nutshell batch filter regression

Modifiable sequence grammar Interactive

encapsulation annotation notation assign

alphabet introduction Objectives of this chapter

getting Started interface Low-level details

序章

二零二一年四月十四分，辽宁阜新，二十三点零三分。

对于社会思考的越多，越有一个迫切的想法——在目前的企业里，没有一个是公有制企业，除国营企业外，个人私有制、家族私有制、红色资本家和帝国买办阶级占据了绝大多数。共产主义者绝对不能仅仅停留在提出问题上，更应该根据实际解决问题，独立自主，联合但不能失去自己的独立性，要保持经济基础和上层建筑相适应，始终以马列毛作为自己的思想基础。

English Study Three

COVID19

covid-19 epidemic forecast

Research on data-driven evaluation and prediction modeling of the development and spread of the new crown epidemic

Implement Data Structure By Python

Book structure ==> review

Data Structure

Graph

Graph database

Breadth first search

depth first search

Directed graph == Undirected graph

Binary Tree

Diagram/graph connecting everything

Only trees created with randomly shuffled data can be more balanced. If all inserted data is sorted, then the binary tree is out of balance.

If there are two sub nodes, the value of one sub node must be less than the sup node, and the value of the other sub node must be greater than the sup node.

Quick Select

Binary tree that makes everything faster

Doubly linked list

Worst case

Node-based data structure

Store data and next physical address

Recursion

Recursion in the eyes of computers

Fast recursive algorithm

QUEUE

Queue: first in, first out[FIFO]

The queue is also an ideal tool for processing asynchronous requests-it can ensure that the requests are executed in the order in which they are received. In addition, it is also often used to simulate real-world scenarios where things need to be processed in an orderly manner, such as airplanes waiting in line for take-off, patients waiting in line to see a doctor

insert data at the end

read data at the begin

remove data at the begin

STACK

insert data at the end

read data at the end

remove data at the end

Queue: last in, first out[LIFO]

Stack: all operations at the end of stack(STACK TOP)

When the order of data processing is opposite to the order of acceptance (LIFO), the stack is just right, like the “undo” action of a word processor, or the function call of a network application, it should be implemented with a stack

Stacks are rarely used in scenarios that require long-term retention of data, but are often used in various algorithms for processing temporary data

rules to follow: last in, first out

The end of the stack is called the top of the stack

The beginning of the stack is called the bottom of the stack

Its operations are at the end of the data structure

So far, our discussion of data structure has focused on its performance

Use stacks and queues to construct smart code

Hash Table

Hash table in two ways: one is the same value as the Value of Key, the general structure of this case we call for the Set (collection); and if the Key and Value corresponding to the content is not the same, then we call it One case is Map, which is commonly known as a collection of key-value pairs.

The ratio of the amount of data to the number of grids is called the load factor ==> (0.7)

The golden rule to avoid conflicts and save space: add ten grids for every seven elements added

Split link

Deal with conflicts

Alphabet

multiply list

A dictionary of fun and profitable synonyms

hash tables ==> dictionary (data structure)

Find a quick hash table查找快速哈希表

Intersection

Average situation

The role of O()

The two exchange positions

Sorting Algorithm

Select Sort

The two exchange positions

Compare the remaining values with the extracted values, find the minimum value and assign its index to the minimum value

Exchange the position of the extracted value and the minimum value according to the index

Bubble Sort

The essence of the sorting algorithm is a loop, so you only need to focus on the first loop.

DataStructure

Part3Queue-Stack

Use Stack Implement Queue

stack

• push–>append

• pop–>pop

• peek–>return the new item

• isEmpty–>return Bool

• size–>return len

入栈

出栈

queue

• enqueue–>append
• dequeue–>pop
• isEmpty–>return Bool
• size–>retuen size

入队

出队

stack–>queue

queue–>stack

Part2Algorithm Analysis

Four methods for generating list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

import timeit

def connect():
	l = []
	for i in range(1000):
		l = l + [i]

def append():
	l = []
	for i in range(1000):
		l.append(i)

def comprehension():
	l = [i for i in range(1000)]
	
def list_range():
	l = list(range(1000))

t1 = timeit.timeit('connect()', 'from __main__ import connect', number = 100000)
print('connect ', t1, 'millisecondes')

By running the code 100,000 times to find the time required for each method, we conclude that the best method is list range()

O(1) <– append O(n) <– + if the length of list needed connecting is n

Part1Introduction

GCD_LCM

GCD: greatest common divisor

Euclid Algorithm:欧几里得算法

1
2
3
4
5
6
7
8

def gcd(n, m):
	while n % m != 0:
		oldm = m
		oldn = n
		
		m = oldn
		n = oldm % oldn
	return n

LCM: least common multiple

1
2
3
4
5
6
7
8
9
10
11
12

def lcm(x, y):
    if x > y:
        greater = x
    else:
        greater = y

    while True:
        if greater % x == 0 and greater % y == 0:
            lcmnum = greater
            break
        greater += 1
    return lcmnum

Set/Collection

有序集合：可以包含任意数量的、各不相同的元素，有序集合的每个元素都关联着一个浮点数格式的分值（score），并且有序集合会按照分值，以从小到大的顺序来排列有序集合中的各个元素。

无序集合：集合（set）是一个无序的不重复元素序列。可以使用大括号 { } 或者 set() 函数创建集合，注意：创建一个空集合必须用 set() 而不是 { }**，因为 **{ } 是用来创建一个空字典。

集合不含重复元素，有序和无序的区别在于是否可以用score(index)进行排序

list tuple string是有序集合

dictionary set 是无序集合

注：set是一个不含key的字典，含有key-value pairs的字典又称为Hash Map

Sorting Algorithm

1Bubble Sort

The idea of bubble sort is that in each cycle, the big element goes down and the small one goes up, so that sorting is carried out. The specific process is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

       
def bubble_sort(alist):
        for passnum in range(len(alist) - 1, 1, -1):
        	for i in range(passnum):
            	if alist[i] > alist[i+1]:
                	temp = alist[i]
                	alist[i] = alist[i+1]
                	alist[i+1] = temp
    	return alist

# enhancement bubble sort
def sbubble_sort(lst):

    unsorted_index = len(lst) - 1
    sorted_sign = False

    while not sorted_sign:
        sorted_sign = True
        for i in range(unsorted_index):
            if lst[i] > lst[i+1]:
                sorted_sign = False
                lst[i], lst[i+1] = lst[i+1], lst[i]
        unsorted_index = unsorted_index - 1

Optimize Bubble(鸡尾酒排序)

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

def cocktail_sort(iterable):
    '''鸡尾酒排序（英语：Cocktail Sort/Shaker Sort）是冒泡排序的轻微变形，
    它还有很多奇怪的名字，双向冒泡排序 (Bidirectional Bubble Sort)、
    波浪排序 (Ripple Sort)、摇曳排序 (Shuffle Sort)、
    飞梭排序 (Shuttle Sort) 和欢乐时光排序 (Happy Hour Sort)
    参数：可迭代序列
    返回：升序排序后的可迭代序列
    原理：
     1. 对序列向尾部做升序冒泡排序，最大元素沉落尾部。
     2. 对序列向头部做降序冒泡排序，最小元素升到头部。
     3. 交替重复步骤1、2，逐渐缩小无序元素范围，直到没有无序元素。
    时间复杂度：O(n^2)
    稳定性： 稳定
    '''
    for i in range(len(iterable) - 1, 1, -1):
        bubbled = False

        for j in range(i):
            if iterable[j] > iterable[j + 1]:
                iterable[j], iterable[j + 1] = iterable[j + 1], iterable[j]
                bubbled = True

        for j in range(i, 1, -1):
            if iterable[j] < iterable[j - 1]:
                iterable[j], iterable[j - 1] = iterable[j - 1], iterable[j]
                bubbled = True

        if not bubbled:
            break

    return iterable

2Select Sort

The idea of select sort is to find the smallest value in the first place in the process of each loop, loop to find other smaller values and place it in the next position, and sort by searching. The process is as follows:

1
2
3
4
5
6
7
8
9

def select_sort(a):
    n = len(a) - 1
    for i in range(n):
        min_index = i
        for j in range(i, n+1):
            if a[j] < a[min_index]:
                min_index = j
        a[i], a[min_index] = a[min_index], a[i]
    return a

3Insert Sort

The idea of insert sort is to compare with the previous elements. The big elements are placed at the back and the small ones are placed at the front. The specific process is as follows:

1
2
3
4
5
6
7
8
9
10

def insert_sort(a):
    n = len(a)
    for i in range(1, n):
        cur_val = a[i]
        pos = i
        while pos > 0 and a[pos - 1] > cur_val:
            a[pos] = a[pos - 1]
            pos -= 1
        a[pos] = cur_val
    return a

4ShellSort

Shell sort is another variation of insert sort. The final sort is achieved through interval insert sort and gradually reducing the interval. The process is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def shell_sort(a):
    n = len(a)
    gap = n // 2
    while gap > 0:
        for i in range(gap):
            gap_insert(a, i, gap)   #有间隔的插入排序
        gap //= 2
    return a
def gap_insert(a, sta, gap):
    for i in range(sta + gap, len(a), gap):
        cur_val = a[i]
        pos = i
        while pos > sta and a[pos - gap] > cur_val:
            a[pos] = a[pos - gap]
            pos -= gap
        a[pos] = cur_val
    return a
            

if __name__ == "__main__":
    a = [90, 5, 83, 42, 12, 15]
    print(shell_sort(a))

5MergeSort

Merge sort is based on the idea of divide and conquer. The data to be sorted is divided into two subsequences, the subsequences are sorted, and then the sorted subsequences are merged to achieve the final sorting. The process is as follows:

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

def merge_sort(a):
    if len(a) <= 1:
        return a
    n = len(a) // 2
    left = merge_sort(a[:n])    #子序列归并排序
    right = merge_sort(a[n:])   
    return merge(left, right)   #合并排好序的子序列
def merge(left, right):
    l, r = 0, 0
    res = []
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            res.append(left[l])
            l += 1
        else:
            res.append(right[r])
            r += 1
    res.extend(left[l:])
    res.extend(right[r:])
    return res
            

if __name__ == "__main__":
    a = [90, 5, 83, 42, 12, 15]
    print(merge_sort(a))

6HeapSort

The idea of heap sort is to create a big root heap, exchange the top position of the heap with the last one, and then create a big root heap, repeat the above operations to achieve sorting, the process is as follows:

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

def heap_sort(a):
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):
        siftdown(a, i, n - 1)          #建立大根堆
    for j in range(n - 1, 0, -1):
        a[0], a[j] = a[j], a[0]        #交换后，继续建立大根堆
        siftdown(a, 0, j-1)
    return a
def siftdown(a, sta, end):
    root = sta                  #根节点
    while True:
        child = 2 * root + 1    #左孩子节点
        if child > end:
            break
        if child + 1 <= end and a[child] < a[child + 1]:   #存在右孩子节点
            child += 1
        if a[root] < a[child]:                      #维护大根堆
            a[root], a[child] = a[child], a[root]
            root = child
        else:
            break
    return a
            

if __name__ == "__main__":
    a = [90, 5, 83, 42, 12, 15]
    print(heap_sort(a))

7QuickSort

The idea of quick sorting is to select a baseline, put the one smaller than the baseline on one side, and put the one larger than the baseline on the other side, and achieve the final sorting by sorting the two parts. The process is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def quick_sort(a):
    if len(a) <= 1:
        return a
    left = []
    right = []
    base = a.pop()
    for x in a:
        if x < base:
            left.append(x)
        else:
            right.append(x)
    return quick_sort(left) + [base] + quick_sort(right)
            

if __name__ == "__main__":
    a = [90, 5, 83, 42, 12, 15]
    print(quick_sort(a))

8CountSort

The idea of count sort is to establish a counter, count the number of times each number appears, and then output the statistical results to achieve the final sort. The process is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def count_sort(a):
    n = len(a)
    max_val = max(a)
    count = [0] * (max_val + 1)
    for i in range(n):
        count[a[i]] += 1
    res = []
    for i in range(max_val + 1):
        for j in range(count[i]):
            res.append(i)
    return res
            
            

if __name__ == "__main__":
    a = [90, 5, 83, 42, 12, 15]
    print(count_sort(a))

9BucketSort

The idea of bucket sorting is to put the elements in the corresponding range into the bucket, sort the elements in the bucket, and then take the elements out in order to complete the final sorting. The process is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def bucket_sort(a,n=100,max_num=10000):
    buckets = [[] for _ in range(n)]   #创建桶
    for x in a:
        i = min(x // (max_num // n) , n - 1)    
        buckets[i].append(x)      #将对应的数据放进桶中
        for j in range(len(buckets[i]) - 1 , 0 ,-1):
            if buckets[i][j] < buckets[i][j - 1]:
                buckets[i][j] , buckets[i][j - 1] = buckets[i][j - 1] , buckets[i][j]
            else:
                break
    result = []
    for bin in buckets:
        result.extend(bin)
    return result


if __name__ == "__main__":
    a = [90, 5, 83, 42, 12, 15]
    print(bucket_sort(a))

10RadixSort

The idea of radix sort is to divide integers into different numbers by bit, and compare each number. The specific process is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def radix_sort(a):
    max_val = max(a)
    it = 0
    while 10 ** it <= max_val:
        buckets = [[] for _ in range(10)]
        for x in a:
            i = (x // (10 ** it)) % 10
            buckets[i].append(x)
        a = [j for i in buckets for j in i]
        it += 1
    return a


if __name__ == "__main__":
    a = [90, 5, 83, 42, 12, 15]
    print(radix_sort(a))

致世界的一封公开信

郭嗣琮

【中国民主同盟盟员】

致郭嗣琮教授的一封信

尊敬的郭教授您好:

我是来自理学院信息与计算机科学17-1班的柳宇豪，在听您教授的模糊数课程以及前段时间有关神经网络的讲座中，对您印象颇深，临近毕业，在思想上有些许问题想与您交流，以下是我在思想上拥有的疑问，我将写下我困惑的地方，希望老师您能给予我帮助。

一、郭教授您如何看待当今中国的主要矛盾？大三期间我读了许多书，譬如《毛选》、《红星照耀中国》、《中国私有化大逆转》、《哲学小词典》等等，读的越多我内心的疑惑也就越大。现阶段中国贫富逐步拉大，阶级固化日益严重，许多资本家/企业家越来越脱离群众，一部分先富起来的人们丝毫不掩盖自己对于无产阶级和社会底层的鄙视，并把原始资本的积累归结于自身的努力，（参考“欣小萌事件”、“后浪”、“打工人”等）。我想请问老师您，在这一时代背景下我们青年要做什么，该做什么？是团结起来组建左翼联盟尝试集体公社式经济合作社还是毕业后进入大厂实习找工作？

二、承接上一个问题，在面对日益严重的阶级矛盾和充满整个社会的唯功利主义、唯实用主义以及资产阶级人性论的大环境中，如果我们青年选择尝试组建左翼联盟，实行集体经济，以辩证唯物主义和阶级论为思想基础来创业，以创建一个内部没有资本压迫的公司，这种可能性实现的概率有多大？政府允不允许这一新式企业的出现？我们又该如何保持自我的独立性？您对持有我们这一想法的青年又有什么建议和看法？青年又该如何保持对世界前沿问题包括但不限于学术研究、未来发展方向等这些问题的信息获取？

三、从形式上讲，前两个问题是不同的两个问题，但从本质上讲又是同一个问题，即我们青年大学生在这一时代背景下该怎么做的问题，而第三个问题是关乎我个人的一点疑问。我想请问郭教授您是如何看待爱情的？又该如何处理爱情与理想（现实）的关系？您理想中的爱情又是什么样子的？

以上三点是我在最后大学生涯所面临的最大不解和有疑问的地方，希望郭教授您百忙之中能抽出部分时间帮我解答这些问题，如果条件允许，线下见面交谈这些问题更好。真诚地期待着您的回信。

此致

敬礼

柳宇豪

2021年4月10日

附联系方式：

微信/QQ1982164667

手机：13154187195

个人网站：https://starfire1226.top/

回复：

柳宇豪同学你好！

​ 看到了你的来信，感觉你是一个喜欢思考、忧国忧民、有大志向的青年人。你有想法和疑问来问我，说明你信任我，我也很高兴。

​ 你提的头两个问题，这在人类的历史上有很多人思考（如柏拉图）并实践过（如欧文），同时也是促使马克思主义形成 的一个因素。不管前人是如何总结和评价历史教训的，我有我自己的认识：即社会的任何生产组织过程都离不开两个要素，即资本与劳动力，通俗地说就是“钱和人”。首先，搞公社式合作形式生产组织必须要先有资本，资金从何而来？面对着市场经济环境，投资人是否要求回报 ？当你们真正走入到生产实践之中后，你们才会体会到，生产过程最最重要的就是资本的运作过程；其次是人，谁能保证在金钱面前所有人的灵魂都是圣洁的。所以马克思说共产主义必须在所有人的觉悟都得到极大提高前提下才能实现。我国建国后搞了三十年的人民公社，最终还是失败的；早在200年前英国的罗伯特.欧文就实践过（见我发给你的附件），也是失败的。从本质上讲，公社式生产组织形式是最理想的、最美好的生产方式，但是为什么一次又一次的失败呢？这正是需要你们年轻人多多思考的问题。建议你们年轻人要多读书、多观察、多思考，不要头脑冲动去搞什么联盟。社会问题不是搞个联盟就能解决的，要相信共产党的宗旨和最终目标（尽管我不是共产党员），社会的污垢要靠一个强大的社会力量来洗涤，幻想靠一个无资本压迫的公司来改变社会是不可能的，只有一个政党才能动员起整个社会力量来完成改变社会的目的。公司改变不了社会，但是社会一定能够改变你的公司，致使你的目标最终要失败。

​ 关于你提到的如何看待爱情的问题，我只能告诉你如下感知：（1）这是两个人的事，一厢情愿一定是灾难；（2）浪漫是短暂的，现实是长久的；（3）婚前两人都在粉饰个人的优点，掩饰缺点，婚后一切缺点都将暴露无遗，所以，爱一个人就要能接受对方的缺点；（4）对方爱你的家人、爱你的父母，比爱你更重要；（5）你能找到一位爱生活、爱家庭、能在别人面前尊重你的人，那是你一生最大的幸福。

​ 说了这许多，不知是否对你有用，仅供你参考，顺祝学习进步！

​ 郭嗣琮 4-11

附件：欧文的空想社会主义为什么会失败？

序

四月

严格地说这并不是一封信。

我是一个比较怀旧和喜欢记录的人，我并不相信爱情，或者说不相信自己能遇到爱情，但是最近不断在我脑海里出现的思想，已经严重影响了我的正常生活，那就去正视和解决吧。

最初，对你只有感谢，多次建模合作后，也没感觉你有什么特别，考研时，甚至觉得你些许讨厌。

经过断断续续的了解和认识，我发现自己喜欢上了你，理性让我克制并淡化这种感觉，但，在此我并不想讨论感性与理性，也不想讨论世界观和方法论，我只知道此刻我喜欢上了你，这绝不是一时的冲动和激情，是的，我喜欢你。

我尝试用自己的世界观去解释这一切，去用一切可以想到的观念来掩盖我对你的喜欢，但我发现这是自己对自己的欺骗，我喜欢你的一切，我也愿意接受你的一切。

不得不承认这是我们之间一对特殊的矛盾，我也有过很坏的打算，可能最后除了一段经历外，我们得不到任何有关双方的一切，不过我不后悔，正如我做其他事情一样，我从不后悔经过自己思考后所做地决定和判断，但是却又不得不思考一些问题，那就先做个最坏的打算，留下有关我们的一封信吧，是给你，也是给我自己。

我爱你，正如我爱这封信一样，我当然希望你我能一直陪伴下去，但我也知道现实总是处处有意外，矛盾也始终在斗争。

如果你我有离别的一天，我希望你还不介意看到这封信，我也希望自己还有勇气给予你这封信，它承载了我们在大学美好的回忆，如果，我们有了未来，我也会在合适的时间把这封信给你，让你坐在我身边，我读给你听。

想到了最坏的结局是不是意味着我就对你的爱就会因此而有所保留或潜意识里朝着最坏的结局去了呢？恰恰相反，认识最坏的结局恰恰是为了避免它，而我对你的爱并不会因为有个可能的最坏的结局而减少丝毫。

已经23:35了，电脑快要没电了，有电也写不完我此刻想说的话和对你的爱，那么这篇序就到这里了。

最后，我喜欢你。

写于二零二一年四月六日二十三点三十七分辽宁工程技术大学七舍四三三

2021.4.5

纪念日

2021.4.6

9:25

请原谅我没在QQ和朋友圈特意发文公开你的存在，我并不认为两个人的爱情需要得到其他人的关注，不过你放心，我会将你逐一介绍给我所有的朋友和家人。

22:35

什么是喜欢？这个问题困扰着我，我反复思索着，尝试用尽自己的一切知识着解释喜欢，现在我明白了，喜欢是想多看你一眼。

2021.4.7

第一次以伴侣的方式通话

2021.4.8

21:57

还记得今天火锅和你说的一句话，是要把娶你这件事放到日程了

图书馆里偷偷看你，很美

咬了你的手，嘴感尚可

2021.4.9

21:29

毕业去哪是个问题也不是个问题，你只要好好考研等我娶你

你说研究生毕业稳定后父母才考虑，我也知道你不并想让自己“耽误”了我

那么还有三四年时间，我爱你，虽然在这以后时间段里可能会做出与爱你相反的决定

比如去了一个较远的地方工作，比如默默无闻创业

不要紧，我相信你能理解我，这一切都是为了更加接近你

2021.4.10

5:14

有两件事，这两天应该和你谈谈，

一、你现在的主要任务是学习，是考研， 不要多想我怎么办和以后怎么办，这些问题并不是你当前的主要问题

二、你产生该怎么办这一想法的根本原因在于我的不稳定性，不过你放心，我知道自己应该怎么做

宝儿，我认为这是我们目前乃至未来几年的主要矛盾，虽然在形式上是两个问题，但本质上是一个问题，即关于我的问题，我只有稳定了，这一矛盾才会慢慢解决，分析到这，我也要好好学习，好好努力。

接下来就是找个合适的时间去交流，我们不用逃避这些问题和矛盾，恰恰相反，我们应该好好面对它。

目前的重心：宝儿是好好学习，我是好好在自己的方向努力，虽然表面上看重心并不是谈恋爱，但本质上还是为了我们能走的更远，当然这些问题和矛盾并不会使我对你的爱减少一分。

现在乃至未来几年我们需要做的是：

• 宝儿好好学习，把重心放在学习上，考研过程中遇到什么烦心事告诉我，我会为你解决思想上的问题，并在精神上和物质上给予你最大的帮助
• 我先去大厂磨炼一两年，积累经验并阅读更多书，为自己想做的事打下思想和物质的基础

当这两件事完成之后，我想那时我已经稳定，到时候我会找你，并向你求婚。

已经5:52了该洗漱了，还有希望宝儿这两天快好起来，我去洗漱了，最后，我爱你。

22:30

很高兴你从伤心的情绪中恢复过来，事物的发展总是内部矛盾作用的结果，你我作为物质的载体也是事物，你能很快地从伤心的环节中走出来让我很欣慰，按照事物发展的规律，在备战考研期间你还会有或大或小的情绪波动，那我们也不怕，有了这次经验你也懂了如何处理这对矛盾了。对了还有一件事，我想吻你。

2021.4.11

22:38

今天发生很多开心的事，在图书馆我吻了你的额头和脸颊，虽然可能不算吻，但我很开心。

我还问了你昨天我想吻你,你说我太逗了的原因，你有点害羞，不让我追问，我能看出来，你也期待着吻你，那就找个合适的时机。

当询问我明天是否升旗时说“爱你哟”，我无法形容此刻的心情，就像碰到一本好书，我很开心。

2021.4.12

22:07

今天你吻了我脸颊，我也吻了你，

这是我除了看书之外最喜欢的事情

我还想吻你，天天吻你。

我再给你写这封信呢，爱你，我要天天吻你。

2021.4.13

22:13

2021.4.14

15:10

电话里你说考研期间会好好听话，会学习，不会乱玩，我当然相信你。

2021.4.15

22:16

和于漫交流后你问以后我们会不会吵架？答案是否定的，当然这并不意味着我们在相处的过程中没有矛盾，一个人还会有自我矛盾的时候更何况两个人，之所以说我们不会吵架是因为吵架是处理矛盾的一种方式，我并不喜欢这种方式且认为它单纯的是一种情绪的宣泄对于问题的解决没有任何作用。

我喜欢解决矛盾，在我们有矛盾爆发的情况下，我更害怕你会冷战不交流，一个人去解决两个人之间的矛盾其结果必然是灾难，我希望在矛盾爆发的时候，你我都能冷静，即是那时你不喜欢讲道理也没关系，只要交流，你我之间的小插曲总会解决，因为我爱你，我也相信你不会触及原则性问题，正如我会娶你，你也要相信我。

2021.4.16

21:22

好像有点事情想和你说，又忽然不知道怎么告诉你，或者说还没把我说清楚，那就等清楚再告诉你吧。

对了还有一件趣事，从另一层面也表明了最近不午休状态是比较差的，应该把我俩的聊天框与群聊天框分离开来。

2021.4.17

22:27

吻你是我一天中最期待的时刻，我喜欢吻你，喜欢吻你的耳朵、脸庞、嘴唇和你的一切。

2021.4.18

22:23

今天是目前为止吻你最多的一天，也touch you，and it can be bigger after touching.

拍了四张照片我都喜欢，更喜欢可爱的你。

晚上我们也讨论了很多，首先一点，你很美，尤其在我眼里，这一点不要质疑。

我们都要努力。

不要怕宝儿，五一之前能好的。

2021.4.19

22:45

中午有些不自在，不自在在主要原因在于你我对待异性关系的差异性或者说处理异性关系的差异性，对于你说都认识/都是熟人/怕尴尬这样的词汇让我觉得很不自在，因为上次也是有人这样对我说的，我当然知道你和别人不同，不过还是有点心情上的落差，我很怕你不会处理或者处理的不好让别人误以为你没伴侣，但同时我又相信你能处理好，这种矛盾我想会一直持续很长时间，我也要慢慢克服这种感觉。看书吧，我想多看些书，或者多了解下你，你让我着迷又让我害怕。好像很久没在这里说过我爱你了…

我爱你。

2021.4.20-2021.4.24

22:40

一个错误，我不应该老说“讨厌你”这样的话，尽管我知道你明白我的意思，其实我并不是真正的讨厌你，而是我对于当时的判断误以为你很不尊重我的想法，这使得我不愿意和你交谈太多，当然并不是那种“讨厌”，很抱歉说出这样让你伤心的话，我保证这样的错误不会再犯，我会注重自己的表达，相信我。

2021.4.25-2021.4.29

2021.4.30

22:35

今天玩得很愉快，我很开心。中午吃过饭去唱歌，这是宝儿第一次帮我。

另外你说你喜欢我喊你宝宝，那么，宝宝我爱你。

五月

2021.5.1

9:35

虽然我知道我们终有离别的那一天，我也早有心理准备，但当今早这一时刻到来时，我却显得那么不自然，我想和你在一起，想一直陪在你身边，我又明白现在的我们时刻在一起是件不可能的事。

11:05

我想你宝宝，每时每刻都在想你。

23:45

爱你。

2021.5.2

11:03

2021.5.3-2021.5.6

23:24

捏它的话什么感觉

害羞更多

有一丢丢心跳加速

2021.5.17

15:31

有段时间没写了，昨天你告诉我很久没说爱你了，我爱你。

最近事情有很多，我也要赶快调整下状态了。

六月

这个月是我最开心也是最不舍的一个月，我想陪着你，可以你也知道短暂的分离是在所难免的，我喜欢什么也不干地看着你，我知道异地难免有许多未知的事情发生，我知道你喜欢我，我也想让你知道和你分别我很难过，我想让你知道我很爱你。我对你的爱并不会很明显的表达

…

七月

2021.7.1

19:06

宝贝今天中午我送你到车站，一直忍住没哭，可是晚上吃饭时我才发现，我想你宝宝，我想和你一起去吃你吃不完的筷尚客，我们还点鲅鱼酸菜和牛肉酸菜；我想和你一起去吃摇滚三国；我想和你一起去吃先买鸭货后喝牛肉辣汤的韩盛源；我想和你一起去都是小孩才去的华莱士。

我还没和你逛够万达城的街，我还没和你逛够都是跑步人的操场，我还没有习惯你不在的每一顿饭，我还没有习惯你离我太远，我爱你宝宝，我真的很爱你。

我始终觉得咱们俩一定能走到最后，我想你了。

不能再写了，你好好吃饭，我爱你。

2021.7.2

21:15

今天下午你说我们要去50个地方

我想陪你去

2021.7.3

今天可以说是下了一天雨，中午我休息了会儿，

我不太喜欢下雨天，却喜欢听雨声，

下雨天特别容易想你，

你说下雨天喜欢吃火锅

等我们见面一定要在雨天吃次火锅

你点辣锅，我吃清汤锅

点两份肉、一个豆皮、一个娃娃菜还有你最喜欢的火锅粉。

Python数据结构与算法

Part1数据结构介绍

数据结构: 实现抽象数据类型的过程叫做数据结构

编程: 包括控制语句(control statement)和数据类型(data type)两个方面构成

控制语句包括:

序列执行(sequential execution)/决策分支(decision branch)/循环迭代(loop iteration)

数据类型:

原子数据类型(atomic data type):float/integer/string

集合数据类型(collection data type):

​ ordered collection : string、list、tuple（can ues [index]）可以有repetitive element

​ unordered collection：set、dictionary（hash map），其中set不允许具有重复元素（duplication）不能使用subscriptable(下标index)

目录

[TOC]

2021/10/24

世界工业设计大会

• 数字设计、中低压电器、陶瓷行业、智能制造、生态设计五个领域
• 启动了“智能设计共享云平台”

碳达峰碳中和

• 快形成节约资源和保护环境的产业结构、生产方式、生活方式、空间格局
• 坚定不移走生态优先、绿色低碳的高质量发展道路，确保如期实现碳达峰、碳中和。

2021/10/23

世界物联网博览会

• 推动物联网产业

支付产业数字化

• 支付产业数字化
• 场景化的支持

交通运输市场

• 加快建设统一开放的交通运输市场

• 网约车、共享单车、网络货运等

• 规范企业经营行为

2021/10/22

引导民营资本有序竞争

• 企业自我改革
• 全国工商联将继续关注相关行业企业发展状况，并协调相关部门和地方政府，切实帮助企业解决普遍遇到的创新难、融资难、维权难等突出问题。

2021/10/21

强化反垄断

• 强化反垄断、深入推进公平竞争

绿色发展【中办|国办】

• 产业结构转型
• 中共中央办公厅、国务院办公厅

教师队伍建设

• 打造高水平专业化教师队伍，持续推进教师队伍建设综合改革

2021/10/20

煤炭领域

• 进行数字化、智能化转型

营造公平竞争税收环境

• 推出首批包括10项内容的税务行政处罚“首违不罚”清单

2021/10/19

反垄断

金融领域反垄断和反不正当竞争整治

数字技术

• 互联网
• 大数据
• 云计算
• 人工智能
• 区块链
• 发展数字经济，实施网络强国战略和国家大数据战略

要推动数字经济和实体经济融合发展

把握数字化、网络化、智能化方向，推动制造业、服务业、农业等产业数字化

2021/10/18

全过程民主

• 结果民主–>全过程民主

2021/10/17

生物多样性

• 本质上讲是同碳中和 碳达峰一样, 中国要实现数字化转型, 产能的形式也将转型

2021/10/16

数字化转型

2021/10/13

[经济]新能源汽车

新能源汽车充电难

充电桩不足

原因

• 充电模式不足
• 充电技术限制
• 新能源基础设施建设慢于新能源销售
• 峰值堵塞[国庆]
• 交流电充电速度慢于直流电

趋势

• 企业自建
• 政策要从“补车”向“补桩”转变
• 发展多种充电模式
• 互联网+充电桩+换电模式[共享电车电源]

2021/10/12

美原油期货价超80$

• 高油价将会加剧美国国内的通货膨胀

2021/10/11

中小企业

• 放宽市场准入
• 实施减税降费
• 优化营商环境

2021/10/08

电力煤炭

• 鼓励地方对小微企业和个体工商户用电实行阶段性优惠
• 大型风电、光伏基地建设
• 遏制“两高”项目
• 将市场交易电价上下浮动范围由分别不超过10%、15%，调整为原则上均不超过20%

2021/10/07

共同富裕

• 变优势资源为特色资产，让村民成为股东
• 集资众筹发展

2021/10/03

人才

• 引进+培养

2021/10/02

国家战略人才力量

• 学历｜能力｜人才市场

[经济]限电

东北限电

原因

• 技术原因|生产少供应多
• 居民用电10%|工业用电|服务业用电
• 居民拉闸停电[责任事故]
• 煤炭价格上涨

趋势

• 短期煤炭价格上涨导致电的上游产能成本变大
• 煤的短缺导致上游产能降低

[经济]猪肉价格

猪肉价格腰斩

• 猪肉价格下跌50~60%


原因

• 供给充足
• 产能恢复
• 价格时供求关系的结果
  • 平滑”猪周期”

趋势

• 未来四五月价格还会持续下跌
• 养殖亏损大概一头500
  • 饲料价格上涨
  • 八月全国亏损面打到52.5%
  • 双节”春节|元旦”猪肉价格还是平稳或下跌
• 短期猪肉反弹存在, 但产能的的压力并不会影响上游生产
• 收储|保价

2021/9/26

央视融媒体产业投资基金

• 首个以媒体融合为主题的国家级产业投资基金
• 上海正式成立
• 总规模100亿元，首期规模37亿元
• 投向5G、超高清、人工智能、云计算、区块链

小微企业

工行、农行、交通银行以及多家股份制银行、城商

• 9月30日起
• 减免小微企业和个体工商户的银行账户开户手续费、转账汇款手续费、电子银行服务费等收费

中国银联

• 9月30日起三年内
• 小微企业卡、单位结算卡跨行转账汇款交易实行银联手续费减免

[经济]PPI|CPI

概念

CPI:下游产业「原材料」居民消费水平(消费端To:C)

PPI:生产端上游产业==>大宗商品的上涨(生产端To:B)

消费者物价指数（CPI）是反映与居民生活有关的消费品及服务价格水平的变动情况的重要宏观经济指标，也是宏观经济分析与决策以及国民经济核算的重要指标。

生产价格指数共调查9大类商品：①燃料、动力类；②有色金属类；③有色金属材料类；④化工原料类；⑤木材及纸浆类；⑥建材类：钢材、木材、水泥；⑦农副产品类；⑧纺织原料类。⑨工控产品

大宗商品

• 煤价上涨
• 钢铁价格上涨

CPI|PPI剪刀差

• CPI:服务消费|食品–>疫情
• PPI:大宗商品的价格恢复需求关系–>影响中小企生产成本
• 帮扶中小企业
• 大宗商品包够稳价

2021/9/24

企业融资

• 缓解中小微企业融资难、融资贵问题
• 新兴产业、制造业高质量发展

2021/9/23

十七届深圳文博会

• 重点展示5G、大数据、云计算等技术
• 文博会官网和微信小程序“文博会+”同时搭建“云上文博会”

碳排放

• 碳监测评估试点
• 唐山、太原、上海等16个城市以及火电、钢铁、石油天然气开采等五个重点行业
• 温室气体试点监测、推进减污和降碳协同增效

国债

• 香港发行80亿元国债

2021/9/22

生育率

• 婚俗改革实验区

碳中和

• 9月22日清华大学正式成立碳中和研究院
• 中优势资源加快突破碳中和领域关键核心技术
• 低碳发电与动力
• 新型电力系统
• 零碳交通
• 零碳建筑
• 工业深度减排
• 减污降碳协同增效
• CCUS与碳汇
• 气候变化与碳中和战略

基本认识

1. 碳排放

人类生产经营活动过程中向外界排放温室气体（二氧化碳、甲烷、氧化亚氮、氢氟碳化物、全氟碳化物和六氟化硫等）的过程。

2. 碳达峰

广义来说，碳达峰是指某一个时点，二氧化碳的排放不再增长达到峰值，之后逐步回落。根据世界资源研究所的介绍，碳达峰是一个过程，即碳排放首先进入平台期并可以在一定范围内波动，之后进入平稳下降阶段。

3. 碳中和

碳中和是指企业、团体或个人测算在一定时间内直接或间接产生的温室气体排放总量，然后通过植树造林、节能减排等形式，抵消自身产生的二氧化碳排放量，实现二氧化碳“零排放”。

4.碳汇(Carbon Sink)

一般是指从空气中清除二氧化碳的过程、活动、机制。主要是指森林吸收并储存二氧化碳的多少，或者说是森林吸收并储存二氧化碳的能力。

5. 碳捕集利用与封存（CCUS）

Carbon capture utilization storage

碳捕集利用与封存简称CCUS，是把生产过程中排放的二氧化碳进行捕获提纯，继而投入到新的生产过程中进行循环再利用或封存的一种技术。其中，碳捕集是指将大型发电厂、钢铁厂、水泥厂等排放源产生的二氧化碳收集起来，并用各种方法储存，以避免其排放到大气中。

6. 碳排放权

碳排放权，即核证减排量（Certification Emission Reduction，CER）的由来。2005 年，伴随《京都议定书》生效，碳排放权成为国际商品。碳排放权交易的标的称为“核证减排量（CER）”。

碳排放权配置一级二级市场

一级市场：一般由各省发改委进行配额初始发放的市场，分为无偿分配和有偿分配。

有偿分配附带有竞价机制，遵循配额有偿、同权同价的原则，以封闭式竞价的方式进行。

**二级市场: **是控排企业或投资机构进行交易的市场。

7. 碳交易

把二氧化碳排放权作为一种商品，买方通过向卖方支付一定金额从而获得一定数量的二氧化碳排放权，从而形成了二氧化碳排放权的交易。

碳交易市场是由政府通过对能耗企业的控制排放而人为制造的市场。通常情况下，政府确定一个碳排放总额，并根据一定规则将碳排放配额分配至企业。如果未来企业排放高于配额，需要到市场上购买配额。与此同时，部分企业通过采用节能减排技术，最终碳排放低于其获得的配额，则可以通过碳交易市场出售多余配额。双方一般通过碳排放交易所进行交易。

8. 碳排放配额、自愿减排量（CCER）

按照碳交易的分类，目前我国碳交易市场有两类基础产品，一类为政府分配给企业的碳排放配额，另一类为核证自愿减排量(CCER)。

2020 年 12 月发布的《碳排放权交易管理办法（试行）》中指出，CCER 是指对我国境内可再生能源、林业碳汇、甲烷利用等项目的温室气体减排效果进行量化核证，并在国家温室气体自愿减排交易注册登记系统中登记的温室气体减排量。

第一类，配额交易，是政府为完成控排目标采用的一种政策手段，即在一定的空间和时间内，将该控排目标转化为碳排放配额并分配给下级政府和企业，若企业实际碳排放量小于政府分配的配额，则企业可以通过交易多余碳配额，来实现碳配额在不同企业的合理分配，最终以相对较低的成本实现控排目标。

第二类，作为补充，在配额市场之外引入自愿减排市场交易，即 CCER 交易。CCER 交易指控排企业向实施“碳抵消”活动的企业购买可用于抵消自身碳排的核证量。

“碳抵消”是指用于减少温室气体排放源或增加温室气体吸收汇，用来实现补偿或抵消其他排放源产生温室气体排放的活动，即控排企业的碳排放可用非控排企业使用清洁能源减少温室气体排放或增加碳汇来抵消。抵消信用由通过特定减排项目的实施得到减排量后进行签发，项目包括可再生能源项目、森林碳汇项目等。

碳市场按照 1:1 的比例给予 CCER 替代碳排放配额，即 1 个 CCER 等同于 1 个配额，可以抵消 1 吨二氧化碳当量的排放，《碳排放权交易管理办法（试行）》规定重点排放单位每年可以使用国家核证自愿减排量抵销碳排放配额的清缴，抵消比例不得超过应清缴碳排放配额的 5%。

新型农业

• 农旅结合
• 高标准农田建设，平整土地、整合田块，让农田更适合机械化作业
• 农业机械化、数字化

知识产权

• 2021—2035
• 2025年，知识产权强国建设取得明显成效，知识产权保护更加严格
• 2035年，我国知识产权综合竞争力跻身世界前列

2021/9/21

马克思主义

• 加强新时代马克思主义学院建设
• 马列毛-邓-三代表-科学发展观-习近平新时代

2021/9/18

经济趋势

• 9月18日银保监
• 保险资金投向碳中和、碳达峰和绿色发展相关产业资金规模超过9000亿元
• 交通、能源、环保、水利、市政

2021/9/16

十四五

• 2030年累计建成12亿亩高标准农田

经济趋势

• 高技术制造业增长14.9%
• 高技术服务业增长35.2%

经济调控

• 3.65万亿地方政府专项债券
  • 推进重大工程、基本民生项目尽快形成实物
• 3000亿元支小再贷款额度政策
  • 实体经济发展
  • 地方法人银行向小微企业和个体工商户发放贷款

2021/9/15

2021中关村论坛

• 9月24日到28日在京举办
• 智慧·健康·碳中和”

新能源汽车

• 2021世界新能源汽车大会今天（9月15日）在海口开幕
• 新能源汽车在技术、产业、政策等方面的创新经验与发展趋势

塑料产业

• 2025年，塑料制品生产、流通、消费、回收利用、末端处置全链条治理成效更加显著，白色污染得到有效遏制的目标。

2021/9/14

中办|国办加强网络文明建设

• 中共中央办公厅|国务院办公厅
• 加强重点理论网站
• 深化公众账号、直播带货、知识问答等领域不文明问题治理

2021/9/12

大宗商品|天然气

价格

• 亚洲近一年增长600%
• 欧洲近一年增长1000%

价格暴涨

• 大宗商品分为生产国和消费国
• 供需关系
• 天然气作为清洁能源==>碳中和大环境
• 疫情因素和天气自然环境的因素, 导致天然气的需求大于供给

价格背景

• 液化和管道运输, 所涉及的技术设备成本不一, 天然气并不想石油这类大宗商品, 其价格根据具体的形势具有一定的波动
• 天然气市场供需关系失衡的原因复杂
• 能源型大宗商品价格波动具有一定的时间特征
• 大宗商品的价格不仅受市场的影响更受政治经济的影响, 即其不仅拥有商品属性还包括国家战略

供需错配

• 中国能源使用天然气由去年的4%占比到8%未来随着碳中和的进一步要求, 天然气等新能源的投资比将持续攀升
• 2020年中国天然气消费同比增加6.9%对外依赖程度为43%
• 天然气价格适度市场化是趋势

中国政策

• 抓中间, 放两端|抓住设备运输主体, 放开上游供给和下游销售, 促进市场自由竞争, 激发市场活力
• 改革的红利和市场发展的红利

生态保护补偿制度

• 调动各方参与生态保护积极性
• 强化激励与硬化约束协
• 2025年与经济社会发展状况相适应的生态保护补偿制度基本完备
• 2035年适应新时代生态文明建设要求的生态保护补偿制度基本定型

推行企业活力