头像

snkz5qing

安安静静学算法




离线:2小时前


最近来访(71)
用户头像
_N
用户头像
L_H_R
用户头像
owwkmidream
用户头像
林大B
用户头像
Kijasss
用户头像
21KINGDMG
用户头像
Tingting
用户头像
flzj_kl
用户头像
TianCai123
用户头像
BlackSheep
用户头像
该用户被封禁
用户头像
CodingKirby8620
用户头像
封禁用户
用户头像
cyb-包子
用户头像
理想世界
用户头像
学一年考研去了
用户头像
Sopher
用户头像
.May.
用户头像
Peter_5
用户头像
停笔醉书情


snkz5qing
2小时前

1212地宫取宝

https://www.acwing.com/problem/content/1214/
其中之一题解:手把手教你dp
https://www.acwing.com/solution/content/34645/

ε≡٩(๑>₃<)۶



活动打卡代码 AcWing 846. 树的重心

snkz5qing
5小时前

这题目有点难,需要多看几遍
节点的总数n-size4(叶子结点的数量)
2.png

//需要手动模拟
//我们这个搜索是搜索的图当中节点的编号,而不是边,idx存的是边?????
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 101000,M=N*2;//这里为什么要乘以2?要开最大的数组为什么要乘以2

//请问一下,在树的重心这题里,e[M],ne[M],为什么写成e[N],ne[N]就错了?要开两倍大小嘛?
//yxc:因为是无向图,所有给定的边都需要建立两条方向不同的边。
int ans=N;//记录一下全局的答案,全局的点存的是最大值,肯定超不过数据范围
int n;
int h[N],e[M],ne[M],idx;
bool st[N];
//在a,b之间插入一条新的边
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
    idx++;
}
//以u为根的子树中点的数量
int dfs(int u)
{
    st[u]=true;//标记一下,已经被搜过了

    //记录一下当前点的子树的大小,当前点算一????、
    int sum=1,res=0;//res存的是每一个联通块里面的最大值,





    for (int i = h[u]; i!=-1; i=ne[i] )
    {
        int j=e[i];
        if(!st[j]) 
        {
        int s=dfs(j);//,用s表示当前子树的大小,不需要恢复现场,
        //当前子树也算是一个连通快,所以和res取max,

        res=max(res,s);
         //sum=+s??
         sum+=s;
        }    
    }


    //n-sum是该节点子树以外的连通块的大小
    res=max(res,n-sum);


    ans=min(ans,res);
    return sum;
}
int main()
{
    cin >> n;
     memset(h,-1,sizeof h); //将头结点全部指向为负一,即给数组所在的值为负一,   


      for (int i = 0; i <n-1; i ++ )
      {
          int a,b;
          cin >> a>>b;
          add(a, b),add(b,a);//添加两条无向边
      }


      //dfs(1);//这里以哪个点搜都是一样的,为n也可以,为2也可以
      dfs(2);


    cout << ans<<endl;
    return 0;
}





活动打卡代码 LeetCode 1. 两数之和

y总:时间比空间更紧张一些,先来考虑O(n)的情况,最主要考虑时间复杂度,在时间复杂度最低的情况下,再考虑空间复杂度,因为时间复杂度比较紧张一些
pair也行,也可以用哈希表来做,c里面的map底层是平衡树是nlogn
使用C
中的哈希表——unordered_map[HTML_REMOVED] hash,时间复杂度是o(1)的

//暴力做法:
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
            vector<int> ans;
        for (int i = 0; i < nums.size(); i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[i] + nums[j] == target)
                {
                    ans = vector<int>({j, i});
                    break;
                }
            }
            if (ans.size() > 0) break;
        }
        return ans;
    }
};

第二种

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        vector<int> res;
        unordered_map<int,int> hash;
        for (int i = 0; i < nums.size(); i ++ )
        {
            int another = target - nums[i];
            if (hash.count(another))
            {
                res = vector<int>({hash[another], i});
                break;
            }
            hash[nums[i]] = i;
        }
        return res;
    }
};
作者:yxc
链接:https://www.acwing.com/solution/content/47/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。






snkz5qing
11天前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int main(){

 queue<int> q;//定义⼀个空队列q
 for(int i=0;i<10;i++)
 {

  q.push(i);//将i的值压入queue中
}
    for(int i=1;i<4;i++)
    q.pop();//弹出队首元素
// 访问队列的队⾸元素和队尾元素
cout<<q.front()<<endl;

cout<<q.back()<<endl;

cout<<q.size()<<endl;// 输出队列的元素个数


    return 0;
}



snkz5qing
12天前



snkz5qing
12天前

将数据结构转化为图形去理解比较好:
找到了一篇转换为图像的大佬的题解
转载:

https://www.acwing.com/blog/content/4934/



活动打卡代码 AcWing 844. 走迷宫

snkz5qing
12天前
#include <iostream>
#include <cstring>//使用memset()需要用到的头文件
#include <algorithm>

using namespace std;

const int N = 110;

//typedef pair<int, int> PII;//这个类型里面有两个元素,二元组


