【c++笔试强训】（第十篇）
目录
在字符串中找出连续最⻓的数字串（模拟+双指针）
题目解析
1.题目链接：字符串中找出连续最长的数字串_牛客题霸_牛客网
2.题目描述
描述
读入一个字符串str，输出字符串str中的连续最长的数字串
输入描述：
个测试输入包含1个测试用例，一个字符串str，长度不超过255。
输出描述：
在一行内输出str中里连续最长的数字串。
示例1
输入：
abcd12345ed125ss123456789
复制输出：
123456789
讲解算法原理
解法：
算法思路：
双指针：
遍历整个字符串，遇到数字的时候，⽤双指针找出这段连续的数字⼦串，根据此时的⻓度更新起始位置和⻓度。
编写代码
c++算法代码：
#include <iostream>
#include <string>
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] >= '0' && s[i] <= '9')
{
int j = i;
while(j < s.size() && s[j] >= '0' && s[j] <= '9') j++;
if(j - i > len)
{
begin = i;
len = j - i;
}
i = j;
}
}
if(begin == -1) cout << "" << endl;
else cout << s.substr(begin, len) << endl;
return 0;
}java算法代码：
import java.util.Scanner;
import java.io.*;
public class Main
{
public static void main(String[] args) throws Exception
{
BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
char[] s = br.readLine().toCharArray();
int begin = 0, len = 0;
for(int i = 0; i < s.length; i++)
{
if(s[i] >= '0' && s[i] <= '9')
{
int j = i;
while(j < s.length && s[j] >= '0' && s[j] <= '9') j++;
if(j - i > len)
{
begin = i;
len = j - i;
}
i = j;
}
}
for(int i = begin; i < begin + len; i++)
{
System.out.print(s[i]);
}
}
}
岛屿数量（BFS/DFS）
题目解析
1.题目链接：岛屿数量_牛客题霸_牛客网
2.题目描述
描述
给一个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
讲解算法原理
解法：
算法思路：
经典的floodfill算法。⽤dfs或者是bfs找出⼀个联通的区域，并且标记上。看看⼀共能找出⼏个联通块。
编写代码
c++算法代码：
class Solution
{
public:
int solve(vector<vector<char>>& grid)
{
int ret = 0; // 记录最终结果
int m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == '1')
{
ret++; // 发现⼀个岛屿
dfs(grid, i, j); // 把这个岛屿全部修改成 '0'
}
}
}
return ret;
}
int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};
void dfs(vector<vector<char>>& grid, int i, int j)
{
grid[i][j] = '0'; // 把该位置先变成 '0'
int m = grid.size(), n = grid[0].size();
// 遍历相邻的所有位置
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 && grid[x][y] == '1')
dfs(grid, x, y);
}
}
};java算法代码：
import java.util.*;
public class Solution
{
int m, n;
int[] dx = {0, 0, 1, -1};
int[] dy = {1, -1, 0, 0};
boolean[][] vis = new boolean[210][210];
public int solve (char[][] grid)
{
// dfs
m = grid.length; n = grid[0].length;
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;
}
public void dfs(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 < m && y >= 0 && y < n && grid[x][y] == '1' &&
!vis[x][y])
{
dfs(grid, x, y);
}
}
}
}原文地址：https://blog.csdn.net/weixin_73861555/article/details/143794314
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！