算法分析期末复习

算法分析考试课后习题

chap1 概论

求包含 n(n>1)个元素的无序序列中第 k 小的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <queue>
#include <iostream>
using namespace std;
priority_queue<int, vector<int>, less<int>> que; //递增排序
int main()
{
    int n;    //输入的整数个数为n
    cin >> n; //输入n
    int *a = new int[n];
    for (int i = 0; i < n; i++) //输入n个数
    {
        cin >> a[i];    //输入a[n]
        que.push(a[i]); //插入到队尾
    }
    int m; //需要输出的第k个数
    cin >> m;
    for (int i = 0; i < n - m; i++)
    {
        que.pop(); //弹出队头元素
    }
    cout << que.top();
    return 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <queue>
#include <iostream>
// #include <cstdio>

using namespace std;
int Comp(int *a, int n, int k)
{
    int i, j = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    for (i = 0; i < n; i++)
    {
        pq.push(a[i]);
    }
    for (i = 1; i <= k; i++)
    {
        j = pq.top();
        pq.pop();
    }
    return j;
}
int main()
{
    int x;    //输入的整数个数
    cin >> x; //输入x
    int *a = new int[x];
    for (int i = 0; i < x; i++)
    { //输入a[x]
        cin >> a[i];
    }
    int y; //需要输出的第k=y大的数
    cin >> y;
    int n = x;
    for (int k = 1; k <= n; k++)
    {
        if (k == y)
        {
            cout << Comp(a, n, k);
            break;
        }
        else
            continue;
    }
    return 0;

}

chap2 递归

小明的幸运数

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
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//函数实现
//十进制
int f(int x)
{
    int sum1 = 0;
    while (x != 0)
    {
        sum1 += x % 10;
        x = x / 10;
    }
    return sum1;
}
//二进制
int g(int y)
{
    int sum2 = 0;
    while (y != 0)
    {
        sum2 += y % 2;
        y = y / 2;
    }
    return sum2;
}

int main()
{
    int n;
    cin >> n;//输入n

    int a = 0; //计数器

    for (int i = 1; i <= n; i++)
    {
        if (f(i) == g(i))
        {
            a++;//计数
            cout << i << " ";
        }
    }
    cout << "\n";
    cout << a << endl;
    return 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
#include <iostream>
#include <string>
#include <bits/stdc++.h>
using namespace std;
bool Palindrome(const string& s)
{
    if(s.size()==0||s.size()==1)
        return true;
    else if(s[0]!=s[s.size()-1])
        return false;
    else
        return Palindrome(s.substr(1, s.size() - 2));
}

int main()
{
    string chuan;
    cin >> chuan;
    if(Palindrome(chuan))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

chap3 分治

逆序对

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
#include <iostream>
#include <bits/stdc++.h>
//暴力枚举
using namespace std;
int main()
{
    int counter = 0;
    int num = 0;
    int i, j;

    cin >> num;
    int a[num];//定义一个数组来接收输入的数字
    for (i = 0; i < num; i++)
    {
        cin >> a[i];
    }
    for (i = 0; i < num - 1; i++)
    {
        for (j = i + 1; j < num; j++)
        {
            if (a[j] < a[i])

                counter++;

        }
    }
    cout << counter << endl;
    return 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
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
//采用分治法寻找序列中的最大和最小值
#include <bits/stdc++.h>
#include <iostream>
#define max(x, y) x >= y ? x : y
#define min(x, y) x <= y ? x : y
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 200; //数组最大尺寸200
int a[maxn];

int Max, Min;

void init()
{
    Max = -INF;
    Min = INF;
}

void PartGet(int left, int right)
{
    if (left == right)
    {
        if (a[left] > Max)
            Max = a[left];
        if (a[left] < Min)
            Min = a[left];
        return;
    }
    int mid = (left + right) / 2;
    PartGet(left, mid);
    PartGet(mid + 1, right);
}
int main()
{
    int Size = 0;

    while (cin >> Size && Size)
    {
        for (int i = 0; i < Size; i++)
            cin >> a[i];

        init();

        PartGet(0, Size - 1);

        cout << Max <<" "<< Min << endl;
    }
    return 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
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
#include <cstdio>
#include <sstream>
#include <string>
#include <iostream>

using namespace std;

int main()
{
    int i;
    string strTemp;
    stringstream sStream;
    cin >> i;
    // int i = 0;
    int a[100];
    int k;
    // char sep;
    cin >> strTemp;
    int pos = strTemp.find(',');
    while (pos != string::npos)
    {
        strTemp = strTemp.replace(pos, 1, 1, ' '); //将字符串中的','用空格代替
        pos = strTemp.find(',');
    }

    sStream << strTemp; //将字符串导入的流中

    for (k = 0; k < i; k++)
    {
        // scanf("%d", &a[i]);
        // cin >> a[k];
        while (sStream)
        {
            sStream >> a[k++];
        }
    }
    int num;
    cin >> num;
    int left = 0;
    int right = i - 1;
    int b[100];
    int b1 = 0;
    int index = -1;
    while (true)
    {
        if (a[(left + right) / 2] == num)
        {
            b[b1++] = num;
            index = (left + right) / 2;
            break;
        }
        if (a[(left + right) / 2] < num)
        {
            b[b1++] = a[(left + right) / 2];
            left = (left + right) / 2 + 1;
        }
        if (a[(left + right) / 2] > num)
        {
            b[b1++] = a[(left + right) / 2];
            right = (left + right) / 2 - 1;
        }
        i = right - left;
        if (i < 0)
        {
            break;
        }
    }
    if (index != -1)
    {
        cout << index << endl;
    }
    else
    {
        cout << "no" << endl;
    }
    for (k = 0; k < b1; k++)
    {
        if(k<(b1-1))
            cout << b[k] << ",";
        else
            cout << b[k];
    }
    return 0;
}

chap4 蛮力

九个数字分别组成三个三位数，比例为 1:2:3

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
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
//暴力法+递归
// 1 2 3
// 4 5 6
// 7 8 9
int force(int num)
{
    if (num >= 9)
    {
        double one, two, three;
        one = a[0] * 100 + a[1] * 10 + a[2];
        two = a[3] * 100 + a[4] * 10 + a[5];
        three = a[6] * 100 + a[7] * 10 + a[8];
        if(two / one == 2 && three / one == 3)
        {
            cout << one << " " << two << " " << three << endl;
        }
        return 0;
    }
    else
    {
        int n;
        for (int i = num; i < 9; i++)
        {
            n = a[i];
            a[i] = a[num];
            a[num] = n;
            force(num + 1);
            n = a[i];
            a[i] = a[num];
            a[num] = n;
        }
    }
        return 0;
}
int main()
{
    ios::sync_with_stdio(false); //关掉scanf 和cin 的同步加快效率
    force(0);
    return 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
26
27
28
29
30
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int a, b, c, d, e;
int counter = 0;
int main()
{
    for (a = 1; a <= 9; a++)
    {
        for (b = 1; b <= 9; b++)
        {
            for (c = 1; c <= 9; c++)
            {
                for (d = 1; d <= 9; d++)
                {
                    for (e = 1; e <= 9; e++)
                    {
                        if (a != b && a != c && a != d && a != e && b != c && b != d && b != e && c != d && c != e && d != e)
                        {
                            if ((a * 10 + b) * (c * 100 + d * 10 + e) == (a * 100 + d * 10 + b) * (c * 10 + e))
                                counter++;
                        }
                    }
                }
            }
        }
    }
    cout << counter << endl;
    return 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int rabbit_chicken;//鸡和兔的数量
    int rabbit_foot, chicken_foot; //兔脚鸡脚
    int x, y, z;                   //鸡脚百位十位个位
    int a, b, c;                   //兔脚百位十位个位
    for (x = 1; x <= 5; x++)
    {
        for (a = 1; a <= 5; a++)
        {
            for (y = 0; y <= 5; y++)
            {
                    for (b = 0; b <= 5; b++)
                    {
                        for (z = 0; z <= 5; z++)
                        {
                            for (c = 0; c <= 5; c++)
                            {
                                chicken_foot = (z + y * 10 + x * 100);
                                rabbit_foot = (c + b * 10 + a * 100);
                                if (chicken_foot % 2 == 0 && rabbit_foot % 4 == 0)
                                {
                                    if (chicken_foot / 2 == rabbit_foot / 4)
                                    {
                                        rabbit_chicken = (chicken_foot / 2);
                                        cout << rabbit_chicken << " " << rabbit_chicken << " " << chicken_foot << " " << rabbit_foot << endl;
                                    }
                                }
                            }
                        }
                    }
            }
        }
    }

    return 0;
}

chap5 回溯

从一组整数中选择若干个,使它们的和恰好为指定的数,要求找出选择元素个数最少的解

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
#include<iostream>
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
int To_Judge(int array[20], int sum, int num, int i);
int Backtrace(int array[20], int sum, int num,int r);
int Layer(int array[20], int sum, int num,int r);
int n, k, r = 0, flag = 0, operation[20] = {0}, s[20] = {0};
int To_Judge(int array[20], int sum, int num, int i) {//判断并存储序号
	if (sum > k)//已在op里或和大于k
		return 0;
	else
	{
		sum += array[i];
		operation[num] = i;
		if (sum==k && num<=r)
		{
			r = num;
			for (int j = 1; j < r+1; j++)
			{
				s[j - 1] = array[operation[j]];
			}
			flag = 1;
			return 0;
		}
		Backtrace(array, sum, num + 1,i+1);
	}
			return 0;
}
int Layer(int array[20], int sum, int num,int r) {//树每层能取的值
	for (int i = r; i <= n; i++)
	{
		To_Judge(array, sum, num, i);
	}
	return 0;
}
int Backtrace(int array[20], int sum, int num,int r) { //树深度num行
	if (num > n)
		return 0;
	Layer(array, sum, num, r);
	return 0;
}

int main() {
	int array[20] = {0};
	cin >> n;
	cin >> k;
	r = n;
	for ( int i = 1; i <= n; i++)
	{
		cin >> array[i];
	}
	Backtrace(array, 0, 1,1);
	if (flag==0)
	{
		printf("No solution");
	}
	else
	{
		for (int i = 0; i < r; i++)
		{
			cout << s[i] << " ";
		}
		cout << endl << r;
	}
}

回溯法求组合

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
#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
int To_Judge(char arr[20], int num, int i,int k);
int Backtrace(char array[20], int num, int k);
void Layer(char arr[20], int num, int k);
char operation[20];
int n, m;
int To_Judge(char array[20], int num, int i,int k)
{
    if (i > n)
        return 0;
    else
    {
        operation[num] = array[i];
        Backtrace(array, num + 1, i + 1);
    }
        return 0;
}
void Layer(char array[20], int num, int k)
{
    for (int i = k; i < n; i++)
    {
        To_Judge(array, num, i, k);
    }
}
int Backtrace(char array[20], int num, int k)
{
    if (num >= m)
    {
        for (int i = 0; i < m; i++)
        {
            cout << operation[i];
        }
        cout << endl;
        return 0;
    }
    Layer(array, num, k);
    return 0;
}

int main()
{
    char array[20];
    cin >> n;//所有字符的个数
    cin >> m;//指定字符的个数
    cin >> array;
    Backtrace(array, 0, 0);
}

chap6 分支限界法

马儿偷懒

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
#include <iostream>
#include <queue>
#include <bits/stdc++.h>
#include <cstring>
using namespace std;
const int maxn = 500;
queue<pair<int, int>> q; //马能走到的棋盘上的坐标
bool vis[maxn][maxn]; //表示是否已经访问过
int n, m, sx, sy, len[maxn][maxn];
int sum;                                                                  //表示马到达该坐标处的最少步数
int dis[8][2] = {1, 2, 2, 1, 1, -2, 2, -1, -1, 2, -2, 1, -1, -2, -2, -1}; //马可以走的八个方向
void bfs()
{
    q.push(make_pair(sx, sy)); //入队
    vis[sx][sy] = 1;           //标记已经访问过
    while (!q.empty())
    {
        //取队首元素
        int x = q.front().first;
        int y = q.front().second;
        q.pop(); //出队
        for (int i = 0; i < 8; i++)
        { //遍历可走的方向
            int dx = x + dis[i][0];
            int dy = y + dis[i][1];
            if (dx >= 1 && dx <= n && dy >= 1 && dy <= m && !vis[dx][dy])
            {                                //可达点
                vis[dx][dy] = 1;             //标记已访问过
                len[dx][dy] = len[x][y] + 1; //距离加1
                q.push(make_pair(dx, dy));   //以该点起点
            }
        }
    }
}
int main()
{
    cin >> n >> m >> sx >> sy;    //输入棋盘大小，马的初始位置
    memset(len, -1, sizeof(len)); //初始距离为-1，表示不能到达
    len[sx][sy] = 0;              //起点到起点距离为0

    //bfs求解马到棋盘上任意一点的最少步数
    bfs();
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            sum += len[i][j];
            // cout << len[i][j] << " ";
        }
        // cout << endl;
    }
    cout << sum << endl;
}

刺杀行动

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
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int map[1005][1005];
bool vis[1005][1005];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
struct edge{
    int x,y;
};
queue<edge>q;
int n,m;
bool check(int mid)
{
    memset(vis,0,sizeof(vis));
    edge s;
    s.x=1,s.y=1;
    q.push(s);
    vis[1][1]=1;
    while(!q.empty())
    {
        edge u=q.front(); q.pop();
        for(int i=0;i<4;i++)
        {
            int mx=u.x+dx[i],my=u.y+dy[i];
            if(mx>=1&&mx<=n&&my>=1&&my<=m&&!vis[mx][my]&&map[mx][my]<=mid)
            {
                vis[mx][my]=1;
                q.push((edge){mx,my});
            }
        }
    }
    bool flag=1;
    for(int i=1;i<=m;i++)
    {
        if(!vis[n][i])
        {
            flag=0;
        }
    }
    if(!flag)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    int l=0,r=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&map[i][j]);
            r=max(r,map[i][j]);
        }
    }
    int ans=21474836;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {
            r=mid-1;
            ans=min(ans,mid);
        }
        else
        {
            l=mid+1;
        }
    }
    printf("%d",ans);
    return 0;
}

