基本上把牛客网的华为机试题做完了，总结了一些在做题过程中收集的知识点。

1.处理输入数据的框架：

1
2
3
4
5
6
7
8

while True:
	try:
		# 这里是程序的主体
		# 处理字符串的用input()
		#
	except:
		# 多行输入对应单个输出的话，输出语句写在这里。
		break

2.常用的数据结构：

有个字典挺好用的，在统计数量上有奇效。它设有默认值。

1
2

from collections import defaultdict
a = defaultdict(int)

3.字符串的操作：

参考：https://www.runoob.com/python/python-strings.html

比较常用的说一下：
in 操作符 如果字符串包含给定的字符返回True

string.join(seq）以string作为分隔符，将seq中所有的元素合并为一个新的字符串。

count 返回str在string里面出现的次数

find 检查是否包含在指定范围内，如果是返回开始的索引值，否则返回-1

isalnum 如果至少有一个字符并且所有字符都是字母或者数字则返回True

isalpha 如果至少有一个字符并且所有字符都是字母则返回True

Isupper 如果是大写返回True

islower 如果是小写返回True

isdigit如果至少有一个字符并且所有字符都是数字则返回True

max 返回字符串最大的字母

min 返回字符串最小的字母

%s 是一种字符串格式化的语法，基本用法就是将值入到%s占位符的字符串中。%s表示格式化一个对象为字符

1
2

string = "good"  #类型为字符串
print("string=%s" %string)   #输出的打印结果为 string=good

r’ ‘ 告诉系统不需要转义，就是直接的这个字符串。不涉及到转义字符。

统计字符串的字母的个数：

1
2
3
4
5
6
7
8
9
10
11

from collections import Counter
Counter(input())
#返回的是一个以元素为key，元素个数为value的Counter对象，通常配合most_common()使用。代码如下：
# 这里一定要两者配合使用，否则Couter返回的是一个counter对象，对题目没有帮助。

from collections import Counter
#统计字符串
# top n问题
user_counter = Counter("abbafafpskaag")
print(user_counter.most_common(3)) #[('a', 5), ('b', 2), ('f', 2)]
print(user_counter['a']) # 5

4.ASCII字符转换

ord()字符转换成ASCII值

chr()ASCII值转换成字符

5.range的倒序遍历：

range（start,end-1,-1) # range(9,-1,-1)

6.自定义排序

注意，这里使用的条件是数组，不是字符串。

1

o

默认是函数值从小到大排序

7.数值精度

例如：result为一个list，为result中每个值保留4位。
result = [("%.4f" % i) for i in result]

8.字节的长度：

GBk 中文两个字节
UTF 中文三个字节
查看不同编码下的字节长度：

1

len(i.encode('gbk'))  # 'gbk','utf8'

9.print(a,b)是自带空格的，输出为：a b

10.二维数组和一维数组其实差不多。

11.定义一个新的结构体：(链表，数的结点等)

1
2
3
4

class Node(object):
    def __init__(self,elem):
        self.elem = elem
        self.next = None

12.判断一个数是否是质数：

1
2
3
4
5
6
7
8

链接：https://www.nowcoder.com/questionTerminal/f8538f9ae3f1484fb137789dec6eedb9
来源：牛客网
#从质数的性质出发，质数的意思就是从2到自身的开平方，没有一个数可以整除它。
def isPrime(n):
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

13.排列与组合：

组合用combinations

排列用permutations

1
2
3
4
5
6
7
8
9

form itertools import combinations, permutations
list01 = list(combinations('abc',2))
print(list01)
list02 = list(permutations([1,2,3],3))
print(list02)

results:
[('a','b'),('a','c'),('b','c')]
[(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)]

14.输出一个矩阵

1
2
3

# 这里的矩阵是
for i in range(x):
		print(' '.join(list(map(str,res[i]))))

15.参数改变的问题

参考：https://www.cnblogs.com/monkey-moon/p/9347505.html

不想改变的话用copy.deepcopy(a)

16.位移

1

a = a >> 1

17.字符串格式化

方法一：format函数

1
2
3
4

>>> print('{:.3f}'.format(1.23456))
1.235
>>> print(format(1.23456, '.2f'))
1.23

format有不同用法，前者使用了占位符{}，使用占位符可以同时输出多个，后者一次只能输出一个，需要注意的是占位符中的冒号不能丢。推荐使用占位符+format输出。

1
2

>>> print('{:.3f} {:.2f}'.format(1.23456, 1.23456))
1.235 1.23

方法二：’%.xf’方法

1
2
3

>>> print('%.2f' % 1.23456)
1.23
# 有多个的，和上面的一样，括号括起来就行。

