强化训练：day7(字符串中找出连续最长的数字串、岛屿数量、拼三角）

本文主要是介绍强化训练：day7(字符串中找出连续最长的数字串、岛屿数量、拼三角），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

  1. 字符串中找出连续最长的数字串
  2. 岛屿数量
  3. 拼三角

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

1.1 题目描述

1.2 解题思路

  双指针——使用两个指针，一个找数字的头，一个找数字的尾，再用一个变量保存它们之间的长度，如果当前长度为前一个长度大，就更新结果，继续找下一个数字字符串。

1.3 代码实现

#include <iostream>
using namespace std;
#include <string>
int main() {string s;cin >> s;int left = 0, right = 0;int len = 0;string ret;int n = s.size();// while(right < s.size())// {//     while(right < s.size() && s[right] <= '0' || s[right] >= '9') right++;//     left = right;//     while(right < s.size() && s[right] >= '0' && s[right] <= '9') right++;//     if(len < right - left)//     {//         len = right - left;//         ret = s.substr(left, right - left);//     }//         left = right;// }while (left < n && right < n) {while (left < n && (s[left] <= '0' || s[left] >= '9')) left++;right = left;while (right < n && (s[right] >= '0' && s[right] <= '9')) right++;if (len < right - left) {len = right - left;ret = s.substr(left, right - left);}left = right;}if(ret.size() == 0) cout << "";else cout << ret;cout << ret;return 0;
}

2. 岛屿数量

2.1 题目描述

2.2 题目描述

  典型的dfs， dfs函数的功能：将一个陆地及其相邻的陆地进行标记。
  对整个地图进行循环，只要找到一个陆地就进行一次dfs，将其相邻的陆地都进行标记，防止对已经标价过的陆地重复统计。
  当循环结束，也就意味着所有的陆地都已经标记，只需要统计进行了几次dfs即可。
  对于有关递归的问题，如果不理解，建议画图，通过走读代码，将每一次代码执行后的结果都画出来，这样更容易明白整个解题过程。

2.3 代码实现

class Solution {public:int m, n;bool vis[201][201];int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};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') {grid[x][y] = '0';dfs(grid, x, y);}}}int solve(vector<vector<char> >& grid) {int ret = 0;memset(vis, 0, sizeof vis);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') {dfs(grid, i, j);ret++;}}return ret;}
};

3. 拼三角

3.1 题目描述

3.2 解题思路

  这个题数据量很小，直接三层for循环就解决了。
  然后看了别人的题解，竟然发现了一些奇思妙想……
  看图吧：

3.3 代码实现

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

总结

  对于第一题，当时使用一模一样的代码，不知道为什么当时写的时候测试用例总是只能过百分之80，今天测试的时候就成百分之百了……挺无语的。不过今天的重点还是第二题，dfs，大家可以通过画图来理解整个解题思路噢。
  那么第天七的内容就到此结束了，如果大家发现有什么错误的地方，可以私信或者评论区指出喔。我会继续坚持训练的，希望能与大家共同进步！！！那么本期就到此结束，让我们下期再见！！觉得不错可以点个赞以示鼓励！

这篇关于强化训练：day7(字符串中找出连续最长的数字串、岛屿数量、拼三角）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---