chap7 贪心

数字接龙

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
#include <vector>
#include <stdio.h>
#include <algorithm>
class Solution
{
public:
    Solution() {}
    ~Solution() {}
    int findContentChildren(std::vector<int> &g, std::vector<int> &s)
    {
        std::sort(g.begin(), g.end());
        std::sort(s.begin(), s.end());
        unsigned int child = 0;
        unsigned int cookie = 0;
        while (child < g.size() && cookie < s.size())
        {
            if (g[child] <= s[cookie])
            {
                child++;
            }
            cookie++;
        }
        return child;
    }
};
int main()
{
    int n, m;
    scanf("%d", &n);
    // cin << n;
    scanf("%d", &m);
    int x;
    Solution solve;
    std::vector<int> g;
    std::vector<int> s;
    for (int i = 0; i < n; i++){
        scanf("%d", &x);
        g.push_back(x); }
    for (int j = 0; j < m; j++){
        scanf("%d", &x);
        s.push_back(x);}
    printf("%d\n", solve.findContentChildren(g, s));
    return 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
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 <cstdio>
#include <iostream>
#include <bits/stdc++.h>
// #include <algorithm>
using namespace std;
int com(int a, int b)
{
    // int a1 = a, b1 = b;
    int la = 10, lb = 10;
    while (a / la)
    {
        la *= 10;
    }
    while (b / lb)
    {
        lb *= 10;
    }
    return (a * lb + b) - (b * la + a);
}
int main()
{
    int  i, j, n;
    int d[20], t;
    // scanf("%d", &n);
    cin >> n;

    for (i = 0; i < n; i++)
    {
        // scanf("%d", &d[i]);
        cin >> d[i];
    }
    for (j = 0; j < n - 1; j++)
        for (i = 0; i < n - 1 - j; i++)
        {
            if (com(d[i], d[i + 1]) < 0)
            {
                t = d[i + 1];
                d[i + 1] = d[i];
                d[i] = t;
            }
        }
    for (i = 0; i < n; i++)
    {
        cout << d[i];
    }
    cout << endl;

    return 0;
}

chap8 动态规划

求解机器人移动的路径数

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
#include <iostream>
using namespace std;

int route(int x, int y);

int route(int x,int y)
{
    if(x==0&&y==0)
    {
        return 1;
    }
    else if(x==0)
    {
        return route(x, y - 1);
    }
    else if(y==0)
    {
        return route(x - 1, y);
    }
    else
    {
        return route(x - 1, y) + route(x, y - 1);
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    cout << route(n, m);
    return 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, t;
int val[60];
int num[100010];

int main()
{
    while (scanf("%d%d", &n, &t) == 2 && n)
    {
        memset(num, inf, sizeof(num));
        num[0] = 0;

        for (int i = 0; i < n; i++)
        {
            cin >> val[i];

        }

        for (int i = 1; i <= t; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i >= val[j])
                    num[i] = min(num[i], num[i - val[j]] + 1);
            }
        }

        for (int i = t; i >= 0; i--)
        {
            if (num[i] < inf)
            {
                cout << num[i]<< endl;
                break;
            }
            else
            {
                cout << "no answer";
                break;
            }
        }
    }

    return 0;
}

算法分析基础知识

算法的特征：

输入，输出，确定性，有穷性，可行性

常见的大 O 表达式

img

NP（Non-Deterministic Polynomial，非确定多项式）问题：

是指时间复杂度为非多项式量级的算法问题。当数据规模 n 越来越大时，非多项式量级算法的执行会急剧增加，求解问题的执行时间无限增长。所以，非多项式时间复杂度的算法是非常低效的。

常见复杂度从低阶到高阶有：

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2)