18.字典的遍历：

（1）遍历key值

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

>>> a
{'a': '1', 'b': '2', 'c': '3'}
>>> for key in a:
       print(key+':'+a[key])
a:1
b:2
c:3
>>> for key in a.keys():
       print(key+':'+a[key])
a:1
b:2
c:3

(2)遍历value

1
2
3
4
5
6

>>> for value in a.values():
       print(value)
 
1
2
3

（3）遍历字典项

1
2
3
4
5
6

>>> for key,value in a.items():
       print(key+':'+value)
 
a:1
b:2
c:3

(4)按一定的顺序遍历字典项：

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

# 按key排序
#对字典按键（key）进行排序（默认由小到大）
test_data_0=sorted(dict_data.keys())
#输出结果
print(test_data_0) #[3, 6, 7, 8, 10]
test_data_1=sorted(dict_data.items(),key=lambda x:x[0])
#输出结果
print(test_data_1) #[(3, 11), (6, 9), (7, 6), (8, 2), (10, 5)]
# 按value排序
#对字典按值（value）进行排序（默认由小到大）
test_data_2=sorted(dict_data.items(),key=lambda x:x[1])
#输出结果
print(test_data_2) #[('8', 2), ('10', 5), ('7', 6), ('6', 9), ('3', 11)]
test_data_3=sorted(dict_data.items(),key=lambda x:x[1],reverse=True)
#输出结果
print(test_data_3) #[('3', 11), ('6', 9), ('7', 6), ('10', 5), ('8', 2)]

很简单的东西，但是如果不去看的话，就很容易忘记，所以一定要复习一下，不然不会就很可惜。主要梳理一下相关的知识线，然后牛客的题目错题整一整。

参考：https://blog.csdn.net/fafawf/article/details/81457650

ASL参考：https://www.cnblogs.com/ygsworld/p/10238729.html

在华为面试的时候，面试官问了我一下知道查找算法都有哪些吗，我蒙了，又问索引查找和哈希查找的区别是什么，我又蒙了。这些其实都是很简单的东西啊，虽然很简单，但是你忘了就啥都不懂，显得很白痴。其实在查找中，最难的是数表查找。。。平均查找长度，KMP算是查找的内容。字符串匹配。

一.总概

七种查找算法其实可以分成4类，顺序查找和分块（索引）查找是一类，二分查找、插值查找、斐波那契查找是一类，树表是一类，哈希查找是一类。问题经常问的是平均查找长度，查找的最大次数之类的，最常考察的查找算法是二分查找。
顺序查找就是一个一个去找，分块就是先分成几个部分，然后索引是几个块的最大值，先找在哪个块，然后再用顺序查找。二分查找这一类是跳着找，只不过看怎么跳的，二分顾名思义就是找那一半的值。插值就是不一定找一半啊，改成自适应了。斐波那契就是取黄金比例的点的值，0.618。数表查找是属于动态查找的，就是先建树，再查找，细展开包括，二叉树，然后是自平衡二叉树（2-3树，红黑树，B树还有B+树）。最后一类是哈希查找。就是首先通过一个映射函数把数组映射成一个表中的key，然后value就是这个值。每次要找某个值时，把这个值映射一下，然后对应key，value就是要找的那个数。
复杂度：

二.顺序查找

很常见的就是问顺序查找的平均查找长度：成功的ASL为（n+1）/2。失败的ASL为n。分块（索引）查找的时间复杂度为O（m+n）。

三.二分查找

经常考的是二分查找的比较次数，或者是查找不成功需要比较的次数等。
查找不成功的比较次数为二叉判定树的最大深度，为（log2n）+1。

二分查找的ASL的计算需要画判定树。举个例子：

这里的不成功的节点是空的外部结点，注意距离不包含这些外部节点，这些只是用来计算个数的。

斐波那契查找的要求是数组个数是F【k】-1，注意不是F【K】。

三.数表查找

二叉查找树的最差情况是o（n）。

四.哈希查找

查找复杂度为O（1）

主要处理两个问题，用给定的哈希函数构造哈希表；根据选择的冲突处理方法解决地址冲突。

现在为了处理骨架数据，往往使用的方法是图卷积。图卷积一开始是使用于社交网络领域，用来处理一些非欧式空间的信息，这样定义的点为实体，边则是实体之间的关系，通常是异构的。而在ST-GCN中，可以说是首次成功将（2018）图卷积应用到基于骨架的行为识别中，这种引用是直觉上的，因为骨架数据中，骨骼的端点就可以看成是图中的点，然后边就是他们的关系（相邻与否）。用一个邻接矩阵就可以描述关键点之间的关系。这里我的记录顺序就从一篇知乎大神写的理解图卷积的文章出发，然后解读ST-GCN，接着是ST-GCN的改进文章，2s-AGCN。

