机试考前复习

Learning

链表

链表中的节点每k个一组翻转 [牛客](https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?tpId=295&tqId=722&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page) 
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
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        vector<int> list;
        ListNode* node = head;
        while(node){
            list.push_back(node->val);
            node = node->next;
        }
        int l = 0, r = k-1;
        while(r < list.size()){
            int i = l, j = r;
            while(i < j){
                int tmp = list[i];
                list[i] = list[j];
                list[j] = tmp;
                i++; j--;
            }
            l = l + k;
            r = r + k;
        }

        ListNode* dummyhead = new ListNode(0);
        ListNode* newHead = dummyhead;
        for(auto num : list){
            newHead->next = new ListNode(num);
            newHead = newHead->next;
        }
        return dummyhead->next;
    }
};

排序

快速排序 
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
#include<iostream>
using namespace std;

int n;
const int N = 100010;
int arr[N];

void quicksort(int l, int r){

    // 递归终止情况
    if(l >= r) return;

    // 分成子问题
    int i = l-1, j = r+1, x = arr[(l + r) >> 1];
    while(i < j){
        do i++; while(arr[i] < x);
        do j--; while(arr[j] > x);
        if(i < j) swap(arr[i], arr[j]);
    }

    quicksort(l, j); quicksort(j+1, r);

}