img

最好、最坏情况时间复杂度

1
2
3
4
5
6
7
8
9
10
function find(array,x){
    var pos = -1;
    for(var i=0;i<array.length;i++){
        if(array[i] == x){
            pos = i;
            break;
        }
    }
    return pos;
}

上面代码表示，查找变量 x 在数组 array 的位置。如果 x 不在数组 array 里，则返回-1。通过从数组第一个元素开始找，当找到变量 x 时则不继续往下找。否则，会遍历完整个数组。最好情况是，数组第一个元素就是要找的变量 x，此时的时间复杂度为 O(1)，即最好情况时间复杂度。最坏情况是，要遍历完整个数组，此时的时间复杂度为 O(n)，即最坏情况时间复杂度。

基本数据结构：线性结构，树结构，图结构，集合

递归与分治

1、递归法

使用递归方法时须注意的问题：

(1) 递归调用函数必须在满足某个条件时能够退出该程序

(2) 递归调用由于使用堆栈，因此占用的存储空间会很大，且所花费的时间也很多，因而效率低下。

2、分治法

将一个规模比较大的问题分解成若干个规模较小的问题，然后将这些子问题的解合并解出整个问题的解。

什么是数组

数组（Array）是一种 线性表 数据结构，它用一组 连续的内存空间，来存储一组具有相同类型的数据。

