48days强训——day7
第一题：字符串中找出连续最长的数字串
描述 读入一个字符串str，输出字符串str中的连续最长的数字串 输入描述： 个测试输入包含1个测试用例，一个字符串str，长度不超过255。 输出描述： 在一行内输出str中里连续最长的数字串。 示例1 输入： abcd12345ed125ss123456789 输出： 123456789
思路：遍历字符串，当遇到数字时，用双指针计算子字符串的长度。若该长度大于之前记录的最大长度，更新起始位置和最大长度。最后输出最长连续数字串。
代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin >> s;
int begin = -1,len = 0;
for(int i = 0; i < s.size();i++)
{
if(s[i] <= '9' && s[i] >= '0')
{
int j = i;
while ( j < s.size() && s[j] <= '9' && s[j] >= '0') j++;
if(j-i > len)
{
begin = i;
len = j - i;
}
i = j;
}
}
cout << s.substr(begin,len);
return 0;
}第二题：岛屿数量
描述 给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。 岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。 例如： 输入 [ [1,1,0,0,0], [0,1,0,1,1], [0,0,0,1,1], [0,0,0,0,0], [0,0,1,1,1] ] 对应的输出为3 (注：存储的01数据其实是字符'0','1') 示例1 输入： [[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]] 返回值： 3 示例2 输入： [[0]] 返回值： 0 示例3 输入： [[1,1],[1,1]] 返回值： 1 备注： 01矩阵范围<=200*200
解法（深度优先，广度优先）：遍历整个用bfs或者dfs找出⼀个联通的区域，并且标记上。
代码：
广度优先：
class Solution
{
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
bool vis[201][201] = { false };
int n, m;
public:
void bfs(vector<vector<char> >& grid, int ex, int ey)
{
queue<pair<int, int>>q;
q.push({ ex,ey });
vis[ex][ey] = true;
while (q.size())
{
auto [a, b] = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int x = a + dx[i], y = b + dy[i];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' &&!vis[x][y])
{
q.push({ x,y });
vis[x][y] = true;
}
}
}
}
int solve(vector<vector<char> >& grid)
{
n = grid[0].size(), m = grid.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;
}
};深度优先：
class Solution
{
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
bool vis[201][201] = { false };
int n, m;
public:
void dfs(vector<vector<char> >& grid, int ex, int ey)
{
vis[ex][ey] = true;
for (int i = 0; i < 4; i++)
{
int x = ex + dx[i], y = ey + dy[i];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !vis[x][y])
{
dfs(grid, x, y);
}
}
}
int solve(vector<vector<char> >& grid)
{
n = grid[0].size(), m = grid.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;
}
};第三题：拼三角
链接：拼三角
题目描述 给出6根棍子，能否在选出3根拼成一个三角形的同时剩下的3根也能组成一个三角形？ 输入描述: 首先在一行中给出一个 t,1≤t≤103t,1 \le t \le 10^3t,1≤t≤103，代表测试数据的组数 接下来t行，每行给出6个数字代表棍子长度，棍子长度为正且小于10910^9109 输出描述: 在一行中输出 “Yes” or “No” 示例1 输入 2 1 1 1 1 1 1 1 2 3 4 5 6 2 1 1 1 1 1 1 1 2 3 4 5 6 输出 Yes No
思路：这个题暴力枚举有10种情况，再将这六个数排序，枚举后会发现规律如下：
假设：0+1<2那么0 1 3 也不可能成立，因为这是一个升序数组。最后只需要判断四种情况。
代码：
#include<bits/stdc++.h>
using namespace std;
int nums[6];
int main()
{
int t;
cin >> t;
while(t--)
{
for(int i = 0; i < 6; i++) cin >> nums[i];
sort(nums,nums+6);
if(nums[0] + nums[1] > nums[2] && nums[3]+nums[4] > nums[5] ||
nums[0] + nums[2] > nums[3] && nums[1] + nums[4] > nums[5]||
nums[0] + nums[3] > nums[4] && nums[1] + nums[2] > nums[5]||
nums[0] + nums[4] > nums[5] && nums[1] + nums[2] > nums[3])
cout << "Yes" << endl;
else cout<< "No" << endl;
}
return 0;
}腾讯云开发者
