0%

2018秋招笔试整理

发表于 更新于 分类于 阅读次数： Valine：

2018秋招笔试整理,updated at [2018.8.29],不打算发布了，太多了，之后整理到自己的笔试本

时间记录

华为 笔试 8.8
——华为8.8 大小写字母转化
——华为8.8 小偷偷东西问题
——华为8.8 验证typedef的正确性
网易 笔试 8.11
——网易8.11 丰收
——网易8.11 塔
——网易8.11 整理房间
头条 笔试 8.12
——头条8.12 世界杯开幕式
——头条8.12 文章病句标识
——头条8.12 积分卡牌游戏
——头条8.12 区间最大最小值
——头条8.12 直播爱好者
链家 笔试 8.18
——链家8.18 取消社团预约
——链家8.18 道路修建
——链家8.18 扑克牌
头条 二笔 8.25
——————————
好未来 笔试 8.28
——好未来8.28 拆数字串
——好未来8.28 加与或的关系
——好未来8.28 求给定位置下的数组的排列组合
——好未来8.28 掷骰子
——好未来8.28 求正整数数组的最大升序和
——好未来8.28 字符串字串替换
瓜子 笔试 9.4
携程 笔试 9.4

华为 笔试 8.8

华为8.8 大小写字母转化

1
2
3
4
5
6
7
8
9
10
11
题目描述
输入任意个字符串，将其中的小写字母变为大写，大写字母变为小写，其他字符不用处理；
输入描述:
任意字符串：abcd12#%XYZ
输出描述:
输出字符串：ABCD12#%xyz
示例1
输入
abcd12#%XYZ
输出
ABCD12#%xyz

此题AC。这里看起来很简单,但是有个大坑，输入的时候需要一行输入getline(cin,str),因为可能出现12 12这样的情况，如果直接cin>>str输出则是12换行12,这样就只能过40%了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int main() {
//    freopen("../in.txt", "r", stdin);
    string str;
    while (getline(cin,str)) {
        int len = str.length();
        for (int i = 0; i < len; i++) {
            if (str[i] >= 'a' && str[i] <= 'z') {
                str[i] -= 32;
            } else if (str[i] >= 'A' && str[i] <= 'Z') {
                str[i] += 32;
            }
            cout << str[i];
        }
        cout << endl;
    }
}

华为8.8 小偷偷东西问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
小偷来到了一个神秘的王宫，突然眼前一亮，发现5个宝贝，每个宝贝的价值都不一样，且重量也不一样，但是小偷的背包携带重量
有限，所以他不得不在宝贝中做出选择，才能使偷到的财富最大，请你帮助小偷计算一下。
输入描述:
宝贝价值：6,3,5,4,6
宝贝重量：2,2,6,5,4
小偷背包容量：10
输出描述:
偷到宝贝的总价值：15
示例1
输入
6,3,5,4,6
2,2,6,5,4
10
输出
15

此题AC。这题就是一个背包，这题也坑，输入是用逗号分隔的，C++对于这种IO处理感觉不怎么友好，网上抄了一个分隔，然后套了一下背包模板。

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 <bits/stdc++.h>

using namespace std;
/*01背包问题
01背包问题的特点是，">每种物品仅有一件，可以选择放或不放。
01背包问题描述：
有N件物品和一个容量为V的背包。第i件物品的重量是c[i]，价值是w[i]。
求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
*/
#define N 100

char s[100];
int wei[N], val[N], f[N];

void split(char *str, int *num) {
    const char *sep = ","; //可按多个字符来分割
    char *p;
    int i = 0;
    p = strtok(str, sep);
    while (p) {
        num[i++] = atoi(p);
//        printf("%s ", p);
        p = strtok(NULL, sep);
    }
//    printf("\n");
}

int main() {
//    freopen("../in.txt", "r", stdin);
    int i, j, m, n = 5;
    cin >> s;
    split(s, val);
    cin >> s;
    split(s, wei);
    scanf("%d", &m);
    for(i=0; i<n; i++)
    {
        for(j=m; j>=wei[i]; j--)
            f[j] = max(f[j], f[j-wei[i]]+val[i]);
    }
    printf("%d\n",f[m]);
}

