網(wǎng)易互聯(lián)網(wǎng)筆試（3.27）
網(wǎng)易互聯(lián)網(wǎng)筆試（3.27）
網(wǎng)易互聯(lián)網(wǎng)3.27日筆試，四道筆試題一道簡答題，四道筆試題AK，簡答題考察設(shè)計模式不會。
創(chuàng)新互聯(lián)建站專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都網(wǎng)站建設(shè)、做網(wǎng)站、米脂網(wǎng)絡(luò)推廣、小程序定制開發(fā)、米脂網(wǎng)絡(luò)營銷、米脂企業(yè)策劃、米脂品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們最大的嘉獎；創(chuàng)新互聯(lián)建站為所有大學(xué)生創(chuàng)業(yè)者提供米脂建站搭建服務(wù)，24小時服務(wù)熱線：18980820575，官方網(wǎng)址：www.cdcxhl.com
第一道題模擬使用單體技能和群體技能攻擊怪物的場景、第二題字符串處理、第三題構(gòu)造具有限制條件的完全二叉樹、第四題動態(tài)規(guī)劃問題。
題目
第一題
- 題意
給定兩個怪，分別具有a，b血量；給定兩個技能，單體技能傷害為x，群體技能傷害為y。單體技能同時只能攻擊一個怪物，群體技能可同時攻擊兩個怪物。問給定a、b、x、y時，最少的攻擊次數(shù)。
- 臨場思路
問題的關(guān)鍵在于什么時候使用單體技能、什么時候使用群體技能？
臨場沒有思考清楚這一問題，直接暴力比較三種策略（答案出自這三種策略之一）：
- 僅使用單體技能
- 僅使用群體技能
- 先使用群體技能消耗直到一只怪死亡、再使用單體技能帶走另一只怪。
第二題
- 題意
給定一個只包含小寫字母的字符串。用戶可以不限次標(biāo)記連續(xù)的兩個字符，要求標(biāo)記的兩個字符相同或者是大小相鄰（值相差1）。標(biāo)記字符后，可以獲取字符具有的分?jǐn)?shù)，a-z分別有1-26分，問最高得分是多少。
- 臨場思路
順序處理字符串，每次截取一個可標(biāo)記連續(xù)子串，子串任意相鄰的兩個字符相同或者值大小相差1。子串存在三種情況：
- 長度為1：無法標(biāo)記。
- 長度為大于1的偶數(shù)：可全部標(biāo)記，獲取所有分?jǐn)?shù)。
- 長度為大于1的奇數(shù)：需要選擇一個字符放棄標(biāo)記，選擇的原則是該字符左右兩邊子串長度為偶數(shù)，且為滿足這一條件的最小值。最后獲取所有標(biāo)記字符的分?jǐn)?shù)。
第三題
- 題意
給定1-n編號的n個節(jié)點，要求構(gòu)造完全二叉樹，但存在一個限制條件。限制條件是，每個節(jié)點（除父節(jié)點）編號與其父節(jié)點編號的乘積為偶數(shù)。
- 臨場思路
經(jīng)模擬3節(jié)點、4節(jié)點、5節(jié)點等簡單情況，發(fā)現(xiàn)內(nèi)節(jié)點編號均為偶數(shù)，葉子節(jié)點均為奇數(shù)。然后直接兩遍遍歷1-n，第一遍輸出所有偶數(shù)，第二遍輸出所有奇數(shù)。
第四題
- 題意
給定一片n*m的矩陣沼澤地，需要從（0,0）位置移動到（n，m）位置，運(yùn)行向左、下、右三個方向移動，并且移動會有代價，問最小代價是多少？移動代價計算方式為，若相同地型之間移動，代價為1；若在不同地形之間移動，代價為2。
- 臨場思路
典型的dp問題。
定義二維數(shù)組dp[n][m]，dp[i][j]表示移動到位置（i，j）的最小代價。
可以從左、上、右三個相鄰格子移動到（i，j）位置，考慮到從右邊移動到（i，j）代價必定高于從上方移動，還剩下兩種情況。遞推公式為：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> board(n, vector(m));
vector> dp(n, vector(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)頁標(biāo)題：網(wǎng)易互聯(lián)網(wǎng)筆試（3.27）
地址分享：http://m.jiaotiyi.com/article/dsoihsg.html