贝壳找房开发笔试的四道题目。
题目描述
计算绝对值，给出n个正整数，要求找出相邻两个数字中差的绝对值最小的一对数字，如果有相同的，输出最前一对数。
2<n<=100
输入：
为两行，第一行为n，第二行为n个用空格符分开的正整数。
输出：
一行两个正整数，要求按照原来的顺序输出
#思路
很暴力。。。
#code
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n;
cin>>n;
pair<int,int>res;
vector<int>nums(n,0);
while(n--)
{
int temp=0;
cin>>temp;
nums[n]=temp;
}
res.first=nums[0];
res.second=nums[1];
int min_res=abs(nums[1]-nums[0]);
for(int i=1;i<nums.size()-1;++i)
{
if(abs(nums[i+1]-nums[i])<min_res)
{
res.first=nums[i];
res.second=nums[i+1];
min_res=abs(nums[i+1]-nums[i]);
}
}
cout<<res.first<<" "<<res.second;
system("pause");
return 0;
}
题目描述
感觉就是求最长严格上升子序列。
#思路
之前在leetcode（第300题）上做过一样的题目，动态规划就可以了。
#code
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int lengthOfLIS(vector<int>& nums) {
if(nums.size()==0)
return 0;
vector<int>res(nums.size(),1);
for(int i=1;i<nums.size();++i)
{
for(int j=0;j<i;++j)
{
if(nums[i]>nums[j])
res[i]=max(res[i],res[j]+1);
}
}
sort(res.begin(),res.end());
return res.back();
}
int main()
{
long n;
cin>>n;
vector<int>nums(n,0);
while(n--)
{
int temp=0;
cin>>temp;
nums[n]=temp;
}
cout<<lengthOfLIS(nums);
system("pause");
return 0;
}
题目描述
举重大赛，要求比赛双方中体重较小值要大于等于较大值的百分之90，问N个人最多进行多少场比赛，任意两个人最多进行一次比赛。
#思路
先排序再二分查找。
#code
//不知道能过多少个，下来之后用二分法写的。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int search(vector<int>&nums,int l,int r,int weight)
{
while(l<=r)
{
int mid=l+((r-l)>>1);
if(weight<nums[mid])
r=mid-1;
else if(weight>nums[mid])
l=mid+1;
else
return mid;
}
return l;
}
int num_of_bisai(vector<int>&nums)
{
if(nums.size()<=1)
return 0;
sort(nums.begin(),nums.end());
int res=0;
for(int i=0;i<nums.size()-1;++i)
{
int j=i+1;
int index=search(nums,j,nums.size()-1,nums[i]*10/9);
if(nums[index]==nums[i]*10/9)
{
while(index<nums.size()&&nums[index]==nums[i]*10/9)
{
index++;
}
index--;
}
else if(nums[index]>nums[i]*10/9)
{
while(index>=j&&nums[index]>nums[i]*10/9)
{index--;}
}
else
{
while(index<nums.size()&&nums[index]<nums[i]*10/9)
{index++;}
index--;
}
if(index-j>0)
res+=index-j+1;
}
return res;
}
int main()
{
long n;
cin>>n;
vector<int>nums(n,0);
while(n--)
{
int temp=0;
cin>>temp;
nums[n]=temp;
}
cout<<num_of_bisai(nums);
system("pause");
return 0;
}
//暴力法，只过了一部分
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int num_of_bisai(vector<double>&nums)
{
if(nums.size()<=1)
return 0;
sort(nums.begin(),nums.end());
int res=0;
for(int i=0;i<nums.size()-1;++i)
{
for(int j=i+1;j<nums.size();++j)
{
if(nums[j] <= (nums[i]*10/9))
res++;
else
break;
}
}
return res;
}
int main()
{
long n;
cin>>n;
vector<double>nums(n,0);
while(n--)
{
double temp=0;
cin>>temp;
nums[n]=temp;
}
cout<<num_of_bisai(nums);
system("pause");
return 0;
}
题目描述
特殊的测试，为保证服务器稳定，请求队列中的请求负荷必须按照先递增后递减的规律（仅递增，仅递减也可以），给你一个请求队列，可以增加负荷值，求最小增加总和并且让队列满足要求。相同的相邻元素不算递增或者递减。
满足条件的队列：
1，2，8，4，3
1，3，5
10
不满足的：
1，2，2，1
2，1，2
12，12
#思路
和leetcode上面有个题目很像，用的贪心算法，看的别人的，没做出来。
#code
long minSum(vector<int>nums) {
if(nums.size()== 1)
return 0;
if(nums.size()== 2&&nums[0] == nums[1])
return 1;
if(nums.size()== 2 && nums[0] != nums[1])
return 0;
vector<int>nums_copy(nums.begin(),nums.end());
int i = 0;
while(i < nums.size()-1 && nums[i] < nums[i+1])
i++;
int j = n-1;
while(j > 0 && nums[j] < nums[j-1])
j--;
//从左到右、从右往左找到满足条件的值。
while(i < j) {//在小的一边做加法，一点点贪心的做，因为只能做加法，所以应该在小的那边做。
if(nums[i] < nums[j]) {//如果nums[i]<nums[j],那么加nums[i+1]的数即可。
if(nums[i+1] < nums[i]+1)//不满足条件，将其修改为前一个元素加一。
nums[i+1] = nums[i]+1;
i++;//i++
} else {
if(nums[j-1] < nums[j]+1)
nums[j-1] = nums[j]+1;//保证递减。
j--;
}
}
// 从前往后不断递减，从后往前不断增加，知道最后i==j,保证数组满足条件。
return accumulate(nums.begin(),nums.end(),0)-accumulate(nums_copy.begin(),nums_copy.end(),0);