华为8.8 获取typedef的最终类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
题目描述
C++中的typedef好处很多，可以让标准化自己DIY的类型，为便于理解typedef能干啥，本题考察各种typedef后，某个自定义类型的最终形态是啥。
输入为两部分，共两行：
第一行是一堆typedef定义，标准C++语句，以分号结束，这里不用考虑struct/union这类，只需要考虑基本类型和指针。
第二行是制定某个自定义type
输出为该自定义type的最终形态
如输入：
typedef int INT; typedef INT** INTP;
INTP
则输出：int * *
注意，如果有指针类型，则指针表达的*和前面的类型中间间隔一个空格，和编译器的输出保持一致；另外，如果第一行输入的语句是编译不过的，或者第二行选择的type在第一行中没有定义，则输出none
输入描述:
typedef的一堆自定义类型，并制定最终需要看的类型名
输出描述:
该类型名的完整名字，和编译器输出保持一致
示例1
输入
typedef int INT; typedef INT** INTP;
INTP
输出
int * *
备注:
如果有指针类型，则指针表达的*和前面的类型中间间隔一个空格

这题过了40%。不知道还有什么情况了。用java写的，华为这几题的IO都出的挺蛋疼的。我的思路就是搞个map，然后递归搜索替换一下。

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
import java.util.HashMap;
import java.util.Iterator;
import java.util.Scanner;

//这个代码只过了40%
public class Main {
    public static void bianli(HashMap<String, String> map) {
//        Map<String, String> map = new HashMap<String, String>();
        for (String key : map.keySet()) {
            map.get(key);
            System.out.println(key);
        }
    }