一.如何理解图卷积

参考：https://www.zhihu.com/question/54504471/answer/611222866

我看了几篇关于图卷积的简单解读，感觉这篇是最好理解的，作者是从空域的角度去解读图卷积的操作的。以下内容就摘自该文章。

图卷积的核心思想是利用边的信息（邻接矩阵），对节点信息进行聚合从而生成新的节点表示。

上述核心思想贯穿整个逻辑线，其他的角度我们暂且不去分析，例如利用节点生成边表示之类的。就像电脑一开始也不是这么小的，我们一步一步看最后的图卷积公式是怎么演化来的吧。首先有几个符号记一下：

1.平均法

比如说，我们要计算我之后的工资水平是怎样的。这个要怎么计算呢？最简单的想法就是看看你周围的人工资是怎样的，也就是直接把和我关系最亲密（相邻）的人的工资相加后，就可以衡量我的工资水平。也就是$$aggtrgate(X_i) = \sum_{j\in neighbor(i)}A_{ij}X_j$$
平均数只要对加和的系数进行归一化就行了，这里就不提了。

2.加权平均法

前面提到的和我关系最亲密（相邻）的人，实际上这里的关系量化得还不够细，人之间的亲密度是不同的，也就是我们还得考虑边的权重，我们只需要把无权图变成有权图就可以啦。这里稍微拓展一下就是一个工作了，就是如何构建有权图（比如节点间的相似度之类的）
$$aggtrgate(X) = AX$$
这里的A是有权图（就不是简单的0和1）

3.添加自环

当然我们不能简单地考虑朋友的工资，我们还得考虑我们个人的经历和努力程度，这些都和我们的工资息息相关。所以就是添加一个自环就行。也就是我们自己和自己也有关系，之前是设为没有关系的。
$$aggtrgate(X) = (A+I)X$$

4.另一种思路

有的时候别人对我的工资并不感兴趣，而是想知道我的真正的底子是怎么样的，这时候要考察我的工资和朋友们工资的差距。也就是想知道一个差分的值。这里就有涉及到拉普拉斯矩阵的概念啦：$D_{ii}=\sum_{j\in N}A_{ij}$
$$
\begin{aligned}
\operatorname{diff}(X) &=(D-A) X \
&=D X-A X \
\operatorname{diff}\left(X_{i}\right) &=\sum_{j \in N} A_{i j} X_{i}-\sum_{j \in N} A_{i j} X_{j} \
&=\sum_{j \in N} A_{i j}\left(X_{i}-X_{j}\right)
\end{aligned}
$$
上述式子就是计算差分的。可以看出来就是把自己的工资依次和邻接点的工资相减，然后再累加起来。

###4.1.归一化

无论是那种方法都没有提到归一化的问题，这个归一化很重要，因为有的交际花可能朋友圈质量不咋滴，但是它广啊，这样累加起来，那结果也是了不得的。严谨来说，这会导致哪些比较孤僻的大佬特征就比较小，哪些离群近的特征就比较大，这样就违背我们找金女婿的初衷了。哈哈哈哈哈。

这里的公式感觉还是有点怪怪的，但是你只要知道这个操作是为了归一化就行了。

4.3.对称归一化

为了解决平均的问题，我们不仅要知道我们的平均，还得知道我们最亲密的人的平均，这样才是最准确的。因为我们的朋友也是各有各的性格的嘛。比如一个程序员，他的朋友可能有绿茶婊，我们就要剔除这种不好的影响。（这种朋友影响我们对该程序员工资的预测），所以就有：

这样就同时考虑到了本身和邻接点的平均情况了。但是这上面的公式都没有涉及到参数啊，我们在学CNN网络的时候一般网络都是有参数去学习不是嘛？（这里我们考虑邻接矩阵是无权重的）。所以最后还得给他一个权重矩阵去学习：
$\hat{D}^{-0.5} \hat{A} \hat{D}^{-0.5} \Theta$

总结

回想一下一开始的引用文，图卷积就是信息聚合的一种方法，回想一下二维卷积不也是在做这种事情吗，对感受野做信息的聚合，将浅层的信息聚合成深层的东西，而网络的不同无非改变聚合的方式罢了。

二.解读ST-GCN

这篇论文很经典，我看过很多次了。每次都可以收获到不一样的东西。

它的思路其实也很简单，就是按人体的物理构造去建图，然后用前面我们的图卷积的方法去对骨架数据做消息聚合，然后在最后用全局池化层来处理长度不定的输入序列。我这里主要侧重去讲图卷积部分，具体的论文细节解读之后我会再整理。