线性表

线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。具有线性表结构的数据结构有：数组、链表、队列、栈等

img

与之相对立的概念是非线性表，比如二叉树、堆、图等。非线性表中的数据之间并不是简单的前后关系。

img

连续的内存空间和相同类型的数据

因为有连续的内存空间和相同类型的数据这两个限制，数组才有 随机访问 的特性。同时，也因为这两个条件限制，让数组的很多操作变得非常低效，比如在数组中进行删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。

数组如何实现随机访问

img

举个例子说明：当创建一个长度为 10 的数组 arr 时，计算机给数组 arr 分配一块连续内存空间 1000~1039。同时，计算机也会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数组。其中，内存块的首地址为 base_address = 1000.

当计算机需要随机访问数组中的某个元素时，首先通过下面的寻址公式，计算出该元素的内存地址

1
a[i]_address = base_address + i*data_type_size

其中 data_type_size 表示数组中每个元素的大小。

容器能否完全代替数据

针对数组类型，很多语音都提供了容器类，比如 JavaScript 中的 Array()、Java 中的 ArrayList、C++STL 中的 vector。

数组本身在定义的时候需要预先指定大小，因为需要分配连续的内存空间。当分配的内存空间不够用时，就需要重新分配更大的空间，将原来的数据复制过去。

