字节跳动2020秋招笔试真题

1、模型文件去重

【题目描述】

抖音上不同的用户类型我们有不同的用户模型文件。
我们有一个模型配置文件，里面有很多的不同的用户类型和他们对应的模型文件。我们需要找出每个模型对应的是哪些用户类型。

给定一行输入，格式是a b
a表示这个用户的用户类型，b表示这个用户对应的模型文件。
请你输出每个模型文件对应的用户类型。
注意1：每个模型文件可能对应多个用户类型，用户类型之间用空格作为切分。
注意2: 如果有多个用户类型输出，用户类型之间的排序按照字母表排序。
注意3: 如果有多个模型输出，模型输出的顺序按照模型文件在输入数据中顺序，即从上到下。
输入描述
输入第1行: 用户类型 N（表示有多少个 用户类型）
接下来的N行：用户类型 模型文件

输出描述
模型文件用户类型1 用户类型2

1
abc 1.txt

输出

1.txt abc

【解题思路】

用一个map做hash，其中以string作为key，字符串去重集合set<string>作为value。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
 
vector<string> l;
map<string, set<string>> s;
 
int main() {
    int n;
    string a, b;
    cin >> n;
    for (; n--;) {
        cin >> a >> b;
        if (!s.count(b))
            l.push_back(b);
        s[b].insert(a);
    }
    for (auto b : l) {
        cout << b;
        for (auto a : s[b]) {
            cout << " " << a;
        }
        cout << endl;
    }
    return 0;
}

2、穿越沙漠的补给次数

【题目描述】旅行者穿越沙漠的过程中需要不断地消耗携带的饮用水，到达终点前会经过几个绿洲，每个绿洲均设有水分补给站可以为旅行者提供水分补给并收取一定的费用。

沿途共有n个补给站，每个补给站收取的费用都一样，但是提供的水量不尽相同。起点到终点的距离为D公里，postion[i]表示第i个补给站距离起点的距离，单位为公里，supply[i]表示第i 个补给站可以提供的水量，单位为升。

假设旅行者在起点时携带了W升的水，每行走1公里需要消耗1升的水量，身上可携带的水量没有上限，且携带的水量多少不会对体能消耗产生影响，鉴于每次进补给站花费的钱都是一样多，期望用最少的补给次数到达终点，请帮忙计算最少的补给次数。

输入描述

第一行输入整数D和W, D表示起点到终点的距离，W表示初始携带的水量

第二行输入数组postion，长度为N，分别表示N个补给站分别距离起点的距离

第三行输入数组supply，长度为N, 分别表示N个补给站分别可以供给的水量

数据范围：1 <= D, W<=10^8, 0<=N<=1000, 0<position[i],supply[i]<D

输出描述

输出一个整数表示最少的补给次数，若无法到达终点则返回-1

示例1

输入

10 4
1 4 7
6 3 5

输出

1

说明

每行输入用空格隔开。起点到终点共10公里，初始时携带4升水，途径3个补给站。共需补给一次：只需在第1个补给站补给一次获得6升水，即可走完全程

【解题思路】

贪心。假设你现在有携带的水量为W，当前位置为curPos，那么你携带的水能够支撑你走到curPos+W位置，走到该位置之后你再考虑去该位置（如果有）及之前的水站加水（可能在该位置之前有多个水站），此外，为了保证最少的加水次数，应该到能加到最多水的水站加水，而且加完水之后应该给这个水站加一个标记（used数组），以后不能再到该水站取水。

【参考代码】

public static int solve(int D, int W, int[] pos, int[] sup){
    int res = 0;
 
    // 用来指示在特定的水站有没有取过水，一个水站只能取一次水
    boolean[] used = new boolean[pos.length];
 
    // 旅行者现在所在的位置
    int curPos = 0;
 
    while (curPos<D){
        // 每次直接跳到能够着的最大位置，携带的水也会被喝光
        curPos+=W;
        W = 0;
        // 如果已经到达终点，则直接返回加了多少次水
        if(curPos>=D) return res;
 
        // 标记一下能获得最多水的水站在pos中的下标
        int maxIndex = -1;
 
        for(int i=0;i<pos.length;i++){
            // 当前还没到指定的水站，则不能从这些水站取水，直接break
            if(pos[i]>curPos) break;
            // 如果还没从该水站取水，则会看在这里取水能否得到最大的水量
            if(!used[i] && sup[i]>W) {
                W = sup[i]; maxIndex = i;
            }
        }
 
        // 没水了，而且也没有水站可以取水，可能在路途上被渴死
        if(maxIndex==-1) return -1;
 
        used[maxIndex] = true;
        res++;
    }
    return res;
}

3、走迷宫

【题目描述】给定一个迷宫，找到最快从起点到达重点的路径所需要的步数。
假设迷宫如下，假定左上角坐标为(0,0)，右下角坐标为 (3,2)
1 0 -1 1
-2 0 -1 -3
2 2 0 0
-2是迷宫的起点，坐标为(0,1)
-3是迷宫的终点，坐标为(3,1)
-1代表障碍物，不能行走
1和2代表传送门，传送门由正整数标示，只会成对出现。站在传送门上，能仅用一步就传送到相同数字的另一个传送门的位置：1只能传送到1，2只能传送到2。站在传送门上也可以选择不传送。
从起点到终点有若干种走法，举例如下：
(0,1)->(1,1)->(1,2)->(2,2)->(3,2)->(3,1)，共花费5步
或者
(0,1)->(0,0)-传送>(3,0)->(3,1)，共花费3步
经检验3步是所需的最少步数，最后结果返回3

输入描述
每一行输入都是用空格隔开的整数
第一行给出迷宫地图的长和宽，均为正整数
之后每一行的每一个数字，都代表迷宫的一格
-2表示起点，-3表示终点，-1表示不可通过的障碍物，0表示可通过的道路，大于0的正整数代表传送门，并且保证成对出现，在传送门上，可以仅用一步传送到另一个相同数字的传送门的位置。

输出描述
输出最少要多少步能够从起点走到终点。
输出-1如果没有任何办法从起点走到终点。

备注
迷宫大小<=200*200

示例1
输入

4 3
1 0 -1 1
-2 0 -1 -3
2 2 0 0

3

说明
(0,1)->(0,0)-传送>(3,0)->(3,1) ，共花费3步

【解题思路】

BFS经典类型题目，注意边界细节处理。

【参考代码】

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println(new Solution().solve(in));
    }
    
    public static class Solution {
 
        public static class State {
            public final Square square;
            public int step;
 
            public State(Square square, int step) {
                this.square = square;
                this.step = step;
            }
 
            @Override
            public int hashCode() {
                return square.hashCode();
            }
 
            @Override
            public boolean equals(Object obj) {
                if (obj instanceof State) {
                    return this.square.equals(((State) obj).square);
                }
                return false;
            }
            
            public void nextUnvisitedStates(Square[][] map, Set<State> toVisit, Set<State> visited, Map<Integer, WarpGate> warpGate) {
                if (square.x > 0) {
                    Square left = map[square.x - 1][square.y];
                    addUnvisitedStateToList(left, toVisit, visited);
                }
 
                if (square.x < map.length - 1) {
                    Square right = map[square.x + 1][square.y];
                    addUnvisitedStateToList(right, toVisit, visited);
                }
 
                if (square.y > 0) {
                    Square up = map[square.x][square.y - 1];
                    addUnvisitedStateToList(up, toVisit, visited);