1.图的构建

这里用时空图来表示N个关节点与T帧的人体骨架序列中空间与时间的连接关系。

2.权重函数

这个部分是最关键的，也是ST-GCN的创新点。在二维卷积中，我们的权重函数是一个匹配的可以按照空间顺序（矩阵）建立索引来进行按元素的乘法，但是对图就没办法了，这里是采用了映射的策略，就是将某一类点统一用某一个权重值。这里用了三种对节点的分区策略：单标签、距离分区以及空间结构分区（离心和向心）。最后一种的公式表示为：

这里的j有三个。分析一下这个公式，输出等于归一化的邻接矩阵（自相关的）去点乘输入矩阵然后再点乘一个权重矩阵。
然后还有一个权重就是TCN的权重了，这里和二维卷积类似，就是有一个对应的关系：（这里是通道数（特征维度）改变的过程）

三.解读2s-AGCN

因为项目中有使用到这篇论文中的方法，所以必须很熟悉地掌握。这篇是ST-GCN的改进论文，所以只需要额外掌握一些东西就行，也就是本文的主要贡献点，一共就两个，一个是自适应图卷积网络，还有一个是双流框架，使用了骨架（二阶数据）数据。

1.自适应图卷积

就是改变原来的只有表示物理结构的邻接矩阵，从一个变成了三个。

A：和ST-GCN的一样，不多说了，就是归一化的N*N的邻接矩阵。

B：也是一个N*N的邻接矩阵，但是他的值是没有限制的，和其他参数一起参数化和优化，矩阵起到注意机制的作用。

C：是一个数据相关图。为每个样本学习一个唯一的图。为了确定两个顶点之间是否存在连接以及强度，使用归一化的嵌入高斯函数来计算两个顶点的相似性。这里就是用了两个映射函数，把两个输入转换一下，然后用向量内积算一下，然后再将矩阵归一化。就是我们要的矩阵了（图）：

作者没有直接用Bk和Ck去替换Ak，而是将他们添加到里面，Bk值和两个嵌入函数参数初始化为0，这样可以在不降低原有性能的基础上增强模型的灵活性（Resnet）。

2.双流网络

这里只要知道骨骼怎么得到的就好了，因为后面的输入就是一个骨骼对应一个节点，后面的细节都是一样的。每个骨骼都是由两个关节绑定的，我们定义靠近骨骼重心的关节是源关节，远离重心的关节是目标关节，每个骨骼的表示是从源关节指向目标关节。我们为每个骨骼指定一个唯一的目标关节，关节的数量比骨骼数量多一个，中心关节没指定给任何骨骼，所以我们添加一个值为0的空骨骼。这样就一一对应起来的。

树经常涉及遍历的算法和性质，很多题目都是遍历的变体，或者说需要借用遍历的逻辑去解题，所以首先应该掌握的是几种遍历的方法（递归和非递归），然后就是需要对一些树相关的概念了解，比如说平衡二叉树（子树的高度绝对值相差不超过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

# 引用：https://blog.csdn.net/z_ryan/article/details/80854233
//中序遍历
void InOrderWithoutRecursion1(BTNode* root)
{
    //空树
    if (root == NULL)
        return;
    //树非空
    BTNode* p = root;
    stack<BTNode*> s;
    while (!s.empty() || p)
    {
        //一直遍历到左子树最下边，边遍历边保存根节点到栈中
        while (p)
        {
            s.push(p);
            p = p->lchild;
        }
        //当p为空时，说明已经到达左子树最下边，这时需要出栈了
        if (!s.empty())
        {
            p = s.top();
            s.pop();
            cout << setw(4) << p->data;
            //进入右子树，开始新的一轮左子树遍历(这是递归的自我实现)
            p = p->rchild;
        }
    }
}

就是要让代码跟着自己的逻辑走，然后精简代码。非递归版本的遍历需要额外使用一个栈，用来存储根节点，来进入到右边的节点。

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

# 引用：https://blog.csdn.net/z_ryan/article/details/80854233
void PreOrderWithoutRecursion1(BTNode* root)
{
    if (root == NULL)
        return;
    BTNode* p = root;
    stack<BTNode*> s;
    while (!s.empty() || p)
    {
        //边遍历边打印，并存入栈中，以后需要借助这些根节点(不要怀疑这种说法哦)进入右子树
        while (p)
        {
            cout << setw(4) << p->data;
            s.push(p);
            p = p->lchild;
        }
        //当p为空时，说明根和左子树都遍历完了，该进入右子树了
        if (!s.empty())
        {
            p = s.top();
            s.pop();
            p = p->rchild;
        }
    }
    cout << endl;
}

