【C++】 —— 笔试刷题day_7_规定上下左右相邻的岛屿是同一座岛屿(同一行第一列和最后一列也算相邻),现在你处

刷题day_7，继续加油啊！！！

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

题目链接：字符串中找出连续最长的数字串

题目解析

这道题可以说非常简单了，我们只需要在给定的字符串中找到最长的数字串即可。

算法分析

这道题很简单，就直接来看解题思路：

• 定义i ，遍历给定的字符串str
• 遇到数字字符，定义j记录当前位置，i再从当前位置开始向后遍历直到遍历结束或者遇到的字符不是数字字符；
• 如果当前遍历到的是最长的就更新结果，记录当前位置。
• 更新结果之后，让i接着向后遍历即可。

代码实现

#include using namespace std;int main() { string str; cin >> str; int begin = -1, len = 0; int n = str.size(); for (int i = 0; i < n; i++) { if (str[i] >= \'0\' && str[i] <= \'9\') { int j = i; while (i < n && str[i] >= \'0\' && str[i] <= \'9\') { i++; } if (i - j > len) { begin = j; len = i - j; } } } if (begin == -1) cout << \"\" << endl; else cout << str.substr(begin, len) << endl; return 0;}

这里注意：最后输出时这使用的是string中的substr函数，所以需要进行一下判断。

二、岛屿数量

题目链接：岛屿数量

题目解析

大眼一观题目，一道典型的搜索题；

现在来看一下它们要求：

给一个01矩阵（字符矩阵），其中0代表海洋、1代表岛屿；

现在如果两个岛屿相邻，那它们就属于同一个岛屿（相邻是指的上、下、左、右）。

我们要判断，给定的字符数组中，岛屿的数量。

算法思路

这里一道搜索题，先简单来分析一下：

我们找到一个岛屿，然后从这个岛屿开始向四周遍历；这里存在一些问题？

1. 我们怎么计算岛屿的数量?
2. 我们怎么判断岛屿是否和其他岛屿同属于一个岛屿?

这些问题，也是博主在初次遇见这个题时的疑惑

现在就来解决这些疑惑：

• 首先我们要使用深度优先遍历DFS或者广度优先遍历BFS，遍历一个岛屿，将其相邻的岛屿都遍历一遍，并且做上标记；
• 那这个标记，就定义一个bool类型的数组vis来记录每一个岛屿是否被遍历过。（如果被遍历过就不用再遍历了）
• 最后，我们每进行一次遍历，就将一块岛屿连到了一起；所以我们进行了几次遍历，就存在几个岛屿。

这样我们就解决了如何记录岛屿数量的问题，也解决了如何判断这个岛屿是否和其他岛屿同属于一个岛屿的问题（我们这里每一个岛屿只会被遍历一次，就不会被重复记录）。

所以这道题大致思路就以清晰了：

首先我们定义dx、dy表示一个位置上下左右四个位置对应的行列坐标变化值。

vis，记录每一个位置是否被遍历过；（题目中描述：矩阵范围<= 200乘200，所以行列都直接开辟[201]即可）

• 首先找到字符数组中的1，从1`出开始进行深度优先遍历；
• 记录进行深度优先遍历的次数，即最终岛屿的数量。

深度优先遍历：

对于DFS，就是遍历当前位置i , j(记录当前位置，表示已经被遍历过）再接着遍历当前位置的相邻位置上、下、左、右。

递归来实现即可。

代码实现

class Solution {public: int dx[4] = {0,0,1,-1}; int dy[4] = {1,-1,0,0}; bool vis[201][201] = {false}; int solve(vector<vector<char> >& grid) { int ret = 0; int m = grid.size(); int n = grid[0].size(); for(int i = 0;i<m;i++) { for(int j = 0;j<n;j++) { //如果当前位置是岛屿,且没有被遍历过 if(grid[i][j] == \'1\' && vis[i][j] == false) {  //深度优先遍历  dfs(grid,i,j);  ret++; } } } return ret; } void dfs(vector<vector<char>>& grid, int i, int j) { vis[i][j] = true; int m = grid.size(); int n = grid[0].size(); for(int k=0;k<4;k++) { //x,y 是当前位置相邻位置的坐标 int x = i+dx[k]; int y = j+dy[k]; //如果x,y没有越界,且(x,y)位置是岛屿且没有被遍历过 if(x>=0 && x<m && y>=0 && y<n && grid[x][y] == \'1\' && vis[x][y] == false) dfs(grid,x,y); } }};

三、拼三角

题目链接：拼三角

题目解析

这里题目给定t组数据，每一组数据中包含6个整数，让我们判断这六个整数能否组成两个三角形

算法思路

题目描述也是和简单的，就是输入六个数，然后判断这六个数能否组成三角形。

暴力解法：

这里暴力解法，直接枚举所有的情况（因为这里题目给出的6个数，所有的情况也就只有20种），所以直接枚举也不麻烦。

这里再看：

选择0、1、2位置则剩余3、4、5；和选择3、4、5剩余0、1、2位置

这两种是同一种情况，所以当前就只需要枚举10种情况即可。

现在我们接着看：（是否能再进行优化）

现在我们先让给定的6个数有序

现在我们数组已经有序，从6个数选出来3个数，所有情况如上图所示

现在数组是有序的，所以：

• 如果arr[0] + arr[1] >arr[2]，那我们就无需再判断0 , 1 , 2、0 , 1 , 3、0 , 1 , 4这些情况了，此时已经可以构成三角形了
• 而arr[0] + arr[1] < arr[2]，那我们arr[0] + arr[1]就一定小于arr[3]；就无需再判断0 , 1 , 3和0 , 1 , 4等这些情况了。
• 所以，现在我们只需要判断0 , 1 , 2、0 , 2 , 3、0 , 3 , 4、0 , 4 , 5四种情况即可。

代码实现

#include#includeusing namespace std;int main(){ int n = 0; cin>>n; while(n--) { int arr[6]; 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;}

** 到这里本篇文章就结束了，继续加油！**

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws