头像

acwing_zfw




离线:1小时前


最近来访(104)
用户头像
彩色铅笔
用户头像
Feelme
用户头像
怎样共勉_7
用户头像
Wiselnn
用户头像
snkz5qing
用户头像
limie
用户头像
YooQ
用户头像
桐生一马
用户头像
搏一搏板车杠雷诺
用户头像
做AC梦
用户头像
天使-高某人和彦
用户头像
sep
用户头像
iu.
用户头像
Meguri
用户头像
一起床就读书
用户头像
skydegree
用户头像
可乐会冒泡
用户头像
lexingsen
用户头像
Pipipapi
用户头像
Bug-Free

分享 【排序】

考研算法辅导课

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int q[N], n, sz, w[N];

void insert_sort() {    // 插入排序

    for (int i = 1; i < n; i ++) {
        int t = q[i], j = i;
        while (j && q[j - 1] > t) {
            q[j] = q[j - 1];
            j --;
        }
        q[j] = t;
    }
}

void binary_search_insert_sort() {  // 折半插入排序

    for (int i = 1; i < n; i ++) {
        if (q[i - 1] <= q[i]) continue;
        int t = q[i];
        int l = 0, r = i - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (q[mid] > t) r = mid;
            else l = mid + 1;
        }
        for (int j = i - 1; j >= r; j --)
            q[j + 1] = q[j];
        q[r] = t;
    }
}

void bubble_sort() {    // 冒泡排序

    for (int i = 0; i < n - 1; i ++) {
        bool has_swap = false;
        for (int j = n - 1; j > i; j --) {
            if (q[j - 1] > q[j]) {
                swap(q[j - 1], q[j]);
                has_swap = true;
            }
        }
        if (!has_swap) break;
    }
}

void select_sort() {    // 选择排序

    for (int i = 0; i < n - 1; i ++) {
        int k = i;
        for (int j = k + 1; j < n; j ++) 
            if (q[j] < q[k]) k = j;
        swap(q[i], q[k]);
    }
}

void shell_sort() {     // 希尔排序

    // for (int d = n / 2; d; d /= 2) {
    for (int d = n / 3; d; d = d == 2 ? 1 : d / 3) {
        for (int start = 0; start < d; start ++) {
            for (int i = start + d; i < n; i += d) {
                int t = q[i], j = i;
                while (j > start && q[j - d] > t) {
                    q[j] = q[j - d];
                    j -= d;
                }
                q[j] = t;
            }
        }
    }
}

void quick_sort(int l, int r) {     // 快速排序

    if (l >= r) return ;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j) {
        do i ++; while (q[i] < x);
        do j --; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }

    quick_sort(l, j);
    quick_sort(j + 1, r);
}

void up1(int u) {   // 迭代写法

    while (u > 1 && q[u >> 1] < q[u]) {
        swap(q[u >> 1], q[u]);
        u /= 2;
    }
}

void up(int u) {    // 递归写法

    if (u <= 1) return ;

    if (q[u >> 1] < q[u]) {
        swap(q[u >> 1], q[u]);
        up(u >> 1);
    }
}

void down(int u) {  // 递归写法

    int t = u;
    if (u * 2 <= sz && q[u * 2] > q[t]) t = u * 2;
    if (u * 2 + 1 <= sz && q[u * 2 + 1] > q[t]) t = u * 2 + 1;

    if (u != t) {
        swap(q[t], q[u]);
        down(t);
    }
}

void down2(int u) { // 迭代写法

    int t = u;
    if (u * 2 <= sz && q[u * 2] > q[t]) t = u * 2;
    if (u * 2 + 1 <= sz && q[u * 2 + 1] > q[t]) t = u * 2 + 1;

    while (u != t) {
        swap(q[u], q[t]);
        u = t;
        if (u * 2 <= sz && q[u * 2] > q[t]) t = u * 2;
        if (u * 2 + 1 <= sz && q[u * 2 + 1] > q[t]) t = u * 2 + 1;
    }
}

