头像

哥德巴赫




离线:5小时前


最近来访(65)
用户头像
Zzzzzzzzzz
用户头像
织葉
用户头像
Amaryllis_
用户头像
小张睡不醒
用户头像
胡尔摩斯
用户头像
zww
用户头像
三零种子选手
用户头像
champagne
用户头像
elgir
用户头像
heavens.
用户头像
ㅤㅤㅤㅤ_1
用户头像
辣鸡号航母
用户头像
tyjz_yyds
用户头像
长夜难明
用户头像
0_94
用户头像
lindi530
用户头像
gulu_sy
用户头像
jion0.0
用户头像
Twinkling
用户头像
学得会学得会


//1.头文件
#include <stack>

//2.声明
stack<int> s;       //声明栈内元素都是int类型一个栈s

//3.操作
s.push(1);      //在栈s顶插入元素1
s.pop();        //删除栈s的顶部元素
s.top();        //获取栈顶元素的值
s.size();       //求栈的大小
s.empty();      //判断栈是否为空

队列

//1.头文件
#include <queue>

//2.声明
queue<int> q;       //声明队列内元素都是int类型一个队列q

//3.操作
q.push(1);      //在队尾顶插入元素1
q.pop();        //删除队尾元素
q.front();      //获取队头元素的值
q.back();       //获取队尾元素的值
q.size();       //求队列大小
q.empty();      //判断队列是否为空

优先队列

//1.头文件
#include <queue>

//2.声明--默认为大顶堆
priority_queue<int> q;                  //默认大顶堆
priority_queue<int, vector<int>, greater<int> > q;  //指定堆的类型为小顶堆
priority_queue<int, vector<int>, less<int> > q;     //指定堆的类型为大顶堆

//3.操作
q.push(1);      //在堆内插入元素1且仍保持堆的结构
q.pop();        //弹出堆顶元素
q.top();        //获取堆顶元素的值

pair

//1.头文件
#include <utility>

//2.声明
pair<string, int> p;        //声明第一个元素为string类型,第二个元素为int型的对

//3.操作
p.first;            //访问p的第1个元素
p.second;           //访问p的第2个元素

//pair支持比较操作,默认以first为第一关键字,second为第二关键字

vector容器

//1.头文件
#include <vector>

//2.声明
vector<int> vec;        //声明元素int型vector对象,该对象大小为0,容器内无任何元素
vector<int> vec(100);       //声明含有100个元素,初值为0的int型vector对象
vector<int> vec(100,2);     //声明含有100个元素,初值为2的int型vector对象

//3.操作
vec.push_back(1);           //在向量vec末尾插入元素1
vec.insert(vec.begin()+i,1);        //在第i个元素后面插入1(在下标为i的地方插入1,剩余元素后移)
vec.erase(vec.begin()+2);       //删除第三个元素(删除下标为2的元素)
vec.erase(vec.begin()+i,vec.begin()+j); //删除下标i~j的元素
vec.size();             //求向量大小
vec.clear();                //清空向量

//4.访问vector中的元素
vec[i];                 //使用下标访问元素(同数组)