int n,m;
int g[N][N];//存储地图
int d[N][N];//记录每个顶点到源点的距离,存储距离
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
pair<int, int> q[N*N];//开的数组大一点,别越界了。如果只写N的话会出错,所以要开大一点
//PII Pre[N][N];
int bfs()
{
    //手写队列
    int hh=0,tt=0;
    q[0]={0,0};//数组队列里面有中第一个数组存的元素有两个,而一般的只能存一个。
    memset(d,-1, sizeof d);//初始化各个点到源点的距离为-1
    d[0][0]=0;//int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};//偏移量

    while(hh<=tt)//队列不为空
    {
        pair<int, int> t=q[hh++];
        //分别向四个方向扩展
        for (int i = 0; i<4; i ++ )
        {//x表示沿着这个方向走的话,会走到哪一点,
           int x=t.first+dx[i],y=t.second+dy[i];

        //x在边界内,并且没有走过,没有用过
         //首先(x,y)不能越界, 然后g[x][y] == 0说明可以走(g[x][y] == 1说明是障碍物)
            //最后是只更新未被访问的点到源点的距离 (要求d[x][y] == -1)    
            if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1)//;这可恶的分号,让我看了半天。
            {
                //说明已经用过了
                d[x][y]=d[t.first][t.second]+1;////代表的是里面的值加1,//更新未被访问的点到源点的距离
                // Pre[x][y]=t;
                q[++tt]={x,y};//这里别忘了写扩展的坐标x,y(x,y)进队
            }
        }   
    }


     //  int x=n-1,y=m-1;
    // while(x||y)
    // {
    //      cout << x<<' '<<y<<endl;
    //      auto t=Pre[x][y];
    //      x=t.first,y=t.second;
    // }
    return d[n-1][m-1];//返回右下角元素到源点的距离,从0开始
}

int main()
{
    cin >> n>>m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
             cin >> g[i][j];
    cout << bfs()<<endl;
    return 0;
}

stl中队列的写法

#include <iostream>
#include <cstring>
#include <algorithm>
#include<queue>//练习队列的用法
using namespace std;
const int N = 110;
typedef pair<int, int> PII;//这个类型里面有两个元素,二元组,给此类型起了个别名

int n,m;
int g[N][N];//存储地图
int d[N][N];//记录每个顶点到源点的距离,存储距离
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
//开的数组大一点,别越界了。

int bfs()
{
    ////数组队列里面有中第一个数组存的元素有两个,而一般的只能存一个。
    queue<PII> q;//定义一个pair(双元组)类型的队列
    memset(d,-1, sizeof d);//初始化各个点到源点的距离为-1
    d[0][0]=0;//int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};//偏移量
    q.push({0,0});//将第一个元素从队尾插入
    while(!q.empty())//队列不为空
    {
        auto t=q.front();//返回对头元素,back()是队尾元素
             q.pop();//将队头元素弹出
        for (int i = 0; i<4; i ++ )
        {//x表示沿着这个方向走的话,会走到哪一点,
           int x=t.first+dx[i],y=t.second+dy[i];//first ,second是pair类型的函数
        //x在边界内,并且没有走过,没有用过,是可以走的,并且没有计算与原点的距离
            if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1)
            {
                d[x][y]=d[t.first][t.second]+1;
                q.push({x,y});//将可行的点,插入队尾
            }
        }   
    }
    return d[n-1][m-1];
}

int main()
{
    cin >> n>>m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
             cin >> g[i][j];
    cout << bfs()<<endl;
    return 0;
}

深搜的写法:
摘自抽风大佬
迷宫深搜.png

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

int a[110][110], dist[110][110];
int Next[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int Min = 99999999;
int p, q, n, m;

void dfs(int x, int y)
{
    //reach the destination
    if(x == p && y == q) return ;

    int i, tx, ty;   
    for(i = 0; i <= 3; i++)
    {
        tx = x + Next[i][0];
        ty = y + Next[i][1];

        if(tx < 1 || tx > n || ty < 1 || ty > m)
            continue;

        if(!a[tx][ty] && dist[tx][ty] > dist[x][y] + 1)
        {
            dist[tx][ty] = dist[x][y] + 1;
            dfs(tx, ty);
        }
    }

    return;
}

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

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> a[i][j];

    //the position of destination
    p = n, q = m;

    memset(dist, 0x3f, sizeof dist);
    dist[1][1] = 0;
    dfs(1, 1);

    cout << dist[n][m] << endl;

    return 0;
}

dfs(写法)

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

using namespace std;

int n, m;

const int N = 110;

int g[N][N];
int ans = N * N;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int st[N][N];

void dfs(int x, int y, int cnt)
{
    if(cnt > ans) return;
    if(x == n - 1 && y == m - 1)
    {
        ans = cnt;
        return;
    }

    for(int i = 0; i < 4; i ++)
    {
        int newX = x + dx[i];
        int newY = y + dy[i];
        if(newX >= 0 && newY >= 0 && newX < n && newY < m && g[newX][newY] == 0 && st[newX][newY] > st[x][y] + 1)
        {
            st[newX][newY] = st[x][y] + 1;
            dfs(newX, newY, cnt + 1);
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            scanf("%d", &g[i][j]);

    memset(st, 0x3f, sizeof st);
    st[0][0] = 0;
    dfs(0, 0, 0);
    cout << ans << endl;
    return 0;
}

作者:Mered1th
链接:https://www.acwing.com/solution/content/11686/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


分享 stl

snkz5qing
12天前

stl.png