我在考虑要不要去找份实习。问一下吧。
问问有些已经有这个意向的同学。不，已经问了袁权了。他说明天去找他。
先去试一把呗，搞不好可以呢。
找日常实习。
目前最为要紧的是CCFCSP一定要过，然后再是张亮的代码讲解。还有三天的时间。
[TOC]
Z字扫描(Zigzag Scan)
将二维矩阵压缩成行输出：
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
| int index=0;
for(int i=0;i<rows+cols-1;i++){
if(i&1){
for(int j=max(0,i-cols+1);j<=min(i,row-1);j++){
res[index++]=mtx[j][i-j];
}
}else{
for(int j=min(i,rows-1);j>=max(0,i-cols+1);j--){
res[index++]=mtx[j][i-j];
}
}
}
int n,index;
for(int i=0;i<2*n-1;i++){
if(i&1){
for(int j=max(i,i-n+1);j<=min(i,n-1);j--){
res[index++]=mtx[j][i-j];
}
}else{
for(int j=min(i,n-1);j>=max(i,i-n+1);j++){
res[index++]=mtx[j][i-j];
}
}
}
|
那么反过来，输入一串数字，变成Z型矩阵：
只需要更改中间赋值代码：
res[index++]=mtx[j][i-j]->mtx[j][i-j]=res[index++]
根据CCF例题中读入扫描数据，将扫描数据按照这样的顺序写入矩阵 M：从左上角$M_{0,0}$开始，接下来填充它的右侧相邻的元素$M_{0,1}$，然后依次向左下方填充直至$M_{1,0}$，接下来从它下侧相邻的元素$M_{2,0}$开始，依次向右上方填充直至 $M_{0,2}$，依次类推，循环往复，直至填充满整个矩阵或用尽所有扫描数据。
由于 Z 字形扫描的路径是从左上角到右下角，数组结尾处可能存在着连续的 0，为了节省空间，可以不存储这些连续的 0。得到的数据被称为扫描数据。
输入的数组元素可能是只有部分，针对它的实现是：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| int index=1,n;
for(int i=0;i<15;i++){
if(i&1){
for(int j=max(0,i-7);j<=min(i,7);j++){
int num=0;
if(index<=n){
cin>>num;
index++;
}
mtx[j][i-j]=num;
}
}else{
for(int j=min(i,7);j>=max(0,i-7);j--){
int num=0;
if(index<=n){
cin>>num;
index++;
}
mtx[j][i-j]=num;
}
}
}
|
上面又有可以进行优化的地方。在初始化的时候我们把每个矩阵元素都置为0.所以可以在满足条件之后跳出。
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
| int n;
int index=1;
bool flag=false;
for(int i=0;i<15;i++){
if(i&1){
for(int j=max(0,i-7);j<=min(i,7);j++){
if(index==n){
flag=true;
break;
}
index++;
cin>>mtx[j][i-j];
}
}else{
for(int j=min(i,7);j>=max(0,i-7);j--){
if(index==n){
flag=true;
break;
}
index++;
cin>>mtx[j][i-j];
}
}
if(flag)break;
}
|
并查集(Union Find Set)
并查集支持：
- 查询：两个点u，v是否属于同一个集合。(==查询根节点是否一样,递归==)
- 合并：把u，v所在的集合合并成一个。(==把A的根节点更换为B树上的节点==)
使用数组来模拟树结构，数组index=i位置上存的树，表示i节点父节点的编号。
| 1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
| 1 |
1 |
1 |
4 |
4 |
6 |
6 |
7 |
存储直接父亲是谁。
1
2
3
4
5
6
7
8
9
10
11
12
13
| int father[1e5];
for(int i=1;i<=n;i++){
father[i]=i;
}
int find(int a){
if(father[a]==a)return a;
return father[a]=find(father[a]);
}
void merge(int x,int y){
father[find(x)]=father[y];
}
|
路径压缩
当树的深度比较深，将其
动态规划(Dynamic Plan)
是我觉得很麻烦且一直没掌握好的dp。
给出一个数组，找出最长的递增的子序列。
[1,5,2,4,3]->3 [1,2,4]or[1,2,3]
1
2
3
4
5
6
7
8
9
10
11
12
|
void L(vector<int> &nums,int i){
int max_len=1;
if(i==nums.size()-1){
return 1;
}
for(int j=i+1,j<=nums.size();j++){
if(nums[j]>nums[i])max_len=max(max_len,L(nums,j)+1);
}
return max_len;
}
|
使用递归去深搜比较慢。因此选择对算法进行优化：
动态规划避免重复节点的计算，利用Hash表来保存计算的中间结果。
好吧这个还没有学会，明天继续。
