目录
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;
}
因为是排序过后的,所以只需要遍历包含第一个数在内的四种情况即可。