而容器是将数组的一些操作的细节封装起来，而且支持动态扩容。这样，你就不需要关系底层的扩容逻辑，容器会自动分配更大的内存空间。因此，容器的性能会比直接使用数组，会有一定的性能消耗。

缓存

缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。缓存就是利用空间换时间的设计思想，将数据加载在内存中来提高数据查询的速度。

链表

与数组相反，链表不需要一块连续的内存空间，而是通过“指针”将一组零散的内存块串联起来。其中，内存块称为链表的“结点”。每个结点除了存储数据 data 外，还记录链上的下一个结点的地址，我们把这个记录下个结点地址的指针叫作后续指针 next

  • 链表的优点：插入和删除一个数据非常快，时间复杂度是 O(1)
  • 链表的缺点：随机访问数据却没有数组好，时间复杂度是 O(n)

注：在链表插入和删除一个数据这个动作是非常快，但要找到要插入的位置或要删除的数据就慢了

单链表

头结点：指第一个结点，用来记录链表的基地址

尾结点：指最后一个结点。不过这个结点的指针不是指下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点

循环链表

与单链表的区别在于：循环链表的尾结点指针指向链表的头结点，像是把一条绳子的头尾相连，变成一个环。与单链表相比，循环链表的优点是从链尾到链头比较方便。循环链表适合处理具有环型结构的数据。

