Think World

从个人成长角度来说，从经历中学点什么总是重要的

0%

Posted on

并查集定义

​ 并查集:一种维护集合的数据结构, 可以支持两种操作

1. union: 合并两个集合
 2. find:判断两个元素是否在一个集合中

并查集的操作

并查集是由father链接构成的树

1
int father[MAX]; //每个结点保存自己的father结点的下标
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
//
void init(int n){
	for(int i=0;i<n;i++){
	father[i]=-1;//每个人都是自己的父亲,树高为1,负值表示高度
	}
}

//带路径的压缩
void Find(int x){ //Find的递归写法 
	if(Father[x]<0 ){ return x; } // x为根
	else {
			return Father[x] = Find(x); //采用路径压缩
	}
}

void Union(int a,int b){ //按秩合并
	int fa = Find(a);
    int fb = Find(b);
    if( fa!=fb) {
        if(Fathe[fa]<Father[fb}]){ //fa的树更高,fb并到fa
            Father[fb] = fa;
        }else if( Father[fa] == Father[fb]){
            Father[fb] = fa;//树高+1
            Father[fa]--;
        }else{
            Father[fa] =  fb;
        }
    }
}

相关题目:

PAT1114 Family Property

[code]:

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
const double INF = 1e-7;
int father[10001];//维护并查集
bool vis[10001];//表明那个是有效的id

int find(int x) {
    while(x != father[x])
        x = father[x];
//    father[init] = x;
    return x;
}

void Union(int a, int b){
    int fa = find(a);
    int fb = find(b);
    if(fa==fb) return;
    if(fa<fb){//a是根
        father[fb] = fa;
    }else{
        father[fa]=fb;
    }
}

//这里id就用int表示即可,方便用并查集实现
struct Node{
    int id, fid,mid,cn,estate,area;
    int cid[10];//k<5
    Node(int i, int f, int m,int cn):id(i),fid(f),mid(m),cn(cn),estate(0),area(0){
        for(int i=0;i<10;i++){
            cid[10]=0;
        }
    };
};



struct Data{
    int people;//人数
    int id;
    double estate;
    double area;
    bool flag;//表明该data是否根结点
    Data():people(0),estate(0),area(0),flag(false),id(0){};
};

bool cmp(Data a, Data b){//estate 降序
    return abs(a.area - b.area) > INF ? a.area > b.area : a.id < b.id;
}
Data roots[10000];
int main(){
    int N;
    cin>>N;
    vector<Node> nodes;
    for(int i=0;i<10001;i++){
        father[i]=i;
    }
    for(int i=0;i<N;i++){
        int id, fid,mid,cn;
        cin >> id >> fid>> mid>>cn;
        Node temp = Node(id,fid,mid,cn);
        for(int j=0;j<cn;j++){
            cin>>temp.cid[j];
        }
        cin>> temp.estate >> temp.area;
        nodes.push_back(temp);
    }//读入每个人的信息
    //进行合并
    for(int i=0;i<N;i++){
        Node temp = nodes[i];
        int  k = nodes[i].cn;
        if(temp.fid!=-1){
            Union(temp.id, temp.fid);
            vis[temp.fid] = true;
        }
        if(temp.mid!=-1){
            Union(temp.id,temp.mid);
            vis[temp.mid] = true;
        }
        for(int j=0;j<k;j++){
            Union(temp.id,temp.cid[j]);
            vis[temp.cid[j]] = true;
        }
        vis[temp.id] = true;
    }

    //统计每个家族的情况
    int count = 0;
    for(int i=0;i<N;i++){
        Node temp = nodes[i];
        int x = find(temp.id);
        roots[x].id = x ;//用于比较
        if(!roots[x].flag){
            count++;
            roots[x].flag = true;
        }
        roots[x].estate +=temp.estate;
        roots[x].area += temp.area;
    }
    for(int i=0;i<10000;i++){
        if(vis[i]){
            roots[find(i)].people++;
        }
    }
    for(int i=0;i<10000;i++){
        if(roots[i].flag){
//            cout<<roots[i].id<< " "<<roots[i].estate<< " "<<roots[i].area<<" " <<roots[i].people<<endl;
            roots[i].estate = roots[i].estate /(1.0*roots[i].people);
            roots[i].area= roots[i].area / (1.0*roots[i].people);
        }
    }
    sort(roots,roots+10000,cmp);//
    cout<<setiosflags(ios::fixed)<< setprecision(3);
    for(int i=0;i<count;i++){
        char ss[5];
        sprintf(ss,"%04d",roots[i].id);
        cout<<ss<<" "<<roots[i].people<<" "<<roots[i].estate<<" "<<roots[i].area<<endl;
    }


}

Posted on Edited on

写在前面

这里用来记录PAT解题的一些考点,注意事项,源代码请到这里[link]去找. 按照题号写的, “XX_w2.cpp”是参考的大神的代码