//使用迭代器访问vector中的元素
vector<int>::iterator it;
for(it=vec.begin();it!=vec.end();it++)
    cout<<*it<<endl;`

注:vector中的元素是结构体时,要将结构体定义为全局的,否则会出错。

map

map的本质是一棵红黑树

//1.头文件
#include <map>

//2.声明
map<string, int> m;     //声明关键字为string型,对应的值int型的对

//3.操作
m["aaa"]=1;         //字符串"aaa"的值为1

unordered_map

unordered_map的本质是哈希表

//1.头文件
#include <unordered_map>

//2.声明
unordered_map<string, int> m;       //声明关键字为string型,对应的值int型的对

//3.操作
m["aaa"]=1;         //字符串"aaa"的值为1
m.count("aaa");         //查询m中是否存在值为“aaa”的元素

字符串string

//1.头文件
#include <string>

//2.声明
string str;         //声明一个字符串str

//3.操作
str.insert(2,"abc");        //在下标为2的位置之前插入"abc"
str.erase(2);           //删除从下标2开始的之后的所有元素
str.erase(2,1);         //删除下标从2开始的一个的元素
str.find('A');          //从头查找字符'A',返回'A'在str中首次成功的位置,若失败,则返回-1

其它常用辅助函数

//头文件
#include <algorithm>

//1.sort排序
sort(a.begin(), a.end());

//2.reverse翻转数组
reverse(a.begin(), a.end());

//头文件
#include <cstring>

//3.memset数组初始化函数,将某一块内存全部填充为指定的值
memset(f, -1, sizeof(f));


活动打卡代码 AcWing 38. 二叉树的镜像

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if (!root) return root;
        swap(root->left, root->right);
        mirrorTree(root->left);
        mirrorTree(root->right);
        return root;
    }
};


活动打卡代码 AcWing 39. 对称的二叉树

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return dfs(root->left, root->right);
    }

    bool dfs(TreeNode* root1, TreeNode* root2) {
        if (!root1 && !root2) return true;
        if (!root1 || !root2 || root1->val != root2->val) return false;
        return dfs(root1->left, root2->right) && dfs(root1->right, root2->left);
    }
};


活动打卡代码 AcWing 25. 剪绳子

class Solution {
public:
    int cuttingRope(int n) {
        if (n <= 3) return (n - 1) * 1;
        int res = 1;
        if (n % 3 == 1) res *= 4, n -= 4;
        if (n % 3 == 2) res *= 2, n -= 2;
        while (n) res *= 3, n -= 3;
        return res;
    }
};



class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        nums.push_back(0);
        int n = nums.size();
        for (int i = 0; i < n; i ++ )
            while (nums[i] >= 0 && nums[i] < n && nums[i] != i && nums[i] != nums[nums[i]])
                swap(nums[i], nums[nums[i]]);
        for (int i = 1; i < n; i ++ )
            if (nums[i] != i) return i;
        return n;
    }
};


活动打卡代码 LeetCode 42. 接雨水

class Solution {
public:
    int trap(vector<int>& height) {
        int res = 0;
        stack<int> stk;
        for (int i = 0; i < height.size(); i ++ ) { // 遍历每个元素
            int last = 0; // 上一个柱子的高度
            while (stk.size() && height[stk.top()] <= height[i]) {
                res += (height[stk.top()] - last) * (i - stk.top() - 1);
                last = height[stk.top()];
                stk.pop();
            }
            if (stk.size()) res += (height[i] - last) * (i - stk.top() - 1);
            stk.push(i);
        }
        return res;
    }
};


活动打卡代码 AcWing 456. 车站分级

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

using namespace std;

const int N = 2010, M = 1e6 + 10;

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

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

void topsort()
{
    int ll = 0, rr = -1;
    for (int i = 1; i <= n + m; i ++ )
        if (!d[i]) q[++ rr] = i;

    while (ll <= rr)
    {
        int t = q[ll ++ ];
        for (int j = h[t]; ~j; j = ne[j])
        {
            int x = e[j];
            d[x] --;
            if (!d[x]) q[++ rr] = x;
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ )
    {
        int cnt;
        cin >> cnt;
        memset(st, 0, sizeof st);
        int start = n, end = 1; // 记录从哪个站走到哪个站(因为题目说从首到尾中间的这些站点要符合要求,其余点不规定)
        while (cnt -- )
        {
            int stop;
            cin >> stop;
            start = min(start, stop);
            end = max(end, stop);
            st[stop] = true;
        }

        int ver = n + i; // 用一个不包含在原来点内部的点且能够有标识的点记录中间分割点
        for (int j = start; j <= end; j ++ )
            if (st[j]) add(ver, j, 1);
            else add(j, ver, 0);
    }

    topsort();

    for (int i = 1; i <= n; i ++ ) dist[i] = 1;
    for (int i = 0; i < n + m; i ++ )
        for (int j = h[q[i]]; ~j; j = ne[j]) // 有一点迪杰斯特拉的思想在里面
        {
            int x = e[j];
            dist[x] = max(dist[x], dist[q[i]] + w[j]);
        }

    int res = 1;
    for (int i = 1; i <= n; i ++ ) res = max(res, dist[i]);
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 164. 可达性统计

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

using namespace std;

const int N = 30010;

int n, m;
int d[N], q[N];
int h[N], e[N], ne[N], idx;
bitset<N> f[N];

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

void topsort()
{
    int ll = 0, rr = -1;
    for (int i = 1; i <= n; i ++ )
        if (!d[i]) q[ ++ rr] = i;

    while (ll <= rr)
    {
        int t = q[ll ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            d[j] -- ;
            if (!d[j]) q[ ++ rr] = j;
        }
    }
}

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

    topsort();

    for (int i = n - 1; i >= 0; i -- )
    {
        int j = q[i];
        f[j][j] = 1;
        for (int k = h[j]; ~k; k = ne[k])
            f[j] |= f[e[k]];
    }

    for (int i = 1; i <= n; i ++ ) cout << f[i].count() << endl;
    return 0;
}


活动打卡代码 AcWing 1192. 奖金

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

using namespace std;

const int N = 10010, M = 20010;

int n, m;
int d[N], q[N], dist[N];
int h[N], e[M], ne[M], idx;

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

bool topsort()
{
    int ll = 0, rr = -1;
    for (int i = 1; i <= n; i ++ )
        if (!d[i]) q[++ rr] = i;

    while (ll <= rr)
    {
        int t = q[ll ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            d[j] --;
            if (!d[j]) q[++ rr] = j;
        }
    }
    if (rr < n - 1) return false;
    return true;
}

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

    if (!topsort()) cout << "Poor Xed" << endl;
    else 
    {
        for (int i = 1; i <= n; i ++ ) dist[i] = 100;

        for (int i = 0; i < n; i ++ )
        {
            int j = q[i];
            for (int k = h[j]; ~k; k = ne[k])
            {
                int x = e[k];
                dist[x] = max(dist[x], dist[j] + 1);
            }
        }

        int res = 0;
        for (int i = 1; i <= n; i ++ ) res += dist[i];
        cout << res << endl;
    }

    return 0;
}


活动打卡代码 AcWing 1191. 家谱树

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

using namespace std;

const int N = 110, M = N * N / 2;

int n;
int q[N], d[N];
int h[N], e[M], ne[M], idx;

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

void topsort()
{
    int ll = 0, rr = -1;
    for (int i = 1; i <= n; i ++ )
        if (!d[i]) q[ ++ rr] = i;

    while (ll <= rr)
    {
        int u = q[ll ++ ];
        for (int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            d[j] --;
            if (!d[j]) q[ ++ rr] = j;
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        int son;
        while (cin >> son, son)
        {
            add(i, son);
            d[son] ++;
        }
    }

    topsort();

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