【强训笔记】day7

NO.1

思路：双指针模拟，begin表示最长数字字符串最后一个字符，而len表示数字字符串的长度，i用来遍历，如果为数字，那么定义j变量继续遍历，直到不为数字，i-j如果大于len，就更新len。最后string的substr打印就行了。

代码实现：

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

int main() {
    string s;
    cin>>s;
    int begin=-1,len=0;
    int n=s.size();
    for(int i=0;i<n;i++)
    {
        if(s[i]>='0'&&s[i]<='9')
        {
            int j=i;
            while(j<n&&s[j]>='0'&&s[j]<='9') j++;
            if(j-i>len)
            {
                begin=i;
                len=j-i;
            }
            i=j;
        }
    }

    cout<<s.substr(begin,len)<<endl;
    return 0;
    
}

NO.2

思路：dfs遍历，先用创建一个bool数组，先进行遍历，如果该位置的值为1，且bool数组在该位置为false，那么就调用dfs函数进行搜索，在dfs中先将bool数组的该位置改为true，在遍历它的上下左右四个位置，进行dfs搜索。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,1,-1};
    bool vis[210][210]={0};
    int solve(vector<vector<char> >& grid) {
       int 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)
    {
        vis[i][j]=true;
        for(int k=0;k<4;k++)
        {
            int x=i+dx[k],y=j+dy[k];
            if(x>=0&&x<grid.size()&&j>=0&&j<grid[0].size()&&grid[x][y]=='1'&&!vis[x][y])
            {
                dfs(grid,x,y);
            }
        }
    }
};

NO.3

思路：枚举出总共有10种情况，而只要满足以下的四种情况那么就符合，输出Yes。
代码实现：

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

int t;
int arr[6];

int main()
{
    cin>>t;
    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;
}