2020.5.16

1106 Lowest Price in Supply Chain

同类题目:

  • 求叶子结点的最小层
  • 有向无权图的单元最短路的条数

​ 考点: 利用 图的DFS / BFS 求叶子结点的最小层(要减枝,不然会超时)

利用vector<int> Nodes[max] 构建邻接链表

问题

  1. 结果要求保留小数点后4位, 需要控制输出格式 , cout<<setiosflag(ios::fixed)<<setprecision(4)<<…
  2. 一般用double代替float,保留一定的精度
  3. 边界min_depth的初值我设置成9999, 有点小,卡了三个样例,要注意边界值的设置
  4. bfs,我经常容易忘记结点出队/=,害

1115 Counting Nodes in a BST

  • 计算BST中最低层和次低层的结点的个数

相关考点:

1. BST的构建--insert,creatBST模板函数
 2. DFS

问题:

​ 这次还是边界设置错啦,–int depth=-1; //只有一个结点的时候,出错

1114 Family Property

  • 统计求集合的并集,并集合中的信息

相关考点:

​ 1.并查集的find 和 union 模板(==遗留问题, 路径压缩的并查集和非路径压缩有什么区别??,这里带路径压缩的find会导致出错)

  1. 这里的4位的id是直接用int来表示的,方便并查集的实现;不过最后的输出格式要额外处理

    • 如何把int转换成string,并且高位用0填充
      • char des[10] ; int src = 1998 ;
      • sprintf(des,”%04d”,src); //把src转换为4位的string,并用0填充,转换的结果存储到des中.

  2. 经常开一个比较大的数组作为全局变量.节省一些处理.

    这道题开大数组,索引起来特别方便.不过要增加一个vis[10000]数组表示id是有效的.

    (自己做题总是小心翼翼,不想浪费太多的空间)

  3. 这道题数据处理的过程,可以多学习一些,自定义了两个struct,一个用来处理输入(输入一个结点,进行一次union操作,int father[]用来保存并查集结构) ；另外一个用来处理输出,(保存每个集合的统计信息)

1126 Eulerian Path

  • 判断图是否是欧拉图,半欧拉图,非欧拉图

    • 欧拉图的定义

      欧拉回路：图G中经过每条边一次并且仅一次的回路称作欧拉回路

      欧拉通路：图G中经过每条边一次并且仅一次的路径称作欧拉通路。
      欧拉图(Eulerian graph)指的就是存在欧拉回路的图。
      半欧拉图(semi-Eulerian graph)指的是存在欧拉通路但不存在欧拉回路的图。

      1.无向图中：

      无向图G为欧拉图，当且仅当G为连通图且所有顶点的度为偶数。

      　无向图G为半欧拉图，当且仅当G为连通图且除了两个顶点的度为奇数之外，其它所有顶点的度为偶数。

      2.有向图中：
      　　有向图G为欧拉图，当且仅当G为连通图，且所有顶点的入度等于出度。
      　　有向图G为半欧拉图，当且仅当G为连通图，且存在顶点u的入度比出度大1，v的入度比出度小1，其它所有顶点的入度等于出度。

基本思路:

  1. 统计所有顶点的度,计算度为奇数的结点的个数
  2. 判断该图是否是连通图

考点

​ 如何判断是否是连通图?

​ 1.利用并查集(在接收输入时,构建并查集) ,时间复杂度

​ 2. 一次深搜DFS ,时间复杂度:

Posted on Edited on 
1
2
3
4
5
6
7
struct Node{
    int height;
    int val;
    Node* left;
    Node* right;
    Node(int v):val(v),left(nullptr),height(1),right(nullptr){};
};

查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Node* find(Node* root ,int val){
	if(root==nullptr){
		return nullptr;
	}
	if(root->val == val){
		return root;
	}else if (root->val>val){
        
		find(root->left , val);
        
	}else{
        
        find(root->right,val);
    }
}

插入

左旋操作

1
2
3
4
5
6
7
8
void L(Node*& root){
    Node* temp = root->right;
    root->right = temp->left;
    temp->left = root;
    updateHeight(root);
    updateHeight(temp);
    root = temp;
}

右旋操作

1
2
3
4
5
6
7
8
void R(Node* & root){//指针引用型
    Node* temp = root->left;
    root ->left = temp->right;
    temp->right = root;
    updateHeight(root);
    updateHeight(temp);
    root = temp;//根结点
}

插入

1
2
3
4
5
6
7
8
9
/*
 * 左右子树高度的差值称为该结点的平衡因子
 */
