網易2018春招筆試編程題題目及參考代碼

作者：NotDeep

鏈接：https://www.nowcoder.com/discuss/70736?type=0&order=0&pos=17&page=1

來源：牛客網

題目練習地址：

https://www.nowcoder.com/test/9763997/summary

參考代碼：

一、牛牛的鬧鐘

分析

對於每一個鬧鐘，計算x分鐘後的時間，和上課時間進行比較，如果不超過上課時間，把鬧鐘時間和保存的答案進行比較，取最晚。

時間複雜度

O(n)

參考代碼

#include <bits/stdc++.h>using namespace std;int h[105], m[105];int main() {int n, x;int ans1 = 0, ans2 = 0, temp1, temp2;int a, b;scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%d%d", &h[i], &m[i]);scanf("%d", &x);scanf("%d%d", &a, &b);for(int i = 0; i < n; i++) {temp2 = m[i] + x;temp1 = h[i] + temp2 / 60;temp2 = temp2 % 60;if(temp1 < a || (temp1 == a && temp2 <= b)) {if(h[i] > ans1 || (h[i] == ans1 && m[i] > ans2)) {ans1 = h[i];ans2 = m[i];}}}printf("%d %d
", ans1, ans2);return 0;}

二、迷路的牛牛

分析

統計一共向左和向右轉了多少次，計算最後的方向相對於初始方向的差異，模擬即可。

時間複雜度

O(n)

參考代碼

#include <bits/stdc++.h>using namespace std;char s[1005];int main() {int now = 0, n;scanf("%d", &n);scanf("%s", s);for(int i = 0; i < n; i++) {if(s[i] == L)now--;elsenow++;}now = (now % 4 + 4) % 4;if(now == 0)printf("N
");else if(now == 1)printf("E
");else if(now == 2)printf("S
");elseprintf("W
");return 0;}

三、安置路燈

分析

貪心。

對於一個需要照亮的位置的右邊一格放置一個路燈就好了。

時間複雜度

O(n)

參考代碼

#include <bits/stdc++.h>using namespace std;int n;char s[1005];int main() {int t;scanf("%d", &t);while(t--) {scanf("%d", &n);scanf("%s", s);int ans = 0;for(int i = 0; i < n; i++) {if(s[i] == X) continue;if(s[i] == .) ans++;i += 2;}printf("%d
",ans);}return 0;}

四、被3整除

分析

手算一下會發現規律。

三個數為一組,第一個數不能被3整除,另外兩個可以被3整除。

於是把區間端點都移到某組的開端,記錄移動過程中滿足的數, 之後就可以通過(b - a) / 3 * 2快速計算。

時間複雜度

O(1)

參考代碼

#include <bits/stdc++.h>using namespace std;int main() {int l, r;scanf("%d%d", &l, &r);int cnt1 = 0, cnt2 = 0, cnt = 0;if(l % 3 == 2 || l % 3 == 0) cnt++;if(r % 3 == 2 || r % 3 == 0) cnt++;while(l % 3 != 1) {if(l % 3 == 2 || l % 3 == 0) cnt1++;l--;}while(r % 3 != 1) {if(r % 3 == 2 || r % 3 == 0) cnt2++;r++;}cnt += (r - l) / 3 * 2;printf("%d
", cnt - cnt1 - cnt2);return 0;}

五、數對

分析

對於一個b, n範圍內的數模b的序列應該是:

0,1,2,...,b-1, 0, 1, 2,..., b-1,...0,1,2,..n%b

前面部分是個循環節,所以可以通過(n / b) * max(0, b - k)計算。

後面部分是max(0, n % b - k + 1),

於是我們枚舉合法的b計算就可以了。

k = 0的情況特判處理。

時間複雜度

O(n)

參考代碼

#include <bits/stdc++.h>using namespace std;int main() {int n, k;cin >> n >> k;if(k == 0) cout << 1LL * n * n << endl;else {long long ans = 0;for(int i = k + 1; i <= n; i++){ans += (n / i) * (i - k);if(n % i >= k) ans += n % i - k + 1;}cout << ans << endl;}return 0;}

