算法解题报告2019

张天宇 on 2019-08-22

本文主要收录了最近做过的2019年大厂秋招笔试题,包括华为、网易C++、网易雷火、Zoom、美团、小米等,其他暂未整理收录。不定期更新。

2019-07-31-华为-笔试

1.强迫症卖家

题目描述:
  1. 小明有10000台设备,以每台D价格卖出去。

  2. 不求数量,只求每台价格最接近D。

  3. 他只收整数钱。

解题思路:

剪枝。

代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//by 张天宇
#include<iostream>
#include <cmath>
#include<cstdio>
#include<string>
using namespace std;
int main(){
double d,tmp=10,minc=100000,t=100000000,resu;
int m,n,mc,nc, p;
cin>>d;
for (int j=1;j<=10000;j++){
t=100000000;
for (int i=d*j;i<=10000*d;i++){
tmp=(double)i/j;
resu=fabs(tmp-d);
if (resu>t){
break;
}
else{
t=resu;
}
if (resu<fabs(minc-d)){
mc=i;
nc=j;
minc=tmp;
}
}
}
cout<<mc<<" "<<nc<<endl;
}

2019-08-03-网易C+±笔试

1.辗转相除

题目描述:

求解超大范围的最大公约数。a最大100000位,b最大18位。

代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//by 黎
import java.math.BigInteger;
import java.util.Scanner;

public class test {
public static void main(String[] args) {
String s1, s2;
Scanner sc = new Scanner(System.in);
s1 = sc.next();
s2 = sc.next();
BigInteger b1 = new BigInteger(s1);
BigInteger b2 = new BigInteger(s2);
BigInteger b3;
if(b1.compareTo(b2) < 0) {
b3 = b1; b1 = b2; b2 = b3;
}
System.out.println(b1.gcd(b2));
}
}

2.按位OR

题目描述:
  1. 输入M、N,包含两种情况,如果M为1代表将N插入到集合;M为2代表集合中是否存在一个和子集,满足子集中所有数字的Or值恰好为k。
  2. 输出YES或者NO,输入的数据均小于等于100000。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 寻找贡献位
#include<bits/stdc++.h>
using namespace std;
int p[131072] ;
int mx = 131071 ;
int q ;
int main()
{
scanf("%d",&q) ;
while(q--) {
int op , x;scanf("%d%d",&op,&x) ;
if(op == 1) {
if(p[x] == x) continue ;
int s = mx ^ x;
for(int i = s ; i ; i = (i - 1) & s) {
p[i ^ x] |= x ;
}
p[x] = x;
}
else {
if(p[x] == x) puts("YES") ;
else puts("NO");
}
}
return 0;
}

3.优秀序列

题目描述:
  1. 定义一个优秀序列为:①S、T优秀,那么S+T优秀;②S如果优秀,各位取反去掉前导0也是优秀的。

  2. 给一个优秀的S,判断T是否优秀。

解题思路:

每次从T中剔除S或者S取反,如果剩下的也是优秀,那么T就是优秀。

代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 卢
def reverse(s):
rs = ''.join([str(1 - int(i)) for i in s])
if int(rs) == 0:
return rs
else:
return rs.lstrip('0')


def check(t: str, process):
if t == '':
return True
result = False
for p in process:
if t.startswith(p) and check(t[len(p):], process):
return True
return result


n = int(input())
for _ in range(n):
s = input()
t = input()
process = []
while s not in process:
process.append(s)
s = reverse(s)
# process = process[-2:]
if check(t, process):
print('YES')
else:
print('NO')

4.参考:

http://m.nowcoder.com/discuss/216237

2019-08-04-网易雷火-笔试

1.模拟鼠标点击

题目描述:
  1. 每个窗口大小不一样,也可能超出屏幕。
  2. 按照打开顺序输入窗口坐标,左上角坐标及宽高,ID从1开始。
  3. 对于每次鼠标点击,输出窗口ID,出界了输出-1。