    public static String getAns(HashMap<String, String> map, String p) {
        if (p.contains("*")) {
            String[] tmp = p.split("\\*");
            p=p.replace("*", " *");
            for (int i = 0; i < tmp.length; i++) {
                p=p.replace(tmp[i], getAns(map, tmp[i]));
            }
            return p;
        } else {
            if (map.containsKey(p)) {
                return getAns(map, map.get(p));
            } else
                return p;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str;
        while (in.hasNextLine()) {//注意while处理多个case
            str = in.nextLine();
            String[] tmp1 = str.split(";");
            HashMap<String, String> map = new HashMap<String, String>();
            for (int i = 0; i < tmp1.length; i++) {
                //将字符串前面的空格去掉
                char check = tmp1[i].charAt(0);
                if (check == ' ') {
                    tmp1[i] = tmp1[i].substring(1, tmp1[i].length());
//                    System.out.println(tmp1[i]);
                }
                //将字符串分隔成key和value
                String oper = tmp1[i];
                String[] tmp2 = oper.split(" ");
                map.put(tmp2[2], tmp2[1]);
            }
//            bianli(map);
            //然后通过map转化出来结果
            String need = in.nextLine();
//            String ans = map.get(need);
            if (map.containsKey(need)) {
                System.out.println(getAns(map, need));
            } else {
                System.out.println("none");
            }
        }
    }
}

网易 笔试 8.11

网易2019校招笔试编程题参考代码
还是自己太菜了，感觉他们瞌睡丰收加字典的都做的还行。我这几题一直卡着。有需要的去看上面这个链接的代码。

网易8.11 丰收

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
题目描述
又到了丰收的季节,恰逢小易去牛牛的果园里游玩
牛牛常说他对整个果园的每个地方都了如指掌,小易不太相信,所以他想考考牛牛
在果园里有N堆苹果,每堆苹果的数量为ai,小易希望知道从左往右数第x个苹果是属于哪一堆的。
牛牛觉得这个问题太简单,所以希望你来替他回答。
输出描述:
第一行一个数n(1<=n<=10^5)。
第二行n个数ai(1<=ai<=1000),表示从左往右数第i堆有多少苹果
第三行一个数m(1<=m<=10^5),表示有m次询问
第四行m个数qi,表示小易希望知道第qi个苹果属于哪一堆
输入描述:
m行,第i行输出第qi个苹果属于哪一堆
示例1
输入
5
2 7 3 4 9
3
1 25 11
输出
1
5
3
备注:
如果有指针类型，则指针表达的*和前面的类型中间间隔一个空格

**这个只过了90%(就是下面这个，要标答的上面去看链接)**，题目里面没有说边界情况如何处理。还是有点迷。思路没错，就是把搞一个数组存放边界然后二分、

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
#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int maxn = 1e5 + 10;

int main() {
    //freopen("../in.txt", "r", stdin);
    ll n, a[maxn], i;
    cin >> n;
    for (i = 0; i < n; i++)
        cin >> a[i];
    ll m, q[maxn];
    cin >> m;
    for (i = 0; i < n; i++)
        cin >> q[i];

    vector<ll> pos;
    pos.push_back(a[0]);
    for (i = 1; i < n; i++) {
        pos.push_back(pos.back() + a[i]);
    }
    vector<ll>::iterator iter;
    for (i = 0; i < m; i++) {
        iter = lower_bound(pos.begin(), pos.end(), q[i]);
        cout << iter - pos.begin() + 1 << endl;
    }
}

网易8.11 塔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
■题目描述
小易有一些立方体,每个立方体的边长为1,他用这些立方体搭了一些塔。
现在小易定义:这些塔的不稳定值为它们之中最高的塔与最低的塔的高度差
小易想让这些塔尽量稳定,所以他进行了如下操作:每次从某座塔上取下一块立方体,并把它放到另一座塔上。
注意,小易不会把立方体放到它原本的那座塔上,因为他认为这样毫无意义
现在小易想要知道,他进行了不超过k次操作之后,不稳定值最小是多少。

输入描述:
第一行两个数n,k(1<=n<=100,1<=k<=1000)表示塔的数量以及最多操作的次数。
第二行n个数,ai(1<=ai<=10^4)表示第i座塔的初始高度。
输出描述:
第一行两个数s,m,表示最小的不稳定值和操作次数(m=k)
接下来m行,每行两个数x,y表示从第x座塔上取下一块立方体放到第y座塔上。
示例1
输入
3 2
5 8 5
输出
0 2
2 1
2 3

这题就坑了，自己思路也标答差不多，每次拿之后排一次序，但是自己写的只过了20%，自己写的时间复杂度比较大，挂了也挺正常,但是只有20%还是挺不对的。
思路:贪心。每次从最高的塔拿一块放到最低的塔上。讲道理的话应该spj吧。。。

网易8.11 整理房间

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
■题目描述
又到了周末,小易的房间乱得一团糟。
他希望将地上的杂物稍微整理下,使每团杂物看起来都紧凑
些,没有那么乱。
地上一共有n团杂物,每团杂物都包含4个物品。第i物品的坐
标用(ai,bi)表示,小易每次都可以将它绕着(xi,yi)逆时针旋转
90°,这将消耗他的一次移动次数。如果一团杂物的4个点构
成了一个面积不为0的正方形,我们说它是紧凑的。
因为小易很懒,所以他希望你帮助他计算一下每团杂物最少
需要多少步移动能使它变得紧凑。
输入描述:
第一行一个数n(1<=n<=100),表示杂物的团数。
接下来4n行,每4行表示一团杂物,每行4个数xi,yi,ai,bi(-10^4<=xi,Yi,ai,bi<=10^4)
表示第i个物品旋转的中心点坐标和它本身的坐标。
输出描述:
n行,每行1个数,表示最少移动次数。

输入
4
1 1 1 0
-1 1 0 0
-1 1 0 0
1 -1 0 0
1 1 0 0
-2 1 0 0
1 -1 0 0
1 1 0 0
-1 1 0 0
-1 1 0 0
-1 1 0 0
2 2 0 1
-1 0 0 -2
3 0 0 -2
-1 1 -2 0
输出
1
-1
3
3

头条 笔试 8.12

头条的IO今天也不是很友好，第一题简单的DFS不知道为啥有点不对。最后60%+100%+0%+0%+10%,这个没有拿到面试机会，第二次笔试之后约了视频面

头条笔试题解

头条8.12 世界杯开幕式

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
■题目描述
世界杯开幕式会在球场C举行,球场C的球迷看台可以容纳M*N个球迷。在球场售票完成后,现官方想统计此次开幕式一共有多少个球队球迷群体,最大的球队球迷群体有多少人。
经调研发现,球迷群体在选座时有以下特性
●  同球队的球迷群体会选择相邻座位,不同球队的球迷群体会选择不相邻的座位。(注解:相邻包括前后相邻、左右相邻、斜对角相邻。)
●  给定一个MN的二维球场,0代表该位置没有坐人,1代表该位置已有球迷,希望输出球队群体个数P,最大的球队群体人数Q。
输入描述:
第一行,2个数字,M及N,使用英文逗号分割;
接下来M行,每行N的数字,使用英文逗号分割;
输出描述:
一行,2个数字,P及Q,使用英文逗号分割;
其中,P表示球队群体个数,Q表示最大的球队群体人数

输入
10,10
0,0,0,0,0,0,0,0,0,0
0,0,0,1,1,0,1,0,0,0
0,1,0,0,0,0,0,1,0,1
1,0,0,0,0,0,0,0,1,1
0,0,0,1,1,1,0,0,0,1
0,0,0,0,0,0,1,0,1,1
0,1,1,0,0,0,0,0,0,0
0,0,0,1,0,1,0,0,0,0
0,0,1,0,0,1,0,0,0,0
0,1,0,0,0,0,0,0,0,0
输出
6,8

备注:
数据范围
0<M<1000
0<N<1000

这题只过了60%,这么简单的搜索告诉我爆了，求大佬帮忙看下哪儿有问题。

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
#include <bits/stdc++.h>
#define LL long long
using namespace std;
#define INF 0xffffff
const int maxn = 1005;

int Map[maxn][maxn];
int dir[8][2] = {0, 1, 1, 0, 1, 1, -1, -1, 0, -1, -1, 0, 1, -1, -1, 1};
char str[1005];
int m, n, ans, sum, cnt;

void dfs(int x, int y) {
    cnt++;
    if (cnt > sum) {
        sum = cnt;
    }
    Map[x][y] = 0;
    int i, j;
    for (int k = 0; k < 8; k++) {
        i = x + dir[k][0];
        j = y + dir[k][1];
        if (i >= 1 && i <= m && j >= 1 && j <= n && Map[i][j] == 1)
            dfs(i, j);
    }
}

void split(char *str, int *num) {
    const char *sep = ","; //可按多个字符来分割
    char *p;
    int i = 0;
    p = strtok(str, sep);
    while (p) {
        num[i++] = atoi(p);
        p = strtok(NULL, sep);
    }
}

int main() {
//    freopen("../in.txt", "r", stdin);
    cin >> str;
    int num[2];
    split(str, num);
    m = num[0], n = num[1];
    for (int i = 1; i <= m; i++) {
        cin >> str;
        for (int j = 1, k = 0; j <= n; j++) {
            Map[i][j] = str[k] - '0';
            k += 2;
        }
    }
    ans = 0;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            if (Map[i][j] == 1) {
                cnt = 0;
                dfs(i, j);
                ans++;
            }
        }
    cout << ans << "," << sum << endl;
}