int getBalanceFactor(Node* root){
    return getHeight(root->left) - getHeight(root->right);
}
void updateHeight(Node* root){
    root->height = max(getHeight(root->left),getHeight(root->right))+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
void insert(Node*& root, int v){
    if(root == NULL){
        root = new Node(v);
        return ;
    }else{
        if(root->val>v){//向左子树插
            insert(root->left,v);//
            if(getBalanceFactor(root)==2){//如果不平衡,向左插,只会增加1
                if(getBalanceFactor(root->left)==1){//LL型
                    R(root);
                }else if(getBalanceFactor(root->left)==-1){
                    L(root->left);
                    R(root);
                }

            }
        }else{
            insert(root->right,v);
            if(getBalanceFactor(root)==-2){
                if(getBalanceFactor(root->right)==-1){//RR
                    L(root);
                }else if(getBalanceFactor(root->right)==1){//RL
                    R(root->right);
                    L(root);
                }
            }
        }
    }
       updateHeight(root);//插入之后记得update一下高度
}

之前就是插入之后,忘记updateHeight(),出错了

删除

<==================较为复杂,之后再填坑======>

建立AVL

1
2
3
4
5
6
7
8
Node* CreatAVL(vector<int> nodes){
    Node* root = NULL;
    int size = nodes.size();
    for(int i=0;i<size;i++){
        insert(root,nodes[i]);
    }
    return root;
}

Posted on Edited on

[题目]

[link]大致意思是判断一个插入序列是否是合法的BST/镜像BST先根序列,如果是的话,求它的后根

[基本思路]

  1. 首先利用递归判断是否是合法的BST或者镜像BST的先根遍历

​ 原理: root是第一个元素, 比root小的 // 比root大的 聚集在一起

方法2:也可以把它作为插入序列,跟据他构建一个BST树,再求这个新建的BST的先根序列,如果一致,则之前那个插入序列就是先根序列.

  1. 判断出如果是合法的BST前缀,按照此作为插入序列,构造BST

​ 如果是合法的镜像BST前缀,按照次作为插入序列,构造镜像BST

  1. 跟据构造好的BST/镜像BST 求其后根遍历

[代码]

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
///还是只能过部分测试样例,==,害,好难嗷
/*
 * 之后有修改好了,最初的那部分问题--出现在如果 出现和根结点值相同的结点,
 *  应该是放在右子树的一个结点, 而不是右子树(/=\),
 *  因为插入顺序是先根遍历顺序,如果把和根结点相同的点归为右子树,它将会作为右子树的根(它会向出现)
 */
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int MAX = 1010;
int pre[MAX];
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int v):val(v),left(nullptr),right(nullptr){};
};

//判断是否是合法的先根序列
bool  isBST(int left, int right){
    if(right<=left){
        return true;
    }
    int root = pre[left];
    int mid = right;
    for(int i=left+1;i<right;i++){
        if(pre[i] >root){
            mid = i;
            break;
        }
    }
    for(int i=mid ; i<right;i++){
        if(pre[i]<root){
            return false;
        }
    }
    return isBST(left+1,mid) && isBST(mid,right);
}

bool isMIBST(int left, int right){
    if(right<=left){
        return true;
    }
    int root = pre[left];
    int mid = right;
    for(int i=left+1;i<right;i++){
        if(pre[i]<=root){//左子树
            mid=i;
            break;
        }
    }
    for(int i=mid;i<right;i++){
        if(pre[i]>root){
            return false;
        }
    }
    return isMIBST(left+1,mid) && isMIBST(mid,right);
}


void insert(Node*& root,int val){
    if(root==NULL){
        root = new Node(val);
    }else{
        if(val>=root->val){
            insert(root->right,val);
        }else{
            insert(root->left,val);//相等数值的判断情况
        }
    }
}


void insertMI(Node*& root,int val){
    if(root==NULL){
        root = new Node(val);
    }else{
        if(val>=root->val){
            insertMI(root->left,val);
        }else{
            insertMI(root->right,val);//相等数值的判断情况
        }
    }
}

Node* creatBST(int nodes[],int size){
    Node* root = nullptr;
    for(int i=0;i<size;i++){
        insert(root,nodes[i]);
    }
    return root;
}

Node* creatMIBST(int nodes[],int size){
    Node* root = nullptr;
    for(int i=0;i<size;i++){
        insertMI(root,nodes[i]);
    }
    return root;
}

void postO(Node* root,Node* final){
    if(root==nullptr){
        return ;
    }else{
        postO(root->left,final);
        postO(root->right,final);
        if(root==final){
            cout<<root->val;
        }
        else
        {
            cout<<root->val<<" ";
        }
    }

}

int main(){
    int count;
    cin>>count;
    for(int i=0;i<count;i++){
        cin>>pre[i];
    }
    if(pre[1]<pre[0]){
        if(isBST(0,count)){
            cout<<"YES" <<endl;
            Node* root = creatBST(pre,count);
            postO(root,root);
        }else{
            cout<<"NO";
        }

    }else{
        if(isMIBST(0,count)){
            cout<<"YES" <<endl;
            Node* root = creatMIBST(pre,count);//跟据MIBST构造一个数
            postO(root,root);
        }else{
            cout<<"NO";
        }
    }
    cout<<endl;
}