双向链表

单链表只有一个方向，结点只有一个后续指针 next 指向后面的结点。而双向链表支持两个方向，每个结点除了有后续指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。

双向循环链表

循环链表+双向链表

如何基于链表实现 LRU 缓存淘汰算法？

思路：我们维护一个有序单链表，越靠近链表尾部的结点时越早之前访问的。当一个新的数据被访问时，我们从链表头开始顺序遍历链表。

1.如果此数据之前已经被缓存在链表中来，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部

2.如果此数据没有在缓存链表中，又可以分为两种情况：

  • 如果此时缓存未满，则将此结点直接插入到链表的头部；

  • 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部

####栈
栈的特点是先进先出，只允许在一端插入和删除数据。

  • 栈顶：栈的最后一个元素
  • 栈底：栈的第一个元素
  • 出栈：从栈顶删除最后一个元素
  • 入栈：向栈顶压入新的元素 ####队列

队列的特征是，先进先出。跟栈一样，队列也是一种操作受限的线性表数据结构。

队列的基本操作：

  • 入列：在队列尾部添加一个元素

  • 出列：从队列头部移除一个元素

树

img

二叉树

二叉树是最常用的树结构。每个节点最多有两个子节点，分别为左子节点和右子节点。二叉树可以同时有两个左右子节点，也可以只有一个左子节点或右子节点。

img

存储二叉树有两种方法：

  • 基于指针或者引用的链式存储法

  • 基于数组的顺序存储法

  1. 链式存储法：

每个节点有三个字段，一个存储数据，另外两个左右两个子节点的指针。只要找到根节点，就可以通过左右子节点的指针将整颗树串起来。

  1. 数组的顺序存储法：

把根节点存在下标为 i = 1 的位置，左子节点存储在下标为 2*i = 2 的位置，右子节点存储在下标为 2 *i + 1 = 3 的位置。以此类推，B 节点左子节点存储在 2 _ i = 2 _ 2 = 4 的位置，右子节点存储在 2 _ i + 1 = 2 _ 2 + 1 = 5 的位置。

1569773359693-342473c6-f5e6-43be-95fd-abe396c32a9b

满二叉树（Fully Binary Tree）

1569773360395-1c42f71d-af37-40a0-9225-1a6ca099c686

叶子节点全部在最底层，且除叶子节点外，每个节点都有左右两个子节点

完全二叉树（Complete Binary Tree）

1569773364572-6858d889-535a-4a8a-8fb0-9e192c4b62ea

叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大。

分治法（分解，解决，合并）

算法思想：为了解决一个大的问题，可以：1) 把它分成两个或多个更小的问题； 2) 分别解决每个小问题； 3) 把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。

选择排序算法时间复杂度 O（n 平方）

归并排序程序将花费(nlogn) 的时间。

快速排序时间复杂度：

T（n）=T（n-1）+O(n)

最好情况：

T（n）=2T(n/2)+O(n)

动态规划算法

动态规划算法的特点：

动态归化算法是将问题分解成若干个子问题，通过求解这些子问题的最优解来求整个问题的最优解。与分治法不同的是，这些子问题往往并不相互独立，不能将子问题的解作为最后问题的解。动态规划往往用于求解问题的最优解

贪心算法

贪心算法的基本要素：贪心选择和最优子结构

分支限界法

以广度优先或最小耗费方式搜索问题解的算法叫分支限界法，分支限界法分为两种：队列式和优先队列式

回溯

回溯（backtracking）是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间（ solution space），这个空间必须至少包含问题的一个解（可能是最优的）。下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。一旦定义了解空间的组织方法，这个空间即可按深度优先的方法从开始节点进行搜索。

回溯方法的步骤如下：

(1)定义一个解空间，它包含问题的解。

(2)用适于搜索的方式组织该空间。

(3)用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。

回溯算法的一个有趣的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保留从开始节点到当前 E-节点的路径。因此，回溯算法的空间需求为 O（从开始节点起最长路径的长度）

排序算法整理

选择排序

1
2
3
4
5
6
7
8
9
10
void selectionSort(int arr[] , int n){
    for(int i=0 ;i<n ; i++){//主遍历，遍历后的部分有序
        int minIndex = i;//每一轮便利中，最小元素下标
        for( int j = i+1 ; j<n ; j++){//子遍历
            if(arr[j]<arr[minIndex])
                minIndex = j;
        }
        swap(arr,i,minIndex);
    }
}

