当前位置 : 主页 > 编程语言 > 其它开发 >

网易互联网笔试(3.27)

来源:互联网 收集:自由互联 发布时间:2022-05-30
网易互联网笔试(3.27) 网易互联网3.27日笔试,四道笔试题一道简答题,四道笔试题AK,简答题考察设计模式不会。 第一道题模拟使用单体技能和群体技能攻击怪物的场景、第二题字符
网易互联网笔试(3.27)

网易互联网3.27日笔试,四道笔试题一道简答题,四道笔试题AK,简答题考察设计模式不会。

第一道题模拟使用单体技能和群体技能攻击怪物的场景、第二题字符串处理、第三题构造具有限制条件的完全二叉树、第四题动态规划问题。

题目 第一题
  • 题意

给定两个怪,分别具有a,b血量;给定两个技能,单体技能伤害为x,群体技能伤害为y。单体技能同时只能攻击一个怪物,群体技能可同时攻击两个怪物。问给定a、b、x、y时,最少的攻击次数。

  • 临场思路

问题的关键在于什么时候使用单体技能、什么时候使用群体技能?

临场没有思考清楚这一问题,直接暴力比较三种策略(答案出自这三种策略之一):

  1. 仅使用单体技能
  2. 仅使用群体技能
  3. 先使用群体技能消耗直到一只怪死亡、再使用单体技能带走另一只怪。
第二题
  • 题意

给定一个只包含小写字母的字符串。用户可以不限次标记连续的两个字符,要求标记的两个字符相同或者是大小相邻(值相差1)。标记字符后,可以获取字符具有的分数,a-z分别有1-26分,问最高得分是多少。

  • 临场思路

顺序处理字符串,每次截取一个可标记连续子串,子串任意相邻的两个字符相同或者值大小相差1。子串存在三种情况:

  1. 长度为1:无法标记。
  2. 长度为大于1的偶数:可全部标记,获取所有分数。
  3. 长度为大于1的奇数:需要选择一个字符放弃标记,选择的原则是该字符左右两边子串长度为偶数,且为满足这一条件的最小值。最后获取所有标记字符的分数。
第三题
  • 题意

给定1-n编号的n个节点,要求构造完全二叉树,但存在一个限制条件。限制条件是,每个节点(除父节点)编号与其父节点编号的乘积为偶数。

  • 临场思路

经模拟3节点、4节点、5节点等简单情况,发现内节点编号均为偶数,叶子节点均为奇数。然后直接两遍遍历1-n,第一遍输出所有偶数,第二遍输出所有奇数。

第四题
  • 题意

给定一片n*m的矩阵沼泽地,需要从(0,0)位置移动到(n,m)位置,运行向左、下、右三个方向移动,并且移动会有代价,问最小代价是多少?移动代价计算方式为,若相同地型之间移动,代价为1;若在不同地形之间移动,代价为2。

  • 临场思路

典型的dp问题。

定义二维数组dp[n][m],dp[i][j]表示移动到位置(i,j)的最小代价。

可以从左、上、右三个相邻格子移动到(i,j)位置,考虑到从右边移动到(i,j)代价必定高于从上方移动,还剩下两种情况。递推公式为:dp[i][j]=min(dp[i-1][j],dp[i][j-1])(此公式仅表示状态之间的依赖关系)。

代码 第一题
#include "bits/stdc++.h"

using namespace std;

int method1(int a, int b, int x, int y);
int method2(int a, int b, int x, int y);
int method3(int a, int b, int x, int y);

int main()
{
	int a, b;
	int x, y;
	cin >> a >> b >> x >> y;

	int cnt = INT_MAX;
	cnt = min(cnt, method1(a, b, x, y));
	cnt = min(cnt, method2(a, b, x, y));
	cnt = min(cnt, method3(a, b, x, y));

	cout << cnt << endl;
	return 0;
}

int method1(int a, int b, int x, int y)
{
	int cnt = (a + x - 1) / x + (b + x - 1) / x;
	return cnt;
}

int method2(int a, int b, int x, int y)
{
	int cnt = 0;
	int low = min(a, b);
	int high = max(a, b);
	cnt += (low + y - 1) / y;
	cnt += (high - cnt * y + x - 1) / x;
	return cnt;
}

int method3(int a, int b, int x, int y)
{
	int cnt = max((a + y - 1), (b + y - 1)) / y;
	return cnt;
}
第二题
#include "bits/stdc++.h"

using namespace std;

int main()
{
	string str;
	cin >> str;

	int score = 0;
	int i = 0;
	while (i < str.size()) {
		int j = i + 1;
		while (j < str.size() && (str[j] == str[j - 1] || abs(str[j] - str[j - 1]) == 1))
			j++;
		for (int k = i; k < j; k++)
			score = score + str[k] - 'a' + 1;

		if ((j - i) % 2 == 1) {
			char min_char = 'z';
			for (int k = i; k < j; k++) {
				if ((k - i) % 2 == 0 && str[k] < min_char)
					min_char = str[k];
			}
			score = score - (min_char - 'a' + 1);
		}
		i = j;
	}

	cout << score << endl;

	return 0;
}
第三题
#include "bits/stdc++.h"

using namespace std;

int main()
{
	int n;
	cin >> n;
	for (int i = 2; i <= n; i += 2) {
		cout << i << ' ';
	}
	for (int i = 1; i <= n; i += 2) {
		cout << i << ' ';
	}

	return 0;
}
第四题
#include "bits/stdc++.h"

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;

	vector<vector<int>> board(n, vector<int>(m));
	vector<vector<int>> dp(n, vector<int>(m, INT_MAX));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
		}
	}

	dp[0][0] = 0;
	for (int j = 1; j < m; j++) {
		dp[0][j] = dp[0][j - 1] + (board[0][j] == board[0][j - 1] ? 1 : 2);
	}
	for (int i = 1; i < n; i++) {
		dp[i][0] = dp[i - 1][0] + (board[i][0] == board[i - 1][0] ? 1 : 2);
	}
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			dp[i][j] = min(dp[i][j], dp[i - 1][j] + (board[i - 1][j] == board[i][j] ? 1 : 2));
			dp[i][j] = min(dp[i][j], dp[i][j - 1] + (board[i][j - 1] == board[i][j] ? 1 : 2));
		}
	}

	cout << dp[n - 1][m - 1] << endl;

	return 0;
}
上一篇:数据结构 - (1)顺序表
下一篇:没有了
网友评论