void heap_sort() {      // 堆排序,下标从1开始  
    sz = n;

    for (int i = n >> 1; i; i --) down(i);  // 建个大根堆

    for (int i = 0; i < n - 1; i ++) {
        swap(q[1], q[sz]);
        sz --;
        down2(1);
    }
}

void merge_sort(int l, int r) {     // 归并排序

    if (l >= r) return ;

    int mid = l + r >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (q[i] <= q[j]) w[k ++] = q[i ++];
        else w[k ++] = q[j ++];
    }
    while (i <= mid) w[k ++] = q[i ++];
    while (j <= r) w[k ++] = q[j ++];

    for (int i = l, j = 0; j < k; i ++, j ++) q[i] = w[j];
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> q[i];

    // insert_sort();
    // binary_search_insert_sort();
    // bubble_sort();
    // select_sort();
    // shell_sort();
    // quick_sort(0, n - 1);
    heap_sort();
    // merge_sort(0, n - 1);

    for (int i = 1; i <= n; i ++) cout << q[i] << ' ';

    return 0;
}



多机调度问题

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 10010, M = 110;
int n, m, q[N], res;

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> q[i];
    sort(q, q + n);

    priority_queue<int, vector<int>, greater<int>> heap;    // 小根堆

    for (int i = n - 1; i > n - 1 - m; i --)
        heap.push(q[i]);

    for (int i = n - 1 - m; i >= 0; i --)
    {
        int x = heap.top();
        heap.pop();
        heap.push(x + q[i]);
    }

    while (heap.size())
    {
        res = max(res, heap.top());
        heap.pop();
    }
    cout << res << endl;

    return 0;
}

循环队列

#include <iostream>
#include <cstring>
#include <algorithm>

#define MaxSize 50

using namespace std;

// 顺序循环队列
typedef int Elemtype;

typedef struct 
{
    Elemtype data[MaxSize];
    int front, rear;
} SqQueue;  // 循环队列

void initQueue(SqQueue &Q)
{
    Q.front = Q.rear = 0;
}

bool isEmpty(SqQueue Q)
{
    return Q.front == Q.rear;
}

bool enQueue(SqQueue &Q, int x)
{
    if ((Q.rear + 1) % MaxSize == Q.front) return false;
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MaxSize;
    return true;
}

bool deQueue(SqQueue &Q, int &x)
{
    if (Q.front == Q.rear) return false;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
    return true;
}


// 链式循环队列
struct Node
{
    int val;
    Node *next;
    Node() : val(0), next(NULL) {}
    Node(int x) : val(x), next(NULL) {}
} *front, *rear;

void InitQueue()
{
    front = rear = new Node();
}

void EnQueue(int x) // 入队
{
    Node *p = new Node(x);
    rear->next = p;
    rear = p;
}

bool DeQueue(int &x)
{
    if (front == rear) return false;
    Node *p = front->next;
    x = p->val;
    front->next = p->next;
    if (rear == p) rear = front;    // 如果队列中只有一个结点,删除后变空
    delete p;
    return true;
}

void show()
{
    auto p = front->next;
    while (p)
    {
        cout << p->val << ' ';
        p = p->next;
    }
    cout << endl;
}

int main()
{
    InitQueue();
    for (int i = 1; i <= 5; i ++ ) EnQueue(i);
    int x;
    DeQueue(x);
    cout << x << endl;

    show();

    return 0;
}



问题描述

编写一个算法,在基于单链表表示的待排序关键字序列上进行简单选择排序

算法思想

每趟在原始链表中摘下关键字最大的结点,插入结果链表的最前端。

输入

3 1 2 5 4

输出

1 2 3 4 5

CODE

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

struct Node
{
    int val;
    Node* next;
    Node(int x) : val(x), next(NULL) {}
};

void print(Node *head)
{
    auto p = head;
    while (p)
    {
        cout << p->val << ' ';
        p = p->next;
    }
    cout << endl;
}

