头像

萌萌


访客:867

离线:1天前



萌萌
7天前

一个算法题,要求先输入一个int类型的T,表示接下来有T行数据,然后每行输入一个字符串,但这个字符串没有说明长度,且有空格,这样的输入要怎么输入了?
string str;
如果用cin>>str;这样来进行输入,就不能把空格输入进来
如果用getline(cin,str);这样来进行输入,就会影响到前面的输入cin>>T,
所以有没有更好的输入方式?



活动打卡代码 AcWing 783. 括号序列

萌萌
8个月前
/*
合法括号序列:前缀和>=0,且最后前缀和为0
*/
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

const int mod=1e9+7;
vector<int> as,bs;

//求前缀和
void get_preix_sum(string &str,vector<int> &sum){
    for(int i=0;i<str.size();i++){
        if(str[i]=='(') sum[i+1]=sum[i]+1;
        else sum[i+1]=sum[i]-1;
    }
}

int main(){
    string str1,str2;
    cin>>str1;
    cin>>str2;

    int n=str1.size(),m=str2.size();
    as=vector<int>(n+1),bs=vector<int>(m+1);
    get_preix_sum(str1,as);
    get_preix_sum(str2,bs);

    vector<vector<int>> f(n+1,vector<int>(m+1));//状态表示:f[i][j]表示str1的前i个字母和
                                                //str2的前j个字母组合能有多少种方式
    if(as[n]+bs[m]!=0) cout<<0<<endl; //若前缀和不为0,则不能组成合法括号序列
    else{
        for(int i=0;i<=n;i++){
            for(int j=0;j<=m;j++){
                if(!i&&!j) f[i][j]=1;//空串为合法的
                else{
                    if(as[i]+bs[j]>=0){//当前缀和>=0时才行
                        if(i) f[i][j]+=f[i-1][j];
                        if(j) f[i][j]+=f[i][j-1];
                        f[i][j]%=mod;
                    }
                }
            }
        }
        cout<<f[n][m]<<endl;
    }


    return 0;
}


活动打卡代码 AcWing 756. 蛇形矩阵

萌萌
8个月前
#include<iostream>
#include<vector>

using namespace std;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> f(n,vector<int>(m));
    vector<vector<bool>> st(n,vector<bool>(m));

    int x=0,y=0,d=1;
    for(int i=0;i<n*m;i++){
        f[x][y]=i+1;
        st[x][y]=true;
        int nexx=x+dx[d],nexy=y+dy[d];
        if(nexx>=0&&nexx<n&&nexy>=0&&nexy<m&&!st[nexx][nexy]) x=nexx,y=nexy;
        else {
            d=(d+1)%4;
            nexx=x+dx[d],nexy=y+dy[d];
            x=nexx,y=nexy;
        }
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
        {
            cout<<f[i][j]<<" ";
        }
        cout<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 780. 爱健身的小王

萌萌
8个月前
#include<iostream>

using namespace std;

int main(){
    int t;
    cin>>t;
    while(t--){
        int a;
        cin>>a;
        if(a%4==0||a%4==2) cout<<a*4+1<<endl;
        else if(a%4==1) cout<<a*2+1<<endl;
        else cout<<a+1<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 781. 趣味字母卡片

萌萌
8个月前
#include<iostream>
#include<algorithm>
#include<unordered_set>

using namespace std;

int main(){
    string str;
    cin>>str;
    for(auto &c:str) c=tolower(c);

    for(char c='a';c<='z';c++){
        int k=0;
        while(k<str.size()&&str[k]!=c) k++;
        unordered_set<char> hash;
        for(int i=k+1;i<str.size();i++) hash.insert(str[i]);

        bool can=true;
        for(int i=0;i<k;i++){
            if(!hash.count(str[i])){
                can=false;
                break;
            }
        }
        if(can){
            cout<<c<<endl;
            break;
        }
    }
    return 0;
}


活动打卡代码 AcWing 782. 避嫌抢劫

萌萌
8个月前
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int N=200001;
vector<vector<int>> c;

bool cmp(vector<int> &t1,vector<int> &t2){
    return t1[1]>t2[1];
}

int main(){
    int n,d;
    cin>>n>>d;
    for(int i=0;i<n;i++) {
        int a,b;
        cin>>a>>b;
        vector<int> path(2);
        path[0]=a,path[1]=b;
        c.push_back(path);
    }

    sort(c.begin(),c.end(),cmp);

    bool flag=false;
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            if(abs(c[j][0]-c[i][0])>=d){
                flag=true;
                cout<<c[j][1]+c[i][1]<<endl;
                break;
            }
        }
        if(flag) break;
    }

    return 0;
}



萌萌
8个月前
#include<iostream>

using namespace std;

int main(){
    int t;
    cin>>t;
    while(t--){
        int a;
        cin>>a;
        if(a%4==0||a%4==2) cout<<a*4+1<<endl;
        else if(a%4==1) cout<<a*2+1<<endl;
        else cout<<a+1<<endl;
    }
    return 0;
}



萌萌
10个月前

LeetCode 130 被围绕的区域

1、题目
给定一个二维的矩阵,包含 ‘X’ 和 ‘O’(字母 O)。

找到所有被 ‘X’ 围绕的区域,并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

示例:

X X X X
X O O X
X X O X
X O X X
运行你的函数后,矩阵变为:

X X X X
X X X X
X X X X
X O X X
解释:

被围绕的区间不会存在于边界上,换句话说,任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上,或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。

2、分析
采用:并查集
四周边缘的’O’看成第一类,中间不和’O’联通的’O’看成第二类。题目意思即是把第二类的’O’变成’X’。采用并查集,找到同一类就合并。由于一维数组更方便找父节点,所以把二维数组映射为一维数组。即nm行的数组映射为下标0~nm-1,而我们的并查集集合开一个nm+1的数组,下标nm为一个虚节点,把第一类的节点归为虚节点一类,这样在最后遍历时,只需要判断是否和虚节点为一类,则可以知道是否需要变为’X’。

3、代码

class Solution {
public:
    vector<int> p;
    int find(int x)
    {
        if(p[x]!=x) 
        {
            p[x]=find(p[x]);  //一定要路径压缩一下,不然会超时
            return find(p[x]);
        }

        return p[x];
    }

    int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

    void solve(vector<vector<char>>& board) {
        if(board.empty()||board[0].empty()) return;
        int n=board.size(),m=board[0].size();
        for(int i=0;i<=n*m;i++) p.push_back(i);  //m*n是虚节点

        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                if(board[i][j]=='O')
                {
                    if(i==0||i==n-1||j==0||j==m-1)  //若是在四周边缘处,和虚节点合并
                        p[find(i*m+j)]=find(n*m);
                    else
                    {
                        for(int k=0;k<4;k++)  //向四个方向合并
                        {
                            int nexi=i+dx[k],nexj=j+dy[k];
                            if(nexi>=0&&nexi<n&&nexj>=0&&nexj<m)
                            {
                                if(board[nexi][nexj]=='O')
                                    p[find(i*m+j)]=find(nexi*m+nexj);
                            }
                        }
                    }
                }

            }

        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                if(board[i][j]=='O')
                {
                    if(find(i*m+j)==find(m*n)) continue;  //判断是否和虚节点是一类
                    else board[i][j]='X';
                }
            }
    }
};