六、矩形重疊

分析

分別枚舉所有的橫縱坐標,挨著判斷每個矩形是否符合條件，計數維護最大即可。

時間複雜度

O(n^3)

參考代碼

#include <bits/stdc++.h>using namespace std;const int maxn = 50 + 5;int X1[maxn], Y1[maxn];int X2[maxn], Y2[maxn];set<int> xx, yy;int main() {int n;cin >> n;for(int i = 0; i < n; i++) {cin >> X1[i];xx.insert(X1[i]);}for(int i = 0; i < n; i++) {cin >> Y1[i];yy.insert(Y1[i]);}for(int i = 0; i < n; i++) {cin >> X2[i];xx.insert(X2[i]);}for(int i = 0; i < n; i++) {cin >> Y2[i];yy.insert(Y2[i]);}int ans = 0;for(int x : xx) {for(int y : yy) {int cnt = 0;for(int i = 0; i < n; i++) {if(X1[i] <= x && Y1[i] <= y && X2[i] > x && Y2[i] > y) cnt++;}ans = max(ans, cnt);}}cout << ans << endl;return 0;}

七、牛牛的背包問題

分析

容量太大,沒辦法dp。

看到物品數量是30,直接爆搜也不行。。

於是對半分成兩部分枚舉之後,二分計算貢獻。

當然用個map來做個map版本的背包也是茲磁的吧？

時間複雜度

O(2^(n/2) * log(2^(n/2)))

參考代碼

#include <bits/stdc++.h>using namespace std;typedef long long LL;LL v[35];vector<LL> val1, val2;int n, w;void calc(LL *item, int mx, vector<LL> &val){for(int i = 0; i < mx; i++){LL sum = 0;for(int j = 0; j < 20; j++){if(i & (1 << j)){sum += item[j];if(sum > w) break;}}if(sum <= w) val.push_back(sum);}}int main() {val1.clear();val2.clear();scanf("%d%d", &n, &w);for(int i = 0; i < n; i++) scanf("%lld", &v[i]);calc(v, 1 << (n / 2), val1);calc(&v[n - (n + 1) / 2], 1 << (n - n / 2), val2);sort(val2.begin(), val2.end());LL ans = 0;for(int i = 0; i < val1.size(); i++){ans += upper_bound(val2.begin(), val2.end(), w - val1[i]) - val2.begin();}printf("%lld
", ans);return 0;}

八、牛牛找工作

分析

實際上對於每個難度的工作，只有報酬最高的那一種是可能成為答案的，剩下的都可以無視。

由於只有N項工作和M個小夥伴，最多只會出現N+M種難度(能力值)，所以可以把難度和能力值映射到不超過N+M個數上(std通過排序+map來完成)。

對這些難度(能力值)分別求出最高的報酬，再按i從小到大的順序維護難度(能力值)不超過i的最大報酬。最後輸出每個小夥伴對應的能力值以下的最高報酬即可。

時間複雜度

O((N+M)*log(N+M))

參考代碼

#include <bits/stdc++.h>using namespace std;map<int,int> mp;int cnt = 0;int ans[200005];int d[100005], p[100005];int val[200005];int a[100005];int main() {int n, m;scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) {scanf("%d%d", &d[i], &p[i]);val[i] = d[i];}for(int i = 1; i <= m; i++) {scanf("%d", &a[i]);val[i + n] = a[i];}sort(val + 1, val + 1 + n + m);for(int i = 1; i <= n + m; i++) {if(val[i] != val[i - 1]) {cnt++;mp[val[i]] = cnt;}}for(int i = 1; i <= n; i++) ans[mp[d[i]]] = max(ans[mp[d[i]]], p[i]);for(int i = 2; i <= n + m; i++) ans[i] = max(ans[i], ans[i - 1]);for(int i = 1; i <= m; i++)printf("%d
", ans[mp[a[i]]]);return 0;}

推薦閱讀：