米哈游笔试03/27 部分思路+代码
代码不保证完全正确，但思路基本上清晰，仅供参考。
第一道题 最长好子字符序列
输入一个字符串s ，找出最长的子字符串满足1807的顺序（但不能是1087或其他顺序 其中 1 8 0 7 可以重复）
比如 1180080108707 最长的就是118000007或者118000077 也就是长度为9 所以输出9
很多人用dp只能过90%的原因，事后有人发现普通的dp实现导致881807会输出5，但实际应该是4，所以应该提前对字符串做处理，保证1之前没有其他字符。
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
string preprocess(string s) {
string ts = "";
string s1807 = "x1807";
bool find_one = false;
for(int i = 0; i < s.size(); i++) {
if(!find_one && s[i] == '1') {
find_one = true;
}
if(find_one && s1807.find(s[i]) != string::npos) {
ts += s[i];
}
}
return ts;
}
int main() {
string s;
getline(cin, s);
string s1807 = "x1807";
s = preprocess(s);
vector<vector<int>> dp(s.size() + 1, vector<int>(s1807.size(), 0));
for(int i = 0; i < s.size(); i++) {
for(int j = 1; j < s1807.size(); j++) {
if(s[i] == s1807[j]) {
dp[i + 1][j] = max(dp[i][j], dp[i][j-1]) + 1;
} else {
dp[i + 1][j] = dp[i][j];
}
}
}
cout << dp[s.size()][s1807.size() - 1] << endl;
return 0;
} 第二道 小明去游乐园
游乐场有n个项目
每个项目有对应的积分 玩了能获得积分 没玩要扣除相应的积分
求最多能获得多少分
比如
3
3 1 1
3 6 9
3个项目
分别在3点前 1点前 1点前参加 分别的积分是 3 6 9
算上游玩要花的一个小时 其实是要在 2点 0点 0 点 之前去玩
所以样例最多积分是 9+3-6=6分
这道题，个人认为类似 任务调度的题 ，例如 P2949 [USACO09OPEN]Work Scheduling G
首先所有项目按照时间排序，使用堆（优先队列）管理已选的项目，把获利最小的项目放在堆顶，然后如果已选的项目数量（也可以当作已经消耗的时间）和当前比较的项目的时间更短，证明可以直接选择项目（加入堆），否则判断当前项目和堆顶项目谁的获利更大，更大的就加入其中。
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
struct Game {
int t;
int w;
Game(int tt, int tw) : t(tt), w(tw) {};
bool operator<(const Game& other) const {
// 让优先队列从小到大排序
return w > other.w;
}
};
bool t_cmp(const Game& g1, const Game& g2) {
// 按ddl排序
return g1.t < g2.t;
}
void input(int n, vector<Game>& all, vector<int>& ts, vector<int>& ws) {
for(int j = 0; j < n; j++) {
int t;
cin >> t;
ts.push_back(t);
}
for(int j = 0; j < n; j++) {
int w;
cin >> w;
ws.push_back(w);
}
for(int j = 0; j < n; j++) {
all.push_back(Game(ts[j], ws[j]));
}
}
long long max_value_games(const vector<Game>& all) {
long long ans = 0;
priority_queue<Game> take;
for(int i = 0; i < all.size(); i++) {
if(all[i].t <= take.size()) {
if(take.top().w < all[i].w) {
ans = ans - take.top().w * 2 + all[i].w;
take.pop();
take.push(all[i]);
}
} else {
ans += all[i].w;
take.push(all[i]);
}
}
return ans;
}
int main() {
int T;
cin >> T;
for(int i = 0; i < T; i++) {
int n;
cin >> n;
vector<Game> all;
vector<int> ts;
vector<int> ws;
input(n, all, ts, ws);
sort(all.begin(), all.end(), t_cmp);
cout << max_value_games(all) << endl;
}
return 0;
} 第三题 输入两个数字作为左右区间 求区间内 奇数位的和 和 偶数位的和 相等的数字的个数
例如 9-130 有 11 22 33 44 55 66 77 88 99 110 121 等11个 输出11
比如 1221这种就是奇数位和偶数位和相等的数字
暂时没有找到非常好的方法，初步理论是 奇数位和 和 偶数位和 的差值是 11的倍数（包括0倍）的时候，这个数可以被11整除，而题目里面的相等（也就是0倍数）是一个特殊情况， 所以按照11步长递增，判断每个数是不是满足要求。 每个数直接去判断算有点太慢，所以使用数组来模拟进位，并在过程中记录奇数位和偶数位的变换，当没有进位的时候，提前停止，减少复杂度。
#include <iostream>
#include <vector>
using namespace std;
vector<int> i2v(int num) {
vector<int> v(10, 0);
int i = 0;
while(num) {
v[i++] = num % 10;
num /= 10;
}
return v;
}
int count(int l, int r) {
vector<int> v = i2v(l);
int odd_sum = 0;
int even_sum = 0;
int count = 0;
for(int i = 0; i < v.size(); i++) {
if(i & 0x1) {
even_sum += v[i];
} else {
odd_sum += v[i];
}
}
int carry;
int old_value;
for(int i = l; i <= r; i += 11) {
if(even_sum == odd_sum) {
count++;
}
v[0] += 1;
odd_sum += 1;
v[1] += 1;
even_sum += 1;
carry = 0;
for(int j = 0; j < v.size(); j++) {
if(j > 1 && carry == 0) {
break;
}
old_value = v[j];
v[j] = v[j] + carry;
carry = v[j] / 10;
v[j] = v[j] % 10;
if(j & 0x1) {
// 偶数位
even_sum += (v[j] - old_value);
} else {
// 奇数位
odd_sum += (v[j] - old_value);
}
}
}
return count;
}
int main() {
int l, r;
cin >> l >> r;
for(int i = l; i <= r; i++) {
if(i % 11 == 0) {
l = i;
break;
}
}
cout << count(l, r) << endl;
return 0;
} 第四道 由序列化先序遍历求中序遍历
给一个由先序遍历序列化的二叉树（字符串） 求出它的中序遍历（数字）
比如 A
B C
D E
输入“A(B(D,),C(,E))”
输出 DBACE
扣细节，主要思路是 '（ ' 前面的就是根节点，之后的话，使用栈来处理'（' '）'符号，当栈里面只有一个'（' 并且当前字符是 ' ,'，就可以拆分成左右两个子树，然后递归处理即可，记得处理好叶子节点的情况，叶子节点没有'('和')'。#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
vector<string> output;
void mid_order(const string& s, int l, int r) {
if(l >= r) {
return;
}
string o;
stack<char> stk;
bool find = false;
for(int i = l; i < r; i++) {
if(s[i] == '(') {
find = true;
o = s.substr(l, i - l);
for(int j = i; j < r; j++) {
if(s[j] == '(') {
stk.push(s[j]);
} else if(s[j] == ')' && !stk.empty() && stk.top() == '(') {
stk.pop();
} else if(s[j] == ',' && stk.size() == 1) {
mid_order(s, i + 1, j);
output.push_back(o);
mid_order(s, j + 1, r - 1);
break;
}
}
break;
}
}
if(!find) {
o = s.substr(l, r - l);
output.push_back(o);
}
}
int main() {
int t;
cin >> t;
cin.ignore();
for(int i = 0; i < t; i++) {
string s;
getline(cin, s);
output.clear();
mid_order(s, 0, s.size());
for(int i = 0; i < output.size() - 1; i++) {
cout << output[i] << " ";
}
cout << output.back() << endl;
}
return 0;
} 第五题 判断凸多边形
给一系列平面坐标 把他们按输入顺序首尾相连 判断是不是一个凸多边形
tip: 对于边AB BC 如果C在边的同一侧 则这个点满足凸多边形
计算几何，简单暴力的去判断就可以通过，重点在如何判断点在边的那一边，这个和判断一个点是否在三角形内部有异曲同工之处，使用向量叉积的z值符号是否同号来判断，叉积只需要计算z = x1*y2 - x2*y1。#include <iostream>
#include <vector>
using namespace std;
struct Point {
double x, y;
Point(double tx, double ty) : x(tx), y(ty) {};
};
double get_side(Point* p1, Point* p2, Point* p3) {
double x1, x2, y1, y2;
x1 = p3->x - p1->x;
x2 = p2->x - p1->x;
y1 = p3->y - p1->y;
y2 = p2->y - p1->y;
return (x1 * y2 - x2 * y1);
}
bool is_porly(const vector<Point*>& ps) {
for(int i = 0; i < ps.size(); i++) {
double res = 0;
int count = 0;
Point* pi = ps[i], *pj;
int j;
if(i == ps.size() - 1) {
pj = ps[0];
j = 0;
} else {
pj = ps[i + 1];
j = i + 1;
}
for(int k = 0; k < ps.size(); k++) {
if(k == i || k == j) continue;
Point* pk = ps[k];
double side = get_side(pi, pj, pk);
if(count == 0) {
res = side;
} else if(res * side < 0) {
return false;
}
count++;
}
}
return true;
}
int main() {
int T;
cin >> T;
for(int i = 0; i < T; i++) {
int n;
cin >> n;
vector<Point*> ps;
for(int j = 0; j < n; j++) {
double x, y;
cin >> x >> y;
ps.push_back(new Point(x, y));
}
cout << is_porly(ps) << endl;
}
return 0;
} 
投递美团等公司10个岗位