【C++】 —— 笔试刷题day_7

刷题day_7，继续加油啊！！！
  一、字符串中找出连续最长的数字串

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

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

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

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

  代码实现

1. #include <iostream>
2. using namespace std;
4. int main() {
5.     string str;
6.     cin >> str;
7.     int begin = -1, len = 0;
8.     int n = str.size();
9.     for (int i = 0; i < n; i++) {
10.         if (str[i] >= '0' && str[i] <= '9') {
11.             int j = i;
12.             while (i < n && str[i] >= '0' && str[i] <= '9') {
13.                 i++;
14.             }
15.             if (i - j > len) {
16.                 begin = j;
17.                 len = i - j;
18.             }
19.         }
20.     }
21.     if (begin == -1) cout << "" << endl;
22.     else cout << str.substr(begin, len) << endl;
23.     return 0;
24. }

复制代码

  这里留意：最后输出时这使用的是string中的substr函数，所以必要进行一下判断。
  二、岛屿数量

标题链接：岛屿数量
标题剖析

大眼一观标题，一道典型的搜刮题；
如今来看一下它们要求：
   给一个01矩阵（字符矩阵），其中0代表海洋、1代表岛屿；
  如今如果两个岛屿相邻，那它们就属于同一个岛屿（相邻是指的上、下、左、右）。
  我们要判断，给定的字符数组中，岛屿的数量。
  算法思路

这里一道搜刮题，先简单来分析一下：
我们找到一个岛屿，然后从这个岛屿开始向附近遍历；这里存在一些题目？
   

• 我们怎么盘算岛屿的数量?
  
• 我们怎么判断岛屿是否和其他岛屿同属于一个岛屿?
  

  这些题目，也是博主在初次遇见这个题时的疑惑
如今就来解决这些疑惑：
   

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

  如许我们就解决了如何记录岛屿数量的题目，也解决了如何判断这个岛屿是否和其他岛屿同属于一个岛屿的题目（我们这里每一个岛屿只会被遍历一次，就不会被重复记录）。
  所以这道题大致思路就以清楚了：
   起首我们界说dx、dy表现一个位置上下左右四个位置对应的行列坐标变化值。
  vis，记录每一个位置是否被遍历过；（标题中形貌：矩阵范围<= 200乘200，所以行列都直接开发[201]即可）
  

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

  深度优先遍历：
   对于DFS，就是遍历当前位置i , j(记录当前位置，表现已经被遍历过）再接着遍历当前位置的相邻位置上、下、左、右。
  递归来实现即可。
  代码实现

1. class Solution {
2. public:
3.     int dx[4] = {0,0,1,-1};
4.     int dy[4] = {1,-1,0,0};
5.     bool vis[201][201] = {false};
6.     int solve(vector<vector<char> >& grid) {
7.         int ret = 0;
8.         int m = grid.size();
9.         int n = grid[0].size();
10.         for(int i = 0;i<m;i++)
11.         {
12.             for(int j = 0;j<n;j++)
13.             {
14.                 //如果当前位置是岛屿,且没有被遍历过
15.                 if(grid[i][j] == '1' && vis[i][j] == false)
16.                 {
17.                     //深度优先遍历
18.                     dfs(grid,i,j);
19.                     ret++;
20.                 }
21.             }
22.         }
23.         return ret;
24.     }
25.     void dfs(vector<vector<char>>& grid, int i, int j)
26.     {
27.         vis[i][j] = true;
28.         int m = grid.size();
29.         int n = grid[0].size();
30.         for(int k=0;k<4;k++)
31.         {
32.             //x,y 是当前位置相邻位置的坐标
33.             int x = i+dx[k];
34.             int y = j+dy[k];
35.             //如果x,y没有越界,且(x,y)位置是岛屿且没有被遍历过
36.             if(x>=0 && x<m && y>=0 && y<n && grid[x][y] == '1' && vis[x][y] == false)
37.                 dfs(grid,x,y);
38.         }
39.     }
40. };

复制代码

三、拼三角

标题链接：拼三角
标题剖析

   这里标题给定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四种情况即可。
  

  代码实现

1. #include<iostream>
2. #include<algorithm>
3. using namespace std;
5. int main()
6. {
7.     int n = 0;
8.     cin>>n;
9.     while(n--)
10.     {
11.         int arr[6];
12.         for(int i=0;i<6;i++)
13.         {
14.             cin>>arr[i];
15.         }
16.         sort(arr,arr+6);
17.         if(arr[0] + arr[1] >arr[2] && arr[3] + arr[4] > arr[5]
18.         ||arr[0] + arr[2] >arr[3] && arr[1] + arr[4] > arr[5]
19.         ||arr[0] + arr[3] >arr[4] && arr[1] + arr[2] > arr[5]
20.         ||arr[0] + arr[4] >arr[5] && arr[1] + arr[2] > arr[3])
21.         {
22.             cout<<"Yes"<<endl;
23.         }
24.         else
25.             cout<<"No"<<endl;
26.     }
27.     return 0;
28. }

复制代码

  ** 到这里本篇文章就结束了，继续加油！**
  我的博客即将同步至腾讯云开发者社区，邀请各人一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。