9月12日米哈游笔试(平台后端笔试(第二批))
第一题
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int q; cin >> q; stack<int> stk; while (q -- ) { string s; cin >> s; int res = 0; for (char c: s) { if (c == '{') stk.push(0); else if (c == '[') stk.push(1); else { int t = stk.top(); stk.pop(); if (t == 0 && c == ']' || t == 1 && c == '}') res ++ ; } } cout << res << endl; } return 0; }
第二题(用公式更快)
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int q; cin >> q; while (q -- ) { int x; cin >> x; x /= 3; // 12 -> 4 (1, 1, 2) (1, 2, 1) ... int res = 0; for (int i = 1; i <= x - 2; i ++ ) { int d = x - i; res += d - 1; } cout << res << endl; } return 0; }
第三题
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> PII; int g[12][12], a, b, c, d, n = 10, m = 9; bool st[12][12]; int dx[8] = {-2, -3, -3, -2, 2, 3, 3, 2}; int dy[8] = {-3, -2, 2, 3, 3, 2, -2, -3}; int k1x[8] = {0, -1, -1, 0, 0, 1, 1, 0}; int k1y[8] = {-1, 0, 0, 1, 1, 0, 0, -1}; int k2x[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; int k2y[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; int bfs() { queue<PII> q; q.push({a, b}); st[a][b] = true; int lev = 0; while (q.size()) { int len = q.size(); for (int i = 0; i < len; i ++ ) { auto& p = q.front(); q.pop(); int x = p.first, y = p.second; if (x == c && y == d) return lev; for (int j = 0; j < 8; j ++ ) { int _a = x + dx[j], _b = y + dy[j]; int k1a = x + k1x[j], k1b = y + k1y[j]; int k2a = x + k2x[j], k2b = y + k2y[j]; if (_a < 0 || _a >= n || _b < 0 || _b >= m || st[_a][_b] || (k1a == c && k1b == d) || (k2a == c && k2b == d)) continue; q.push({_a, _b}); st[_a][_b] = true; } } lev ++ ; } return -1; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> a >> b >> c >> d; cout << bfs() << endl; return 0; }
系统设计题(忘了考虑保底出货的逻辑,加一个特判应该就可以了)
package main import ( "fmt" "math/rand" "sync" ) var ( N = 10 // 一个玩家抽最多允许10次,同时也是保底次数 P = 0.07 // 中奖概率 M = 6 // 奖品数量 ) const ( status_ok = 0 // 中奖了 status_no = 1 // 非酋了 rand_max = 10000 // 抽奖概率的精确粒度 ) var cnt = make(map[int]int) // 玩家抽了多少次表 var lock = sync.Mutex{} // 互斥锁 var randHit = int(rand_max * P) // 小于这个数就是中奖了 func Lottery(ID int) int { // 加锁 + 退栈时自动解锁 lock.Lock() defer lock.Unlock() // 记录当前玩家抽奖数 _, ok := cnt[ID] if !ok { cnt[ID] = 0 } cnt[ID] ++ // 已经到0了,或者已经参与过N次了,直接返回失败 if M == 0 || cnt[ID] > N { return status_no } // 抽奖 var v = rand.Intn(rand_max) if v < randHit { // 中奖了 M-- // 奖品数减少 fmt.Printf("玩家%d中奖了,他抽了%d次,还剩%d个奖品\n", ID, cnt[ID], M) return status_ok } return status_no } // 测试一下,假如玩家id是从0~9十个人,每个人尝试点击12次 func main() { for i := 0; i < 120; i++ { go Lottery(i % 10) } fmt.Println("米哈游抽奖活动已结束!") }