[笔试强训day07]

南桥

发布于 2024-05-14 08:24:53

830

发布于 2024-05-14 08:24:53

文章被收录于专栏：南桥谈编程南桥谈编程

文章目录

OR59 字符串中找出连续最长的数字串
NC109 岛屿数量
- 解法一：bfs
- 解法二：dfs
拼三角

OR59 字符串中找出连续最长的数字串

#include<iostream>

using namespace std;

int main()
{
    string s;
    cin>>s;
    int len=0,newi=-1;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]>='0'&&s[i]<='9')
        {
            int j=i;
            while(s.size()&&s[j]>='0'&&s[j]<='9')
            {
                j++;
            }
            if(j-i>len)
            {
                newi=i;
                len=j-i;
            }
            i=j;
        }
    }
    if(newi==-1) cout<<" "<<endl;
    else cout<<s.substr(newi,len)<<endl;
    return 0;
}

NC109 岛屿数量

解法一：bfs

#include <vector>
#include<queue>
class Solution {
    int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
    typedef pair<int,int> PII;
    bool vis[300][300];
    int m,n,ans;
public:

    int solve(vector<vector<char> >& grid) {
        if(grid.empty()||grid[0].empty()) return 0;
        m=grid.size(),n=grid[0].size();
        int ret=0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]=='1'&&!vis[i][j])
                {
                    ret++;
                    bfs(grid,i,j);
                }
            }
        }   
        return ret; 
    }

    void bfs(vector<vector<char>>& grid,int i,int j)
    {
        queue<pair<int,int>> q;
        q.push({i,j});
        vis[i][j]=true;

        while(q.size())
        {
            auto [a,b]=q.front();
            q.pop();

            for(int k=0;k<4;k++)
            {
                int x=a+dx[k],y=b+dy[k];
                if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]=='1'&&!vis[x][y])
                {
                    q.push({x,y});
                    vis[x][y]=true;
                }
            }
        }
    }

    
};

解法二：dfs

#include <vector>
#include<queue>
class Solution {
    int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
    typedef pair<int,int> PII;
    bool vis[300][300];
    int m,n,ans;
public:

    int solve(vector<vector<char> >& grid) {
        if(grid.empty()||grid[0].empty()) return 0;
        m=grid.size(),n=grid[0].size();
        int ret=0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]=='1'&&!vis[i][j])
                {
                    ret++;
                    dfs(grid,i,j);
                }
            }
        }   
        return ret; 
    }

    void dfs(vector<vector<char>>& grid,int i,int j)
    {
        grid[i][j]='0';
        for(int k=0;k<4;k++)
        {
            int x=i+dx[k],y=j+dy[k];
            if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y]&&grid[x][y]=='1')
            {
                dfs(grid,x,y);
            }
        }
    }

    
};

拼三角

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

int main()
{
    int t;
    cin>>t;
    int arr[6];
    while(t--)
    {
        for(int i=0;i<6;i++) cin>>arr[i];
        sort(arr,arr+6);
        if(arr[0] + arr[1] > arr[2] && arr[3] + arr[4] > arr[5] ||
            arr[0] + arr[2] > arr[3] && arr[1] + arr[4] > arr[5] ||
            arr[0] + arr[3] > arr[4] && arr[1] + arr[2] > arr[5] ||
            arr[0] + arr[4] > arr[5] && arr[1] + arr[2] > arr[3])
            cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    
    return 0;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-05-11，如有侵权请联系 cloudcommunity@tencent.com 删除

int