今日刷题汇总 - day007

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

1.1、题目

1.2、思路

读完题知道，需要求一段字符串中最长且是连续的数字字符串。既然涉及到找最长，意味着具有比较关系，所以立马想到利用一个变量字符串temp进行统计各个连续的数字字符串的长度，最后留取最长retstr的返回即可。另外，还可以利用双指针，标记每一次出现数字字符的起始位置，然后纪录其连续的长度，然后返回最长处的其实位置的字串也行。那么。接下来两个思路都写一写吧。

1.3、程序实现 – 比较

首先，我们根据思路和题目定义三个字符串，一个str作为原字符串输入，一个retstr最后最后的返回字符串，一个temp作为比较retstr更新字符串，接着，开始遍历str的各个字符，当遇见数字字符，则尾插进temp中，否则，遇见其它字符则比较retstr和temp的长度，如果temp的长度大于retstr时，则保留最长的数字字符串到retstr，否则清空短的字符串temp继续遇见遍历到下一个数字字符再次依次尾插连续数字字符统计长度，依次类推，得到最后的最长数字连续字符串retstr输出即可。

#include <iostream>
#include <string>
using namespace std;bool isNum(char c)
{return c <= '9' && c >= '0';
}int main() {string str;string retstr;string temp;cin >> str;size_t len = str.size();for (int i = 0; i <= len; i++){if (isNum(str[i])){temp += str[i];} else{if (retstr.size() < temp.size())retstr = temp;elsetemp.clear();}}cout << retstr << endl;return 0;
}

1.4、程序实现 – 双指针

接下来，双指针需要利用begin标记遍历出现数字字符的位置，且定义一个j从begin处开始遍历连续数字字符串的长度，遇见非数字字符停止，求得 j - i 的长度保存到maxlen中，然后，将 i 置到 j 处继续遍历，且每一次标记begin和maxlen保持更新为最长的数字字符串的起始地址和长度即可。最后利用substr输出指定位置的字串即可。

#include <iostream>
#include <string>
using namespace std;bool isNum(char ch)
{return ('0' <= ch && ch <= '9');
}int main()
{string str;cin >> str;int begin = -1;int maxlen = -1;for(int i = 0;i< str.size();i++){if(isNum(str[i])){int j = i;while(j < str.size() && isNum(str[j]))j++;if(j -i > maxlen){begin = i;maxlen = j-i;}i = j;}     }cout << str.substr(begin, maxlen) << endl;return 0;
}

2、岛屿数量

2.1、题目

2.2、思路

读完题知道，又是属于在一个二维数组里进行搜索/扩散/累计啊等问题。那么立马就想到了深度优先搜索dfs和广度优先搜索bfs，然后让我们实现统计，属于联通的岛屿(即具有上下左右连通的‘1’)的个数。那么这里就采用dfs解决即可。比之前的腐烂的苹果和单词搜索更简单一些，因为只需要计数即可。接下来，就是程序实现。

2.3、程序实现 - dfs

首先，既然采用dfs把固定的套路和模板先写上即可。定义m,n计算二维数组的大小，方便稍后遍历，再定义两个方向数组dx和dy，接着定义bool类型的vis数组，表示是否已连通。模板写好，接着就是遍历二维数组判断是否是岛屿，是则计数count且dfs搜索上下左右是否连通。连通就规划为一块岛屿，否则就继续遍历，直到规划出所有连通的岛屿，规划出多少那么coun就恰好统计出结果，最后返回count即可。

class Solution {
public:int m,n;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){m = grid.size();n = grid[0].size();int count = 0;for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(grid[i][j] == '1' && !vis[i][j]){count++;dfs(grid,i,j);}}}return count;}
};

那么，继续完善dfs函数，其实方法都类似，先进入dfs后标记当前属于岛屿，再此岛屿基础上，就是在4个方向上判断是否是岛屿‘1’且没有越界且没有被标记已连通，是则与当前岛屿执行递归标记连通，否则周围就没有需要连通的岛屿了。

class Solution {
public:int m,n;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){m = grid.size();n = grid[0].size();int count = 0;for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(grid[i][j] == '1' && !vis[i][j]){count++;dfs(grid,i,j);}}}return count;}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];int y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !vis[x][y])dfs(grid,x,y);}}
};

3、拼三角

3.1、题目

3.2、思路

