【高德地图笔试题汇总】2024-04-11-高德地图春招笔试题-三语言题解(CPP/Python/Java)

🍭 大家好这里是KK爱Coding ，一枚热爱算法的程序员

✨ 本系列打算持续跟新高德地图近期的春秋招笔试题汇总～

💻 ACM银牌🥈| 多次AK大厂笔试｜编程一对一辅导

👏 感谢大家的订阅➕ 和喜欢💗

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。

文章目录

- 🎧 01.K小姐的学习小组
- - 问题描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 数据范围
  - 题解
  - 参考代码
- 🎹 02.LYA 的跳跃游戏
- - 问题描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 数据范围
  - 题解
  - 参考代码
- 写在最后
- 📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。

🎧 01.K小姐的学习小组

问题描述

K小姐是学校一名新来的计算机老师,为了提高班级里同学们的编程能力,她想到了一个非常好的方法:先让所有的同学手拉手围成一个圈,然后每名同学从自己右手边找到离自己最近的、编程能力比自己弱的两名同学组成学习小组。如果没有比自己编程能力弱的同学,则在学习小组中对应位置输出 $- 1$ 。

现在给定 $n$ 名同学的编程能力值,请你帮助K小姐按以上方法划分学习小组。

输入格式

第一行包含一个正整数 $n$ ,表示班级中同学的总数。

第二行包含 $n$ 个整数,表示每个同学的编程能力值,第 $i$ 个整数表示第 $i$ 号同学的编程能力值。

输出格式

输出 $n$ 行,每行 $3$ 个整数,表示一个学习小组。其中第 $i$ 行表示第 $i$ 号同学的学习小组,第一个整数是第 $i$ 号同学的编号,后两个整数是小组中另外两名编程能力弱于第 $i$ 号同学的同学的编号。如果找不到符合条件的同学,则在对应位置输出 $- 1$ 。

样例输入

[7,3,10,20,16]

样例输出

[[0,1,-1],[1,-1,-1],[2,0,1],[3,4,0],[4,0,1]]

数据范围

$\leq n \leq 10^5$
编程能力值是 $0,10^9]$ 内的整数
对于 $30\%$ 的数据, $n < 1000$
对于 $70\%$ 的数据, $\leq n \leq 10^5$

题解

本题可以使用单调栈来解决。我们可以从右往左遍历同学,维护一个单调递减的栈,栈中存储同学的编号。对于当前遍历到的同学 $i$ ,可以从栈顶弹出编程能力大于等于当前同学的同学,直到栈为空或者栈顶同学的编程能力小于当前同学。此时栈中剩余的同学就是编程能力小于当前同学的同学,我们可以从栈顶取出最多两个同学作为当前同学的学习小组成员。

具体实现时,我们可以先从右往左遍历一次同学,初始化单调栈；然后再从右往左遍历一次同学,利用单调栈找到每个同学的学习小组成员。最后对于学习小组成员不足两个的同学,在对应位置补 $- 1$ 即可。

时间复杂度 $O (n)$ ,空间复杂度 $O (n)$ 。

参考代码

Python

def find_group(score):
    n = len(score)
    res = [[] for _ in range(n)]
    for i in range(n):
        res[i].append(i)
    st = []
    
    def cal(i):
        m = len(st)
        m -= 1
        while len(res[i]) < 3 and m >= 0:
            res[i].append(st[m])
            m -= 1

    for i in range(n - 1, -1, -1):
        while st and score[st[-1]] >= score[i]:
            st.pop()
        st.append(i)

    for i in range(n - 1, -1, -1):
        while st and score[st[-1]] >= score[i]:
            st.pop()
        cal(i)
        st.append(i)

    for i in range(n):
        while len(res[i]) < 3:
            res[i].append(-1)

    return res

Java

public static List<List<Long>> findGroup(List<Long> score) {
        int n = score.size();
        List<List<Long>> res = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            List<Long> temp = new ArrayList<>();
            temp.add((long) i);
            res.add(temp);
        }
        Stack<Integer> st = new Stack<>();
        for (int i = n - 1; i >= 0; i--) {
            while (!st.isEmpty() && score.get(st.peek()) >= score.get(i))
                st.pop();
            st.push(i);
        }
        for (int i = n - 1; i >= 0; i--) {
            while (!st.isEmpty() && score.get(st.peek()) >= score.get(i))
                st.pop();
            cal(res, i, st);
            st.push(i);
        }
        for (List<Long> list : res) {
            while (list.size() < 3)
                list.add(-1L);
        }
        return res;
    }

vector<vector<long>> findGroup(vector<long>& score){
    int n = score.size();
    vector<vector<long>> res(n);
    for(int i = 0; i < n; i++){
        res[i].push_back(i);
    }
    vector<int> st;
    auto cal = [&](int i){
        int m = st.size();
        m -- ;
        while(res[i].size() < 3 && m >= 0)
            res[i].push_back(st[m --]);
    };
    for(int i = n - 1; i >= 0; i --)
    {
        while(st.size() && score[st.back()] >= score[i])
            st.pop_back();
        st.push_back(i);
    }
    for(int i = n - 1; i >= 0; i --)
    {
        while(st.size() && score[st.back()] >= score[i])
            st.pop_back();
        cal(i);
        st.push_back(i);
    }
    for(int i = 0; i < n; i ++)
    	while(res[i].size() < 3)
            res[i].push_back(-1);
    return res;
}