循环主体和中序遍历是一样的，只不过打印的操作放在了前面一个寻找最左边的节点的循环前面了。

做博客实际上是一个沉淀的过程，做过的事情不能就淡淡的做过了，记录下来，是不是再看一看，做过的的东西就不容易忘记。或者说要再做的时候，再拿出来看一看，也会更快入手，还有一点就是证明你确实有做过东西了。我相信没有什么是太晚的，一切最好的开始就是现在，养成习惯是最好的。

说实话，数据集是整个过程中最繁琐的，当时我在做NTU的实验的时候，就是因为数据集部分没有做好，耽搁了很长的时间，还是着了没人带的亏。所以这个部分的话一定要知道很完整的过程，然后要避开中间的坑。
整个数据集处理的过程大概分成3个部分：源数据的预处理（数据格式的转换，生成各种适配文件），生成数据集（batch，多GPU数据与标签对应的问题，数据的预处理等），加载数据集（和前面类似）。

​ 链表和数组有点相似，但是它的元素之间是由一个指针相连接的，而且它要读取某一个元素的话也不能一下子就找到它，而是要遍历整个链表。由于链表的结构具有重复性、复杂性，所以很多链表的题目都用到了递归和分解步骤的方法。还有一点就是要善用指针，很多问题用指针就可以很巧妙地完成，当然这个指针的数量不一定唯一，例如在找环的时候，指针就有快慢指针。还有就是借用其他的数据结构，也就是用空间来换时间的方法。这几种方法都有一些地方需要注意，否则很容易就出错。

一.递归问题

来看几个递归题的例子。

1. 输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

   这个要求的输出是一个链表，由于链表的结构具有重复性，所以可以用递归的方法来完成。递归的方法看起来逻辑也很清楚。

   1 2 3 4 5 6

   # 返回从尾部到头部的列表值序列，例如[1,2,3] def printListFromTailToHead(self, listNode): # write code here if listNode is None: return [] return self.printListFromTailToHead(listNode.next) + [listNode.val]

   这个方法只用了三行，递归方法的结构一般就是“递归出口+一般情况的处理+下一个递归入口“。写的时候就按这个结构去写，一般不会出错。这里下一个递归入口是包含在一般情况的处理当中的。然后递归的返回式一般是由函数组成的，函数即结果，我们这个时候就忽略函数里面的细节，把它当成是正确的返回结果就行了，这样理解起来，或者写起来就不会感觉很乱。
   这题的非递归解法就需要借用到其他的数据结构，栈。利用栈的FILO的性质来完成链表的倒置。

2. 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

   这题是一个比较难的题目，因为它不仅仅考察了一个数据结构的性质，它考察了链表和二叉搜索树的性质，这题如果不知道二叉树的中序遍历的结果是一个升序结果的话，那就做不出来。递归的思想就是按递归的结构去思考问题。首先我们要清楚递归出口是什么，在这里就是如果两种情况：输入的节点不存在，则直接返回空。或者该节点不存在孩子，那么就直接返回该节点。接着思考一般情况下的处理，这个一般情况就是中序遍历：首先完成左边的子树遍历，然后再遍历根节点，接着最后完成右边的子树遍历。这个过程还要转换链表，所以首先我们左边的结果就是另一个递归的过程，在这个递归中，我们将它看成是已经完成的结果，也就是它返回的东西已经是一个双向链表了。这样就不用去纠结左子树到底是什么情况了。这个时候我们再把根节点接上去，当然这里要考虑左子树为空的情况。右边也是一样的操作。最后返回的值一定是一个双向链表。这里要注意。

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

   def Convert(self, pRootOfTree): # write code here if not pRootOfTree: return None if pRootOfTree.left ==None and pRootOfTree.right == None: return pRootOfTree # 左子树生成双向链表 left = self.Convert(pRootOfTree.left) # 找到左子树的最右边的节点 p = left while left and p.right: p = p.right # 将根节点加入到左子树的双向链表中 if left : p.right = pRootOfTree pRootOfTree.left = p # 右子树生成双向链表 right = self.Convert(pRootOfTree.right) # 将右子树的双向链表加入前面的链表中。 if right : right.left = pRootOfTree pRootOfTree.right = right return left if left else pRootOfTree

二.复杂问题分解成n个步骤

将复杂问题分解成小问题，然后再依次去解决这些小问题。这个方法用在哪里都不会有错，首先将问题模块化分解，就比较容易找出我们在哪一步出错，其次，这也容易让我们缕清解题的思路，逻辑上不容易混。这里要注意全局变量和局部变量的区别。我们使用小问题解决问题，也可以解决指针变量变化的问题。这个复杂问题分解要不要写成许多函数的形式也要具体看问题分析。