解题思路:
  1. 从最新的往后遍历,找到后放到最前面。前面所有端口优先级减一,然后按照优先级再排序。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// by 黎
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXW 3840
#define MAXH 2160
struct st{
int id; //id
int x;
int y; //坐标
int w; //宽
int h; //高
int p; //优先级
} s[1005];
int n, m;
void init(int n){
for (int i = 0; i < n; ++i){
cin >> s[i].x >> s[i].y >> s[i].w >> s[i].h;
s[i].p = i;
s[i].id = i + 1;
}
}
bool compare(st a, st b){
return a.p < b.p;
}
bool check(int x, int y){
if (x < 0 || x > MAXW || y < 0 || y > MAXH){
return false;
}
for (int i = n - 1; i >= 0; --i){
if (x >= s[i].x && x <= s[i].x + s[i].w && y >= s[i].y && y <= s[i].y + s[i].h){
for (int j = i + 1; j < n; ++j){
s[j].p--;
}
s[i].p = n - 1;
cout << s[i].id << endl;
sort(s, s + n, compare);
return true;
}
}
return false;
}
int main(){
int x, y;
cin >> n >> m;
init(n);
for (int i = 0; i < m; ++i){
cin >> x >> y;
if (!check(x, y)){
cout << "-1" << endl;
}
}
}

2.Stern-Brocot Tree

题目描述:

给定一种树,见文末,还有他的构造方法。求输入分子分母后该数的位置。

解题思路:
  1. 按照题目格式直接构造即可。由于数据量不大,可以考虑直接打表查询。

  2. 前两列作为基础线直接加进去,边界元素单独处理,后面使用递推式递推,注意1/2、1/1等特殊元素的位置,index*2就好。

踩坑:
  1. 分子和分母虽然说1000以内,但是也说明了整个树最多十三行,所以数据规模其实很小。

  2. 每一行的数据个数是2的n次方,没认真读题,第1000行时候数据量非常大。前几次提交的代码都内存爆掉了。

  3. 开始以为是法雷序列,但是第四行出现了大于4的元素5,因此不属于法雷序列,只能使用递推式构造。

代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//by 张天宇
#include<iostream>
#include <math.h>
using namespace std;
#define nnn 8195
struct A{
int a,b;
}num[13][nnn];
int main(){
num[1][1].a=0;num[1][1].b=1;
num[1][2].a=1;num[1][2].b=1;
num[2][1].a=0;num[2][1].b=1;
num[2][2].a=1;num[2][2].b=2;
num[2][3].a=1;num[2][3].b=1;
num[2][4].a=2;num[2][4].b=1;
for (int i=3;i<13;i++){
for (int j=1;j<=pow(2,i);j++){
if (j==1){
num[i][j].a=0;
num[i][j].b=1;
}
else if (j==2){
num[i][j].a=1;
num[i][j].b=i;
}
else if (j==pow(2,i)){
num[i][j].a=i;
num[i][j].b=1;
}
else if (j%2==1){
num[i][j].a=num[i-1][(j+1)/2].a;
num[i][j].b=num[i-1][(j+1)/2].b;
}
else {
num[i][j].a=num[i-1][j/2].a+num[i-1][j/2+1].a;
num[i][j].b=num[i-1][j/2].b+num[i-1][j/2+1].b;
}
}
}
int p,q;
cin>>p>>q;
if (p==1&&q==1)
cout<<1<<" "<<1<<endl;
else if (p==1)
cout<<q<<" "<<1<<endl;
else if (q==1)
cout<<p<<" "<<pow(2,p-1)<<endl;
else
for (int i=1;i<13;i++){
for (int j=1;j<=pow(2,i);j++){
if (num[i][j].a==p && num[i][j].b==q){
cout<<i<<" "<<j/2<<endl;
return 0;
}
}
}
}
参考:

Stern-Brocot Tree

3.安保函数测试

题目描述:

根据输出结果实现函数。

解题思路:

使用给出的程序得出样例,进行拟合,得到函数,计算并输出。