int main(){
cin >> n;
for(int i = 0; i < n; i++){
cin >> arr[i];
}
 quicksort(0, n-1);

    for(int i = 0; i < n; i++){
        cout << arr[i] << " ";
    }

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

int n;

vector<int> add(vector<int>& A, vector<int>& B){
    if(B.size() > A.size()) return add(B, A);
    // 默认A的大小比B大
    vector<int> C;
    int t = 0;
    for(int i = 0; i < A.size(); i++){
        if(i < B.size()) t += B[i];
        t += A[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if(t) C.push_back(t);
    return C;
}

int main(){
    string a, b;
    cin >> a >> b;
    vector<int> A;
    vector<int> B;
    // 倒序存入
    for(int i = a.size()-1; i >= 0; i--){
        A.push_back(a[i]-'0');
    }
    for(int i = b.size()-1; i >= 0; i--){
        B.push_back(b[i]-'0');
    }

    vector<int> C = add(A, B);

    for(int i = C.size()-1; i >= 0; i--){
        cout << C[i];
    }

}

数学问题

试除法判断质数 
1
2
3
4
5
6
bool prime(int t){
    if(t < 2) return false;
    for(int i = 2;i <= t / i;i++)//循环为了加快速度，可以只到t / i
        if(t % i == 0) return false;
    return 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
30
31
32
33
34
35
36
#include<iostream>
using namespace std;

int n;

bool is_prime(int num){
    if(num < 2) return false;
    for(int i = 2; i <= num / i; i++){
        if(num % i == 0) return false;
    }
    return true;
}

int main(){
    cin >> n;
    int num;
    int i;
    while(n--){
        cin >> num;
        for(i = 2; i <= num / i; i++){
            if(is_prime(i)){
                int count = 0;
                while(num && num % i == 0){
                    count += 1;
                    num /= i;
                }
                if(count != 0) cout << i << " " << count << endl;
            }


        }
        if(num > 1) cout << num << " " << 1 << endl;
        cout << 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
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n;

int gcd(int a, int b){
    if(b == 0) return a;
    else{
        return gcd(b, a % b);
    }
}

int main(){
    scanf("%d", &n);
    while(n--){
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", gcd(a, b));
    }
}

搜索与图论

建图 
1
2
3
4
5
6
7
8
9
int n;
const int N = 100010;
int h[N], ne[N * 2], e[N * 2], idx;

void add(int a, int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
计算子树大小 
1
2
3
4
5
6
7
8
9
10
void dfs_sz(int u, int parent){
    sz[u] = 1;
    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(j != parent){
            dfs_sz(j, u);
            sz[u] += sz[j];
        }
    }
}
图中点的层次 
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<algorithm>
#include<cstring>
#include<queue>

using namespace std;

const int N = 100010;
int dist[N]; // dis[N]用来计算从1到n点的距离
bool st[N]; //表示当前的点是否访问过
int h[N], ne[2 * N], e[2 * N], idx;
int n, m;

void add(int a, int b){
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}

void bfs(){
    memset(dist, 0x3f3f3f3f, sizeof(dist));
    queue<int> q;
    q.push(1);
    st[1] = true;
    dist[1] = 0;

    while(!q.empty()){
        int t = q.front(); q.pop();
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(!st[j]){
                dist[j] = dist[t] + 1;
                q.push(j);
                st[j] = true;
            }
        }
    }

    if(dist[n] > 0x3f3f3f3f / 2) cout << -1 << endl;
    else cout << dist[n] << endl;

}

int main(){
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    // 构建图
    while(m--){
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
    }

    bfs();
}
拓扑排序 
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
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;

int n, m;
const int N = 100010;
int h[N], ne[N], e[N], idx;
int d[N]; // 用来存储入度
queue<int> q;
vector<int> path;

void add(int a, int b){
    e[idx] = b,  ne[idx] = h[a], h[a] = idx++;
    d[b] += 1;
}

void topsort(){
    while(!q.empty()){
        int t = q.front(); q.pop();
        path.push_back(t);
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            d[j] --;
            if(d[j] == 0){
                q.push(j);
            }
        }
    }
}

int main(){
    cin >> n >> m;
    int a, b;
    memset(h, -1, sizeof h);
    while(m--){
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    // 将所有入度为0的节点加入到队列中
    for(int i = 1; i <= n; i++){
        if(d[i] == 0){
            q.push(i);
        }
    }

    topsort();
    if(path.size() == n){
        for(auto num : path){
            printf("%d ", num);
        }
        puts("");
    }
    else printf("-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
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N = 1e6 + 10;
typedef pair<int, int> PII; // 存储从节点 1 到当前点的最小距离

int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];
int n, m;

void add(int a, int b, int c){
  e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dijkstra(){
  priority_queue<PII, vector<PII>, greater<PII>> q;
  memset(dist, 0x3f, sizeof dist);
  dist[1] = 0;
  q.push({0, 1}); // 注意：这里 `dist[1]` 的值已经是 `0`

    while(!q.empty()){
        auto t = q.top();
        int distance = t.first, ver = t.second;
        q.pop();

        if(st[ver]) continue;
        st[ver] = true;

        for(int i = h[ver]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[ver] + w[i]){
                dist[j] = dist[ver] + w[i];
                q.push({dist[j], j});
            }
        }
    }

}

int main(){
  memset(h, -1, sizeof h);
  scanf("%d%d", &n, &m);
  while(m--){
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    add(a, b, c);
  }

  dijkstra(); // 修复：缺少 Dijkstra 调用

  if(dist[n] == 0x3f3f3f3f) puts("-1"); // 修复：正确的无穷大判断
  else printf("%d\n", dist[n]);

  return 0;

}
prim求最小生成树 https://www.acwing.com/solution/content/38312/ 
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

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 510;
int g[N][N];//存储图
int dt[N];//存储各个节点到生成树的距离
int st[N];//节点是否被加入到生成树中
int pre[N];//节点的前去节点
int n, m;//n 个节点，m 条边

void prim()
{
    memset(dt,0x3f, sizeof(dt));//初始化距离数组为一个很大的数（10亿左右）
    int res= 0;
    dt[1] = 0;//从 1 号节点开始生成
    for(int i = 0; i < n; i++)//每次循环选出一个点加入到生成树
    {
        int t = -1;
        for(int j = 1; j <= n; j++)//每个节点一次判断
        {
            if(!st[j] && (t == -1 || dt[j] < dt[t]))//如果没有在树中，且到树的距离最短，则选择该点
                t = j;
        }

        //2022.6.1 发现测试用例加强后，需要判断孤立点了
        //如果孤立点，直返输出不能，然后退出
        if(dt[t] == 0x3f3f3f3f) {
            cout << "impossible";
            return;
        }


        st[t] = 1;// 选择该点
        res += dt[t];
        for(int i = 1; i <= n; i++)//更新生成树外的点到生成树的距离
        {
            if(dt[i] > g[t][i] && !st[i])//从 t 到节点 i 的距离小于原来距离，则更新。
            {
                dt[i] = g[t][i];//更新距离
                pre[i] = t;//从 t 到 i 的距离更短，i 的前驱变为 t.
            }
        }
    }

    cout << res;

}

void getPath()//输出各个边
{
    for(int i = n; i > 1; i--)//n 个节点，所以有 n-1 条边。

    {
        cout << i <<" " << pre[i] << " "<< endl;// i 是节点编号，pre[i] 是 i 节点的前驱节点。他们构成一条边。
    }
}

int main()
{
    memset(g, 0x3f, sizeof(g));//各个点之间的距离初始化成很大的数
    cin >> n >> m;//输入节点数和边数
    while(m --)
    {
        int a, b, w;
        cin >> a >> b >> w;//输出边的两个顶点和权重
        g[a][b] = g[b][a] = min(g[a][b],w);//存储权重
    }

    prim();//求最下生成树
    //getPath();//输出路径
    return 0;
}

动态规划

最小路径和 [leetcode 64 题](https://leetcode.cn/problems/minimum-path-sum/description/?envType=problem-list-v2&envId=dynamic-programming) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        if(n <= 1 && m <= 1) return grid[0][0];
        // f[i][j] 表示走到 (i, j) 的最小路径
        vector<vector<int>> f(n, vector<int>(m, 0x3f3f3f3f));
        f[0][0] = grid[0][0];
        for(int i = 1; i < m; i++) f[0][i] = f[0][i-1] + grid[0][i];
        for(int i = 1; i < n; i++) f[i][0] = f[i-1][0] + grid[i][0];

        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                f[i][j] = min(f[i-1][j] + grid[i][j], f[i][j]);
                f[i][j] = min(f[i][j-1] + grid[i][j], f[i][j]);
                // cout << i << " " << j << " " << f[i][j] << endl;
            }
        }
        return f[n-1][m-1];
    }

};