1.输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。

看上图的分析应该就知道问题要怎么分解了，然后实现如下：

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

# 返回 RandomListNode
def Clone(self, pHead):
    # write code here
    #分成三步，复制，生成链接，分离
    if not pHead:
        return None
    dummy = pHead
    
    while dummy:
        dummyNext = dummy.next
        copyNode = RandomListNode(dummy.label)
        dummy.next = copyNode
        copyNode.next = dummyNext
        dummy = dummyNext
    
    dummy = pHead
    while dummy:
        copyNode = dummy.next
        dummyRandom = dummy.random
        if dummyRandom:
            copyNode.random = dummyRandom.next
        dummy = copyNode.next
        
    dummy = pHead
    copyHead = dummy.next
    while dummy:
        copyNode = dummy.next
        dummyNext = copyNode.next
        dummy.next = dummyNext
        if dummyNext:
            copyNode.next = dummyNext.next
        else:
            copyNode.next = None
        dummy = dummyNext
    return copyHead

2.输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

在这一题中，我们需要两个链表的长度，读取链表长度的方法就是去遍历这个链表，然后累加节点的数量。

1
2
3
4
5

res = 0
while Head:
    Head = Head.next
    res += 1
return res

像这么写的话就要小心了，因为在这里我们是直接拿Head去遍历的，这样一来的话Head就会移动到链表的尾部，也就是None，之后就找不到表头了，所以这一段最好写成函数的形式，或者是另设一个变量去遍历。完整的代码如下：

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

def FindFirstCommonNode(self, pHead1, pHead2):
    # write code here
    if not pHead1 or not pHead2:
        return None
    def count_num(Head):
        res = 0
        while Head:
            Head = Head.next
            res += 1
        return res
    num_pHead1 = count_num(pHead1)
    num_pHead2 = count_num(pHead2)
    if num_pHead1 > num_pHead2:
        for i in range(num_pHead1-num_pHead2):
            pHead1 = pHead1.next
    if num_pHead2 > num_pHead1:
        for i in range(num_pHead2-num_pHead1):
            pHead2 = pHead2.next
    while pHead1 != None and pHead2 != None and pHead1 != pHead2:
        pHead1 = pHead1.next
        pHead2 = pHead2.next
    return pHead1

三.指针的作用

指针用得好，链表没烦恼。很多问题需要借用指针来完成，简单的，遍历、获取链表的长度等。解题过程就像是缝衣服，指针就像是针线一样，起到了关键的作用，用得巧的话，很多题目可以在很低的复杂度下完成，当然，这种解法相对来说也比较复杂。

1.输入一个链表，反转链表后，输出新链表的表头。

这里是借助了两个指针和一个临时的指针完成的，真的就像是缝衣服一样。一般这类题目都需要两个指针以上，一个指针指向当前的指针，也就是遍历的位置，然后一个指针指向后一个节点的位置，避免找不到链表，然后一些其他的辅助指针。像这题就是需要一个指向当前指针的前面一个指针，完成链表的反转。

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

def ReverseList(self, pHead):
    # write code here
    if not pHead or pHead.next == None :
        return pHead
    pPre = None
    pThis = pHead
    while pThis != None:
        tmp = pThis.next
        pThis.next = pPre
        pPre = pThis
        pThis = tmp
    return pPre

数组的考点（关键字）主要包括三个，分别是查找、排序、位运算以及数的特点。和字典（哈希表）、字符串有交叉，主要和考察数组中数的个数这类型的题目相关。

一.查找

要掌握二分查找，因为它的时间复杂度比按顺序查找快（数组不为有序的情况下）。二分查找法一共三个指针，分别是left,right,mid。判断mid指向的数是否是要查找的数，不是的话，left = mid+1 或者 right = mid-1。下面是使用的例子。注意mid的赋值要在循环里面写，循环的跳出条件为left>right

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

def GetFirstK(data,k,start,end):
    if start > end:
        return -1
    middleIndex = (start+end)//2
    middleData = data[middleIndex]
    if middleData ==k:
        if (middleIndex >0 and data[middleIndex-1] != k) or middleIndex == 0:
            return middleIndex
        else:
            end = middleIndex -1
    elif middleData >k:
        end = middleIndex-1
    else:
        start = middleIndex+1
    return GetFirstK(data,k,start,end)

查找问题还往往和数的特点结合，例如奇偶性、数的数量等。这类问题可以用位运算来帮助解决。有几种常用的位运算技巧或者性质必须掌握：
1.辨别奇偶性：

这是利用了奇数和偶数的二进制表示的最后一位不同的性质。

1
2