涉及的数据结构知识点:

BST

  1. 如何跟据插入序列构建一个BST树

    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
    struct Node{
        int val;
        Node* left;
        Node* right;
        Node(int v):val(v),left(nullptr),right(nullptr){};
    };
    void insert(Node*&  root,int val){//注意这里是引用
        if(root==nullptr){
            root = new Node(val);
        }
        else{
            if(val<root->val){
                insert(root->left, val);//插入左子树
            }else{
                insert(root->right,val);
            }
        }
    }

    Node* creatBST(int nodes[],int size){
        Node* root = nullptr;
        for(int i=0;i<size;i++){
            insert(root,nodes[i]);
        }
        return root;
    }

    1. (构建一个镜像BST树的方法是相同的,在镜像BST中,右子树都小于根, 左子树都大于等于根)
    2. 可以把BST的先根遍历做为插入序列构造BST,得到的BST的先根遍历序列和之前的一样

  2. BST的中根遍历序列是递增的

  3. BST的删除操作

    //核心思想:如果N为要删除的结点, 用结点N的前驱Pre 或者 后继 next 来替换N

    //前驱为BST树中左子树最右的结点

    //后继为BST树中右子树最左的结点

    删除值为X的结点

    1.当前root为空,说明不存在值为x的结点,直接返回

    2.如果当前root的权值恰好为给定的权值x,root即为我们要删除的结点

    ​ 1)如果root不存在左右孩子(叶子),则直接删除.

    ​ 2)如果root只存在左子树,则用它的前驱pre覆盖root,在左子树中删除结点pre

    ​ 3)如果root存在左右子树,则在右子树中寻找后继next,然后让next覆盖root,接着在左子树中删除pre

    3.如果当前root的值大于给定的权值x,从root的左子树中寻找要删除的结点

    4.如果当前root的值小于给定的权值x,从root的右子树寻找

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
Node* findMax(Node* root){
    while(root->right != nullptr){
        root = root->right;
    }
    return root;
}

Node* findMin(Node* root){
    while(root->left != nullptr){
        root = root->left;
    }
    return root;
}
void delete(Node* & root, int x){//注意这里是引用
    if(root==nullptr){
        cout<<"fail to find x";
        return ;
    }else if (root-> val == x){
        if(root->right== nullptr && root->left == nullptr){
            //删除结点,没有释放空间
            root=nullptr;//把root设置为null,父结点就找不到了
        }else if(root->right == nullptr){
            Node* pre  = findMax(root->left); //这里只是得到pre的地址,并不能得到pre的父结点的左右子树指针
            root->val = pre->val;
           	deleteNode(root->left,pre->left);//在左子树中删除结点pre
        }else {
             Node* next  = findMin(root->right); //这里只是得到pre的地址,并不能得到pre的父结点的左右子树指针
            root->val = next->val;
           	deleteNode(root->right,next->val);//在左子树中删除结点pre
        }
    }
    else if(root->val>x){
        deleteNode(root->right,x);
    }else{
        deleteNode(root->left,x);
    }
}

Posted on Edited on

广度优先搜索(BFS)

​ BFS:搜索过程中，遇到分叉口时，总是先依次访问从该分叉口能直接到达的所有结点，然后再按照这些结点被访问的顺序去依次访问他们能直接到达的所有结点。以此类推，直到所有结点都被访问为止。

解题思路：

  • 状态：需要确定所求解问题的状态，通过状态的拓展，遍历所有状态
  • 状态拓展的方式：用队列去存储状态，每次去队列头部进行拓展(FIFO)
  • 有效状态：利用题目要求，对BFS搜索树进行剪枝。注意有效状态数的上限，是否符合复杂度要求
  • 应用场景：
    • 解决最短路径(最优问题)

相关例题

计算矩阵中块的个数

1
2
3
#include<iostream>
#include<queue>
using namespace std;

走出迷宫的最小步数

玛雅人的密码

​ 题解思路:

​ 首先要先确定解题的状态(构造一个结构体,保存当前字符串,移位的次数)

​ 合适拓展状态:
​ 出队时,把当前字符串从0-k-1,都与右侧的元素交换, 移位次数加一(另外要有一个vis保存已经遍历过的字符串,已经判断过的字符串不再入队)

​ 结束状态:

​ 找到符合要求的字符串,返回移位次数

