数据结构算法刷题

• 一些小技巧

1. vector当数组用

   vector<int> v(n + 1);
   scanf("%d", &v[j]);

1051 Pop Sequence

思路：重新模拟题目

#include <stdio.h>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
const int N = 1010;

int main (int argc, char *argv[])
{
    int n, m, k;
    vector<int> v(n + 1);
    // int arr[N];
    scanf("%d%d%d", &n, &m, &k);
    int value;
    for (int i = 0; i < k; i++) {
        stack<int> st;
        for (int j = 0; j < m; j++) {
            scanf("%d", &v[j]);
        }
        int Index = 0;
        bool flag = true;
        for (int j = 1; j <= m; j++) {
            st.push(j);
            if (st.size() > n) {
                flag = false;
                break;
            }
            while (!st.empty() && st.top() == v[Index]) {
                Index++;
                st.pop();
            }
        }
        if (flag && Index == m) {
            printf("YES\n");
        }
        else {
            printf("NO\n");
        }
    }
    return 0;
}

注意stack要在每次循环内重新初始化，不然栈中会存在之前的数据，vector也要重新初始化，每次push_back不会使数组保存在1-m。

1074 Reversing Link list

思路:将地址加入一个vector中，使用reverse函数将地址进行翻转即可。

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 10;

struct node {
    int data;
    int next;
}Node[N];


int main (int argc, char *argv[])
{
    int start, n, k;
    scanf("%d %d %d", &start, &n, &k);
    int add, data, next;
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", &add, &data, &next);
        Node[add].data = data;
        Node[add].next = next;
    }
    vector<int> v;
    int x = start;
    int num = 0;
    for (int i = 0; i < n; i++) {
        if (x == -1) {
            break;
        }
        v.push_back(x);
        x = Node[x].next;
        num++;
    }
    for (int i = 0; i < num / k; i++) {
        reverse(v.begin() + i * k, v.begin() + i * k + k);
    }
    for (int i = 0; i < num - 1; i++) {
        printf("%05d %d %05d\n", v[i], Node[v[i]].data, v[i+1]);
    }
    printf("%05d %d -1\n", v[num - 1], Node[v[num - 1]].data);
    return 0;
}

1032 Sharing

思路：开始的时候是判断字符相不相同，发现字符可能重复，因此只要判断地址有没有相同就可以解决问题了，为避免双重循环，用一个isAppear数组记录地址有无出现。

#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;

struct node {
    char a;
    int next;
}Node[N];

bool isAppear[N];
int main (int argc, char *argv[])
{
    fill(isAppear, isAppear + N, false);
    int query1, query2, n;
    scanf("%d%d%d", &query1, &query2, &n);
    int add, ne;
    char c;
    for (int i = 0; i < n; i++) {
        scanf("%d %c %d", &add, &c, &ne);
        Node[add].a = c;
        Node[add].next = ne;
    }
    while (query1 != -1) {
        isAppear[query1] = true;
        query1 = Node[query1].next;
    }
    while (query2 != -1) {
        if (isAppear[query2]) {
            printf("%05d\n", query2);
            return 0;
        }
        query2 = Node[query2].next;
    }
    printf("-1\n");
    return 0;
}

注意：地址5位补全。

1052 Linked list sort

思路：从起始路径出发将所有节点加入vector中，最后用一个sort排序，从小到大输出。

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 10;

struct node {
    int add;
    int key;
    int next;
}Node[N];

bool cmp(node a, node b){
    return a.key < b.key;
}
vector<node> v;
int main (int argc, char *argv[])
{
    int n, st;
    scanf("%d %d", &n, &st);
    int cur, key, next;
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", &cur, &key, &next);
        Node[cur].add = cur;
        Node[cur].key = key;
        Node[cur].next = next;
    }
    int temp = st;
    while (temp != -1) {
        v.push_back(Node[temp]);
        temp = Node[temp].next;
    }
    sort(v.begin(), v.end(), cmp);
    if (v.size() == 0) {
        printf("0 -1\n");
    }
    else {
        printf("%lu %05d\n", v.size(), v[0].add);
        for (int i = 0; i < v.size() - 1; i++) {
            printf("%05d %d %05d\n", v[i].add, v[i].key, v[i+1].add);
        }
        printf("%05d %d -1\n", v[v.size()-1].add, v[v.size()-1].key);
    }
    return 0;
}

注意：并不是所有节点都有用到，以及考虑所有都是脏数据的情况，起始地址为-1。

Deduplication on a Linked List

思路：开两个数组即可，用一个flag来判断是否重复了。

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
const int N = 1e5 + 10;
const int K = 1e4 + 10;

struct node {
    int add;
    int key;
    int next;
}Node[N];

bool flag[N];
vector<int> v;
vector<int> re;

int main (int argc, char *argv[])
{
    fill(flag, flag + K, false);
    int n;
    int start;
    scanf("%d %d", &start, &n);
    int now, key, next;
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &now, &key, &next);
        Node[now].add = now;
        Node[now].key = key;
        Node[now].next = next;
    }
    int temp = start;
    while (temp != -1) {
        if (flag[abs(Node[temp].key)] == true) {
            re.push_back(temp);
        }
        else {
            v.push_back(temp);
            flag[abs(Node[temp].key)] = true;
        }
        temp = Node[temp].next;
    }
    for (int i = 0; i < v.size() - 1; i++) {
        printf("%05d %d %05d\n", Node[v[i]].add, Node[v[i]].key, Node[v[i+1]].add);
    }
    printf("%05d %d -1\n", Node[v[v.size()-1]].add, Node[v[v.size()-1]].key);
    if (re.size() == 0) {
        return 0;
    }
    for (int i = 0; i < re.size() - 1; i++) {
        printf("%05d %d %05d\n", Node[re[i]].add, Node[re[i]].key, Node[re[i+1]].add);
    }
    printf("%05d %d -1\n", Node[re[re.size()-1]].add, Node[re[re.size()-1]].key);
    return 0;
}

注意：re数组里可能没有值，要判断size大小。

赏

谢谢你请我吃糖果

支付宝