C++笔试强训day7

目录

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;
}

因为是排序过后的，所以只需要遍历包含第一个数在内的四种情况即可。