def is_even(num):
    return num&1 == 0

2.相同的数通过异或后得到的结果为零。利用这个性质，我们可以在其他的数字都出现两次，只有一个数出现一次的数组中获得这个数。

1
2
3
4
5
6
7

a,b = 0,0
#这里是找两个只出现一次的数的代码片段
for i in array:
    if IsR(pos,i):
        a ^= i
    else:
        b ^= i

3.位移某一个二进制表示的数。下面是右移。

1

tmp >>= 1

二.排序

必须掌握常用的排序方法，比如说快排。下面是快排的代码：

1
2

还有一种排序很重要，那就是自定义排序。python的两个版本的写法有点不一样，这个也是必须掌握的。

1
2

三.相关数据结构

1.字典（哈希表）

主要是在考察数组中数的个数的问题中使用。举个例子：

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

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers,duplication):
        dic = {}
        for num in numbers:
        		#添加关键字操作
            if not num in dic:
                dic[num] = 1
            #对字典的键值对操作
            else:
                dic[num] += 1
        for num in numbers:
            if dic[num] != 1:
                duplication[0] = num
                return True
        return False

2.字符串

也是用在考察数组中数的个数的题目中。转换的技巧如下（两者互转）：

1
2
3
4

#数组转字符串
s = ''.join(numbers)
#字符串转数组
nunbers = list(s)

之后用字符串中的count函数以及filter关键字来筛选出符合要求的数：

1

tmp = list(filter(lambda c: s.count(c) >1,s))

保持良好的习惯才是成功的关键，自律只是泡沫和短暂的兴奋剂。

​ 今天听了一个牛客网的大神开的技术专场，感觉很有收获，所以在这里做一个记录。说来也是机缘巧合，本来这场讲座是需要转发到朋友圈才能拿到直播链接的，但是群里面管理员说可能有些已经转发，但是还没处理的情况存在，所以就把链接先发出来了，直接白嫖。
​ 今天大神主要讲了一下关于找工作的事情。我大致将收获分成三个方面来整理。

现在的就业情况如何？

​ 总的来说，大环境是不好的，疫情这么严重了，虽然有一些企业可能在这段时间是一个机会， 需要人手，但是总体来说还是不容乐观的。而且，不断强调的一点，算法比开发难！！！！我应该灵活一点，但是不要乱点技能树，我不是神，也不是很厉害的人，就一个很普通的人。

面试有什么需要注意的？我不知道的事

​ 最后一个疑问环节是固定的，在面试的前三个环节中，你能不能拿到offer其实已经定下来了，这个环节只能是减分环节，绝对不会加分的。所以这个疑问环节一定不要问一些让面试官反问的问题，尽量只让他回答就好。所以就问一些万金油的问题，比如了解团队的工作。
​ 面试有好几轮，然后前面的面试官会给简历打tag，所以一定要给面试官留下好印象。这个印象会往下传递的。这里大神提到了一个博客的问题，如果简历有提供博客链接的话，面试官一定会点进去看的，而且不仅仅是看表面的而已，而且还会看你有没有真的有内容，我觉得我这点做的不够，也许这就是为什么我之前的简历直接被刷掉的原因。太空了，还不如直接不写上去。后面会提到这个写博客的事情。
​ python其实也是有研发岗位的，可能不多，但还是有的。比如说知乎和豆瓣，哔哩哔哩也是吧。

要做什么准备？接下来怎么做？找工作的策略是什么？

​ 牛客网！！！啥都别说了，直接睡在牛客网就行了。牛客网🐂🍺！！！！！！面经，刷题，渠道，都有！还有什么比这个更方便的？
​ 论文肯定要先完成的，不然之前做的努力不就都白费了？然后保持刷题，刷题，刷题！！！！习惯一定要养成。然后就是心中要有一颗技能树，或者说是知识树，这点也很重要，这个概念和思维导图的概念很像，简单来说就是缺啥补啥。
​ 如果实习找不到的话，一定要找一个项目来做。总而言之，要不断充实自己，进步。
​ 找工作、实习第一步：广撒网，这点超级重要，一点是机会就多了，然后你也会有很多的面试经验，其次，一个人往往对自己是什么水平很难把握，通过一次广撒网的操作，你就知道了。什么公司要你，你就是什么水平的，基本上。但是也不要气馁，大神也不是一日就成为大神的，一步一步来。大神的简历一开始也没有3、4段实习的经历的。所以，一定不要有畏难心理，做到自己能够做的最好，就OK了。下一步就是再找更好的，所以实习一定要有，但是不一定要找大厂，因为实力不允许啊。但是有总比没有好，你说是吧。

简单记录一下复现ST-GCN时遇到的坑