代码:
1
2
3
4
5
6
7
8
9
10
11
// 96%
#include <iostream>
using namespace std;
int main() {
double x;
while (cin >> x) {
double t = (((40.371000443862030 * x - 36.819003817396109) * x + 0.378003118162729) * x + 0.385499228352909) * x + 3.052100046401021;
printf("%.6f\n", t);
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# 测试对,未AC,可能是没写while
# by 豪
import numpy as np
x = [0.00,0.01,0.02,0.03,0.04,0.05,0.06,0.07,0.08,0.09,0.10,
0.11,0.12,0.13,0.14,0.15,0.16,0.17,0.18,0.19,0.20,
0.21,0.22,0.23,0.24,0.25,0.26,0.27,0.28,0.29,0.30,
0.31,0.32,0.33,0.34,0.35,0.36,0.37,0.38,0.39,0.40,
0.41,0.42,0.43,0.44,0.45,0.46,0.47,0.48,0.49,0.50,
0.51,0.52,0.53,0.54,0.55,0.56,0.57,0.58,0.59,0.60,
0.61,0.62,0.63,0.64,0.65,0.66,0.67,0.68,0.69,0.70,
0.71,0.72,0.73,0.74,0.75,0.76,0.77,0.78,0.79,0.80,
0.81,0.82,0.83,0.84,0.85,0.86,0.87,0.88,0.89,0.90,
0.91,0.92,0.93,0.94,0.95,0.96,0.97,0.98,0.99]
y= [3.052100,3.055956,3.059673,3.063044,3.065872,
3.067970,3.069161,3.069278,3.068161,3.065665,
3.061648,3.055984,3.048551,3.039242,3.027956,
3.014604,2.999104,2.981386,2.961389,2.939061,
2.914361,2.887258,2.857728,2.825759,2.791348,
2.754502,2.715238,2.673581,2.629567,2.583243,
2.534662,2.483891,2.431003,2.376083,2.319225,
2.260533,2.200119,2.138108,2.074631,2.009832,
1.943862,1.943862,1.809066,1.740593,1.671655,
1.602452,1.533194,1.464102,1.395405,1.327342,
1.260162,1.194125,1.129498,1.066559,1.005596,
0.946908,0.890800,0.837589,0.787603,0.741177,
0.698658,0.660400,0.626769,0.598141,0.574899,
0.557438,0.546162,0.541485,0.543831,0.553631,
0.571330,0.597379,0.632242,0.676388,0.730301,
0.794471,0.869399,0.955597,1.053583,1.163889,
1.287054,1.423626,1.574166,1.739242,1.919432,
2.115326,2.327520,2.556621,2.803247,3.068025,
3.351591,3.654594,3.977686,4.321535,4.686815,
5.074211,5.484419,5.918145,6.376099,6.859006]
x = np.array(x)
y = np.array(y)
f1 = np.polyfit(x, y, 10)
p1 = np.poly1d(f1)
# print('p1 is :\n',p1)
while True:
xx = input()
xxx = float(xx)
m = p1(xxx)
mm = round(m,6)
print(mm)

2019-08-17-Zoom-笔试

1.移动距离

题目描述:

X星球居民小区的楼房全是一样的,并且按矩阵样式排列。其楼房的编号为1,2.3…。当排满行时,从下一行相邻的楼往反方向排号。比如:当小区排号宽度为6时,开始情形如下:
1 2 3 4 5 6
12 11 10 9 8 7
13 14 15
我们的问题是:已知了两个楼号m和n,需要求出它们之间的最短移动距离(不能斜线方向移动)。

代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
int abs(int i){
if (i < 0){ //求绝对值
return (-1 * i);
}
else{
return i;
}
}
int main(){
int m, n, w;
int i1, j1, i2, j2; //m的坐标为(i1,j1),n的坐标为(i2,j2)
scanf("%d %d %d", &w, &m, &n);

int a[100][w];
i1 = (m - 1) / w;
i2 = (n - 1) / w;
if (i1 % 2 == 0){
j1 = m - w * i1 - 1;
}
else{
j1 = w - m + w * i1;
}
if (i2 % 2 == 0){
j2 = n - w * i2 - 1;
}
else{
j2 = w - n + w * i2;
}
printf("%d\n", abs(i1 - i2) + abs(j1 - j2));
return 0;
}

2.算法Frequency

题目描述:

编写一个算法frequency,统计一个输入字符串中各个不同字符出现的频度,按出现频度由高到低的顺序组成新的
字符串并输出。
输入字符串的长度最长: 1024
输入描述:程序输入为一个字符串
输出描述:输出也为一个字符串

代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <stdlib.h>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
void BubbleSort(int *p, int length, int *ind_diff){
for (int m = 0; m < length; m++){
ind_diff[m] = m;
}
for (int i = 0; i < length; i++){
for (int j = 0; j < length - i - 1; j++){
if (p[j] < p[j + 1]){
float temp = p[j];
p[j] = p[j + 1];
p[j + 1] = temp;

int ind_temp = ind_diff[j];
ind_diff[j] = ind_diff[j + 1];
ind_diff[j + 1] = ind_temp;
}
}
}
}

int main(){
int a[128] = {0};
int ind[128] = {0};
string s;
cin >> s;
for (int i = 0; i < s.length(); i++){
a[s[i]]++;
}
BubbleSort(a, 128, ind);
for (int j = 0; j < 128; j++){
if (a[j]){
cout << (char)ind[j];
}
}
cout << endl;
return 0;
}

2019-08-22-美团-笔试

1.美团骑手包裹区间分组

题目描述:

将字符串切割分组,使得每个组内的字母不在其他组内出现,返回每个组的长度。

解题思路:

统计每个字母第一次出现的下标和最后一次出现的下标的,就可以得到每个字母的区间范围,然后合并这些区间范围。

代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def part(S):
sstr = []
for i in range(0, 26):
if S.count(chr(ord("A") + i)):
sstr.append( [S.find(chr(ord("A") + i)), S.rfind(chr(ord("A") + i))] )
sstr = sorted(sstr, key=lambda x: x[0])
left = sstr[0][0]
right = sstr[0][1]
res = list()
for sssstr in sstr:
if sssstr[0] <= right:
right = max(right, sssstr[1])
else:
res.append([left, right])
left = sssstr[0]
right = sssstr[1]

res.append([left, right])
return [sssstr[1] - sssstr[0] + 1 for sssstr in res]


if __name__ == "__main__":
a = input()
resu = part(a)
for rr in resu:
print(rr, end=' ')

2.最小唯一前缀

题目描述:

给定一些字符串,逗号隔开,寻找能够唯一确定该字符串的最小前缀。

解题思路:
  1. 对所有单词进行排序,使得长得相近的单词靠在一起。
  2. 取出其中的一个单词,获取左右相邻的两个单词与本身的公共前缀。
  3. 两个公共前缀,最长的那个公共前缀的长度加上 1,就是本身单词的,最短唯一前缀。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import os


def tmp(strr):
meituan = strr.copy()
meituan.sort()
n, res = len(meituan), []
left, right = 0, 0
for i, v in enumerate(meituan):
if i + 1 < n:
right = len(os.path.commonprefix([v, meituan[i + 1]]))
l = max(left, right)
res.append([v, v[0:l + 1]])
left, right = right, 0
result = []
for www in strr:
for rrr in res:
if rrr[0] == www:
result.append(rrr[1])
return result


if __name__ == '__main__':
w = input()
sssss = w.split(",")
res = tmp(sssss)
print(",".join(str(v) for v in res))

2019-09-07-小米-笔试

1.二叉树

题目描述:

给出一个使用括号嵌套表示的二叉树,如1(2(3,4(,5)),6(7,)),输出该二叉树的中序遍历顺序。

解题思路:

建立二叉树,并中序输出。

代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <vector>
#include <numeric>
#include <limits>
#include <stack>
#include <stdlib.h>
#include <list>
using namespace std;
typedef struct node{
int data;
struct node *lchild;
struct node *rchild;
}BTNode;
//根据嵌套括号表示法的字符串生成链式存储的二叉树
void create2(BTNode *&root,string str){
root=NULL;
BTNode *p;
int i=0,k=0;
stack<BTNode*> s;
char ch=str[i];
while(ch!='\0'){
switch(ch){
case '(':{
s.push(p);
k=1; //下次添加左孩子节点
break;
}
case ',':{
k=2; //下次添加右孩子节点
break;
}
case ')':{
s.pop();
break;
}
default:{
p=(BTNode*)malloc(sizeof(BTNode));
p->lchild=p->rchild=NULL;
p->data=ch;
if(root==NULL)
root=p;
else{
if(k==1){
s.top()->lchild=p;
}else if(k==2)
s.top()->rchild=p;
}
break;
}
}
ch=str[++i];
}

}
//中序遍历
void inorder(node *root, vector<int> &path){
if(root != NULL)
{
inorder(root->lchild, path);
path.push_back(root->data);
inorder(root->rchild, path);
}
}
int main() {
string res;
string _input;
getline(cin, _input);
node *T;
create2(T,_input.c_str());
vector<int> ppp;
inorder(T,ppp);
for (int i=0;i<ppp.size();i++){
cout<<ppp[i]-48;
}
cout<<endl;
return 0;
}

2.类似LeetCode 322 零钱兑换

https://leetcode-cn.com/problems/coin-change/solution/dong-tai-gui-hua-tao-lu-xiang-jie-by-wei-lai-bu-ke/