Node* select_sort(Node* head)
{
    Node *dummy = new Node(0), *p, *q, *r, *s;

    while (head) 
    {
        s = p = head; r = q = NULL;
        // s和r记忆最大节点和其前驱,p为工作指针,q为其前驱
        while (p)
        {
            if (p->val > s->val) 
            {
                s = p;
                r = q;
            }
            q = p; p = p->next;
        }
        // 删除最大节点
        if(s == head)           
            head = head->next;
        else
            r->next = s->next;  
        // 头插法
        s->next = dummy->next;
        dummy->next = s;
    }

    return dummy->next;
}

int main()
{
    int nums[5] = {3, 1, 2, 5, 4};
    Node* dummy = new Node(0);
    auto tail = dummy;
    for (int x : nums)
    {
        auto p = new Node(x);
        tail->next = p;
        tail = tail->next;
    }

    print(dummy->next);    

    auto p = select_sort(dummy->next);
    print(p);

    return 0;
}



问题描述

假设图用邻接表表示,设计一个算法,输出从顶点 $i$ 到顶点 $j$ 的所有简单路径

输入格式

第一行包含三个整数 $n$ , $m$ 和 $k$。

接下来 $m$ 行,每行包含两个整数 $x$ 和 $y$,表示存在一条从点 $x$ 到点 $y$ 的有向边 ($x$,$y$)。

接下来 $k$ 行,每行包含两个整数 $s$ 和 $t$,表示要求输出顶点 $s$ 到顶点 $t$ 的所有简单路径。

输入

6 8 3
1 2
1 3
2 4 
3 4
4 5
5 3
2 7
7 4
1 4
2 5
1 5

输出


1 -> 4 的所有简单路径:
1 3 4 
1 2 7 4 
1 2 4 

2 -> 5 的所有简单路径:
2 7 4 5 
2 4 5 

1 -> 5 的所有简单路径:
1 3 4 5 
1 2 7 4 5 
1 2 4 5 

c++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

int n, m, k;
bool st[N];
vector<int> path;

struct Node
{
    int id; // 编号
    int w;  // 权值
    Node* next;
    Node(int _id) : id(_id), next(NULL){}
} *head[N];     // 邻接表