头条8.12 文章病句标识

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
题目描述
为了提高文章质量,每一篇文章(假设全部都是英文)都会有m名编辑进行审核,每个编辑独立工作,会把觉得有问题的句子通过下标记录下来,比如[1,10],1表示病句的第一个字符,10表示病句的最后一个字符。也就是从1到10这10个字符组成的句子,是有问题的。
现在需要把多名编辑有问题的句子合并起来,送给总编辑进行最终的审核。比如编辑A指出的病句是[1,10],[32,45];B编辑指出的病句[5,16],[78,94],那么[1,10]和[5,16]是有交叉的,可以合并成[1,16],[32,45],[78,94]
输入描述
编辑数量m,之后每行是每个编辑的标记的下标集合,第一个和最后一个下标用英文逗号分隔,每组下标之间用分号分隔
输出描述
合并后的下标集合,第一个和最后一个下标用英文逗号分隔每组下标之间用分号分隔。返回结果是从小到大递增排列

输入
3
1,10;32,45
78,94;5,16
80,100;200,220;16,32
输出
1,45;78,100;200,220

备注
数据范围
m<2^16
下标数值<2^32
每个编辑记录的下标<2^16组

区间合并问题，具体可以参照:
https://leetcode-cn.com/problems/merge-intervals/description/

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
79
80
81
82
83
84
#include <bits/stdc++.h>
using namespace std;

typedef vector<pair<int, int> > RangeList;

RangeList cover(const RangeList &intervals) {
    int left = intervals[0].first, right = intervals[0].second;
    RangeList result;

    for (int i = 1; i < intervals.size(); ++i) {
        // 前面自成一个区间，那么就此分开
        if (intervals[i].first > right) {
            result.push_back(make_pair(left, right));
            left = intervals[i].first;
            right = intervals[i].second;
        } else if (intervals[i].second > right) {
            right = intervals[i].second;
        }
    }
    result.push_back(make_pair(left, right));

    return result;
}

RangeList intervals;

