笔试专题（三）

字符串中找出连续最长的数字串

题目链接

题解

1. 考察双指针 + 模拟
2. 算法思路：给定一个i = 0，让i++，如果遇到数字字符就创建一个变量j = i，让j去遍历，如果j下标的字符是数字字符就持续遍历，如果遇到字母就停止，记录下数字字符开始的下标和数字字符的长度，然后让j赋值给i，继续让i去找数字字符

代码

#include <iostream>
#include<string>
using namespace std;

int main()
{
   string s;
   cin >> s;
   int n = s.size();
   int begin = 0,len = 0;
   for(int i = 0;i < n;i++)
   {
       if(s[i] >= '0' && s[i] <= '9')
       {
            int j = i;
            // j < n防止越界
            while(j < n && s[j] >= '0' && s[j] <= '9') j++;
            if(j - i > len)
            {
                begin = i;
                len = j - i;
            }
            i = j;
       }
   }

   cout << s.substr(begin,len) << '\n';

   return 0;
}

拼三角

题目链接

题解

1. 考察枚举，两边之和大于第三边
2. 解法一可以使用三层for循环和check判断，解法二可以使用dfs判断，解法三是对枚举的优化
3. 解法三：一共有20中情况，但是会出现重复的情况比如012 - 345，这样就少了一半，就只有10中情况了，优化的解法可以先排序，分为下图的10种情况，第一列的012 - 345如果成立，那么后面的就不需要判断了，如果不成立，根据单调性如果 0 + 1 < 2的，那么后面的 0 + 1 < 3的，后面的也是如此

代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

// 解法一:利用单调性的解法
bool check(vector<int> ret)
{
    if(ret[0] + ret[1] > ret[2] && ret[3] + ret[4] > ret[5] ||
      ret[0] + ret[2] > ret[3] && ret[1] + ret[4] > ret[5] ||
      ret[0] + ret[3] > ret[4] && ret[1] + ret[2] > ret[5] ||
      ret[0] + ret[4] > ret[5] && ret[1] + ret[2] > ret[3]
      )
        return true;
    
    return false;
}
int main()
{
    vector<int> ret(6);
    int t;
    cin >> t;
    while(t--)
    {
        for(int i = 0;i < 6;i++) cin >> ret[i];
        sort(ret.begin(),ret.end());
        if(check(ret)) cout << "Yes" << '\n';
        else cout << "No" << '\n';
    }

    return 0;
}