当前位置：首页 > backend >正文

笔试模拟 day7

backend 2025/7/4 22:25:21

观前提醒：

笔试所有系列文章均是记录本人的笔试题思路与代码，从中得到的启发和从别人题解的学习到的地方，所以关于题目的解答，只是以本人能读懂为目标，如果大家觉得看不懂，那是正常的。如果对本文的某些知识有不同的观点，欢迎讨论。

题目链接：

第一题：登录—专业IT笔试面试备考平台_牛客网【重做】

第二题：岛屿数量_牛客题霸_牛客网

第三题：字符串中找出连续最长的数字串_牛客题霸_牛客网

---------------------------------------------------我是分割线---------------------------------------------------------------

第一题

思路：

读完题目，我们就可以直接提出一种解法，直接三重循环，遍历每一种情况，然后判断不就可以吗？

1）解法一：三重循环

好，所以来思考一下时间复杂度是否可以，可能刷题多的同学反映过来，三重循环，是过不了10^3级的数据的但是我们看这道题，他将六根火柴分为两个三角形，所有我们遍历一半，另一半就出来了，所有六根火柴的需要遍历的组合有10种，所以经过演算，这种O(n^3)的复杂度看着大，但实际上使用实现的可能。

但是这种解法我们是有几个注意的点

题目给出的数据，最大是有10^9，所以我们要使用long long类型来存储数据。
那就是一种优化思路：在正常的判断三角形的过程中，我们要判断三遍，但是如果结合上有序性，我们就可以将三遍化为一边。

2）解法二

在经过解法一后，我们的思路本质是遍历下面的十种情况而已。

但是我们查看十种情况，可以发现如果我们的火柴是有序的，那么被我圈圈的数组有必要判断吗？

我们的回答是没有，因为如果四大组的第一个数组组合，都不满足条件，后面的组合更不可能满足了。

我们以【0，1，2~3，4，5】与【0，1，3~2，4，5】为例。

所以我们的十种数据，直接变为四组数据需要判断。

直接if+else就好。

代码：

//解法一
#include<iostream>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
bool ret=false;bool Judgment(vector<long long> nums,int n)
{bool ret=false;for(int i=0;i<6;i++){for(int j=i+1;j<6;j++){for(int k=j+1;k<6;k++){bool left=false,right=false;long long a=nums[i],b=nums[j],c=nums[k];if(c<a+b) left=true;vector<long long> remain;for (int m = 0; m < 6; ++m) {if (m != i && m != j && m != k) {remain.push_back(m);}}sort(remain.begin(), remain.end());if(nums[remain[0]]+nums[remain[1]]>nums[remain[2]]) right=true;ret |=(left && right);}}}return ret;
}
int main()
{int n=0;cin>>n;vector<long long> nums(6,0);for(int i=0;i<n;i++){cin>>nums[0]>>nums[1]>>nums[2]>>nums[3]>>nums[4]>>nums[5];sort(nums.begin(),nums.end());
//排序数组，保证数组的顺序if(Judgment(nums,6)){printf("Yes\n");}else{printf("No\n");}}return 0;
}//解法二
#include<iostream>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;int main()
{bool flag=false;int n=0;cin>>n;vector<long long> nums(6,0);for(int i=0;i<n;i++){cin>>nums[0]>>nums[1]>>nums[2]>>nums[3]>>nums[4]>>nums[5];sort(nums.begin(),nums.end());if(nums[0]+nums[1]>nums[2] && nums[3]+nums[4]>nums[5]) flag=true;if(nums[0]+nums[2]>nums[3] && nums[1]+nums[4]>nums[5]) flag=true;if(nums[0]+nums[3]>nums[4] && nums[1]+nums[2]>nums[5]) flag=true;if(nums[0]+nums[4]>nums[5] && nums[1]+nums[2]>nums[3]) flag=true;if(flag)printf("Yes\n");elseprintf("No\n");flag=false;}return 0;
}

---------------------------------------------------我是分割线---------------------------------------------------------------

第二题

思路：

一道经典的dfs/bfs题目，无需多言大家直接使用dfs/bfs

这里本人使用dfs，dfs的代码更简洁，这里我们要分析dfs函数的作用，根据题目，dfs函数的作用应该是找到以（i，j）为起点的联通块。

具体实习看代码

代码：

class Solution {int dx[4]={1,-1,0,0};int dy[4]={0,0,1,-1};int m=0,n=0;vector<vector<bool>> check{201,vector<bool>(201,false)};
public:void dfs(vector<vector<char>>& grid,int a,int b){for(int i=0;i<4;i++){int x=a+dx[i],y=b+dy[i];if(x>=0 && x<m && y>=0 && y< n && grid[x][y] == '1' && !check[x][y]){check[x][y]=true;dfs(grid,x,y);}}}int solve(vector<vector<char> >& grid) {m=grid.size(),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' && !check[i][j]){count++;check[i][j]=true;dfs(grid,i,j);}}}return count;}
};

---------------------------------------------------我是分割线---------------------------------------------------------------

第三题

思路：

读完题目，我们就可以发现这是一道比较简单的模拟题，我们需要做的不过是遍历一遍数组，然后记录下遍历过程中长度最大的数字字符串，在本题中我们使用一个变量len与一个ret存放每次遍历到的数组。

代码：

#include <iostream>
#include <string>
using namespace std;int main() {string str;cin >> str;int n = str.size();string ret;string tmp;int Max = 0;for (int i = 0; i < n; i++) {// cout<<str[i]<<endl;if (str[i] >= '0' && str[i] <= '9') {tmp += str[i];} else {if (tmp.size() > Max) {ret = tmp;Max = tmp.size();}tmp.clear();}// cout<<tmp<<endl;}if (tmp.size() > Max) {ret = tmp;Max = tmp.size();}cout << ret << endl;return 0;
}

查看全文

http://www.xdnf.cn/news/6971.html