网易游戏研发笔试题记录2
发布时间
阅读量：
阅读量
网易有道笔试题（二）
文章目录
-
网易有道笔试题（二）
-
前言
-
一、最多回文数
-
- 1.问题描述
- 2.解决方案
-
二、组合幸运数字
-
- 1.问题描述
- 2.解决方案
-
三、复习0-1背包问题
-
- 1.问题描述
- 2.解决方案
-
总结
前言
准备面游戏研发岗位，特此对算法进行学习
一、最多回文数
1.问题描述
对于给定的一个字符串s，请问其中有多少个长度大于1且连续的子串是回文？回文即为正读和反读完全一致的文字序列（如"aa"、"aba"等）。
2.解决方案
#include<bits/stdc++.h>
using namespace std;
//算法复杂度O(n)
int main()
{
char str[100001];
int i,j,ans,len;
ans = 0;
cin >> str;
len = strlen(str);
for(i=1;i<len;i++){ //从第二个字符开始遍历
//单轴
for(j=1;j<len;j++){
if(i-j>=0 && i+j<len && str[i-j]==str[i+j]){
ans++;
}else{
break;
}
}
//双轴
for(j=0;j<len;j++){
if(i-1-j>=0 && i+j<len && str[i-1-j]==str[i+j]){
ans++;
}else{
break;
}
}
}
cout << ans << endl;
return 0;
}
AI写代码二、组合幸运数字
1.问题描述
小易将他的幸运数字设定为七，请你找出所有能被七整除的子集合，并计算这些子集合的最大总和。若无法找到符合条件的结果，则返回数值-1。
2.解决方案
#include<bits/stdc++.h>
using namespace std;
// 算法复杂度O(n)
int main()
{
int arr[100001];
int i,j,ans;
i = j = 1;
ans = 0;
do
{
cin >> arr[i++];
}while(cin.get() != '\n'); //输入回车结束
// 模拟创建7个priority_queue（优先队列）按值的大小优先
int arr1[i]; int i1;
int arr2[i]; int i2;
int arr3[i]; int i3;
int arr4[i]; int i4;
int arr5[i]; int i5;
int arr6[i]; int i6;
int arr7[i]; int i7;
i1=i2=i3=i4=i5=i6=i7=1;
sort(arr+1,arr+i); //从小到大排序
while(j<i) //将所有数据依次放入桶中
{
if(arr[j]%7==0){
arr7[i7++] = arr[j];
}else if(arr[j]%7==1){
arr1[i1++] = arr[j];
}else if(arr[j]%7==2){
arr2[i2++] = arr[j];
}else if(arr[j]%7==3){
arr3[i3++] = arr[j];
}else if(arr[j]%7==4){
arr4[i4++] = arr[j];
}else if(arr[j]%7==5){
arr5[i5++] = arr[j];
}else if(arr[j]%7==6){
arr6[i6++] = arr[j];
}
j++;
//cout << arr[j++] << endl;
}
//从桶中取出合适的值 1--6 2--5 3--4 两两对应取出
while(--i7>0){
ans += arr7[i7];
}
while(--i6>0&&--i1>0){
ans += (arr6[i6] + arr1[i1]);
}
while(--i5>0&&--i2>0){
ans += (arr5[i5] + arr2[i2]);
}
while(--i4>0&&--i3>0){
ans += (arr4[i4] + arr3[i3]);
}
if(ans == 0){
cout << -1 << endl;
}else{
cout << ans << endl;
}
return 0;
}
AI写代码三、复习0-1背包问题
1.问题描述
给定背包容量、物品重量与价值，选取有限容量内的最大价值的最优解
2.解决方案
#include<bits/stdc++.h>
using namespace std;
/*
0-1 背包问题（迭代版）
输入：
products_count：商品的数量
capacity：背包的容量
weight_array：商品重量数组
value_array：商品价格数组
result：结果数组
*/
int knapsack(int products_count,int capacity,vector<int> &weights,vector<int> &values,vector<vector<int> > &res){
for(int i=1;i<=products_count;i++){//i个物品
for(int j=1;j<=capacity;j++){//背包容量为j
if(weights[i] > j){//当前背包的容量 j 放不下第 i 件商品时
res[i][j] = res[i-1][j];
}else
{
res[i][j] = max( res[i-1][j-weights[i]] + values[i] , res[i-1][j]);
}
}
}
return res[products_count][capacity];
}
int main(){
int products_count,capacity;
int i,j;
cout << "please input products count and knapsack's capacity: " << endl; // 输入商品数量和背包容量
cin>>products_count>>capacity;
vector<int> weights(products_count + 1,0);
vector<int> values(products_count + 1,0);
cout << "please input weight array for " << products_count << " products" << endl;
for(int i=1;i<=products_count;i++)
cin>>weights[i];
cout << "please input value array for " << products_count << " products" << endl;
for(int i=1;i<=products_count;i++)
cin>>values[i];
vector<vector<int> > res(products_count + 1,vector<int> (capacity + 1,0));
knapsack(products_count,capacity,weights,values,res);
cout << "knapsack result is " << res[products_count][capacity] << endl;
for(j=0;j<=capacity;j++){
cout << setw(4) << j << " ";
}
cout << endl;
for(i=0;i<=products_count;i++){
for(j=0;j<=capacity;j++){
cout << setw(4) << res[i][j] << " ";
}
cout << endl;
}
return 0;
}
AI写代码总结
在第二日投入算法学习中后不久, 我决定亲自实践一下, 结果发现自己对图论知识掌握不足, 同时动态规划问题也难以解决, 这让我深感困境. 记录下来, 并打算在明天继续深入研究这个问题, 经过反思总结后发现自己的基础较为薄弱, 尽管如此, 在实践中仍能有所收获和成长, 做出 couple 个相关程序后发现虽然过程曲折但最终还是取得了令人满意的成果! 最初的想法是采用暴力枚举的方法来解决问题, 但很快意识到这种方法的时间复杂度太高（O(n²)）, 立即决定寻求更高效的解决方案——逐步优化到线性时间复杂度（O(n)）的过程中充满了尝试与挑战, 即使经历了波折也感到非常有成就感!
全部评论 (0)
还没有任何评论哟~