​ 队列为空,返回. 

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
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
struct status{
    string cur_str;
    int n;
    status(string cur , int n) : cur_str(cur),n(n){};
};
set<string> vis;
int bfs(queue<status> sset,int len){
    while(!sset.empty()){
        status current = sset.front();
        sset.pop();
        string cur = current.cur_str;
        int n = current.n;
        for(int i=0;i<len-1;i++){
            swap(cur[i],cur[i+1]);//交换
            if(cur.find("2012")!=-1 ){
                return n+1;
            }else{
                if(vis.find(cur)==vis.end()){
                    vis.insert(cur);
                    status next(cur,n+1);
                    sset.push(next);
                }
            }
            swap(cur[i],cur[i+1]);
        }
    }
    return -1;
}
int main(){
    string str;
    int size =0;

    cin>>size;
    cin>>str;
    if(str.find("2012")!=-1){
        cout<< 0;
    }else{ 
        queue<status> sset;
        status init(str,0);
        sset.push(init);
        cout<<bfs(sset,size);
    }
}

Posted on Edited on

贪心算法

贪心算法模板题

无重叠的子区间

435. 无重叠区间

​ 分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
private:
    static bool cmp(vector<int> a, vector<int> b){
    return a[1]<b[1];
}
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.size()==0)
            return 0;
        int n = intervals.size();
        int ans=0;
        sort(intervals.begin(),intervals.end(),cmp);//选择前面的
        int slow=0;
        for(int i=1;i<n;i++){
            if(intervals[slow][1]>intervals[i][0]){
                ans++;
            }else{
                slow=i;
            }
        }
        return ans;
    }
};

452. 用最少数量的箭引爆气球

Posted on Edited on

动态规划解题模板和思路

动态规划套路

动态规划问题的一般形式是求最值，e.g. 最长递增子序列。

核心问题：穷举求最值.　不过，动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。

如何判断问题是否可以采用动态规划求解：

动态规划三要素:重叠子问题、最优子结构、状态转移方程, 如果能够列出来状态转移方程，算法的框架也就基本确定了，只需要考虑一些细节问题即可。

最优子结构

​ 可以从子问题的最优结果中推导出更大规模问题的最优结果

重叠的子问题

​ 可以采用递归调用树，如果递归调用树中存在多个相同的状态结点，则问题具有重叠的子问题

:star:思考状态转移方程的思维框架:

​ 明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case

状态

​ 问题中可能会发生变化的变量，我们做选择的条件(划分了不同的子问题)

e.g. :　在0-1背包中，存在两个状态，「 背包的容量」和 「可选择的物品」

dp数组

​ dp概括了原问题和子问题的最优解的目标

​ e.g. 在0-1背包中，dp[i][j]表示对于前i个物品，当前背包的容量为j时.可以容纳的最大重量

选择

​ 导致状态转移的操作，在0-1背包中，表示第i个物品是否装入背包

base case

​ 初始化条件

其他问题
  • 如何遍历dp表呢？

1、遍历的过程中，所需的状态必须是已经计算出来的。

2、遍历的终点必须是存储结果的那个位置。

相关文章

动态规划 v.s. 回溯

  • 如何理解回溯和动态规划之间的关系？

​ 目前我认为回溯是自顶向下求解，可以利用备忘录优化( C++的备忘录，可以采用 vector<int>mem　存储某个状态下dp的内容,也可以用 unordered_map<string, int> string是状态下标转换的字符)

​ 动态规划是自低向上求解，是利用循环遍历代替暴力递归的一种思路(回溯大多是暴力递归).

可以参考下面的文章中的例子仔细体会

相关例题

背包问题

常见的0-1背包的问题描述：给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性其中第i个物品的重量为wt[i]，价值为val[i]，现在让你用这个背包装物品，最多能装的价值是多少？

字符串类

解决两个字符串的动态规划问题，一般都是用两个指针i,j分别指向两个字符串的最后，然后一步步往前走，缩小问题的规模。

10.正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

1
2
>输入：s = "aa" p = "a*"
>输出：true
动态规划思路

按照上面介绍的过程分析一下吧！

​ 明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case

状态：在s,p匹配过程中，状态有两个：匹配到s串的位置i, 匹配到p串的位置j

定义dp含义：题目要求是判断两个串是否匹配成功,　dp[i][j]表示s[:i] 和 p[:j]两个子串是否匹配,为true　表示匹配成功，否则失败

最终目标是求得dp[s.size()][p.size()]的值

选择：这里的选择感觉指的是　如果当前p串要匹配的字符是*，s串是选择匹配０个／1个／多个

base case以及一些细节信息：如果出现空串如何匹配

为了方便计算，我们定义dp[i+1][j+1]表示s[:i] 和 p[:j]的匹配结果，并且dp[0][0]=true,

同时考虑到，如果出现s为空串，p为”#*"类型，e.g. s=””,p=”a*”,

1
2
s=' '+s;
p=' '+p;

如果不设置这个，不会进入状态转移判断方程，直接退出循环，误判为　匹配失败。

