網(wǎng)易互聯(lián)網(wǎng)筆試（3.27）

網(wǎng)易互聯(lián)網(wǎng)3.27日筆試，四道筆試題一道簡(jiǎn)答題，四道筆試題AK，簡(jiǎn)答題考察設(shè)計(jì)模式不會(huì)。

創(chuàng)新互聯(lián)建站專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都網(wǎng)站建設(shè)、做網(wǎng)站、米脂網(wǎng)絡(luò)推廣、小程序定制開(kāi)發(fā)、米脂網(wǎng)絡(luò)營(yíng)銷(xiāo)、米脂企業(yè)策劃、米脂品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營(yíng)等，從售前售中售后，我們都將竭誠(chéng)為您服務(wù)，您的肯定，是我們最大的嘉獎(jiǎng)；創(chuàng)新互聯(lián)建站為所有大學(xué)生創(chuàng)業(yè)者提供米脂建站搭建服務(wù)，24小時(shí)服務(wù)熱線：18980820575，官方網(wǎng)址：chinadenli.net

第一道題模擬使用單體技能和群體技能攻擊怪物的場(chǎng)景、第二題字符串處理、第三題構(gòu)造具有限制條件的完全二叉樹(shù)、第四題動(dòng)態(tài)規(guī)劃問(wèn)題。

題目

第一題

• 題意

給定兩個(gè)怪，分別具有a，b血量；給定兩個(gè)技能，單體技能傷害為x，群體技能傷害為y。單體技能同時(shí)只能攻擊一個(gè)怪物，群體技能可同時(shí)攻擊兩個(gè)怪物。問(wèn)給定a、b、x、y時(shí)，最少的攻擊次數(shù)。

• 臨場(chǎng)思路

問(wèn)題的關(guān)鍵在于什么時(shí)候使用單體技能、什么時(shí)候使用群體技能？

臨場(chǎng)沒(méi)有思考清楚這一問(wèn)題，直接暴力比較三種策略（答案出自這三種策略之一）：

1. 僅使用單體技能
2. 僅使用群體技能
3. 先使用群體技能消耗直到一只怪死亡、再使用單體技能帶走另一只怪。

第二題

• 題意

給定一個(gè)只包含小寫(xiě)字母的字符串。用戶可以不限次標(biāo)記連續(xù)的兩個(gè)字符，要求標(biāo)記的兩個(gè)字符相同或者是大小相鄰（值相差1）。標(biāo)記字符后，可以獲取字符具有的分?jǐn)?shù)，a-z分別有1-26分，問(wèn)最高得分是多少。

• 臨場(chǎng)思路

順序處理字符串，每次截取一個(gè)可標(biāo)記連續(xù)子串，子串任意相鄰的兩個(gè)字符相同或者值大小相差1。子串存在三種情況：

1. 長(zhǎng)度為1：無(wú)法標(biāo)記。
2. 長(zhǎng)度為大于1的偶數(shù)：可全部標(biāo)記，獲取所有分?jǐn)?shù)。
3. 長(zhǎng)度為大于1的奇數(shù)：需要選擇一個(gè)字符放棄標(biāo)記，選擇的原則是該字符左右兩邊子串長(zhǎng)度為偶數(shù)，且為滿足這一條件的最小值。最后獲取所有標(biāo)記字符的分?jǐn)?shù)。

第三題

• 題意

給定1-n編號(hào)的n個(gè)節(jié)點(diǎn)，要求構(gòu)造完全二叉樹(shù)，但存在一個(gè)限制條件。限制條件是，每個(gè)節(jié)點(diǎn)（除父節(jié)點(diǎn)）編號(hào)與其父節(jié)點(diǎn)編號(hào)的乘積為偶數(shù)。

• 臨場(chǎng)思路

經(jīng)模擬3節(jié)點(diǎn)、4節(jié)點(diǎn)、5節(jié)點(diǎn)等簡(jiǎn)單情況，發(fā)現(xiàn)內(nèi)節(jié)點(diǎn)編號(hào)均為偶數(shù)，葉子節(jié)點(diǎn)均為奇數(shù)。然后直接兩遍遍歷1-n，第一遍輸出所有偶數(shù)，第二遍輸出所有奇數(shù)。

第四題

• 題意

給定一片n*m的矩陣沼澤地，需要從（0,0）位置移動(dòng)到（n，m）位置，運(yùn)行向左、下、右三個(gè)方向移動(dòng)，并且移動(dòng)會(huì)有代價(jià)，問(wèn)最小代價(jià)是多少？移動(dòng)代價(jià)計(jì)算方式為，若相同地型之間移動(dòng)，代價(jià)為1；若在不同地形之間移動(dòng)，代價(jià)為2。

• 臨場(chǎng)思路

典型的dp問(wèn)題。

定義二維數(shù)組dp[n][m]，dp[i][j]表示移動(dòng)到位置（i，j）的最小代價(jià)。

可以從左、上、右三個(gè)相鄰格子移動(dòng)到（i，j）位置，考慮到從右邊移動(dòng)到（i，j）代價(jià)必定高于從上方移動(dòng)，還剩下兩種情況。遞推公式為：dp[i][j]=min(dp[i-1][j]，dp[i][j-1]）（此公式僅表示狀態(tài)之間的依賴關(guān)系）。

代碼

第一題

#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;
}

網(wǎng)頁(yè)題目：網(wǎng)易互聯(lián)網(wǎng)筆試（3.27）
網(wǎng)站地址：http://chinadenli.net/article36/dsoihsg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App開(kāi)發(fā)、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站改版、小程序開(kāi)發(fā)、網(wǎng)頁(yè)設(shè)計(jì)公司、

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)