目录
1.字符串中找出连续最长的数字串
2.岛屿数量
3.拼三角
1.字符串中找出连续最长的数字串
链接
我的思路很简洁，就是双指针遍历，然后不断更新左位置left和右位置right和长度len。
然后我写代码的时候代码思路没跟上原本思路，直接把所有的l，r，len都存起来，然后最后再遍历一遍存起来的数。
回想起才发现思路清晰了，但是代码写的一塌糊涂，其实可以直接在遍历的过程中不断更新l，r，len就可以了。
一开始代码（可以通过，但是繁琐）：
#include <iostream>
#include <vector>
using namespace std;
vector<pair<int, int>> vp(256);
int main() {
string s;
cin >> s;
int l = 0, r = 0;
int k = 0;
while (r < s.size()) {
while (!(s[l] >= '0' && s[l] <= '9')) {
l++;
}
r = l;
while (s[r] >= '0' && s[r] <= '9') {
r++;
}
vp[k++] = { l, r - 1 };
l = r;
}
int len = 0;
int keyi = 0;
for (int i = 0; i < k; ++i) {
if ((vp[i].second - vp[i].first + 1) > len) {
len = vp[i].second - vp[i].first + 1;
keyi = i;
}
}
string t(s.begin() + vp[keyi].first, s.begin() + vp[keyi].second + 1);
cout << t << endl;
return 0;
}改进代码（相当于我改进思路的再改进，因为可以不用不存储右指针，因为有了左和长度就可以判断右）：
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s;
cin >> s;
int begin = -1, len = 0;
for (int i = 0; i < s.size(); i++)
{
if (s[i] >= '0' && s[i] <= '9')
{
int j = i;
while (j < s.size() && s[j] >= '0' && s[j] <= '9') j++;
if (j - i > len)
{
begin = i;
len = j - i;
}
i = j;
}
}
if (begin == -1)
cout << "" << endl;
else
cout << s.substr(begin, len) << endl;
return 0;
}这样不仅代码简洁，而且看起来也舒服。
begin初始化为负 -1 是为了判断有没有更新过。
2.岛屿数量
链接
非常经典的一道DFS题目。
因为我见了很多DFS的题目返回值都为bool，因此我认为DFS必须以bool作返回值，结果导致浪费很多时间还得不到成果。
用不着返回值，直接深度遍历就可以求值：
class Solution {
public:
bool vis[220][220];
int rowCount;
int colCount;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int solve(vector<vector<char>>& grid) {
rowCount = grid.size();
colCount = grid[0].size();
// 用来记录岛屿数量
int num_islands = 0;
for (int row = 0; row < rowCount; row++) {
for (int col = 0; col < colCount; col++) {
// 如果当前位置是岛屿的一部分
if (grid[row][col] == '1' && !vis[row][col]) {
// 从当前位置开始执行DFS, 标记整个岛屿
DFS(grid, row, col);
// 岛屿数量增加
num_islands++;
}
}
}
return num_islands;
}
void DFS(vector<vector<char>>& grid, int row, int col) {
// 将当前位置标记为'0', 表示已访问
vis[row][col] = true;
// 检查并递归访问当前点的上下左右四个相邻点
for(int i = 0; i < 4; ++i)
{
int x = row + dx[i];
int y = col + dy[i];
if(x >= 0 && x < rowCount && y >= 0 && y < colCount && !vis[x][y] && grid[x][y] == '1')
DFS(grid, x, y);
}
}
};3.拼三角
链接
因为只有六根棍子，直接排序后分类讨论即可：
我没有经过思考，所有就把所有情况都遍历了，真的很傻的行为，虽然过了，但是很繁琐嘞，太多情况了。
自己代码：
#include <algorithm>
#include <iostream>
#include <vector>
#define int long long
using namespace std;
bool Check(int a, int b, int c)
{
int min1 = min(a, min(b, c)); // 最小
int max1 = max(a, max(b, c)); // 最大
int mid = a + b + c - min1 - max1;
if (min1 + mid <= max1)
return false;
return true;
}
vector<int> v(6);
void solve()
{
for (int i = 0; i < 6; ++i)
{
cin >> v[i];
}
sort(v.begin(), v.end());
if (Check(v[0], v[1], v[2]))
{
if (Check(v[3], v[4], v[5]))
{
cout << "Yes" << endl;
return;
}
}
if (Check(v[1], v[2], v[3]))
{
if (Check(v[0], v[4], v[5]))
{
cout << "Yes" << endl;
return;
}
}
if (Check(v[2], v[3], v[4]))
{
if (Check(v[0], v[1], v[5]))
{
cout << "Yes" << endl;
return;
}
}
if (Check(v[0], v[2], v[5]))
{
if (Check(v[1], v[3], v[4]))
{
cout << "Yes" << endl;
return;
}
}
if (Check(v[0], v[2], v[4]))
{
if (Check(v[1], v[3], v[5]))
{
cout << "Yes" << endl;
return;
}
}
if (Check(v[0], v[2], v[3]))
{
if (Check(v[1], v[4], v[5]))
{
cout << "Yes" << endl;
return;
}
}
if (Check(v[0], v[1], v[3]))
{
if (Check(v[2], v[4], v[5]))
{
cout << "Yes" << endl;
return;
}
}
if (Check(v[0], v[1], v[4]))
{
if (Check(v[2], v[3], v[5]))
{
cout << "Yes" << endl;
return;
}
}
if (Check(v[0], v[3], v[4]))
{
if (Check(v[1], v[2], v[5]))
{
cout << "Yes" << endl;
return;
}
}
if (Check(v[0], v[3], v[5]))
{
if (Check(v[1], v[2], v[4]))
{
cout << "Yes" << endl;
return;
}
}
cout << "No" << endl;
}
signed main() {
int t;
cin >> t;
while (t--)
solve();
}优化代码（只剩四种情况）：
#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;
}因为是排序过后的，所以只需要遍历包含第一个数在内的四种情况即可。