dp转移方程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool isMatch(string s, string p) {
    s=' '+s;
    p=' '+p;
    int n=s.size();
    int m =p.size();
    vector<vector<bool>> dp (n+1,vector<bool>(m+1,false));
    dp[0][0]=true;

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i]==p[j] || p[j]=='.'){
                dp[i+1][j+1]=dp[i][j];
            }
            else if(p[j]=='*'){
                int flag = s[i]==p[j-1] || p[j-1]=='.';
                dp[i+1][j+1] = (flag && (dp[i][j+1] || dp[i+1][j]) )||(dp[i+1][j-1]);
            }
        }
    }
    return dp[n][m];
}
待备忘录的暴力搜索

(不增加备忘录，会出现超时)

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
unordered_map<string,int> dp;
bool caldp(int i,int j,string s,string p){
    if(j==p.size())
        return i == s.size();

    if(dp[i][j]!=-1){
        return dp[i][j];
    }

    else{
        bool flag = i<s.size() && (s[i]==p[j] || p[j]=='.');
        if(j<p.size()-1 && p[j+1]=='*'){
            dp[i][j]= caldp(i,j+2,s,p) || (flag && caldp(i+1,j,s,p));
            return dp[i][j];
        }else{
            dp[i][j]=flag && caldp(i+1,j+1,s,p);
            return dp[i][j];
        }
    }
}
bool isMatch(string s, string p) {
    int slen=s.size();
    int plen = p.size();
    for(int i=0;i<slen+1;i++){
        dp.push_back(vector<int>(plen,-1));
    }
    return caldp(0,0,s,p);
}

其他

494. 目标和

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

Posted on Edited on

字符串常用的库函数和模板

经典题型总结

1.字符串匹配问题

28. 实现 strStr()

Sunday 算法

主要思路：

从前往后进行匹配，匹配成功时，模式串和主串索引同时+1，指向下一个

如果匹配失败，关注的是主串中参与匹配的最末位字符的下一位字符

  • 如果该字符没有出现在模式串中，移动位数=模式串长度＋１(因为移动位数<模式串长度，都会失败)

    eg: sudbccsde 模式串为：sde,此时ｂ没有出现在模式串中，可以直接略过它，主串从b的下一个位置，与模式串从头匹配

  • 如果该字符出现在该模式串中，移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1，主串移动到该位置　和模式串从头开始匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Sunday( string mstr,string des){//mstr为主串,des为模式串,返回模式串在主串中第一次出现的位置，如果不存在返回-1
	int dlen  = des.size();
	int mlen = mstr.size();
	unordered_map< char ,int>  shift;
	for(int i=0;i<dlen;i++) shift[des[i]]=dlen-i;//如果des中有字符重复，最后存储的是最右侧对应的shift
	int n=mlen-dlen;
	int i=0;
	while(i<=n){//i参与匹配的子串的
		if( mstr.substr(i,dlen)== des) return i; //如果已经找到
		else{
				if(shift.find(mstr[i+dlen])!=shift.end()){
                    i+= shift[mstr[i+dlen]];
                }else{
                    i += dlen+1;
                }
		}
	}
	return -1;
}

2.字符串中的动规问题

5.最长回文子串

​ 思路：定义状态，设计状态转移方程

bool dp[i][j]表示str.substr(i,j-i+1)是否是回文字

动态转移方程: dp[i][j] = dp[i+1][j-1] && (str[i]==str[j])

记录使 dp[i][j]为true的j-i+1的最大值。

时间复杂度: O(n*n)

空间复杂度: O(n*n)

10. 正则表达式匹配

​ 思路：定义状态，设计状态转移方程

目标串　s ,模式串p

bool dp[i][j]表示s[0:i]和p[0:j]之间匹配的结果

３.字符串相关处理

71. 简化路径

利用堆栈的思路解决

如果遇到字符串，压入堆栈中，如果遇到.不变

巧用栈，但是由于

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

class Solution {
public:
    string simplifyPath(string path) {
            vector<string> dirs;
            int index = -1;
        for(auto ptr = path.begin();ptr!=path.end(); ){
            ++ptr;//把跟目录跳过去
            auto _split = find(ptr, path.end(),'/');
            string substr = string(ptr,_split);
           if(substr==".." ){
               if(index>=0)
                {
                    index--;
                    dirs.erase(dirs.end()-1);
                }
            }else if(substr!="."  &&  substr!=""){
               dirs.push_back(substr);   
                index++;
            }
            ptr=_split;
        }
        string ans ="";
        for(int i=0;i<dirs.size();i++){
            ans+="/";
            ans+=dirs[i]; 
        }
        if(ans==""){
            return "/";
        }
        return ans;
    }

8. 字符串转换整数 (atoi)

细节题。注意测试样例

  • 不规则输入，但是有效 “-3924dfa”,”+413”
  • 无效格式 “++1”,”++c”
  • 溢出数据

9.利用str模拟大数相加

10.Add Binary

4.有限自动状态机

确定有限状态自动机（以下简称「自动机」）是一类计算模型,能够回答某种形式的「对于给定的输入字符串 S，判断其是否满足条件 P」的问题。它包含一系列状态，这些状态中：