在搭环境时遇到的坑

具体的项目链接在这：ST-GCN
我的环境：
Ubuntu16.04
cuda：9.0
我的pytorch等ST-GCN的依赖是装在anaconda的沙盒环境里的，opencv、caffe和openpose是用的系统环境。经过测试，可以执行ST-GCN中的测试Demo。
遇到的第一个坑是这里：
要使用 conda install -r requirements.txt 简单安装所需的包时，报错了，基本的意思就是所在的channel没有其中的几个包，因此，我后来就一个一个去装。在这其中又遇到了一些问题。
1.服务器 conda时错误提示 The following specifications were found to be conflict：
解决的办法就是在base环境中输入：conda update conda 。再次conda install 就没报错了。
2.第二个问题就是想安装opencv-python这个包的时候报错。
解决的办法就是：直接在cmd命令行输入：conda install –channel https://conda.anaconda.org/menpo opencv3
3.第三个问题就是安装scikit-video这个包的时候报错。（其实这个问题和第2个问题一样，就是当前的频道没有这个包的资源）
解决的办法就是在–channel中选有这个包的频道啦，那就是https://anaconda.org/conda-forge
4.最骚的是我在装完上面的包之后我的环境的pytorch消失了？
然后我现在在重装。看看等会怎么样吧。
5.第二天发现我的python版本无缘无故变成2.7版本的了，咋回事？
原来是装argparse的时候，系统自动给我降了。我*，后来查了一下发现这个argparse是python自动带着的，没必要再另外去装，所以我把环境删掉之后，再从新搞一次，这次就没装argparse了，import 它也是可以的。
6.额，后面开始跑实验了，但是有一个包漏了torchvision也是要装的····

然后是在远程调试时遇到的坑

因为我是想通过服务器来进行调试的嘛，那就得将项目上传到服务器上，但是有一个问题是因为我把数据库放在项目里面打算一起上传的（通过pycharm），可能是我的电脑内存太低了，根本上传不了这么大的数据库的数据，因此昨天就没上传成功。今天试着分开上传（先上传本来的项目加上下载的model，然后再上传数据库的压缩包），成功了，最后是在性能比较好的服务器上解压的数据库，现在在进一步处理数据库的数据。

跑 test 时报错

就是会说什么意外的值啊之类的
RuntimeError: in loading state_dict for Model….
这个问题我还是没有解决，问题主要就出在无法加载预训练模型，其实后来我自己训练了一个模型也是可以的，然后后我自己训练的模型来测试也是可以的。

后来这个问题解决了，修正的模型在issues里面可以找得到，给个链接吧：
https://github.com/yysijie/st-gcn/issues/182

openpose的安装

这个最让我头大了···
主要的配置过程参考这个博客，但是这其中还有很多的坑，我一一道来。
1.首先是opencv的安装。
这个一堆坑，最简单的方法就是先把之前系统里面装的opencv先删除干净，然后再用一个简单的命令安装2.4的版本。apt-get install libopencv-dev（可能要装依赖，百度一下）
2.然后是caffe的安装。（应该考虑到cuda和cudnn版本的问题）
这个遇到的问题也挺多的，有一个是这个：
其实很多问题在这里都有提到：https://github.com/CMU-Perceptual-Computing-Lab/openpose/blob/master/doc/faq.md#check-failed-for-readprotofrombinaryfile-failed-to-parse-netparameter-file
这个问题在这里面也有提到。
这个问题后来我换成CUDA9.0就解决了，CUDA8.0可能是cudnn的问题，我还是没搞清楚。

3.在解决第二个问题之后，又出现了新的问题（编译openpose成功，运行测试时），就是caffe版本和openpose不匹配的问题：

参考这个：https://blog.csdn.net/chenzhenyu123456/article/details/84259851
其实从主要的参考博客就可以看出一点蛛丝马迹了，caffe版本是升级过的（Makefile文件内容不同），我们就降版本来进行配置吧。
经过测试，完成openpose的配置，并测试成功。（在系统环境下。）

之前65服务器一直怪怪的，就是跑双卡的时候就很宕机，服了。怀疑是新装的驱动问题，我还去搜了一下历史命令····结果也没找到是谁干的好事。现象就是K80的第二个GPU利用率一直很高，明明没有跑程序，我去。然后用watch命令也是很卡，所以我就怀疑是不是这里出现了问题，然后就在csdn上一搜索。诶！我去，真的给我找到啦csdn。刚好这个问题用的显卡也是K80，你说咋这么巧呢？我直觉是因为换了驱动，默认选项变了，然后就这样了。

总而言之，解决的办法：

执行nvidia-smi --persistence-mode=1当然要用sudo啦。