🎹 02.LYA 的跳跃游戏

问题描述

LYA 在玩一个跳跃游戏。游戏地图可以看作一个非负整数数组 $a rr$ ,数组中的每个元素表示在该位置可以跳跃的最大长度。LYA 最开始位于下标 $s t a r t$ 处,每次可以向左或向右跳跃。当他位于下标 $i$ 处时,他可以跳到 $i + a rr [i]$ 或者 $i - a rr [i]$ 。

LYA 的目标是跳到下标 $e n d$ 处。请问他至少需要跳跃几次才能到达目的地?如果无法到达,则返回 $- 1$ 。

输入格式

第一行包含一个正整数 $n$ ,表示数组 $a rr$ 的长度。

第二行包含一个正整数 $s t a r t$ ,表示 LYA 的起始位置。

第三行包含一个正整数 $e n d$ ,表示 LYA 的目标位置。

第四行包含 $n$ 个非负整数,表示数组 $a rr$ ,相邻整数之间用一个空格分隔。

输出格式

输出一个整数,表示 LYA 跳到目标位置所需的最少跳跃次数。如果无法到达,则输出 $- 1$ 。

样例输入

7
5
3
4 2 3 0 3 1 2

样例输出

数据范围

$\leq n \leq 5 \times 10^4$
$\leq arr[i] < n$
$\leq start, end < n$

题解

本题可以使用 BFS 求解。从起点 $s t a r t$ 开始,每次可以向左或向右跳跃,直到到达终点 $e n d$ 。

具体做法如下:

使用队列 $q$ 存储当前可以跳到的位置,初始时将起点 $s t a r t$ 加入队列。
使用数组 $d$ 记录到达每个位置需要的最少跳跃次数,初始时 $d [s t a r t] = 0$ ,其余位置为 $- 1$ 。
当队列不为空时,取出队首位置 $u$ :
- 如果 $u$ 等于终点 $e n d$ ,则返回 $d [u]$ 。
- 如果 $u + a rr [u]$ 在数组范围内且未访问过,则将其加入队列,并更新 $d [u + a rr [u]] = d [u] + 1$ 。
- 如果 $u - a rr [u]$ 在数组范围内且未访问过,则将其加入队列,并更新 $d [u - a rr [u]] = d [u] + 1$ 。
如果队列为空时仍未到达终点,说明无法到达,返回 $- 1$ 。

时间复杂度 $O (n)$ ,空间复杂度 $O (n)$ 。其中 $n$ 为数组长度。

参考代码

Python

from collections import deque

n = int(input())
start = int(input())
end = int(input())
arr = list(map(int, input().split()))

def bfs():
    if start == end:
        return 0
    q = deque([start])
    d = [-1] * n
    d[start] = 0
    while q:
        u = q.popleft()
        if u == end:
            return d[u]
        if u + arr[u] < n and d[u + arr[u]] == -1:
            q.append(u + arr[u])
            d[u + arr[u]] = d[u] + 1
        if u - arr[u] >= 0 and d[u - arr[u]] == -1:
            q.append(u - arr[u])
            d[u - arr[u]] = d[u] + 1
    return -1

print(bfs())

Java

import java.util.*;

public class Main {
    static int n, start, end;
    static int[] arr, d;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        start = sc.nextInt();
        end = sc.nextInt();
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(bfs());
    }

    static int bfs() {
        if (start == end) {
            return 0;
        }
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        d = new int[n];
        Arrays.fill(d, -1);
        d[start] = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            if (u == end) {
                return d[u];
            }
            if (u + arr[u] < n && d[u + arr[u]] == -1) {
                q.offer(u + arr[u]);
                d[u + arr[u]] = d[u] + 1;
            }
            if (u - arr[u] >= 0 && d[u - arr[u]] == -1) {
                q.offer(u - arr[u]);
                d[u - arr[u]] = d[u] + 1;
            }
        }
        return -1;
    }
}

#include <bits/stdc++.h>
using namespace std;

const int N = 50010;
int n, start, ed;
int arr[N], d[N];

int bfs() {
    if (start == ed) return 0;
    queue<int> q;
    q.push(start);
    memset(d, -1, sizeof(d));
    d[start] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (u == ed) return d[u];
        if (u + arr[u] < n && d[u + arr[u]] == -1) {
            q.push(u + arr[u]);
            d[u + arr[u]] = d[u] + 1;
        }
        if (u - arr[u] >= 0 && d[u - arr[u]] == -1) {
            q.push(u - arr[u]);
            d[u - arr[u]] = d[u] + 1;
        }
    }
    return -1;
}

int main() {
    cin >> n >> start >> ed;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cout << bfs() << endl;
    return 0;
}