  • 有一个特殊的状态，被称作「初始状态」。
  • 还有一系列状态被称为「接受状态」，它们组成了一个特殊的集合。其中，一个状态可能既是「初始状态」，也是「接受状态」。

起初，这个自动机处于「初始状态」。随后，它顺序地读取字符串中的每一个字符，并根据当前状态和读入的字符，按照某个事先约定好的「转移规则」，从当前状态转移到下一个状态；当状态转移完成后，它就读取下一个字符。当字符串全部读取完毕后，如果自动机处于某个「接受状态」，则判定该字符串「被接受」；否则，判定该字符串「被拒绝」

注意：如果输入的过程中某一步转移失败了，即不存在对应的「转移规则」，此时计算将提前中止。在这种情况下我们也判定该字符串「被拒绝」

  • 如何挖掘所有可能的状态，得到一个完备的状态集？

    • 把字符串跟据要求或者特点分为不同的状态，用当前处理到字符串的哪个状态作为自动机的状态
    • 进一步确定「初始状态」和「接受状态」的集合

  • 跟据接受的内容，确定划分接受数据的类型

  • 确定状态转移的规则

    在c++中，可以用enum(枚举)存储自动机状态State，定义接受的数据类型(InputType)

    用unordered_map<State , unordered_map<InputType,State>>

相关例题

65. 有效数字

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
71
72
73
74
75
76
77
78
79
80
81
82
class Solution {

public: 
    enum status{
        start,
        int_sign,
        integer,//
        left_point,//
        without_left_point,
        exp,
        exp_sign,
        exp_part,//
        fraction//
    };

    enum input{
        digit,
        point,
        sign,
        eE,
        invaild
    };

    unordered_map<status,unordered_map<input,status> > shift{   
        {start, { {digit,integer},
                {point,without_left_point},
                {sign,int_sign},
                }},
        {int_sign,{{digit,integer},
                  {point,without_left_point}
                    }},
        {integer,{{digit,integer},
                {point,left_point},
                {eE,exp},//指数
                }},
        {left_point,{{digit,fraction},
                    {eE,exp}}},
        {without_left_point,{{digit,fraction}}},
        {exp,{{digit,exp_part},
            {sign,exp_sign}}},
        {exp_sign,{{digit,exp_part}}},

        {exp_part,{{digit,exp_part}}},
        {fraction,{{digit,fraction},
                {eE,exp}}}
    };
    
    input inputtype(char ch){
        input ans = invaild;
        if(ch>='0' && ch<='9'){
            ans = digit;
        }else if( ch =='e' || ch=='E'){
            ans = eE;
        }else if(ch=='+' || ch=='-'){
            ans = sign;
        }else if(ch=='.'){
            ans = point;
        }
        return ans;
    }

    bool isNumber(string s) {
        status ss = start;
        int n= s.size();
        for(int i=0;i<n;i++){
            input chtype = inputtype(s[i]);
            if(chtype==invaild){
                return false;
            }
            if(shift[ss].find(chtype)==shift[ss].end()){
                return false;
            }else{
                ss = shift[ss][chtype];
            }
        }
        if(ss==integer|| ss==left_point || ss==exp_part || ss==fraction){
            return true;
        }else{
            return false;
        }
    }
};

Posted on Edited on

使用时，需要#include<string>

string定义和初始化

1
2
string str;
string str = "abcd";

string中内容的访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//1.直接通过下标访问
string str = "abcd";
str[0];

//2.通过迭代器访问
#include<stdio.h>
#include<string>
using namespace std;
int main(){
    string str ="sadas";
    for(string::iterator it = str.begin();it!=str.end();it++){
        cout<<*it<<" ";
    }
}
//和vector一样，string的迭代器支持加减整数操作

string常用的函数

运算符

1
2
3
4
5
6
7
8
9
10
//operator+=，支持两个string直接拼接
string str1 = "abc",str2 = "xsf",str3;
str3 = str1+str2; // str3 = "abcxsf";
str1 += str2; //str1="abcxsf"


//compare operator == ，!= ,< , <= ,>,>= 比较大小,比较规则是字典序
string str1 = "aa" , str2 = "aaa" ,str3 = "abc" ,str4 = "xyz";
bool b1 = str1<str2; //true
bool b2 = str3>str2;//true

增删改查

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
length()/size() //返回字符串长度
 str.substr(int pos , int len); //返回从pos下标开始，长度为len的子串，时间复杂度为O(len)


//==========增===========
insert(int pos,string); //在pos号下，插入字符串string
insert(iterator it , iterator str , iterator end);//将[str,end)之间的字符串 插入到it所指的位置之前

string str = "safs" , str2="134";
str.insert(3,str2); //str = "saf123s"
string str3 = "abc";
str2.insert(str2.begin()+1,str3.begin(),str3.end());//str2 = "1abc34";

//===========删=O(N)==================
str.erase(iterator it); //用于删除单个元素
str.erase(iterator first, iterator last); //用于删除[first,last)区间
str.erase(int pos , length);//
string str = "dasdfas

    
 str.clear();//清空字符串

//=======find=======
str.find(str2); //当str2是str的子串时，返回其在str中第一次出现的位置，如果str2不是str子串，返回-1

//===替换
str.replace(int pos, int len , str2);//把str从pos下标开始的，长度为len的子串替换为str2(str2的长度可以超过len,)
str.replace(iterator it1, iterator it2,str2);

相关库函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool  isalnum(char c); //用于检测一个字符是否是字母或者十进制数字

bool isalpha(char c);//用于检测一个字符

bool isdigit(char c);//用于检测一个字符是否是十进制数