void display(const RangeList &intervals) {
    cout << intervals[0].first << ',' << intervals[0].second;
    for (int i = 1; i < intervals.size(); ++i)
        cout << ';' << intervals[i].first << ',' << intervals[i].second;
    cout << endl;
}

stack<char *> s;

void split1(char *str) {
    char tmp[10005];
    strcpy(tmp, str);
    const char *sep = ","; //可按多个字符来分割
    char *p;
    int a, b;
    p = strtok(tmp, sep);
    a = atoi(p);
    p = strtok(NULL, sep);
    b = atoi(p);
    intervals.push_back(make_pair(a, b));
}

void split(char *str) {
    const char *sep = ";"; //可按多个字符来分割
    char *p;
    int i = 0;
    p = strtok(str, sep);
    while (p) {
        //再split一次
        s.push(p);
        p = strtok(NULL, sep);
    }
    while (!s.empty()) {
        char *d = s.top();
        s.pop();
        split1(d);
    }
}

int main() {
//    freopen("../in.txt", "r", stdin);
    int n, start, end;
    cin >> n;
    string str;
    char tmp[10005];
    getline(cin, str);
    for (int i = 0; i < n; ++i) {
        getline(cin, str);
//        cout << str << endl;
        strcpy(tmp, str.c_str());
        split(tmp);
    }
    sort(intervals.begin(), intervals.end());

//    display(intervals);
    RangeList result = cover(intervals);
    display(result);
}

头条8.12 积分卡牌游戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
题目描述
小a和小b玩一个游戏,有n张卡牌,每张上面有两个正整数x,y.取一张牌时,个人积分增加,团队积分增加y
求小a,小b各取若干张牌,使得他们的个人积分相等,且团队(小a、小b属于同一团队)积分最大
输入描述
第一行
接下来n行,每行两个正整数x,y
输出描述:
行一个整数
表示小a的积分和小b的积分相等时,团队积分的最大值

说明
当a抽取(2,2),b抽取(1,4),(1,4)时,两人个人积分都是2,团队积分最大,为10分
备注
数据范围
0<n<100
0<x<1000
0<y<1e6