void add(int a, int b)
{
    Node* p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

void dfs(int s, int t)
{
    if (s == t)
    {
        for (auto x : path) printf("%d ", x);
        puts("");
        return ;
    }

    for (auto p = head[s]; p; p = p->next)
    {
        int j = p->id;
        if (!st[j])
        {
            st[j] = true;
            path.push_back(j);
            dfs(j, t);
            path.pop_back();
            st[j] = false;
        }
    }
}


int main()
{
    cin >> n >> m >> k;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    while (k --)
    {
        int s, t;
        cin >> s >> t;
        printf("\n%d -> %d 的所有简单路径:\n", s, t);
        path.push_back(s);
        st[s] = true;
        dfs(s, t);  // 输出顶点s到顶点t的所有简单路径
        st[s] = false;
        path.pop_back();
    }

    return 0;
}



dfs

输入格式

第一行包含两个整数 $n$ 和 $m$。

接下来 $m$ 行,每行包含两个整数 $x$ 和 $y$,表示存在一条从点 $x$ 到点 $y$ 的无向边 ($x$,$y$)。

输入

5 4
1 2
1 3
1 4
3 5

输出

1 2 3 5 4 

c++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;

const int N = 510;

int n, m;
bool st[N];

struct Node
{
    int id; // 编号
    int w;  // 权值
    Node* next;
    Node(int _id) : id(_id), next(NULL){}
} *head[N];     // 邻接表

void add(int a, int b)
{
    Node* p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

void dfs(int u)
{
    stack<int> s;
    s.push(u);
    st[u] = true;

    while (!s.empty())
    {
        int t = s.top();
        s.pop();
        cout << t << ' ';

        for (auto p = head[t]; p; p = p->next)
        {
            int j = p->id;
            if (!st[j])
            {
                s.push(j);
                st[j] = true;
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    for (int i = 1; i <= n; i ++ )
        if (!st[i]) dfs(i);

    return 0;
}

bfs

输入

5 4
1 2
1 3
1 4
3 5

输出

1 4 3 2 5 

c++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 510, M = 100010, INF = 0x3f3f3f3f;

int n, m;
bool st[N];

struct Node
{
    int id; // 编号
    int w;  // 权值
    Node* next;
    Node(int _id) : id(_id), next(NULL){}
} *head[N];     // 邻接表

void add(int a, int b)
{
    Node* p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

void bfs(int u)
{
    queue<int> q;
    q.push(u);
    st[u] = true;

    while (q.size())
    {
        int t = q.front();
        q.pop();
        cout << t << ' ';

        for (auto p = head[t]; p; p = p->next)
        {
            int j = p->id;
            if (!st[j])
            {
                st[j] = true;
                q.push(j);
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    for (int i = 1; i <= n; i ++ )
        if (!st[i]) bfs(i);

    return 0;
}



#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

int n, m, d[N];
bool st[N];

struct Node
{
    int id; // 编号
    int w;  // 权值
    Node* next;
    Node(int _id) : id(_id), next(NULL){}
} *head[N];     // 邻接表

void add(int a, int b)
{
    Node* p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

void bfs()
{
    queue<int> q;
    q.push(1);
    d[1] = 0;
    st[1] = true;

    while (q.size())
    {
        int t = q.front();
        q.pop();
        // cout << t << ' ';

        for (auto p = head[t]; p; p = p->next)
        {
            int j = p->id;
            if (!st[j])
            {
                st[j] = true;
                q.push(j);
                d[j] = d[t] + 1;
            }
        }
    }
}

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

    bfs();

    printf("%d\n", d[n]);

    return 0;
}



代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        TreeNode* now = root;
        while (now || !stk.empty())
        {
            while (now) // 一直向左并将沿途结点压入堆栈
            {
                stk.push(now);
                now = now->left;
            }
            if (!stk.empty())   // 每次取出栈顶,访问它,然后再访问其右子树
            {
                now = stk.top();
                stk.pop();
                res.push_back(now->val);
                now = now->right;
            }
        }
        return res;
    }
};



代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) return res;
        stack<TreeNode*> stk;
        stk.push(root);
        while (stk.size())
        {
            auto t = stk.top();
            stk.pop();
            res.push_back(t->val);
            if (t->right) stk.push(t->right);
            if (t->left) stk.push(t->left);
        }
        return res;
    }
};



迭代

解题思路

由于镜像二叉树的先序遍历=原二叉树的后序遍历,
所以可以先求出镜像先序,最后reverse即可。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> res;
        if (!root) return res;
        stk.push(root);
        while (!stk.empty())
        {
            TreeNode* t = stk.top();
            stk.pop();
            res.push_back(t->val);
            if (t->left) stk.push(t->left);
            if (t->right) stk.push(t->right);
        } 
        reverse(res.begin(), res.end());
        return res;
    }
};

递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> res;

    void dfs(TreeNode* root)
    {
        if (!root) return ;
        dfs(root->left);
        dfs(root->right);
        res.push_back(root->val);
    }

    vector<int> postorderTraversal(TreeNode* root) {
        dfs(root);
        return res;
    }
};



解题思路

【并查集判断图中是否存在环】合并之前如果两个点已经在一个集合里,那么合并之后就必然会形成环。

输入格式

第一行包含两个整数 $n$ 和 $m$。

接下来 $m$ 行,每行包含两个整数 $x$ 和 $y$,表示存在一条从点 $x$ 到点 $y$ 的无向边 ($x$,$y$)。

输入

3 3
1 2
2 3
1 3

输出

有环!

c++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int p[N], n, m;

int find(int x)
{
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) p[i] = i;

    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        a = find(a), b = find(b);
        if (a != b) p[a] = b;
        else 
        {
            puts("有环!");
            return 0;
        }
    }

    puts("无环!");
    return 0;    
}