读完题，理解到让我们实现在6根木棍中，任选3根木棍来拼接三角形，其次，还得判断在剩下的3根木棍中是否还能拼接成三角形。如果同时能，则输出“Yes”，否则输出"No"即可。由于，只有6根数量级不大，直接尝试一波蛮力法试试，蛮力法思路就是遍历每3根都去判断一下，能够组成三角形，能则继续判断剩下3根是否也能组成三角形，能则输出“Yes”，如果不能组成三角形那么输出“No”即可。另外，在写蛮力法时发现，会有很多的冗余操作和判断，会发现具有一些特定，即具备判断的单调性(稍后画图理解)，所以利用这个特点且只针对这道题，就有了更优解法。其次，看其它大佬也有用dfs的，但是我没想出来，而且这里用起来很麻烦且边界不好控制，就不写dfs了。
那么接下来，就是程序实现。

3.3、程序实现 – 蛮力法

首先，根据蛮力法的思路，具体分为以下几个步骤：
(1)、首先，先对木棍长度进行排序，目的是简化，便于逻辑思考下标处理等；
(2)、套三层for循环，遍历判断check三角形的性质是否满足(任意两边之和大于第三边)；
(3)、再(2)满足条件下，继续判断剩下check the other three的三根木棍是否满足三角形性质；
那么，先根据题目要求和思路写好基本框架，再把数组sort排序，再为了增加代码阅读性，我这里采用封装了CheckTriangles函数单独处理是否满足三角形逻辑。

#include <iostream>
#include <algorithm>
using namespace std;bool CheckTriangles(int* arr)
{
}int main()
{int n;cin >> n;while (n--){int arr[6];for (int i = 0; i < 6; i++)cin >> arr[i];sort(arr, arr + 6);//步骤1：排序if (CheckTriangles(arr))cout << "Yes" << endl;elsecout << "No" << endl;}return 0;
}

接着，实现蛮力法遍历逻辑，先根据三边需要求和比较的的关系，写三层for循环，其次，额外封装了一个isTriangle函数，判断是否满足三角形性质，注意哈，这里需要任意两边之和大于第三边为真才满足哈。

#include <iostream>
#include <algorithm>
using namespace std;bool isTriangle(int a, int b, int c)
{return (a + b > c && a + c > b && b + c > a);
}bool CheckTriangles(int* arr)
{//步骤2：for循环嵌套for (int i = 0; i < 3; i++){for (int j = i + 1; j < 4; j++){for (int k = j + 1; k < 5; k++){//步骤3： Check -- isTriangleif (isTriangle(arr[i], arr[j], arr[k])){//步骤4： Check the other three -- isTriangle}}}}return false;
}int main()
{int n;cin >> n;while (n--){int arr[6];for (int i = 0; i < 6; i++)cin >> arr[i];sort(arr, arr + 6);//步骤1：排序if (CheckTriangles(arr))cout << "Yes" << endl;elsecout << "No" << endl;}return 0;
}

最后一步就是检查，若步骤3满足，则剩下的三根木棍是否仍然满足三角形性质。所以，这里定义Residue[3]表示存放剩余木棍的数组，定义index表示它的下标，方便操作，然后遍历原数组，把剩下的数组元素，存放进Residue数组，这样就可以方便把Residue数组每一根木棍一起放进isTriangle进行拼接验证是否满足三角形性质，若满足，则返回ture，否则继续回到步骤2，继续遍历结束为止，直到最后都没有满足，则返回false，则main输出“No”，否则输出"Yes"即可。

#include <iostream>
#include <algorithm>
using namespace std;bool isTriangle(int a, int b, int c)
{return (a + b > c && a + c > b && b + c > a);
}bool CheckTriangles(int* arr)
{//步骤2：for循环嵌套for (int i = 0; i < 3; i++){for (int j = i + 1; j < 4; j++){for (int k = j + 1; k < 5; k++){//步骤3： Check -- isTriangleif (isTriangle(arr[i], arr[j], arr[k])){//步骤4： Check the other three -- isTriangleint Residue[3];int idx = 0;for (int m = 0; m < 6; m++){if (m != i && m != j && m != k){Residue[idx++] = arr[m];}}if (isTriangle(Residue[0], Residue[1], Residue[2])){return true;}}}}}return false;
}int main()
{int n;cin >> n;while (n--){int arr[6];for (int i = 0; i < 6; i++)cin >> arr[i];sort(arr, arr + 6);//步骤1：排序if (CheckTriangles(arr))cout << "Yes" << endl;elsecout << "No" << endl;}return 0;
}

3.4、程序实现 – 巧解(单调性)

解法二，基于解法一的情况下，发现此题具有单调性的特点，所以利用这一特点，能够更快的方便判断求解。为了更好的理解，画个图演示：

#include <iostream>
#include <algorithm>
using namespace std;int main()
{int n;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;}elsecout << "No" << endl;}return 0;
}

4、题目链接

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