头条8.12 区间最大最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
题目描述
两个长度为n的序列ab
问有多少个区间门满足
max a[l, r)< min(b[l, r)
即a[l,r]的最大值小于b[l,r]的最小值
<1e5
ai, bi< le9
输入描述
第一行一个整数n
第二行n个数,第i个为ai
第三行n个数,第i个为bi
0<=l<=r<n
输出描述:
一行一个整数,表示答案

输入
3
3 2 1
3 3 3
输出
3

头条8.12 直播爱好者

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
题目描述
小明在抖音里关注了N个主播,每个主播每天的开播时间是固定
的,分别在s时刻开始开播,t时刻结束。小明无法同时观看两个
主播的直播。一天被分成了M个时间单位。请问小明每天最多能
完整观看多少场直播?
输入描述:
第一行一个整数,代表N
第二行一个整数,代表M
第三行空格分隔的N*2个整数,代表s,t
输出描述
行一个整数,表示答案
示例1
输入
3
10
0 3 3 7 7 0
输出
3
说明
033770表示3个主播开播的时间分别是(0,3)、
(3,7)、(7,0),则这3个直播小明都能完整观看

示例2
输入
3
10
0 5 2 7 6 9
输出
2
说明
0 5 2 7 6 9表示3个主播开播的时间分别是(0,5)、(2,7)、(6,9),
则小明能完整观看的直播为(0,5)、(6,9)2个
示例3
输入
3
10
2 3 4 6 8 1
输出
3
说明
2 3 4 6 8 1表示3个主播开播的时间分别是(2,3)、(4,6)、(8,1),
其中(8,1)表示这场直播会跨天,小明能完整观看的直播为(2,3)、(4,6)、(8,1)3个

链家 笔试 8.18

终于遇到简单一点的笔试了，前两题水题AC，第三题也是暴力，没时间写了只过了36%，还有一种情况没写完。

链家8.18 取消社团预约

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
题目描述：
在中国某大学内，教室资源十分紧张，有n个社团同时申请了在某一天使用同一间教室，假设第i个社团占用该教室的时间记为[li,  ri]。根据学校的规定，教务部门必须且最多取消一个社团的预约，来满足另外n-1个社团的需求，问学校有多少种取消的方案。(若两社团占用时间分别为[l1, r1]和[l2,  r2]，此时若r1=l2，视为时间没有冲突)
输入
第一行包含一个整数n，表示社团的数量。(1≤n≤5000)。
接下来有n行，每行包含两个整数，表示第i个社团占用该教室的时间为[li, ri](1≤li, ri≤106)
输出
输出第一行包含一个整数m，表示可以删去的社团数量。
输出第二行包含m个整数，分别为可删除的社团编号(从小到大排序)。
（如不删除某个预约，则不能算作一种方案。）
样例输入
3
3 10
20 30
1 3
样例输出
3
1 2 3
Hint
输入样例2
4
3 10
20 30
1 3
1 39
输出样例2
1
4
输入样例3
3
1 5
2 6
3 7
输出样例3
0
样例解释
样例1中删除 1，2 ，3社团中的任何一个都可以使得另外两个社团无冲突的使用教室
样例2中删除4以后【1，3】【3，10】【20，30】无冲突，若删除1，2，3中任何一个都会与4冲突。
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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5005;
struct node {
    int l, r;
    int p;
};

bool cmp(node a, node b) {
    if (a.l == b.l)
        return a.r < b.r;
    return a.l < b.l;
}


int n, i;
node a[maxn];
vector<int> ans;

void check(int pos) {
    int begin = 0;
    if (pos == 0) {
        begin = 1;
    }
    int l = a[begin].l, r = a[begin].r, j;
    //pos位置的不要
    for (j = begin + 1; j < n; j++) {
        if (j == pos) {
            continue;
        }
        if (r > a[j].l) {
            break;
        } else {
            l = a[j].l, r = a[j].r;
        }
    }
    if (j == n) {
        ans.push_back(a[pos].p);
    }
}

int main() {
//    freopen("../in.txt", "r", stdin);
    cin >> n;
    for (i = 0; i < n; i++) {
        cin >> a[i].l >> a[i].r;
        a[i].p=i+1;
    }
    sort(a, a + n, cmp);

    //双层循环
    for (i = 0; i < n; i++) {
        check(i);
    }
    if (ans.size() == 0)
        cout << 0 << endl;
    else {
        sort(ans.begin(),ans.end());
        cout << ans.size() << endl << ans[0];
        for (i = 1; i < ans.size(); i++)
            cout << " " << ans[i];
        cout << endl;
    }
}

链家8.18 道路修建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 10;

int main() {
//    freopen("../in.txt", "r", stdin);
    int i,n,tmp,mi=1e5,sum=0;
    cin>>n;
    for(i=0;i<n;i++){
        cin>>tmp;
        if(tmp<mi){
            mi=tmp;
        }
        sum+=tmp;
    }
    cout<<sum-mi<<endl;
}

链家8.18 扑克牌

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
题目描述：
众所周知，一副扑克牌按大小分为13种牌，每种牌各4个花色，总共52张牌。规定13种牌按从小到大的顺序分别为A23456789TJQK，现在从一副牌中抽取20张，每轮选择下列规则中的一项出牌：
①单牌：任意一张牌，如Q；
②对子：两张大小相同的牌，如77；
③三带：三张大小相同的牌，附带至多一张任意牌，如333A；
④四带：四张大小相同的牌，附带至多两张任意牌，如KKKK58；
⑤顺子：至少五张大小连续的牌，如789TJQ。
那么，至少需要多少轮才能将20张牌出完？
输入
输入长度为20的字符串，表示所抽取的20张牌。
输出
输出将20张牌出完所需的最少轮数。
样例输入
8K67A65K27T59K346AK2
样例输出
4
Hint
样例解释
4轮出牌顺序为：
A234567
56789T
KKKKA2
6

好未来 笔试 8.28

6个编程题，有个概率推公式感觉比较简单，最后20分钟还是没搞出来，过了5题

好未来8.28 拆数字串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
题目描述
一个数字串可以被拆开成多个数字串,例如12345拆成12345或
者12345。给一个正整数类型的数字串n,求n拆开后的数能被3整
除的最大数量m是多少。(0也算3的倍数)
举例:n=12345,拆成
1):12,3,45,m=3
2):123,45,m=2
输入描述:
输入一个正整数类型的数字串n(字符串长度<100)
输出描述:
输出一个数字表示n拆开后能被3整除最多的数量
示例1
输入
321
输出
2

