解题报告

算法解题报告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/




标签
解题报告