1.在字符串中找连续最长的数字串题目描述读入一个字符串输出字符串中连续最长的数字串。如果有多个长度相同的最长数字串输出最先出现的那一个。 示例 输入abcd12345ed125ss123456789输出123456789C 完整代码牛客可直接 ACcpp运行#include iostream #include string using namespace std; int main() { string s; cin s; string max_str; // 保存最长数字串 string cur_str; // 当前正在收集的数字串 for (char ch : s) { if (isdigit(ch)) { cur_str ch; } else { // 遇到非数字比较更新最长串 if (cur_str.size() max_str.size()) { max_str cur_str; } cur_str.clear(); } } // 循环结束别忘了最后一段数字串还要比较 if (cur_str.size() max_str.size()) { max_str cur_str; } cout max_str endl; return 0; }思路讲解用两个字符串cur_str遍历收集连续数字max_str记录目前找到最长数字串遍历每个字符是数字 → 追加到cur_str不是数字 → 判断当前串是否更长更新最长串清空当前串⚠️ 重点循环结束后最后一段连续数字还没判断必须再对比一次2.岛屿数量题目大意给你一个由1陆地和0水组成的二维网格请计算网格中岛屿的数量。 岛屿由相邻陆地相连而成相邻指水平 / 竖直方向上下左右斜向不算。思路遇到1→ 找到一座岛计数 1 然后用 DFS / BFS把相连所有陆地标记为水0避免重复访问。C DFS 版本cpp运行#include vector using namespace std; class Solution { public: int numIslands(vectorvectorchar grid) { int m grid.size(); if (m 0) return 0; int 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) { count; dfs(grid, i, j); } } } return count; } void dfs(vectorvectorchar grid, int x, int y) { int m grid.size(); int n grid[0].size(); // 越界 或者 不是陆地直接返回 if (x 0 || x m || y 0 || y n || grid[x][y] ! 1) return; // 标记已访问淹掉陆地 grid[x][y] 0; // 上下左右 dfs(grid, x - 1, y); dfs(grid, x 1, y); dfs(grid, x, y - 1); dfs(grid, x, y 1); } };BFS 版本队列实现cpp运行#include vector #include queue using namespace std; class Solution { public: int numIslands(vectorvectorchar grid) { int m grid.size(); if (!m) return 0; int n grid[0].size(); int cnt 0; // 方向数组 int dirs[4][2] {{-1,0},{1,0},{0,-1},{0,1}}; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { cnt; queuepairint,int q; q.push({i,j}); grid[i][j] 0; while (!q.empty()) { auto [x,y] q.front(); q.pop(); for (auto d : dirs) { int nx x d[0]; int ny y d[1]; if (nx0 nxm ny0 nyn grid[nx][ny]1) { grid[nx][ny] 0; q.push({nx,ny}); } } } } } } return cnt; } };关键点总结不需要额外 visited 数组直接原地修改网格把陆地置0每次碰到未访问陆地岛屿数量 1再扩散清除整片岛屿DFS 递归注意网格极大时可能栈溢出超大矩阵优先 BFS方向数组统一处理上下四个方向代码更简洁。3.拼三角题意给n根木棍长度任选 3 根求能构成三角形的组合总数。 三角形判定优化 三根排序后 \(a\le b\le c\)只需满足 \(\boldsymbol{abc}\)暴力三重循环 \(O(n^3)\)数据量大直接超时最优用排序 双指针 \(O(n^2)\)C AC 代码cpp运行#include iostream #include vector #include algorithm using namespace std; int main() { int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); long long ans 0; // 固定r为最长边下标 for (int r 2; r n; r) { int l 0; int mid r - 1; while (l mid) { if (a[l] a[mid] a[r]) { // l ~ mid-1 全部满足 ans mid - l; mid--; } else { l; } } } cout ans endl; return 0; }思路详解先升序排序循环枚举最长边位置 r左指针l0中间指针midr-1若 \(a[l]a[mid]a[r]\)l到mid-1所有数和a[mid]搭配都成立数量mid-lmid 左移否则和不够l 右移⚠️ 答案要用long long防止数目溢出 int样例测试输入plaintext4 2 2 3 4排序[2,2,3,4]合法三元组(2,2,3)、(2,3,4)、(2,3,4) 输出3暴力写法仅小数据调试不推荐提交cpp运行// O(n³)大数据TLE long long cnt 0; for(int i0;in;i) for(int ji1;jn;j) for(int kj1;kn;k) { int ax[i],bx[j],cx[k]; if(abc) cnt; }谢谢