这题需要注意一下类似112的情况，我的思路是遇到一个1和一个2，必定能组成一个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
#include <bits/stdc++.h>
using namespace std;

int main() {
    //freopen("../in.txt", "r", stdin);
    string str;
    cin >> str;
    int i, len = str.length(), m, number, ans = 0, c1, c2;
    for (i = 0, m = 0, c1 = 0, c2 = 0; i < len; i++) {
        number = str[i] - '0';
        //遇到3的情况直接加1
        if (number % 3 == 0) {
            ans++;
            m = 0, c1 = 0, c2 = 0;
            continue;
        }
        m += number;
        if (number % 3 == 1)
            c1++;
        else
            c2++;
        //判断能不能有一个组合
        if ((m > 0 && m % 3 == 0) || (c1 > 0 && c2 > 0)) {
            ans++;
            m = 0, c1 = 0, c2 = 0;
        }

    }
    cout << ans << endl;
}

好未来8.28 加与或的关系

1
2
3
4
5
6
7
8
9
10
11
12
13
题目描述
一个等式x+y=x|y("|"表示或运算)。给出一个正整数x,满足等式的正整数y有很多个,从第一个开始由小到大数y,给定一个正整数k,求第k个y
输入描述
输入t表示有t组数据(t<100)
每组数据输入x和k(0<x<10^18,0<k<10^18)
输出描述
输出y
示例1
输入
1
4 2
输出
2

这个就是位运算，找出数字X转化成二进制的0的位置，把K也转成二进制然后填进去
但是按照题目的描述，这个最后得到的结果是可能会超过long long，但是这么交还是通过了，感觉可能是数据比较弱

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
#include <bits/stdc++.h>

using namespace std;
#define ll long long

int main() {
    //freopen("../in.txt", "r", stdin);
    ll t,x,k,ans,i,j,a,lenX,lenK,lenA;
    int posX[160],posK[160],posA[160];
    cin>>t;
    while (t--){
        memset(posX,0, sizeof(posX));
        cin>>x>>k;
        i=0,ans=0;
        while (x>0){
            posX[i++]=x&1;
            x=x>>1;
        }
        lenX=i;

        i=0;
        while (k>0){
            posK[i++]=k&1;
            k=k>>1;
        }
        lenK=i;

        for(i=0,j=0,a=0;j<lenK;i++){
            if(posX[i]==0)
                posA[a++]=posK[j++];
            else
                posA[a++]=0;
        }
        lenA=a;
        for(i=lenA-1;i>=0;i--){
            ans=ans<<1;
            ans=ans|posA[i];
        }
        cout<<ans<<endl;
    }
}

好未来8.28 求给定位置下的数组的排列组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
题目描述
举例:
对于固定数组:{0,1,2,3,4,5,6,7,8,9}
输入布尔数组:(0,1,1,1,1,1,1,1,1,0},其中0表示对应下标数组元素可出现也可以不出现,1表示必须出现
输出所有可能性组合,转化成字符串,并按照字符串升序排序
012345678
0123456789
12345678
123456789
输入描述
位置出现的布尔值
输出描述
打印所有组合

示例1
输入
0 1 1 1 1 1 1 1 1 0
输出
012345678
0123456789
12345678
123456789

这题直接按照位进行遍历就好了，不过需要存一份原有和变更的进行记录

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
#include <bits/stdc++.h>

using namespace std;
#define ll long long

int a[10]={0,1,2,3,4,5,6,7,8,9};
int pos[10],i,p[10];
set<string> v;

void Print(){
    string s="";
    for(i=0;i<10;i++){
        if(p[i]==1)
            s+=a[i]+'0';
//            cout<<a[i];
    }
    v.insert(s);
    //    cout<<s<<endl;
}

int main() {
//    freopen("../in.txt", "r", stdin);
    for(i=0;i<10;i++)
        cin>>pos[i];

    int add = 0,tmp;
    while (1){
        int flag=0;
        for(i=9;i>=0;i--){
            if(p[i]==0){
                flag=1;
            }
        }
        if(flag==0){
            break;
        }
        //打印
        tmp=add++;
        for(i=9;i>=0;i--){
            p[i]=pos[i];
            if(pos[i]==0){
                p[i]=tmp&1;
                tmp=tmp/2;
            }
        }
        Print();
    }
    set<string>::iterator it;
    for(it=v.begin();it!=v.end();it++){
        cout<<*it<<endl;
    }
}