    #include <stdio.h>
    #include <ctype.h>
    int main ()
    {
        int i = 0, n = 0;
        char str[] = "*ab%c123_ABC-.";
        while(str[i])
        {
            if( isalnum(str[i]) ) n++;
            i++;
        }
        printf("There are %d characters in str is alphanumeric.\n", n);
        return 0;
    }

///There are 9 characters in str is alphanumeric.

常用操作

大小写字母转换(transform)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//===大小写字母转换===transform
/*
template <class InputIterator, class OutputIterator, class UnaryOperation>
  OutputIterator transform (InputIterator first1, InputIterator last1,
                            OutputIterator result, UnaryOperation op);
    
template <class InputIterator1, class InputIterator2,
          class OutputIterator, class BinaryOperation>
  OutputIterator transform (InputIterator1 first1, InputIterator1 last1,
                            InputIterator2 first2, OutputIterator result,
                            BinaryOperation binary_op);
*/
#include <algorithm>
#include <string>
	string strsrc("Hello, World!");
	transform(strsrc.begin(), strsrc.end(), strsrc.begin(), to_upper);	// 转换为大写
 
	string strsrc("Hello, World!");
	transform(strsrc.begin(), strsrc.end(), strsrct.begin(), to_lower); // 转换为小写

版权声明：本文为CSDN博主「ningto.com」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/tujiaw/article/details/6976424

Posted on Edited on

双指针算法

相关例题

80. 删除有序数组中的重复项 II

给定一个增序排列数组 nums ，你需要在 原地 删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例:

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]

解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。你不需要考虑数组中超出新长度后面的元素。

思路分析：

首先，用变量maxRepeat=2来表示每个元素最多出现两次。定义指针slow，其初始值为maxRepeat-1=1。**

规定区间[0,slow]内的元素为最多出现两次的元素。 [0,slow]中的元素保存的是符合出现次数要求的元素集合

定义变量fast=maxRepeat=2，指向当前考察的元素。

  • 当前考察的元素nums[fast]== nums[slow-maxRepeat-1]，即变量fast所指向的元素1在区间[0,slow]中已出现两次。

    因此继续考察下一个元素，fast向右移动一位。

  • 当nums[fast] != nums[slow - maxRepeat + 1]，即指针fast指向的元素2不等于指针slow - maxRepeat + 1所指向的元素1，

    nums[fast]所指的元素在区间[0,slow]内，未出现超过两次，因此需要将慢指针slow向右移动一位来扩大区间。

    故slow++;接着将快指针fast指向的元素值赋予慢指针slow所指向的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
         if(nums.size()<0){
            return nums.size();
        }
        int index=2;
        int n= nums.size();
        for(int i=2;i<n;i++){
            if(nums[index-2]!=nums[i]){
                nums[index++] = nums[i];
        }
    }
    return index;
    }
};

作者：hardcore-aryabhata
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/solution/kuai-man-zhi-zhen-80-shan-chu-pai-xu-shu-4rnk/
来源：力扣（LeetCode）

75. 颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

自己的思路：使用两个指针pv,lv;　遍历时，保证pv之前保存的都是0，保证　lv之后保存的都是２;

注意：cv计数器：遍历的范围是(0,lv] ,否则会重新调换回来;当cv所指内容是２时，cv所指元素与–lv所指元素调换之后，cv不能直接指向下一个元素; 而和++pv调换之后，cv需要直接指向下一个(因为++pv所指内容只能是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
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        if(n<=1){
            return;
        }
        else if(n==2){
            if(nums[0]>nums[1]){
                swap(nums[0],nums[1]);
            }
            return;
        }
        int lv = n;
        int pv = -1;
        for(int cv=0;cv<lv;){
            if(nums[cv]==0){
                swap(nums[++pv],nums[cv]);//[0,pv]－－０
                cv++;
            }else if(nums[cv] == 2){
                swap(nums[--lv],nums[cv]);//[lv,n)－－２
            }else{
                cv++;
            }
        }
    }
};