目錄

1. 在字符串中找出連續(xù)最長(zhǎng)的數(shù)字串

2.島嶼數(shù)量

3.拼三角

---

1. 在字符串中找出連續(xù)最長(zhǎng)的數(shù)字串

字符串中找出連續(xù)最長(zhǎng)的數(shù)字串_?？皖}霸_牛客網(wǎng) (nowcoder.com)

算法思路：

這是一道簡(jiǎn)單的雙指針題目，首先用i遍歷數(shù)組，當(dāng)遍歷到數(shù)字的時(shí)候，i向后便利，使用count記錄下數(shù)字的長(zhǎng)度。如果數(shù)字的長(zhǎng)度 count 大于 歷史的最大長(zhǎng)度 maxcount，更新 最大長(zhǎng)度的起始位置maxi，和maxcount。

#include <iostream>
#include<string>
using namespace std;int isnumb(char s)//判斷是否是數(shù)字
{return s >= '0' && s <= '9';
}int main() {string s ;cin>>s;int maxi = -1;//最大長(zhǎng)度數(shù)字串的起始位置int maxcount = 0;//歷史最大長(zhǎng)度int  i = 0;while(i < s.size()){ int count = 0;//記錄當(dāng)前數(shù)字串的長(zhǎng)度 while(i < s.size()&&isnumb(s[i]))       {count++;i++;}if(count > maxcount)//當(dāng)前數(shù)字串是否比歷史最大長(zhǎng)度大{maxi = i-count;maxcount = count;}i++;}string ret = s.substr(maxi,maxcount);  cout<<ret<<endl;}
// 64 位輸出請(qǐng)用 printf("%lld")

2.島嶼數(shù)量

?

算法思路：

這是一道經(jīng)典的搜索題，使用dfs和bfs都可以，但是dfs的代碼更好寫，所以使用dfs。

遍歷矩陣找到一塊陸地，對(duì)這塊dfs，ret++ 并將周邊的的陸地全部標(biāo)記為已遍歷過(guò)。

dfs的目的就是將這塊陸地周圍的陸地全部標(biāo)記

class Solution {
public:int m , n;//矩陣的邊界int dx[4] = {0, 0, 1, -1};//向量數(shù)組，為了更好的遍歷上下左右int dy[4] = {1, -1, 0, 0};bool vis[210][210] = { 0 };//標(biāo)記當(dāng)前陸地是否被遍歷過(guò)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])//找到一塊沒(méi)有被遍歷過(guò)的陸地{ret++;dfs(grid, i ,j);}   }}return ret;}void dfs(vector<vector<char> >& grid, int i, int j){vis[i][j] = true;//將當(dāng)前位置標(biāo)記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]是一塊陸地，并且沒(méi)有被便利過(guò)dfs(grid, x, y);}}}};

3.拼三角

拼三角 (nowcoder.com)

、

算法思路：

這道題利用單調(diào)性是有取巧的做法，將輸入的6個(gè)數(shù)進(jìn)行排序。

這里012是數(shù)組下標(biāo)的012，數(shù)組依次增大

?我們那最左邊的4組舉例，如果 0 1 2構(gòu)不成三角形，那么 0 1 3， 0 1 4， 0 1 5，必然構(gòu)不成三角形，因?yàn)?是剩下最小數(shù)字，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;
}