好未来8.28 掷骰子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
题目描述
有一个n面的骰子,掷每一面都是等概率的。其中有m个奖励面,如果掷到奖励面则可以再掷一次骰子。玩家每掷一次都能获得掷到那一面的分数。求玩家可获得分数的期望
输入描述:
第一行输入两个数n m分别表示骰子有n面,有m个面有奖励(0<=m<n<=10^9)
第二行输入n个数字用空格隔开,表示n个面的分数
输出描述
输出期望,保留小数点后两位。

示例1
输入
6 1
1 1 1 1 1 1
输出
1.20

按照大佬给的思路重新写的，没有提交验证，本来自己确实是这个思路，但是之前是直接cout输出，然后通过0%，有点醉、此代码未经验证
https://www.nowcoder.com/discuss/100048

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>

using namespace std;
#define ll long long

int main() {
//    freopen("../in.txt", "r", stdin);
    int n, m, i, sum, tmp;
    float ans = 0;
    cin >> n >> m;
    for (i = 0; i < n; i++) {
        cin >> tmp;
        ans += tmp;
    }
    float out = ans/(float)(n-m);
    printf("%.2f\n",out);
}

好未来8.28 求正整数数组的最大升序和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
题目描述
对于正整数数组,求最大元素和,要求元素大小必须是升序的。
int[] data = {5,1,3,4,9,7,6,8}
最大升序序列是:1,3,4,7,8
int Sum (unsigned int[] data, int n);
int main()
{
	unsigned int data[8];
	for(int i=0; i<8; i++) scanf("%d", &data[i]);
	int ret=Sum (data, 8);
	printf("max sum: %d\n",ret);
	return 0;
}

输入描述:
正整数数组,假定数组长度<100,元素最大值<10000
输出描述:
最大升序和
示例1
输入
5 1 3 4 9 7 6 8
输出
23

DP题

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
#include <bits/stdc++.h>

using namespace std;
#define ll long long

int n, a[1005], Max;
int dp[1005];//dp[i]为前i个数的最大升序子段和
const int inf = 99999;

int main() {
    //freopen("../in.txt", "r", stdin);
    int i = 1, j, temp;
    while (cin >> a[i++]);
    n = i;
    memset(dp, 0, sizeof(dp));
    for (i = 1; i <= n; i++) {
        temp = -inf;
        for (j = 0; j < i; j++) {
            if (a[j] < a[i])
                temp = max(temp, dp[j]);//如果i前没有小于它的，temp就为0
        }                           //且dp[i]也为它本身
        dp[i] = temp + a[i];
    }
    temp = -inf;
    for (i = 1; i <= n; i++)
        if (dp[i] > temp)
            temp = dp[i];
    cout << temp << endl;
}

好未来8.28 字符串字串替换

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
题目描述
使用C语言,实现字符串子串替换接口,可以假设替换前和替换后
的字符串都有最大长度限制,例如
char* ReplaceSubStr(const char* str, const char* srcSubStr,
const char* dstSubStr, char* out)
int main
{
	char str[1024];
	char srcSubStr[1024];
	char dstSubStr[1024];
	char out[1024];
	gets(str);
	gets(src SubStr);
	gets(dstSubStr);
	ReplaceSubStr(str, srcSubStr, dstSubStr, out);
	printf("%s\n",out);
	return 0;
}
输入描述
字符串源串,被替换的子串,目标子串。
输出描述
替换后的新字符串。
示例1
输入
this is a chick
is
are
输出
thare are a chick

这个就不多说了。替换就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>

using namespace std;
#define ll long long

void string_replace(string &strBig, const string &strsrc, const string &strdst) {
    int pos = 0;
    int srclen = strsrc.size();
    int dstlen = strdst.size();

    while ((pos = strBig.find(strsrc, pos)) != -1) {
        strBig.replace(pos, srclen, strdst);
        pos += dstlen;
    }
}

int main() {
//    freopen("../in.txt", "r", stdin);
    string str,s,p;
    getline(cin,str);
    cin>>s>>p;
    string_replace(str, s, p);
    cout << str << endl;
}

瓜子 笔试 9.4

有点赶，100+80
https://www.nowcoder.com/discuss/103418

携程 笔试 9.4

最后一个还是有点难的，100+100+87.5
https://www.nowcoder.com/discuss/103418

听说好看的人都关注了我的公众号《泫言》