头像

科宇

acwing




离线:8小时前


活动打卡代码 LeetCode 200. 岛屿数量

科宇
2天前
typedef pair<int,int> PII;
#define x first
#define y second

class Solution {
public:
    vector<vector<char>> g;
    int n,m;
    vector<vector<bool>> st;
    int numIslands(vector<vector<char>>& grid) {
        g=grid;
        n=grid.size();
        m=grid[0].size();
        int cnt=0;
        vector<vector<bool>> st1(n+1,vector<bool>(m+1, false));
        st=st1;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(grid[i][j]=='1'&&!st[i][j]){
                    bfs(i,j);
                    cnt++;
                }
        return cnt;
    }

    void bfs(int x,int y){
        queue<PII> q;
        q.push({x,y});
        int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
        st[x][y]=true;
        while(q.size()){
            auto t=q.front();
            q.pop();
            for(int i=0;i<4;i++){
                int a=t.x+dx[i],b=t.y+dy[i];
                if(a<0||a>=n||b<0||b>=m||g[a][b]=='0'||st[a][b]) continue;
                q.push({a,b});
                st[a][b]=true;
            }
        }
    }
};


活动打卡代码 LeetCode 189. 旋转数组

科宇
2天前
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int sz=nums.size();
        vector<int> res(sz,0);
        for(int i=0;i<sz;i++){
            res[(i+k)%sz]=nums[i];
        }
        nums=res;
    }
};



科宇
4天前
class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        vector<int> ji,ou,res;
        for(int i:nums){
            if(i%2==0){
                ou.push_back(i);
            }else{
                ji.push_back(i);
            }
        }
        for(int i=0;i<ou.size();i++){
            res.push_back(ou[i]);
            res.push_back(ji[i]);
        }
        return res;
    }
};



科宇
4天前
class Solution {
public:
    int minAddToMakeValid(string s) {
        stack<char> stk;
        int cnt=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='(') stk.push(s[i]);
            else{
                if(stk.size()&&stk.top()=='('&&s[i]==')') {
                    stk.pop();
                }
                else ++cnt;
            }
        }
        return cnt + stk.size();
    }
};


活动打卡代码 AcWing 1498. 最深的根

科宇
6天前
#include <bits/stdc++.h>
using namespace std;

const int N=10010, M=N*2;
int n;
int h[N],e[M],ne[M],idx;
int p[N];
int maxdepth=0;

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

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

int dfs(int u,int father){
    int depth=0;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==father) continue;
        depth= max(depth,dfs(j,u)+1);
    }

    return depth;
}

int main(){
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)p[i]=i;
    int k=n;
    for(int i=0;i<n-1;i++){
        int a,b;
        scanf("%d%d",&a,&b);

        if(find(a)!=find(b)){
            k--;
            p[find(a)]=find(b);
        }
        add(a,b),add(b,a);
    }
    vector<int> nodes;
    if(k>1) printf("Error: %d components",k);
    else{
        for(int i=1;i<=n;i++){
            int depth=dfs(i,-1);
            if(depth>maxdepth){
                maxdepth=depth;
                nodes.clear();
                nodes.push_back(i);
            }
            else if(depth==maxdepth)
                nodes.push_back(i);
        }
        for(int i=0;i<nodes.size();i++)
            printf("%d\n",nodes[i]);
    }
    return 0;
}


活动打卡代码 AcWing 796. 子矩阵的和

科宇
6天前
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,Q;
int s[N][N];

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

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            s[i][j]=s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    while(Q--){
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        printf("%d\n",s[l2][r2]-s[l1-1][r2]-s[l2][r1-1]+s[l1-1][r1-1]);
    }
    return 0;
}



活动打卡代码 AcWing 795. 前缀和

科宇
6天前
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N],s[N];
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) {
        s[i] = s[i-1]+a[i];
    }
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n", s[r]-s[l-1]);
    }
    return 0;
}



活动打卡代码 AcWing 1242. 修改数组

科宇
6天前
// 巧妙的并查集
#include <bits/stdc++.h>
using namespace std;

const int N=1100010;

int p[N];

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

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<N;i++)p[i]=i;
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        x=find(x);
        printf("%d ", x);
        p[x]=x+1;
    }
    return 0;
}
//暴力过7个点
#include <bits/stdc++.h>
using namespace std;

unordered_map<int,int> pq;
vector<int> res;
int maxv=INT_MIN;

int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int x;
        scanf("%d",&x);
        while(pq.count(x)){
            x++;
        }
        pq[x]++;
        res.push_back(x);
    }

    printf("%d",res[0]);
    for(int i=1;i<res.size();i++){
        printf(" %d",res[i]);
    }
    return 0;
}


活动打卡代码 AcWing 1497. 树的遍历

科宇
6天前
#include <bits/stdc++.h>
using namespace std;
const int N=40;
int n;
int postorder[N],inorder[N];
unordered_map<int,int> l,r,pos;
int q[N];

int build(int il,int ir,int pl,int pr){
    int root=postorder[pr];
    int pivot=pos[root];
    if(il<pivot) l[root]=build(il,pivot-1,pl,pl+pivot-1-il);
    if(pivot<ir) r[root]=build(pivot+1,ir,pl+pivot-1-il+1,pr-1);
    return root;
}

void bfs(int u){
    int hh=0,tt=0;
    q[0]=u;
    while(hh<=tt){
        int t=q[hh++];
        if(l.count(t)) q[++tt]=l[t];
        if(r.count(t)) q[++tt]=r[t];
    }
    cout<<q[0];
    for(int i=1;i<n;i++) cout<<' '<<q[i];
    cout<<endl;
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>postorder[i];
    for(int i=0;i<n;i++){
        cin>>inorder[i];
        pos[inorder[i]]=i;
    }

    int root= build(0,n-1,0,n-1);
    bfs(root);
    return 0;
}


活动打卡代码 AcWing 790. 数的三次方根

科宇
6天前
#include <bits/stdc++.h>
using namespace std;

int main(){
    double n;
    cin>>n;
    double l=-10000,r=10000;
    while(r-l>1e-8){
        double mid=(l+r)/2;
        if(mid*mid*mid>=n) r=mid;
        else l=mid;
    }
    printf("%lf",l);
    return 0;
}