笔试练习day7

感谢各位大佬对我的支持,如果我的文章对你有用,欢迎点击以下链接
🐒🐒🐒 个人主页
🥸🥸🥸 C语言
🐿️🐿️🐿️ C语言例题
🐣🐣🐣 python
🐓🐓🐓 数据结构C语言
🐔🐔🐔 C++
🐿️🐿️🐿️ 文章链接目录
🏀🏀🏀 笔试练习题

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

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

题目解析

这道题是找出最长连续的数字,并将这串数字以字符串的形式输出,解题的思路就是用两个指针(i和j)遍历这个字符串

当i指针第一次遇到数字字符时就将位置给到j指针


此时j往后开始去查找这个连续的数字字符串有多长,当j遇到不是数字字符的时候就表示这个连续的数字字符串已经找完了,要计算他的长度.这个长度的计算我们可以直接用两个变量去记录这个数字字符串的起始位置和长度

然后i变到j的下一个位置继续重复上面操作

当遇到字符串长度比之前的len要大的时候就更新begin和len

解法(双指针遍历)

代码

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) {len = j - i;begin = i;}i = j + 1;}}cout << s.substr(begin, len) << endl;return 0;
}

NC109 岛屿数量

NC109 岛屿数量

题目解析

根据题目描述下面的这个例子有3个岛屿

其中绿色圆圈圈起的数字虽然没有上下左右之间的关系,但是也是相连的岛屿

解法

这道题解法就是通过bfs/dfs搜索去寻找连通的岛屿并标记已经找到的岛屿

代码(dfs)

class Solution {public:int m, n;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};bool vis[210][210] = {0};int solve(vector<vector<char> >& grid) {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;}};

因为这个岛屿需要上下左右的搜索,所以需要方向数组(之前的题也有类似的)
在搜索时需要进行标记已经搜索过的岛屿,所以要用一个bool类型的数组vis,因为岛屿矩阵的范围是200200,所以vis数组的范围我们应该选择大于200200的范围
二维数组的长和宽我们用m和n进行表示,ret来记录有多少个岛屿
通过两层for循环去遍历这个二维数组
然后用条件判断当grid[i][j]==1的时候表示这里有岛屿,且我们还要看这个岛屿是否之前已经被搜索过了,所以!vis[i][j]
条件符合时就让ret++记录这个岛屿,并且用dfs去标记周围连通的岛屿

dfs的实现

   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 < m && y >= 0 && y < n && grid[x][y] == '1'&&!vis[x][y]) {dfs(grid, x, y);}}}

进入dfs时grid[i][j]是有岛屿的,所以要进行标记
然后利用方向数组对grid[i][j]的周围进行搜索,并且要判断是否越界,当满足grid[x][y] == '1’和vis[x][y]没有被标记时就继续进入dfs(grid, x, y)

拼三角

拼三角

题目解析

题目意思就是给了6个棍子,但是这6个棍子的长度是不一样的,需要在选出3根来组成一个三角形的同时剩下的3根也能组成

解法(枚举)

因为这道题只给了6根棍子,所以搭配的方式比较少,我们可以把所有情况列出来
由排列组合可得所以的情况只有654/322=10种
具体我们可以用三重for循环去枚举,第一个for循环选第一根棍子,第二跟for循环选第二跟棍子,第三个for循环就选第三根棍子,在循环内部再检查是否能组成三角形
第二个方法就是用dfs去枚举

第三个方法就是优化后的枚举
我们知道三角形的判断条件如下

我们假设三个棍子长度分别为a b c
如果我们将这三个棍子长度进行排序,那么我们判断条件就会简单许多
假如a<b<c

那么我们就会发现判断条件就会少两个

所以我们对开始的6根棍子进行排序,排序过后就需要枚举以下的10种情况

当我们在枚举0 1 2和3 4 5的时候如果他们的条件成立就不需要再枚举后面的情况(因为已经满足条件了)

而如果枚举0 1 2和3 4 5的时候发现不满足条件那么他后面的几种情况就不需要再考虑(因为0+1<2那么0+1也同时<3)

所以根据上面的思路我们只需要枚举4种情况就可以了

代码

#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;elsecout<<"No"<<endl;}return 0;
}