目录
1. 在字符串中找出连续最长的数字串
2.岛屿数量
3.拼三角
1. 在字符串中找出连续最长的数字串
字符串中找出连续最长的数字串_牛客题霸_牛客网 (nowcoder.com)
算法思路：
这是一道简单的双指针题目，首先用i遍历数组，当遍历到数字的时候，i向后便利，使用count记录下数字的长度。如果数字的长度 count 大于 历史的最大长度 maxcount，更新 最大长度的起始位置maxi，和maxcount。
#include <iostream>
#include<string>
using namespace std;int isnumb(char s)//判断是否是数字
{return s >= '0' && s <= '9';
}int main() {string s ;cin>>s;int maxi = -1;//最大长度数字串的起始位置int maxcount = 0;//历史最大长度int i = 0;while(i < s.size()){ int count = 0;//记录当前数字串的长度 while(i < s.size()&&isnumb(s[i])) {count++;i++;}if(count > maxcount)//当前数字串是否比历史最大长度大{maxi = i-count;maxcount = count;}i++;}string ret = s.substr(maxi,maxcount); cout<<ret<<endl;}
// 64 位输出请用 printf("%lld")2.岛屿数量
算法思路：
这是一道经典的搜索题，使用dfs和bfs都可以，但是dfs的代码更好写，所以使用dfs。
遍历矩阵找到一块陆地，对这块dfs，ret++ 并将周边的的陆地全部标记为已遍历过。
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;}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]){ //如果x，y不越界，grid[x][y]是一块陆地，并且没有被便利过dfs(grid, x, y);}}}};
3.拼三角
拼三角 (nowcoder.com)
、
算法思路：
这道题利用单调性是有取巧的做法，将输入的6个数进行排序。
这里012是数组下标的012，数组依次增大
我们那最左边的4组举例，如果 0 1 2构不成三角形，那么 0 1 3， 0 1 4， 0 1 5，必然构不成三角形，因为2是剩下最小数字，0 + 1不能大于 2，那么肯定也不能 大于 3 4 5，所以剩下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;
}