插入排序

vesrion1

1
2
3
4
5
6
7
8
9
10
11
public void insertSort(int arr[], int n){
    for(int i=1; i<n;i++){//主遍历，假设每次子遍历结束时，主指针之前元素均有序
        for(int j=i; j>0&& ;j--){//子遍历，为子指针所指元素查找合适位置
            if(arr[j]<arr[j-1])//小于则交换
                swap(arr , j , j-1);
            else
                break;
        }
    }

}

version2

1
2
3
4
5
6
7
8
9
public void insertSort2(int arr[], int n){
    for(int i = 1; i<n;i++){//主遍历，每次子遍历结束的时候，默认有序
        int temp= arr[i];//存放待排序元素
        int j;//查找上述元素所在位置
        for(j=i; j>0&&arr[j-1]>temp;j--)
            arr[j]=arr[j-1];
        arr[j] = temp;
    }
}

归并排序

总时间=分解时间+解决问题时间+合并时间。分解时间就是把一个待排序序列分解成两序列，时间为一常数，时间复杂度 o(1).解决问题时间是两个递归式，把一个规模为 n 的问题分成两个规模分别为 n/2 的子问题，时间为 2T(n/2).合并时间复杂度为 o（n）。总时间 T(n)=2T(n/2)+o(n).这个递归式可以用递归树来解，其解是 o(nlogn).此外在最坏、最佳、平均情况下归并排序时间复杂度均为 o(nlogn).从合并过程中可以看出合并排序稳定。

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
void mergeSort(int arr[] , int n){
    __mergeSort(arr , 0 , n-1);
}

void __mergeSort(int arr[], int l, int r){
    if(l>= r)
        return;

    int mid = (l+r)/2;
    __mergeSort(arr,l,mid);
    __mergeSort(arr,mid,r);
    __merge(arr, l , mid , r)
}

void __merge(int arr[], int l , int mid , int r){
    int aux[r-l+1];
    for(int i = l ; i< =r ;i++)
        aux[i-l] = arr[i];

    int i = l,j = mid +1;
    for(int k = l;k<=r;k++){
        if(i>mid){
            arr[k] = aux[j-l];
            j++
        }
        else if(j>r){
            arr[k] = aux[i-l];
            i++
        }

        else if(aux[i-l] <aux[j-l]){
            arr[k]= aux[i-l];
            i++;
        }
        else{
            arr[k] = aux[j-l];
            j++;
        }
    }
}

快速排序

version1

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 quickSort(int arr[],int l,int r){//主体函数，向用户公开，可使用
    __quickSort(arr,0,n-1);
}
void __quickSort(int arr[], int n){//内部封装函数，不向用户公开
    if(r-l<=15){
        insertSort(arr,l,r);
        return ;
    }

    int p = __partition(arr,l,r);//将最左端的元素找到对应位置，并传回对应位置
    __quickSort(arr,l,p-1);//将对应位置左端的全部元素排序
    __quickSort(arr,p+1,r);//将对应位置右端的全部元素排序

}

int __partition(int arr[], int l,int r){//排序过程
    swap(arr[l] , arr[rand()%(r-l+1)+l]);
    int v = arr[l];//选取最左端元素，储存
    //arr[l+1 ...j]<v  ; arr[j+1 ... i]>v
    int j=l;//j为最终所在位置
    for(int i = l+1; i<=r ;i++){//i为遍历指针
        if(arr[i]<v){//当前遍历元素小于头元素时，将他放在j之前，大于则放在j之后
            swap(arr[j+1],arr[i]);
            j++；
        }
    }
    swap(arr[l],arr[j]);
    return j;
}

version2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int __partition2(int arr[], int l,int r){
    swap(arr[l] , arr[rand()%(r-l+1)+l]);
    int v = arr[l];//选取最左端元素，储存

    //arr[l+1 ...j]<v  ; arr[j+1 ... i]>v
    int i=l+1 , j=r;
    while(true){
        while(i<=r && arr[i]<v)i++;
        while(j>=l+1 && arr[j]>v)j--;
        if(i>j) break;
        swap(arr[i],arr[j]);
        i++;
        j--;
    }
    swap(arr, l, j);
    return j;
}
code
算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！